求解集送货可拆分车辆路径问题的两阶段启发式方法

Yong WANG; Xiao-lei MA; Yun-teng LAO; Hai-yan YU; Yong LIU

doi:10.1631/jzus.C1300177

Your Location：

Home >

Browse articles >

求解集送货可拆分车辆路径问题的两阶段启发式方法

计算机与自动化 | Updated：2022-05-19

- 求解集送货可拆分车辆路径问题的两阶段启发式方法
- A two-stage heuristic method for vehicle routing problem with split deliveries and pickups
- 信息与电子工程前沿（英文） 2014年15卷第3期页码：200-210
- Affiliations：
  
  1.School of Management, Chongqing Jiaotong University, Chongqing 400074, China
  2.School of Transportation Science and Engineering, Beihang University, Beijing 100191, China
  3.Department of Civil and Environmental Engineering, University of Washington, Seattle, WA 98195-2700, USA
- Author bio：
  
  [ "Yong WANG, E-mail: yongwx6@gmail.com" ]
  [ "Xiao-lei MA, E-mail: xiaolei@buaa.edu.cn" ]
- Funds：
  
  Project supported by the National Natural Science Foundation of China (No. 51138003) and the National Social Science Foundation of Chongqing of China (No. 2013YBJJ035)
- DOI：10.1631/jzus.C1300177
  中图分类号： TP3;TU121
- 收稿：2013-07-03，
  
  修回：2014-2-19，
  
  录用：2013-12-19，
  
  纸质出版：2014-03
- Accepted：
Scan QR Code
求解集送货可拆分车辆路径问题的两阶段启发式方法[J]. 信息与电子工程前沿（英文）, 2014,15(3):200-210.

Yong WANG, Xiao-lei MA, Yun-teng LAO, et al. A two-stage heuristic method for vehicle routing problem with split deliveries and pickups[J]. Frontiers of Information Technology & Electronic Engineering, 2014, 15(3): 200-210.
求解集送货可拆分车辆路径问题的两阶段启发式方法[J]. 信息与电子工程前沿（英文）, 2014,15(3):200-210. DOI： 10.1631/jzus.C1300177.

Yong WANG, Xiao-lei MA, Yun-teng LAO, et al. A two-stage heuristic method for vehicle routing problem with split deliveries and pickups[J]. Frontiers of Information Technology & Electronic Engineering, 2014, 15(3): 200-210. DOI： 10.1631/jzus.C1300177.

摘要

研究目的

集送货可拆分车辆路径问题具有配送和收集需求同时可拆分、客户点需求量可超过单车装载量、客户点被单车访问可超过一次等特点，针对测试该问题的公共数据集寻求有效求解方法，是一项富有挑战性的工作，目前缺乏有效、方便的求解算法。本文探讨求解集送货可拆分车辆路径问题的有效算法。

创新要点

提出两阶段启发式方法，即可行解获取的初始启发式算法和改进初始解的混合启发式算法，为研究车辆路径问题需求拆分和访问次数的松弛提供了有效的求解思路。引用描述该问题实质的逻辑关系模型，结合定义和化简的概念，本文算法为集送货可拆分车辆路径问题的研究，提供了分步计算的实用算法。

方法提亮

组成两阶段启发式方法的各种逻辑关系模型简洁、准确地描述了集送货可拆分车辆路径问题，同时具备可扩展性和可组合性。这些特性的灵活应用，形成本文提出的两阶段优化算法。

重要结论

利用Solomon数据集和可扩展的Solomon数据集进行实验计算，并与禁忌搜索算法（TSA），粒子群算法（PSO）以及并行启发式方法（PHA）比较，结果表明，对于不同规模数据集，本文算法有效节省了总配送成本、提升了平均装载率。

Abstract

The vehicle routing problem (VRP) is a well-known combinatorial optimization issue in transportation and logistics network systems. There exist several limitations associated with the traditional VRP. Releasing the restricted conditions of traditional VRP has become a research focus in the past few decades. The vehicle routing problem with split deliveries and pickups (VRPSPDP) is particularly proposed to release the constraints on the visiting times per customer and vehicle capacity

that is

to allow the deliveries and pickups for each customer to be simultaneously split more than once. Few studies have focused on the VRPSPDP problem. In this paper we propose a two-stage heuristic method integrating the initial heuristic algorithm and hybrid heuristic algorithm to study the VRPSPDP problem. To validate the proposed algorithm

Solomon benchmark datasets and extended Solomon benchmark datasets were modified to compare with three other popular algorithms. A total of 18 datasets were used to evaluate the effectiveness of the proposed method. The computational results indicated that the proposed algorithm is superior to these three algorithms for VRPSPDP in terms of total travel cost and average loading rate.

关键词

Keywords

references

T.J. Ai , V. Kachitvichyanukul . A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery . Comput. Oper. Res. , 2009 . 36 ( 5 ): 1693 - 1702 . DOI: 10.1016/j.cor.2008.04.003 http://doi.org/10.1016/j.cor.2008.04.003 .

C. Archetti , M.W.P. Savelsbergh , M.G. Speranza . To split or not to split: that is the question . Transp. Res. PT E-Logist. Transp. , 2008 . 44 ( 1 ): 114 - 123 . DOI: 10.1016/j.tre.2006.04.003 http://doi.org/10.1016/j.tre.2006.04.003 .

R. Baldacci , P. Toth , D. Vigo . Exact algorithms for routing problems under vehicle capacity constraints . Ann. Oper. Res. , 2010 . 175 ( 1 ): 213 - 245 . DOI: 10.1007/s10479-009-0650-0 http://doi.org/10.1007/s10479-009-0650-0 .

B. Çatay . A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery . Expert Syst. Appl. , 2010 . 37 ( 10 ): 6809 - 6817 . DOI: 10.1016/j.eswa.2010.03.045 http://doi.org/10.1016/j.eswa.2010.03.045 .

A.L. Chen , G.K. Yang , Z.M. Wu . Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem . J. Zhejiang Univ.-Sci.A , 2006 . 7 ( 4 ): 607 - 614 . DOI: 10.1631/jzus.2006.A0607 http://doi.org/10.1631/jzus.2006.A0607 .

J.F. Chen , T.H. Wu . Vehicle routing problem with simultaneous deliveries and pickups . J.Oper. Res. Soc. , 2006 . 57 ( 5 ): 579 - 587 . DOI: 10.1057/palgrave.jors.2602028 http://doi.org/10.1057/palgrave.jors.2602028 .

K. Chepuri , T. Homem-de-Mello . Solving the vehicle routing problem with stochastic demands using the cross- entropy method . Ann. Oper. Res. , 2005 . 134 ( 1 ): 153 - 181 . DOI: 10.1007/s10479-005-5729-7 http://doi.org/10.1007/s10479-005-5729-7 .

H.C.B. de Oliveira , G.C. Vasconcelos . A hybrid search method for the vehicle routing problem with time windows . Ann. Oper. Res. , 2010 . 180 ( 1 ): 125 - 144 . DOI: 10.1007/s10479-008-0487-y http://doi.org/10.1007/s10479-008-0487-y .

M. Dror , P. Trudeau . Savings by split delivery routing . Transp. Sci. , 1989 . 23 ( 2 ): 141 - 145 . .

Y. Gajpal , P. Abad . An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup . Comput. Oper. Res. , 2009 . 36 ( 12 ): 3215 - 3223 . DOI: 10.1016/j.cor.2009.02.017 http://doi.org/10.1016/j.cor.2009.02.017 .

D. Gulczynski , B. Golden , E. Wasil . The split delivery vehicle routing problem with minimum delivery amounts . Transp.Res. PT E-Logist. Transp. , 2010 . 46 ( 5 ): 612 - 626 . DOI: 10.1016/j.tre.2009.12.007 http://doi.org/10.1016/j.tre.2009.12.007 .

F. Hennig , B. Nygreen , M. Christiansen , 等 . Maritime crude oil transportation-a split pickup and split delivery problem . Eur. J.Oper. Res. , 2012 . 218 ( 3 ): 764 - 774 . DOI: 10.1016/j.ejor.2011.09.046 http://doi.org/10.1016/j.ejor.2011.09.046 .

S.C. Ho , D. Haugland . A tabu search heuristic for vehicle routing problem with time windows and split deliveries . Comput.Oper. Res. , 2004 . 31 ( 12 ): 1947 - 1964 . DOI: 10.1016/S0305-0548(03)00155-2 http://doi.org/10.1016/S0305-0548(03)00155-2 .

A. Hoff , I. Gribkovskaia , G. Laporte , 等 . Lasso solution strategies for the vehicle routing problem with pickups and deliveries . Eur. J. Oper.Res. , 2009 . 192 ( 3 ): 755 - 766 . DOI: 10.1016/j.ejor.2007.10.021 http://doi.org/10.1016/j.ejor.2007.10.021 .

M.Z. Jin , K. Liu , R.O. Bowden . A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem . Int. J. Prod. Econ. , 2007 . 105 ( 1 ): 228 - 242 . DOI: 10.1016/j.ijpe.2006.04.014 http://doi.org/10.1016/j.ijpe.2006.04.014 .

S. Lambert , D. Riopel , W. Abdul-Kader . A reverse logistics decisions conceptual framework . Comput.Ind. Eng. , 2011 . 61 ( 3 ): 561 - 581 . DOI: 10.1016/j.cie.2011.04.012 http://doi.org/10.1016/j.cie.2011.04.012 .

C.G. Lee , M.A. Epelman , C.C.Ⅲ White , 等 . A shortest path approach to the multiple-vehicle routing problem with pick-ups . Transp. Res. PTB-Method. , 2006 . 40 ( 4 ): 265 - 284 . DOI: 10.1016/j.trb.2004.11.004 http://doi.org/10.1016/j.trb.2004.11.004 .

J.X. Li , F. Chu , H.X. Chen . Coordination of split deliveries in one-warehouse multi-retailer distribution systems . Comput. Ind. Eng. , 2011 . 60 ( 2 ): 291 - 301 . DOI: 10.1016/j.cie.2010.11.012 http://doi.org/10.1016/j.cie.2010.11.012 .

R. Liu , X.L. Xie , V. Augusto , 等 . Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care . Eur. J. Oper. Res. , 2013 . 230 ( 3 ): 475 - 486 . DOI: 10.1016/j.ejor.2013.04.044 http://doi.org/10.1016/j.ejor.2013.04.044 .

S. Mitra . An algorithm for the generalized vehicle routing problem with backhauling . AsiaPac. J. Oper. Res. , 2005 . 22 ( 2 ): 153 - 169 . DOI: 10.1142/S0217595905000522 http://doi.org/10.1142/S0217595905000522 .

S. Mitra . A parallel clustering technique for the vehicle routing problem with split deliveries and pickups . J. Oper.Res. Soc. , 2008 . 59 ( 11 ): 1532 - 1546 . DOI: 10.1057/palgrave.jors.2602500 http://doi.org/10.1057/palgrave.jors.2602500 .

F.A.T. Montané , R.D. Galvão . A tabu search algorithm for the vehicle routing problem with simultaneous pick- up and delivery service . Comput. Oper. Res. , 2006 . 33 ( 3 ): 595 - 619 . DOI: 10.1016/j.cor.2004.07.009 http://doi.org/10.1016/j.cor.2004.07.009 .

L. Moreno , M.P. de Aragão , E. Uchoa . Improved lower bounds for the split delivery vehicle routing problem . Oper.Res. Lett. , 2010 . 38 ( 4 ): 302 - 306 . DOI: 10.1016/j.orl.2010.04.008 http://doi.org/10.1016/j.orl.2010.04.008 .

P.A. Mullaseril , M. Dror , J. Leung . Split-delivery routing heuristics in livestock feed distribution . J. Oper. Res.Soc. , 1997 . 48 ( 2 ): 107 - 116 . .

W.P. Nanry , J.W. Barnes . Solving the pickup and delivery problem with time windows using reactive tabu search . Transp. Res. PT B-Method. , 2000 . 34 ( 2 ): 107 - 121 . DOI: 10.1016/S0191-2615(99)00016-8 http://doi.org/10.1016/S0191-2615(99)00016-8 .

M. Nowak , O. Ergun , C.C.Ⅲ White . An empirical study on the benefit of split loads with the pickup and delivery problem . Eur. J. Oper. Res. , 2009 . 198 ( 3 ): 734 - 740 . DOI: 10.1016/j.ejor.2008.09.041 http://doi.org/10.1016/j.ejor.2008.09.041 .

L. Özdamar , O. Demir . A hierarchical clustering and routing procedure for large scale disaster relief logistics planning . Transp. Res. PT E-Logist.Transp. , 2012 . 48 ( 3 ): 591 - 602 . DOI: 10.1016/j.tre.2011.11.003 http://doi.org/10.1016/j.tre.2011.11.003 .

J. Rieck , J. Zimmermann . A new mixed integer linear model for a rich vehicle routing problem with docking constraints . Ann. Oper. Res. , 2010 . 181 ( 1 ): 337 - 358 . DOI: 10.1007/s10479-010-0748-4 http://doi.org/10.1007/s10479-010-0748-4 .

M. Saberi , İ.Ö. Verbas . Continuous approximation model for the vehicle routing problem for emissions minimization at the strategic level . J. Transp. Eng. , 2012 . 138 ( 11 ): 1368 - 1376 . DOI: 10.1061/(ASCE)TE.1943-5436.0000442 http://doi.org/10.1061/(ASCE)TE.1943-5436.0000442 .

J.B. Sheu . A novel dynamic resource allocation model for demand-responsive city logistics distribution operations . Transp. Res. PTE-Logist. Transp. , 2006 . 42 ( 6 ): 445 - 472 . DOI: 10.1016/j.tre.2005.05.004 http://doi.org/10.1016/j.tre.2005.05.004 .

J.B. Sheu . Green supply chain management, reverse logistics and nuclear power generation . Transp. Res. PTE-Logist. Transp. , 2008 . 44 ( 1 ): 19 - 46 . DOI: 10.1016/j.tre.2006.06.001 http://doi.org/10.1016/j.tre.2006.06.001 .

M.M. Solomon . Algorithms for the vehicle routing and scheduling problems with time window constraints . Oper. Res. , 1987 . 35 ( 2 ): 254 - 265 . .

A. Subramanian , L.M.A. Drummond , C. Bentes , 等 . A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery . Comput. Oper. Res. , 2010 . 37 ( 11 ): 1899 - 1911 . DOI: 10.1016/j.cor.2009.10.011 http://doi.org/10.1016/j.cor.2009.10.011 .

A. Subramanian , E. Uchoa , A.A. Pessoa , 等 . Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery . Oper. Res. Lett. , 2011 . 39 ( 5 ): 338 - 341 . DOI: 10.1016/j.orl.2011.06.012 http://doi.org/10.1016/j.orl.2011.06.012 .

H.F. Wang , Y.Y. Chen . A genetic algorithm for the simultaneous delivery and pickup problems with time window . Comput.Ind. Eng. , 2012 . 62 ( 1 ): 84 - 95 . DOI: 10.1016/j.cie.2011.08.018 http://doi.org/10.1016/j.cie.2011.08.018 .

Y. Wang , X.L. Ma , Y.H. Wang , 等 . Location optimization of multiple distribution centers under fuzzy environment . J.Zhejiang Univ.-Sci. A (Appl. Phys. & Eng.) , 2012 . 13 ( 10 ): 782 - 798 . DOI: 10.1631/jzus.A1200137 http://doi.org/10.1631/jzus.A1200137 .

Y. Wang , X.L. Ma , Y.T. Lao , 等 . Vehicle routing problem: simultaneous deliveries and pickups with split loads and time windows . J. Transp.Res. Board , 2013 . 2378 120 - 128 . DOI: 10.3141/2378-13 http://doi.org/10.3141/2378-13 .

Y. Wang , X.L. Ma , Y.T. Lao , 等 . A fuzzy-based customer clustering approach with hierarchical structure for logistics network optimization . Expert Syst.Appl. , 2014 . 41 ( 2 ): 521 - 534 . DOI: 10.1016/j.eswa.2013.07.078 http://doi.org/10.1016/j.eswa.2013.07.078 .

T. Zhang , W.A. Chaovalitwongse , Y.J. Zhang . Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries . Comput.Oper. Res. , 2012 . 39 ( 10 ): 2277 - 2290 . DOI: 10.1016/j.cor.2011.11.021 http://doi.org/10.1016/j.cor.2011.11.021 .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据