کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
474737 | 699126 | 2011 | 17 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Efficient frameworks for greedy split and new depth first search split procedures for routing problems Efficient frameworks for greedy split and new depth first search split procedures for routing problems](/preview/png/474737.png)
Split procedures have proven their efficiency within global optimization frameworks for routing problems by splitting giant tours into trips. This is done by generating an optimal shortest path within an auxiliary graph constructed from the giant tour. This article provides a state of the art of split practice in routing problems and gives its key features. The efficiency of the method critically depends on the node-splitting procedure and on the upper and lower bound approximations. Suitable complexity can be obtained using a new depth first search procedure which is introduced here and provides a new algorithm that is specially designed for large scale problems with resource constraints. Experiments show that the depth first search split procedure introduced in this article, used as an evaluation function in a global framework, can improve the results obtained by the use of the “classical” split procedure on the Location-Routing Problem and the Heterogeneous Vehicle Routing Problem. The Location-Routing Problem is also used to provide further analysis and a fair comparative study between the two split versions.
Journal: Computers & Operations Research - Volume 38, Issue 4, April 2011, Pages 723–739