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

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

计算机科学 ›› 2014, Vol. 41 ›› Issue (10): 232-237.doi: 10.11896/j.issn.1002-137X.2014.10.049

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

曾正洋,许维胜,徐志宇

同济大学电子与信息工程学院上海201804;同济大学电子与信息工程学院上海201804;同济大学电子与信息工程学院上海201804

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家自然科学基金重大项目(71090404,71090400),高等学校博士学科点专项科研基金(20130072110045)资助

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

ZENG Zheng-yang,XU Wei-sheng and XU Zhi-yu

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 针对城市物流中普遍存在的物资开放式两级配送情形,构建了开放式两级车辆路径问题的数学模型,它要求物资必须先由远程的中心仓库配送至转运中心(第一级),再由转运中心配送至客户点(第二级),两级车辆在完成各自的配送任务后,均不必返回出发点,若要返回,则必须按照原路返回。为有效求解该NP难问题,设计了一种多起始点变邻域下降算法。扩展算例的测试结果表明,所设计的算法注重求解质量与求解效率的平衡,可有效求解提出的开放式两级车辆路径问题。

关键词: 开放式车辆路径问题,两级车辆路径问题,多起始点方法,变邻域下降法,分割算法

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

曾正洋,许维胜,徐志宇. 开放式两级车辆路径问题建模与多起始点变邻域下降法求解[J]. 计算机科学, 2014, 41(10): 232-237. https://doi.org/10.11896/j.issn.1002-137X.2014.10.049

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. https://doi.org/10.11896/j.issn.1002-137X.2014.10.049

参考文献

[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

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

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0