需求可拆分校车路径问题的元启发式算法

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

摘要/Abstract

摘要： 校车路径规划中,允许站点乘车需求拆分通常能有效地降低校车服务成本。将该问题定义为需求可拆分校车路径问题(SDSBRP)进行求解。由于校车服务中要顾及学生最大乘车时间,且优化目标要兼顾所需校车数量和校车行驶距离,经典SDVRP算法难以直接应用于SDSBRP。因此分析了该问题的解特征,首次构建双目标SDSBRP数学模型,并首次设计针对该问题的元启发式求解算法。该算法首先构造初始可行解,然后在模拟退火算法框架下,引入站点需求拆分的邻域搜索算子进行迭代搜索,逐步改善解的质量。邻域搜索中,设计了多目标问题的邻域接受准则来引导邻域解的搜索方向,并引入破坏重建机制来增加解的多样性。使用已有的测试案例集和改造的测试案例进行算法测试,实验结果表明所提算法收敛性好,能够显著降低校车服务成本。

关键词: 校车路径问题,需求拆分,元启发式算法,模拟退火

Abstract: In school bus route planning for middle and elementary schools,the total cost of school bus service may be reduced if the travel demands of each bus stop can be split and served by several buses.This paper dealt with the split demand school bus routing problem (SDSBRP).Compared with the split delivery vehicle routing problem (SDVRP),the students’ maximum riding time should be considered in SDSBRP.Moreover,the objectives of SDSBRP are minimizing the total number of buses and the total traveling distance.Thus,the methods and strategies for solving classic SDVRP cannot be applied to SDSBRP directly.This paper,for the first time,analyzed the solution properties of SDSBRP,introduced a mathematic formulation for bi-objective SDSBRP,and proposed a metaheuristic algorithm for it.In the algorithm,an initial feasible solution is generated by constructive heuristic.Then,the solution is improved iteratively by neighborhood operators either with or without demand splitting.In addition,a new acceptance criterion and a ruin and recreate mechanism are used to improve the diversity of solutions.For avoiding local optimum,some worsening neighborhood solutions with longer distance can be accepted with a certain probability according to the simulated annealing rule.The efficiency of the proposed algorithm is benchmarked and confirmed by extensive computational experiments.The savings generated from splitting demands are also discussed.

Key words: School bus routing problem,Split deliveries,Metaheuristic algorithm,Simulated annealing

陈小潘,孔云峰,郑泰皓,郑珊珊. 需求可拆分校车路径问题的元启发式算法[J]. 计算机科学, 2016, 43(10): 234-241. https://doi.org/10.11896/j.issn.1002-137X.2016.10.045

CHEN Xiao-pan, KONG Yun-feng, ZHENG Tai-hao and ZHENG Shan-shan. Metaheuristic Algorithm for Split Demand School Bus Routing Problem[J]. Computer Science, 2016, 43(10): 234-241. https://doi.org/10.11896/j.issn.1002-137X.2016.10.045

参考文献

[1] Newton R M,Thomas W H.Design of school bus routes bycomputer [J].Socio-Economic Planning Sciences,1969,3(1):75-85
[2] Park J,Kim B I.The school bus routing problem:A review [J].European Journal of Operational Research,2010,202(2):311-319
[3] Dang Lan-xue,Chen Xiao-pan,Kong Yun-feng.Reivew ofSchool Bus Routing Problem:Concept,Model And Optimizaion Algorithms[J].Journal of Henan University(Natutal science),2013,43(6):682-691(in Chinese) 党兰学,陈小潘,孔云峰.校车路径问题模型及算法研究进展 [J].河南大学学报(自然科学版),2013,43(6):682-691
[4] Dang Lan-xue,Wang Zhen,Liu Qing-song,et al.Heuristic Algorithm for Solving Mixed Load School Bus Routing Problem [J].Computer Science,2013,40(7):248-253(in Chinese) 党兰学,王震,刘青松,等.一种求解混载校车路径的启发式算法 [J].计算机科学,2013,40(7):248-253
[5] Dror M,Trudeau P.Savings by split delivery routing [J].Transportation Science,1989,23(2):141-145
[6] Dror M,Trudeau P.Split delivery routing [J].Naval Research Logistics (NRL),1990,37(3):383-402
[7] Archetti C,Savelsbergh M W P,Grazia Speranza M.To split or not to split:That is the question [J].Transportation Research Part E:Logistics and Transportation Review,2008,44(1):114-123
[8] Silva M M,Subramanian A,Ochi L S.An iterated local search heuristic for the split delivery vehicle routing problem [J].Computers & Operations Research,2015,53(53):234-249
[9] Frizzell P W,Giffin J W.The split delivery vehicle schedulingproblem with time windows and grid network distances [J].Computers & Operations Research,1995,22(6):655-667
[10] 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
[11] Berbotto L,García S,Nogales F J.A Randomized Granular Tabu Search heuristic for the split delivery vehicle routing problem [J].Annals of Operations Research,2014,222(1):153-173
[12] Liu Wang-sheng,Yang Fan,Li Mao-qing,et al.Clustering algorithm for split delivery vehicle routing problem[J].Control and Decision,2012,27(4):535-541(in Chinese) 刘旺盛,杨帆,李茂青,等.需求可拆分车辆路径问题的聚类求解算法 [J].控制与决策,2012,27(4):535-541
[13] Meng Fan-chao,Lu Zhi-qiang,Sun Xiao-ming.Taboo Search algorithm of split Vehicle routing problem [J].Computer Aided Engineering,2010,19(1):78-83(in Chinese) 孟凡超,陆志强,孙小明.需求可拆分车辆路径问题的禁忌搜索算法 [J].计算机辅助工程,2010,19(1):78-83
[14] Ho S C,Haugland D.A tabu search heuristic for the vehicle routing problem with time windows and split deliveries [J].Computers & Operations Research,2004,31(12):1947-1964
[15] Belfiore P,Yoshizaki H T Y.Heuristic methods for the fleet size and mix vehicle routing problem with time windows and split deliveries [J].Computers & Industrial Engineering,2013,64(2):589-601
[16] Belfiore P C,Yoshida Yoshizaki H T.Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil [J].European Journal of Ope-rational Research,2009,199(3):750-758
[17] Thangiah S R,Fergany A,Wilson B,et al.School bus routing in rural school districts [M].Computer-aided Systems in Public Transport.Springer,2008:209-232
[18] Jin Yan-bo.Research on Optimizatin Of School Bus Routing[D].Changchun:Jilin University,2006(in Chinese) 金燕波.校车路径优化问题研究 [D].长春:吉林大学,2006
[19] Archetti C,Mansini R,Speranza M G.Complexity and Reduci-bility of the Skip Delivery Problem [J].Transportation Scien-ce,2005,39(2):182-187
[20] Archetti C,Speranza M G,Savelsbergh M W P.An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem [J].Transportation Science,2008,42(1):22-31
[21] Loureno H,Martin O,Stützle T.Iterated Local Search:Framework and Applications(2rd ed)[M]∥Gendreau M,Potvin J-Y.Handbook of Metaheuristics.Springer US,2010:363-397
[22] Schrimpf G,Schneider J,Stamm-Wilbrandt H,et al.RecordBreaking Optimization Results Using the Ruin and Recreate Principle [J].Journal of Computational Physics,2000,159(2):139-171
[23] Schneider J,Kirkpatrick S.Ruin & Recreate [M]∥Schneider J,Kirkpatrick S.Stochastic Optimization.Berlin:Springer Berlin Heidelberg,2006:73-77
[24] Bent R,Van Hentenryck P.A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows [J].Transportation Science,2004,38(4):515-530
[25] Bent R,Hentenryck P V.A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows [J].Computers & Operations Research,2006,33(4):875-893
[26] Park J,Tae H,Kim B-I.A post-improvement procedure for the mixed load school bus routing problem [J].European Journal of Operational Research,2012,217(1):204-213
[27] Braca J,Bramel J,Posner B,et al.A computerized approach to the New York City school bus routing problem [J].IIE Transac-tions,1997,29(8):693-702

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed