一种求解混载校车路径的启发式算法

Abstract

Abstract: Mixed load school bus routing problem (SBRP) for multiple schools in a city or county,which allows students from different schools to get on same bus at the same time,aims to reduce the number of school buses needed and total operational costs．Several algorithms for solving mixed load SBRP have been developed since 1990s．However,due to the complexity of mixed load SBRP,the neighborhood solutions are not fully explored in these approaches．This paper proposed a new heuristic method for mixed load SBRP using a record-to-record travel (RRT) algorithm and neighborhood operators of pickup and delivery (PDPTW) to minimize the number of required buses．Test results show the effectiveness of this algorithm．Compared with the existing SBRP solutions,this algorithm expands the neighborhood search strategy,and is capable of finding better solutions using fewer buses.

Key words: School bus routing problem (SBRP),Mixed load,Pickup and delivery with time window (PDPTW),Record-to-record travel (RRT)

DANG Lan-xue,WANG Zhen,LIU Qing-song and KONG Yun-feng. Heuristic Algorithm for Solving Mixed Load School Bus Routing Problem[J].Computer Science, 2013, 40(7): 248-253.

References

[1] Newton R M,Thomas W H．Design of school bus routes by computer[J]．Socio-Economic Planning Sciences,1969,3(1):75-85
[2] Braca J,Bramel J,Posner B,et al．A computerized approach to the New York City school bus routing problem[J]．IIE Transactions,1997,29:693-702
[3] de Souza L V,Siqueira P H．Heuristic Methods Applied to the Optimization School Bus Transportation Routes-A Real Case[C]∥IEA/AIE 2010,Part II.Berlin:Springer Verlag,2010:247-256
[4] 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:204-213
[5] Dueck G．New optimization heuristics:The great deluge algorithm and the record-to-record travel[J]．J．Comput．Phys.,1993,104:86
[6] Nanry W,Barnes J．Solving the pickup and delivery problemwith time windows using reactive tabu search[J]．Transportation Research Part B,2000,34:107-21
[7] Li H,LimA．A metaheuristic for the pickup and delivery problem with time windows[C]∥13th IEEE International Confe-rence on Tools with Artificial Intelligence(ICTAI)．2001:160-167
[8] Lau H,Liang Z．Pickup and delivery with time windows:algorithms and test case generations[C]∥Proceedings of the 13th IEEE Conference on tools with Artificial Intelligence(ICTAI)．2001:333-340
[9] Golden B,Assad A,Levy L,et al．The fleet size and mix vehicle routing problem[J]．Computers and Operations Research,1984,11(1):49-66
[10] Toth P,Vigo D．The vehicle routing problem [M]．Philadephia:Society for Industrial and Applied thematics philadephia,2002
[11] Schittekat P,Srensen K,Sevaux M,et al．A matheuristic forthe school bus routing problem[R]．Research paper,2009
[12] Bodin L D,Berman L．Routing and scheduling of school buses by computer[J]．Transportation Science,1979,13(2):113-129
[13] Bodin L D,Golden B,Assad A,et al．Routing and scheduling of vehicles and crews:the state of the art[J]．Computers and Opera-tions Research,1983,10:63-211
[14] Park J,Kim B-I．The school bus routing problem:A review[J]．European Journal of Operational Research,2010,202:311-319
[15] Li L O Y,Fu Z．The school bus routing problem:a case study[J]．Journal of Operation Research Society,2002,53:552-558
[16] 郭强,李育安,郭耀煌.社区儿童接送服务车辆的线路优化[J]．西南交通大学学报,2006(4):486-490
[17] 许文龙,李小娟,宫辉力,等.校车最优路径规划算法[J].地理空间信息,2011(4):67-68
[18] 张苗.基于双层规划的多目标校车路径优化研究[D].成都:西南交通大学,2008
[19] 张富,朱泰英.校车站点及线路的优化设计[J].数学的实践与认识,2012(4):141-146
[20] 张玉兵,吴霄翔,任意.校车安排问题[J].高等数学研究,2011(1):122-125
[21] Fügenschuh A．Solving a school bus scheduling problem withinteger programming[J]．European Journal of Operational Research,2009,193:867-884
[22] Kim B-I,Kim S,Park J．A school bus scheduling problem[J]．European Journal of Operational Research,2012,218:577-585
[23] Chen D,Kallsn H A,Snider R C．School bus routing and scheduling:an expert system approach[J]．Computers and Industrial Engineering,1988,15:179-183
[24] Spada M,Bierlaire M,Liebling T M．Decision-aiding methodology for the school bus routing and scheduling problem[J]．Transportation Science,2005,39:477-490
[25] Desrosiers J,Ferland J A,Rousseau J-M,et al．An overview of a school busing system[M]∥Jaiswal N K．Scientific Management of Transport Systems．North-Holland,Amsterdam,1981:235-243
[26] Gror C,Golden B,Wasil E．A library of local search heuristics for the vehicle routing problem[J]．Math．Prog．Comp.,2010,2:79-101
[27] Carlton W B．A tabu search approach to the general vehicle routing problem[D]．Texas:University of Texas at Austin,1995
[28] Bent R,Van Hentenryck P．A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows[J]．Computers & Operations Research,2006,33:875-893
[29] Golden B L,Wasil E A,Kelly J P,et al．The impact of metaheuristics on solving the vehicle routing problem:algorithms,problem sets,and computational results[M]∥Crainic T,Laporte G．Fleet management and logistics.Boston,MA:Kluwer,1998:33-56
[30] Li F,Golden B,Wasil E．Very large-scale vehicle routing:New test problems,algorithms,and results[J]．Computers & Operations Research,2005,32:1165-1179
[31] Park J,Tae H,Kim B-I．Corrigendum to “Post-improvement procedure for the mixed load school bus routing problem[J/OL].http://dx.doi.org/10.1016/j.ejor.2012.10.050,2012-11-28

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Heuristic Algorithm for Solving Mixed Load School Bus Routing Problem

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 0

Metrics

Comments

Recommended 0