Title
A metaheuristic for the school bus routing problem with bus stop selection A metaheuristic for the school bus routing problem with bus stop selection
Author
Faculty/Department
Faculty of Applied Economics
Publication type
article
Publication
Amsterdam ,
Subject
Economics
Mathematics
Source (journal)
European journal of operational research. - Amsterdam
Volume/pages
229(2013) :2 , p. 518-528
ISSN
0377-2217
ISI
000319307600023
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
Abstract
Existing literature on routing of school buses has focused mainly on building intricate models that attempt to capture as many real-life constraints and objectives as possible. In contrast, the focus of this paper is on understanding the joint problem of bus route generation and bus stop selection - two important sub-problems - in its most basic form. To this end, this paper defines the school bus routing problem (SBRP) as a variant of the vehicle routing problem in which three simultaneous decisions have to be made: (1) determine the set of stops to visit, (2) determine for each student which stop (s)he should walk to, and (3) determine routes that lie along the chosen stops, so that the total traveled distance is minimized. An MIP model of this basic problem is developed. To increase the practical usefulness and to solve large instances of the SBRP, an efficient parameter-free GRASP + VND metaheuristic is developed. This method is a matheuristic since it uses an exact algorithm to optimally solve the sub-problem of assigning students to stops when routes are given. The results of this matheuristic approach on 112 artificially generated instances are compared to solutions found by a sequential method, to solutions obtained by implementing a MIP model in a commercial solver, and to a lower bound obtained by a dedicated column generation approach. Using appropriate statistical techniques, a neighborhood analysis is performed to test the design of the metaheuristic. Similarly, the characteristics of the problem instance that determine the computing time of the metaheuristic are discovered using statistical analysis. Finally, the importance of integrating all decisions in a single model is shown experimentally by comparing the metaheuristic to a sequential method. Experiments show that the matheuristic exhibits excellent performance and finds optimal or close-to-optimal solutions of large instances of the SBRP in very limited computing times. (C) 2013 Elsevier B.V. All rights reserved.
E-info
https://repository.uantwerpen.be/docman/iruaauth/23afce/2184513.pdf
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000319307600023&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000319307600023&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000319307600023&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle