A matheuristic for the school bus routing problem

Patrick Schittekat, Kenneth. Sörensen, Marc Sevaux and Johan Springael

Working Papers from University of Antwerp, Faculty of Business and Economics

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 problem in its most basic form. To this end, we define 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 he should walk to and (3) determine routes that visit the chosen stops, so that the total traveled distance is minimized. We develop an MIP model of this basic problem. To efficiently solve large instances of the SBRP we develop an efficient GRASP+VND metaheuristic. Our method can be called a matheuristic because it uses an exact algorithm to optimally solve the subproblem of assigning students to stops and to routes. The results of our matheuristic approach on 112 artificially generated instances are compared to those obtained by implementing the MIP model in a commercial solver and solving it using a specially developed cutting plane procedure. Experiments show that our matheuristic outperforms the exact method in terms of speed and matched the exact method in terms of solution quality.

Pages: 27 pages
Date: 2009-10
New Economics Papers: this item is included in nep-cmp, nep-ore and nep-ure
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://repository.uantwerpen.be/docman/irua/929053/9e894227.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ant:wpaper:2009010

Access Statistics for this paper

More papers in Working Papers from University of Antwerp, Faculty of Business and Economics Contact information at EDIRC.
Bibliographic data for series maintained by Joeri Nys ().