需求可拆分的节点具有双重需求的车辆路径问题研究进展
|
摘要
针对目前大部分有关节点具有双重需求的车辆路径问题(VRPNDD)均假设需求只能由一辆车服务,即需求不可拆分的问题类型,而在实际运营中经常会允许对客户需求拆分,并由多辆车共同运输或由一辆车多次运输,以便充分利用车辆装载能力和降低车辆行驶成本的情况,将这类问题统称为节点具有双重需求的车辆路径问题(SVRPNDD),该问题的研究主要关注于需求可拆分的同时取送货车辆路径问题(VRPSPDP)及取送货可分割的车辆路径问题(VRPDDP)。本文中提出了适用于各种SVRPNDD的数学模型,分析比较各种问题的特性,并归纳总结各种问题算法的研究进展。
For the present situation that majority of vehicle routing problem with nodes of double demands( VRPNDD)were assumed that each customer must be visited only once,but in practice,it was usually allowed that loads of each customer could be split up in order to be picked up or delivered by more than one vehicle or one vehicle many times,contributing to take full advantage of vehicle loading capacity and reduce the total traveling cost,this kind of VRPNDD was defined as a split vehicle routing problem with nodes of double demands( SVRPNDD),which consisted most of vehicle routing problem( VRP) with split pickups and deliveries( VRPSPDP) and VRP with divisible delivery and pickup( VRPDDP). The mathematical model suitable for various SVRPNDD problems was presented,the properties of different problems were analyzed and compared,and a brief summary of research progress on this field was given.
For the present situation that majority of vehicle routing problem with nodes of double demands( VRPNDD)were assumed that each customer must be visited only once,but in practice,it was usually allowed that loads of each customer could be split up in order to be picked up or delivered by more than one vehicle or one vehicle many times,contributing to take full advantage of vehicle loading capacity and reduce the total traveling cost,this kind of VRPNDD was defined as a split vehicle routing problem with nodes of double demands( SVRPNDD),which consisted most of vehicle routing problem( VRP) with split pickups and deliveries( VRPSPDP) and VRP with divisible delivery and pickup( VRPDDP). The mathematical model suitable for various SVRPNDD problems was presented,the properties of different problems were analyzed and compared,and a brief summary of research progress on this field was given.
引文
[1]DROR M,TRUDEAU P.Savings by split delivery routing[J].Transportation Science,1989,23(2):141-145.
[2]DROR M,TRUDEAU P.Split delivery routing[J].Naval Research Logistics,1990,37(3):383-402.
[3]DROR M,LAPORTE G,TRUDEAU P.Vehicle routing with split deliveries[J].Discrete Applied Mathematics,1994,50(3),239-254.
[4]MITRA S.An algorithm for the generalized vehicle routing problem with backhauling[J].Asia-Pacific Journal of Operational Research,2005,22(2):153-169.
[5]NOWAK M.The pickup and delivery problem with split loads[D].Atlanta:Georgia Institute of Technology,2005.
[6]PARRAGH S N,DOERNER K F,HARTL R F.A survey on pickup and delivery problems:Part I:transportation between customers and depot[J].Journal für Betriebswirtschaft,2008,58(1):21-51.
[7]PARRAGH S N,DOERNER K F,HARTL R F.A survey on pickup and delivery problems:Part II:transportation between pickup and delivery locations[J].Journal für Betriebswirtschaft,2007,57:81-117.
[8]王科峰,叶春明,唐国春.节点具有双重需求的车辆路径问题及其性质[J].系统科学与数学,2011,31(10):1185-1196.
[9]王科峰.节点具有双重需求的车辆路径问题研究[D].上海:上海理工大学,2012.
[10]王科峰,叶春明.节点具有双重需求车辆路径问题及其解的性质分析[J].上海理工大学学报,2013,35(4):329-335.
[11]MOSHEIOV G.Vehicle routing with pick-up and delivery:tourpartitioning heuristics[J].Computers and Industrial Engineering,1998,34(3):669-684.
[12]NAGY G,SALHI S.Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[J].European Journal of Operational Research,2005,162(1):126-141.
[13]MITRA S.A parallel clustering technique for the vehicle routing problem with split deliveries and pickups[J].Journal of the Operational Research Society,2008,59(11):1532-1546.
[14]LAI M,BATTARRA M,DI FRANCESCO M,et al.An adaptive guidance meta-heuristic for the vehicle routing problem with splits and clustered backhauls[J].Journal of the Operational Research Society,2015,66(7):1222-1235.
[15]NOWAK M,ERGUN O,WHITE C C.Pickup and delivery with split loads[J].Transportation Science,2008,42(1):32-43.
[16]NOWAK M,ERGUN O,WHITE C C.An empirical study on the benefit of split loads with pickup and delivery problem[J].European Journal of Operational Research.2009,198:734-740.
[17]NOWAK M,HEWITT M,WHITE C C.Precedence constrained pickup and delivery with split loads[J].International Journal of Logistics:Research and Applications.2012,15(1):1-14.
[18]TANG G C,NING A B,WANG K F,et al.A practical split vehicle routing problem with simultaneous pickup and delivery[C]//16th International Conference on Industrial Engineering and Engineering Management,IEEE,2009:26-30.
[19]唐国春.新的运输路径问题[C]//中国运筹学会第九届学术交流会论文集.北京:中国运筹学会.2008:269-277.
[20]YIN C Z,BU L,GONG H T.Mathematical model and algorithm of split load vehicle routing problem with simultaneous delivery and pickup[J].International Journal of Innovative Computing,Information and Control,2013,9(11):4497-4508.
[21]WASSAN N A,NAGY G.A reactive tabu search meta-heuristic for the vehicle routing problem with divisible deliveries and pickups[R/OL](2017-01-18)[2018-03-05]https://kar.kent.ac.uk/51852/.
[22]NAGY G,WASSAN N A,SPERANZA M G,et al.The vehicle routing problem with divisible deliveries and pickups[J].Transportation Science,2015,49(2):271-294.
[23]AI T J,KACHIVICHYANUKUL V.A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery[J].Computers and Operations Research,2009,36(5):1693-1702.
[24]ARCHETTI C,MANSINI R,SPERANZA M G.Complexity and reducibility of the skip delivery problem[J].Transportation Science,2005,39(2):182-187.
[25]ARCHETTI C,SPERANZA M G.Vehicle routing problems with split deliveries[J].International Transactions in Operational Research,2012,19:3-22.
[26]ARCHETTI C,SAVELSBERGH M W P,SPERANZA M G.To split or not to split:that is the question[J].Transportation Research:Part E,2008,44:114-123.
[27]WANG Y,MA X,LAO Y,et al.Vehicle routing problem:simultaneous deliveries and pickups with split loads and time windows[J].Transportation Research Record:Journal of the Transportation Research Board,2013(2378):120-128.
[28]ARCHETTI C,SAVELSBERGH M W P,SPERANZA M G.Worst-case analysis for split delivery vehicle routing problems[J].Transportation Science,2006,40(2),226-234.
[29]杨亚璪,靳文舟,郝小妮,等.求解集送货可拆分车辆路径问题的启发式算法[J].华南理工大学学报(自然科学版),2010,38(3):58-63.
[30]WANG K F,YE C M,NING A B.Competitive decision algorithm for the split vehicle routing problem with simultaneous pickup and delivery and time windows[C]//International Conference on Future Information Technology and Management Engineering(FITME),IEEE,2010,2:371-375.
[31]AVCI M,TOPALOGLU S.A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery[J].Expert Systems with Applications,2016,53:160-171.
[32]杨鹏,邹浩,徐贤浩.带时间窗集送货需求可分车辆路径问题的改进蚁群算法[J].系统工程,2015,33(9):58-62.
[33]YI W,KUMAR A.Ant colony optimization for disaster relief operations[J].Transportation Research:Part E,2007,43(6):660-672.
[34]WANG K F,YE C M,NING A B.Achieving better solutions for vehicle routing problem involving split deliveries and pickups using a competitive decision algorithm[J].Asia-Pacific Journal of Operational Research,2015,32(4):1550022.
[35]POLAT O.A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups[J].Computers and Operations Research,2017,85:71-86.
[2]DROR M,TRUDEAU P.Split delivery routing[J].Naval Research Logistics,1990,37(3):383-402.
[3]DROR M,LAPORTE G,TRUDEAU P.Vehicle routing with split deliveries[J].Discrete Applied Mathematics,1994,50(3),239-254.
[4]MITRA S.An algorithm for the generalized vehicle routing problem with backhauling[J].Asia-Pacific Journal of Operational Research,2005,22(2):153-169.
[5]NOWAK M.The pickup and delivery problem with split loads[D].Atlanta:Georgia Institute of Technology,2005.
[6]PARRAGH S N,DOERNER K F,HARTL R F.A survey on pickup and delivery problems:Part I:transportation between customers and depot[J].Journal für Betriebswirtschaft,2008,58(1):21-51.
[7]PARRAGH S N,DOERNER K F,HARTL R F.A survey on pickup and delivery problems:Part II:transportation between pickup and delivery locations[J].Journal für Betriebswirtschaft,2007,57:81-117.
[8]王科峰,叶春明,唐国春.节点具有双重需求的车辆路径问题及其性质[J].系统科学与数学,2011,31(10):1185-1196.
[9]王科峰.节点具有双重需求的车辆路径问题研究[D].上海:上海理工大学,2012.
[10]王科峰,叶春明.节点具有双重需求车辆路径问题及其解的性质分析[J].上海理工大学学报,2013,35(4):329-335.
[11]MOSHEIOV G.Vehicle routing with pick-up and delivery:tourpartitioning heuristics[J].Computers and Industrial Engineering,1998,34(3):669-684.
[12]NAGY G,SALHI S.Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[J].European Journal of Operational Research,2005,162(1):126-141.
[13]MITRA S.A parallel clustering technique for the vehicle routing problem with split deliveries and pickups[J].Journal of the Operational Research Society,2008,59(11):1532-1546.
[14]LAI M,BATTARRA M,DI FRANCESCO M,et al.An adaptive guidance meta-heuristic for the vehicle routing problem with splits and clustered backhauls[J].Journal of the Operational Research Society,2015,66(7):1222-1235.
[15]NOWAK M,ERGUN O,WHITE C C.Pickup and delivery with split loads[J].Transportation Science,2008,42(1):32-43.
[16]NOWAK M,ERGUN O,WHITE C C.An empirical study on the benefit of split loads with pickup and delivery problem[J].European Journal of Operational Research.2009,198:734-740.
[17]NOWAK M,HEWITT M,WHITE C C.Precedence constrained pickup and delivery with split loads[J].International Journal of Logistics:Research and Applications.2012,15(1):1-14.
[18]TANG G C,NING A B,WANG K F,et al.A practical split vehicle routing problem with simultaneous pickup and delivery[C]//16th International Conference on Industrial Engineering and Engineering Management,IEEE,2009:26-30.
[19]唐国春.新的运输路径问题[C]//中国运筹学会第九届学术交流会论文集.北京:中国运筹学会.2008:269-277.
[20]YIN C Z,BU L,GONG H T.Mathematical model and algorithm of split load vehicle routing problem with simultaneous delivery and pickup[J].International Journal of Innovative Computing,Information and Control,2013,9(11):4497-4508.
[21]WASSAN N A,NAGY G.A reactive tabu search meta-heuristic for the vehicle routing problem with divisible deliveries and pickups[R/OL](2017-01-18)[2018-03-05]https://kar.kent.ac.uk/51852/.
[22]NAGY G,WASSAN N A,SPERANZA M G,et al.The vehicle routing problem with divisible deliveries and pickups[J].Transportation Science,2015,49(2):271-294.
[23]AI T J,KACHIVICHYANUKUL V.A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery[J].Computers and Operations Research,2009,36(5):1693-1702.
[24]ARCHETTI C,MANSINI R,SPERANZA M G.Complexity and reducibility of the skip delivery problem[J].Transportation Science,2005,39(2):182-187.
[25]ARCHETTI C,SPERANZA M G.Vehicle routing problems with split deliveries[J].International Transactions in Operational Research,2012,19:3-22.
[26]ARCHETTI C,SAVELSBERGH M W P,SPERANZA M G.To split or not to split:that is the question[J].Transportation Research:Part E,2008,44:114-123.
[27]WANG Y,MA X,LAO Y,et al.Vehicle routing problem:simultaneous deliveries and pickups with split loads and time windows[J].Transportation Research Record:Journal of the Transportation Research Board,2013(2378):120-128.
[28]ARCHETTI C,SAVELSBERGH M W P,SPERANZA M G.Worst-case analysis for split delivery vehicle routing problems[J].Transportation Science,2006,40(2),226-234.
[29]杨亚璪,靳文舟,郝小妮,等.求解集送货可拆分车辆路径问题的启发式算法[J].华南理工大学学报(自然科学版),2010,38(3):58-63.
[30]WANG K F,YE C M,NING A B.Competitive decision algorithm for the split vehicle routing problem with simultaneous pickup and delivery and time windows[C]//International Conference on Future Information Technology and Management Engineering(FITME),IEEE,2010,2:371-375.
[31]AVCI M,TOPALOGLU S.A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery[J].Expert Systems with Applications,2016,53:160-171.
[32]杨鹏,邹浩,徐贤浩.带时间窗集送货需求可分车辆路径问题的改进蚁群算法[J].系统工程,2015,33(9):58-62.
[33]YI W,KUMAR A.Ant colony optimization for disaster relief operations[J].Transportation Research:Part E,2007,43(6):660-672.
[34]WANG K F,YE C M,NING A B.Achieving better solutions for vehicle routing problem involving split deliveries and pickups using a competitive decision algorithm[J].Asia-Pacific Journal of Operational Research,2015,32(4):1550022.
[35]POLAT O.A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups[J].Computers and Operations Research,2017,85:71-86.