Optimal school bus routes using mixed–integer programming for long-term school bus system
Keywords:
Mixed integer programming, travelling salesman problem, school bus route optimizationAbstract
In this paper, we apply the mixed–integer programming model for solving the modified school bus routing problem under the given list of bus stops and the distances between each pair of bus stops without the number of students in each bus stop. From this model, the obtained schedule can be used for constructing the registration bus system in the long-term, resulting in a decreasing of 55.04% in the total distance of all bus routes as compared to the current routes of a secondary school located in the urban fringe of Thailand.
References
Dantzig G and Ramser J 1959, The truck dispatching problem Mgmt Sci. 60 80–91.
Christofides N and Eilon S 1969 An algorithm for the vehicle dispatching problem Oper. Res. Quart. 20 309–318.
Eilon S, Watson-Grandy C D T and Christofides N 1971 Distribution management: mathematical modelling and practical analysis (London: Griffin).
Laporte G and Nobert Y 1983 A branch and bound algorithm for the capacitated vehicle routing problem Oper. Res. Spektrum 5 77–85.
Balinski M and Quandt R 1964 On an integer program for a delivery problem Oper. Res. 12 300–304.
Clarke G and Wright J W 1964 Scheduling of vehicles from a central depot to a number of delivery points Oper. Res. 12 568–581.
Gillett B E and Miller L R 1974 A heuristic algorithm for the vehicle dispatch problem Oper. Res. 22 340–349.
Fisher M and Jaikumar R 1981, A generalized assignment heuristic for vehicle routing Networks 11 109–124.
Newton R M and Thomas W H 1974 Bus routing in a multi-school system Comput Opns Res. 1 213–222.
Desrochers M and Laporte G 1991 Improvements and extensions to the Miller–Tucker–Zemlin subtour elimination constraints Oper. Res. Lett. 10 27–36.
Naddef D 1994 A remark on „Integer linear programming formulation for a vehicle routing problem‟ by N.R. Achutan and L. Caccetta, or how to use the Clark & Wright savings to write such integer linear programming formulations Eur. J. OplRes. 75 238–241.
Kara I and Bektas T 2005 Integer linear programming formulations of distance constrained vehicle routing problems Research Report
Department of Industrial Engineering, Baskent University (available on request from the authors).
Bektas T and Elmastas S J 2007 Solving school bus routing problems through integer programming J. Oper. Res. Soc. 58 1599–1604.
Chhabra, D., Bhushan, G. and Chandna, P., 2014, March. Multilevel optimization for the placement of piezo-actuators on plate structures for active vibration control using modified heuristic genetic algorithm. Industrial and Commercial Applications of Smart Structures Technologies 2014 (Vol. 9059, p. 90590J). International Society for Optics and Photonics.
Dhingra, A., Chandna, P 2010 Multi-objective flow shop scheduling using hybrid simulated annealing Measuring Business Excellence 14(3), pp. 30-41
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2019 COMPUSOFT: An International Journal of Advanced Computer Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
©2023. COMPUSOFT: AN INTERNATIONAL OF ADVANCED COMPUTER TECHNOLOGY by COMPUSOFT PUBLICATION is licensed under a Creative Commons Attribution 4.0 International License. Based on a work at COMPUSOFT: AN INTERNATIONAL OF ADVANCED COMPUTER TECHNOLOGY. Permissions beyond the scope of this license may be available at Creative Commons Attribution 4.0 International Public License.
