解决需求可拆分车辆路径问题的先聚类后路径方法
|
摘要
介绍了求解需求可拆分车辆路径问题的"先聚类后路径"的方法,其目标是使用最少车辆获得最小总行驶距离。基于该方法,提出了三阶段算法:首先,根据使用最少车辆的原则,利用最大最小距离聚类,将所有客户点按物理位置分成若干组;然后,采用"推出"和"拉入"操作,调整各组的负荷量,形成重量平衡的聚类组;最后,优化上述组内路径。两案例组7个实例的执行验证了该算法的可行性和有效性;结果表明,该算法在总行驶距离和计算所用时间方面性能优于带有效不等式的两阶段算法、k-means聚类算法、拆分阈值聚类算法和扫描算法等。
引文
[1]M.Dror and P.Trudeau.Savings by split delivery routing[J].Transportation Science,1989,23(2):141-145.
[2]C.Archetti and M.G.Speranza.Vehicle routing problems with split deliveries[J].International Transactions in Operational Research,2012,19:3-22.
[3]J.M.Belenguer,M.C.Martinez and E.Mota.A lower bound for the split delivery vehicle routing problem[J].Operations Research,2000,48(5):801-810.
[4]C.Archettic,A.Hertz and Speranza M G.A tabu search algorithm for the split delivery vehicle routing problem[J].Transportation Science,2006,40(1):64-73.
[5]C.Archettic,M.W.P.Savelsbergh and M.G.Speranza.An optimization-based heuristic for the split delivery vehicle routing problem[J].TransportationScience,2008,42(1):22-31.
[6]S.Chen,B.Golden and E.Wasil.The split delivery vehicle routing problem:Applications,algorithms,testproblems,and computationalresults[J].Networks,2007,49(4):318-329.
[7]M.Z.Jin,K.Liu and R.O.Bowden.A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem[J].International Journal of Production Economics,2007,105(1):228-242.
[8]M.Jin,K.Liu and B.Eksioglu.A column generation approach for the split delivery vehicle routing problem[J].Operations Research Letters,2008,36(2):265-270.
[9]J.M.Tan and R.H.Xu.Solution to vehicle routing problem with split deliveries[J].Journal of System Management,2008,17(1):43-46.
[10]D.Gulczynski,B.Golden and E.Wasil.The split delivery vehicle routing problem with minimum delivery amounts[J].Transportation Research Part E,2010,46:612-626.
[11]R.E.Aleman,X.Zhang and R.R.Hill.An adaptive memory algorithm for the split delivery vehicle routing problem[J].Journal of Heuristics,2010,16(3):441-473.
[12]R.E.Aleman and R.R.Hill.A tabu search with vocabulary building approach for the vehicle routing problem with split demands[J].International Journal of Meta-heuristics,2010,1(1):55-80.
[13]C.Archetti,N.Bianchessi and M.G.Speranza.A column generation approach for the split delivery vehicle routing problem[J].Networks,2011,58(4):241-254.
[14]J.H.Wilck IV and T.M.Cavalier.A Construction Heuristic for the Split Delivery Vehicle Routing Problem[J].American Journal of Operations Research,2012,2:153-162.
[15]谢毅.需求可拆分的物流车辆路线问题研究[D].上海:同济大学,2006.
[16]侯立文,谭家美,赵元.求解带时间窗的客户需求可分条件下的车辆路径问题[J].中国管理科学,2007,15(6):46-51.
[17]孟凡超,陆志强,孙小明.需求可拆分车辆路径问题的禁忌搜索算法[J].计算机辅助工程,2010,19(1):78-83.
[18]谢秉磊,胡小明,张一喆.需求可分的车辆路径问题模型与算法[J].运筹与管理,2012,21(3):72-76.
[19]刘旺盛,杨帆,李茂青,陈培芝.需求可拆分车辆路径问题的聚类求解算法[J].控制与决策,2012,17(4):535-541.
[20]刘旺盛,黄娟.需求可拆分的车辆路径问题的分段求解[J].集美大学学报(自然科学版),2011,16(1):38-44.
[21]马华伟,叶浩然,夏维.允许分割配送的多时间窗车辆调度问题的改进蚁群算法求解[J].中国管理科学,2012,20:43-47.
[22]汪婷婷,倪郁东,何文玲.需求可拆分车辆路径问题的蜂群优化算法[J].合肥工业大学学报,2014,37(8):1016-1019.
[23]向婷,潘大志.求解需求可拆分车辆路径问题的聚类算法[J].计算机应用,2016,36(11):3141-3145.
[24]周涓.基于最大最小距离的多中心聚类算法[D].四川:重庆大学,2006.
[25]J.N.Min,C.Jin and L.J.Lu.A Three-Stage Approach for Split Delivery Vehicle Routing Problem Solving[A].8th IEEEInternational Conference on Logistics,Informatics and Service Sciences(LISS2018)[C].2018:96-101.
[2]C.Archetti and M.G.Speranza.Vehicle routing problems with split deliveries[J].International Transactions in Operational Research,2012,19:3-22.
[3]J.M.Belenguer,M.C.Martinez and E.Mota.A lower bound for the split delivery vehicle routing problem[J].Operations Research,2000,48(5):801-810.
[4]C.Archettic,A.Hertz and Speranza M G.A tabu search algorithm for the split delivery vehicle routing problem[J].Transportation Science,2006,40(1):64-73.
[5]C.Archettic,M.W.P.Savelsbergh and M.G.Speranza.An optimization-based heuristic for the split delivery vehicle routing problem[J].TransportationScience,2008,42(1):22-31.
[6]S.Chen,B.Golden and E.Wasil.The split delivery vehicle routing problem:Applications,algorithms,testproblems,and computationalresults[J].Networks,2007,49(4):318-329.
[7]M.Z.Jin,K.Liu and R.O.Bowden.A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem[J].International Journal of Production Economics,2007,105(1):228-242.
[8]M.Jin,K.Liu and B.Eksioglu.A column generation approach for the split delivery vehicle routing problem[J].Operations Research Letters,2008,36(2):265-270.
[9]J.M.Tan and R.H.Xu.Solution to vehicle routing problem with split deliveries[J].Journal of System Management,2008,17(1):43-46.
[10]D.Gulczynski,B.Golden and E.Wasil.The split delivery vehicle routing problem with minimum delivery amounts[J].Transportation Research Part E,2010,46:612-626.
[11]R.E.Aleman,X.Zhang and R.R.Hill.An adaptive memory algorithm for the split delivery vehicle routing problem[J].Journal of Heuristics,2010,16(3):441-473.
[12]R.E.Aleman and R.R.Hill.A tabu search with vocabulary building approach for the vehicle routing problem with split demands[J].International Journal of Meta-heuristics,2010,1(1):55-80.
[13]C.Archetti,N.Bianchessi and M.G.Speranza.A column generation approach for the split delivery vehicle routing problem[J].Networks,2011,58(4):241-254.
[14]J.H.Wilck IV and T.M.Cavalier.A Construction Heuristic for the Split Delivery Vehicle Routing Problem[J].American Journal of Operations Research,2012,2:153-162.
[15]谢毅.需求可拆分的物流车辆路线问题研究[D].上海:同济大学,2006.
[16]侯立文,谭家美,赵元.求解带时间窗的客户需求可分条件下的车辆路径问题[J].中国管理科学,2007,15(6):46-51.
[17]孟凡超,陆志强,孙小明.需求可拆分车辆路径问题的禁忌搜索算法[J].计算机辅助工程,2010,19(1):78-83.
[18]谢秉磊,胡小明,张一喆.需求可分的车辆路径问题模型与算法[J].运筹与管理,2012,21(3):72-76.
[19]刘旺盛,杨帆,李茂青,陈培芝.需求可拆分车辆路径问题的聚类求解算法[J].控制与决策,2012,17(4):535-541.
[20]刘旺盛,黄娟.需求可拆分的车辆路径问题的分段求解[J].集美大学学报(自然科学版),2011,16(1):38-44.
[21]马华伟,叶浩然,夏维.允许分割配送的多时间窗车辆调度问题的改进蚁群算法求解[J].中国管理科学,2012,20:43-47.
[22]汪婷婷,倪郁东,何文玲.需求可拆分车辆路径问题的蜂群优化算法[J].合肥工业大学学报,2014,37(8):1016-1019.
[23]向婷,潘大志.求解需求可拆分车辆路径问题的聚类算法[J].计算机应用,2016,36(11):3141-3145.
[24]周涓.基于最大最小距离的多中心聚类算法[D].四川:重庆大学,2006.
[25]J.N.Min,C.Jin and L.J.Lu.A Three-Stage Approach for Split Delivery Vehicle Routing Problem Solving[A].8th IEEEInternational Conference on Logistics,Informatics and Service Sciences(LISS2018)[C].2018:96-101.