Computer Science ›› 2016, Vol. 43 ›› Issue (10): 234-241.

### Metaheuristic Algorithm for Split Demand School Bus Routing Problem

CHEN Xiao-pan, KONG Yun-feng, ZHENG Tai-hao and ZHENG Shan-shan

• Online:2018-12-01 Published:2018-12-01

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.

 [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
 No related articles found!
Viewed
Full text

Abstract

Cited

Shared
Discussed
 No Suggested Reading articles found!