Journal of Geo-information Science >
A Meta-heuristic Algorithm to Solve the Large-Scale School Bus Scheduling Problem
Received date: 2013-11-14
Revised date: 2013-12-04
Online published: 2013-12-25
Given school bus trips for each school in a school district, if a school bus can serve multiple trips, the efficiency of school bus service can be improved in terms of the number of buses needed and the total travel cost. The school bus scheduling problem (SBSP), a class of school bus routing problem (SBRP), is concerned with assigning a fleet of buses to serve all the given trips and aims to get optimal bus schedules. Each school has its xed time window within which school bus must arrive at the destination school of the trip. In existing literatures, SBSP is usually formulated as a transportation problem (TP) or an assignment problem (AP). However, many existing algorithms for vehicle routing problem (VRP) have not been fully utilized to solve the problem effectively. This paper proposes a meta-heuristic algorithm for large-scale SBSP. Treating a trip as a virtual stop with time window, the problem can be converted to a vehicle routing problem with time windows (VRPTW). Therefore, the SBSP can be solved in a VRP algorithm framework. After a set of feasible solutions are generated using construction heuristic algorithm, a simulated annealing (SA) algorithm is designed to improve the initial solutions iteratively. Four general operators for VRP, one-point move, two point move, two-opt move and cross-exchange move, are used in the neighborhood search. In addition to the SBSP objectives of minimizing the number of the routes and the total travel distance, the sum of squared number of route stops is added as a new objective. This will guide the neighborhood search toward the situation that deleting some routes more easily. For avoiding local optimum, some worsening neighborhood solutions can be accepted with a certain probability. Computational tests on 15 instances with a homogeneous fleet show the effectiveness of the proposed approaches. Compared with the existing SBSP solutions, the proposed algorithm can solve large-scale SBSP in a reasonable time and find better solutions using fewer buses. In addition, the algorithm can be easily integrated with GIS for solving real world school bus scheduling.
CHEN Xiao-Bo, DANG Lan-Hua, KONG Yun-Feng . A Meta-heuristic Algorithm to Solve the Large-Scale School Bus Scheduling Problem[J]. Journal of Geo-information Science, 2013 , 15(6) : 879 -886 . DOI: 10.3724/SP.J.1047.2013.00879
[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] Park J, Kim B I. The school bus routing problem: A review[J]. European Journal of Operational Research, 2010, 202(2):311-319.
[3] Swersey A J, Ballard W. Scheduling school buses[J]. Management Science, 1984, 30(7):844-853.
[4] Desrosiers J, Ferland J A, Rousseau J M, et al. An overview of a school busing system[M].//Jaiswal N K (Ed.). Scientific Management of Transport Systems, Amsterdam: North-Holland, 1981:235-243.
[5] Desrosiers J, Ferland J A, Rousseau, et al. A multi-period school bus routing and scheduling system[M].//TIMS Studies in the Management Sciences, Amsterdam: Elsevier Science Publishers, 1986, 22:47-71.
[6] FÜgenschuh A. Solving a school bus scheduling problem with integer programming[J]. European Journal of Operational Research, 2009, 193(3):867-884.
[7] Kim B I, Kim S, Park J. A school bus scheduling problem[J]. European Journal of Operational Research, 2012, 218(2):577-585.
[8] Spada M, Bierlaire M, Liebling T M. Decision-aiding methodology for the school bus routing and scheduling problem[J]. Transportation Science, 2005, 39(4):477-490.
[9] Swersey A J, Ballard W. Scheduling school buses[J]. Management Science, 1984, 30(7):844-853.
[10] Spada M, Bierlaire M, Liebling T M. Decision-aiding methodology for the school bus routing and scheduling problem[J]. Transportation Science, 2005, 39(4):477-490.
[11] FÜgenschuh A. A set partitioning reformulation of a school bus scheduling problem[J]. Journal of Scheduling, 2011, 14(4):307-318.
[12] FÜgenschuh A, Martin A. A multicriteria approach for optimizing bus schedules and school starting times[J]. Annals of Operations Research, 2006, 147(1):199-216.
[13] Chen D S, Kallsen H A, Snider R C. School bus routing and scheduling: an expert system approach[J]. Computers & Industrial Engineering, 1988, 15(1):179-183.
[14] Braca J, Bramel J, Posner B, et al. A computerized approach to the New York City school bus routing problem[J]. ⅡE transactions, 1997, 29(8):693-702.
[15] 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.
[16] 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.
[17] 党兰学, 王震, 刘青松, 等.一种求解混载校车路径的启发式算法[J].计算机科学, 2013, 40(7):248-253.
[18] Groër C, Golden B, Wasil E. A library of local search heuristics for the vehicle routing problem[J]. Mathematical Programming Computation, 2010, 2(2):79-101.
[19] Bräysy O, Gendreau M. Vehicle routing problem with time windows, Part Ⅰ: Route construction and local search algorithms[J]. Transportation science, 2005, 39(1):104-118.
[20] Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations research, 1987, 35(2):254-265.
/
| 〈 |
|
〉 |