开放式两级车辆路径问题建模与多起始点变邻域下降法求解

doi:10.11896/j.issn.1002-137X.2014.10.049

Abstract

Abstract: In this paper,a Two-Echelon Open Vehicle Routing Problem (2E-OVRP) model was constructed according to the common open and two-echelon distribution of freight in city logistics．In 2E-OVRP,freight from a remote depot is compulsorily delivered through intermediate depots (called satellites)．The first echelon is from depot to satellites,while the second from satellites to customers．Vehicles of both echelons are not required to return to starting points after fi-nishing their respective distribution,or they are required to do so by making the same trips in the reverse order．We designed a multi-start variable neighborhood descent algorithm to solve this NP-hard problem effectively．Computational tests on several extended benchmark instances show that the designed algorithm pays attention on the balance between solution quality and efficiency and can solve the proposed 2E-OVRP effectively.

Key words: Open vehicle routing problem,Two-echelon vehicle routing problem,Multi-start methods,Variable neighborhood descent algorithm,Split algorithm

ZENG Zheng-yang,XU Wei-sheng and XU Zhi-yu. Modeling and Multi-start Variable Neighborhood Descent Solution of Two-echelon Open Vehicle Routing Problem[J].Computer Science, 2014, 41(10): 232-237.

0
/ / Recommend

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jsjkx.com/EN/10.11896/j.issn.1002-137X.2014.10.049

https://www.jsjkx.com/EN/Y2014/V41/I10/232

References

[1] Perboli G,Tadei R,Vigo D．The Two-Echelon Capacitated Vehicle Routing Problem:Models and Math-Based Heuristics[J]．Transportation Science,2011,45(3):364-380
[2] Jepsen M,Spoorendonk S,Ropke S．A Branch-and-Cut Algorithm for the Symmetric Two-Echelon Capacitated Vehicle Routing Problem[J]．Transportation Science,2013,47(1):23-37
[3] Baldacci R,Mingozzi A,Roberti R,et al．An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem[J]．Operations Research,2013,61(2):298-314
[4] Hemmelmayr V C,Cordeau J F,Crainic T G．An Adaptive LargeNeighborhood Search Heuristic for Two-Echelon Vehicle Routing Problem Arising In City Logistics[J]．Computers & Operations Research,2012,39(12):3215-3228
[5] Saeiklis D,Powell S．A Heuristic Method for the Open Vehicle Routing Problem[J]．Journal of the Operational Research Society,2000,51(5):564-573
[6] Brandao J．A Tabu Search Heuristic Algorithm for Open Vehicle Routing Problem[J]．European Journal of Operational Research,2004,157(3):552-564
[7] 符卓．带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究[J]．系统工程理论与实践,2004,24(3):123-128
[8] 钟石泉,杜纲．基于核心路径禁忌搜索算法的开放式车辆路径问题研究[J]．计算机集成制造系统,2007,13(4):827-832
[9] 李湘勇,田澎．开放式车辆路径问题的蚁群优化算法[J]．系统工程理论与实践,2008,28(6):81-93
[10] 李延晖,刘向．沿途补货的多车场开放式车辆路径问题及蚁群算法[J]．计算机集成制造系统,2008,14(3):557-562
[11] Hansen P,Mladenovic N,Brimaerg J,et al．Variable Neighborhood Search[M]∥Gendreau M,Potvin J．Handbook of Metaheuristics(Second Edition)．New York:Spring Science+ Business Media,LLC,2010:61-86
[12] Mladenovic N,Hansen P．Variable Neighborhood Search[J]．Computers & Operations Research,1997,24(11):1097-1100
[13] Marti R,Moreno-Vega J M,Duarte A．Advanced Multi-StartMethods[M]∥Gendreau M,Potvin J．Handbook of Metaheuristics(Second Edition)．New York:Spring Science+ Business Media,LLC,2010:265-281
[14] Marti R,Resende M G C,Ribeiro C C．Multi-Start Methods for Combinatorial Optimization[J]．European Journal of Operational Research,2013,226(1):1-8
[15] Salehipour A,Sorensen K,Goos P,et al．Efficient GRASP+VND and GRASP+VNS Metaheuristics for the Traveling Repairman Problem[J]．4OR,2011,9(2):189-209
[16] Villegas J G,Prins C,Prodhon C,et al．GRASP/VND andMulti-Start Evolutionary Local Search for the Single Truck and Trailer Routing Problem with Satellite Depots[J]．Engineering Applications of Artificial Intelligence,2010,23(5):780-794
[17] Schittekat P,Kinable J,Sorensen K,et al．A Metaheuristic forthe School Bus Routing Problem with Bus Stop Selection[J]．European Journal of Operational Research,2013,229(2):518-528
[18] Nguyen V P,Prins C,Prodhon C．Solving the Two-Echelon Location Routing Problem by a GRASP Reinforced by a Learning Process and Path Relinking[J]．European Journal of Operational Research,2012,216(1):113-126
[19] Beasley J E．Route First-Cluster Second Methods for VehicleRouting[J]．Omega,1983,11(4):403-408
[20] Prins C．A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem[J]．Computers & Operations Research,2004,31(12):1985-2002
[21] Archetti C,Speranza M G,Hertz A．A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem[J]．Transportation Science,2006,40(1):64-73

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Modeling and Multi-start Variable Neighborhood Descent Solution of Two-echelon Open Vehicle Routing Problem

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 0

Metrics

Comments

Recommended 0