Adopting GRASP to solve a novel model for bus timetabling problem with minimum transfer and fruitless waiting times

Document Type : Original Article

Authors

1 MSc, Faculty of Mathematics and Computer Sciences, Amirkabir University of Technology, Tehran, Iran

2 Department of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic), Iran

Abstract

This paper addresses a variant of bus timetabling problem assuming that travel times changes dynamically over the planning horizon. In addition to minimizing the transfer waiting time, another objective, namely minimizing the fruitless waiting time, is introduced in this paper as a new realistic objective. First, the problem is formulated as a mixed integer linear programming model. Then, since commercial solvers become inefficient to solve moderate and large sized instances of the problem (due to the NP-hardness), a GRASP heuristic algorithm is developed. Computational experiments over a variety of random instances verify the performance of the proposed method.

Keywords

Main Subjects

References

[1] A. Ceder, Public transit planning and operationPublic transit planning and operation: theory, modeling and practice, Elsevier, 2007.
[2] O. J. Ibarra-Rojas, F. Delgado, R. Giesen and J. C. Muñoz, “Planning, operation, and control of bus transport systems: A literature review,” Transportation Research Part B: Methodological, vol. 77, pp. 38-75, 2015.
[3] A. Ceder and N. H. M. Wilson, “Bus network design,” Transportation Research Part B: Methodological, vol. 20, no. 4, pp. 331-344, 1986.
[4] A. Ceder, B. Golany and O. Tal, “Creating bus time tables with maximal synchronization,” Transportation Research Part A: Policy and Practice, vol. 35, no. 10, pp. 913-928, 2001.
[5] A. Eranki, “A model to create bus timetables to attain maximum synchronization considering waiting times at transfer stops,” Graduate Thesis and Dissertations, University of South Florida, 2004.
[6] O. J. Ibarra-Rojas and Y. A. Rios-Solis, “Synchronization of bus timetabling,” Transportation Research Part B: Methodological, vol. 46, no. 5, p. 599–614, 2012.
[7] Y. Shafahi and A. Khani, “A practical model for transfer optimization in a transit network:Model formulations and solutions,” Transportation Research Part A, vol. 44, no. 6, p. 377–389, 2010.
[8] A. Khani and Y. Shafahi, “Transfer optimization in transit networks: headway and departure time coordination,” in 14th International IEEE Conference on, Washington, DC, USA, 2011.
[9] Y. Wu, J. Tang, Y. Yu and Z. Pan, “A stochastic optimization model for transit network timetable design to mitigate the randomness of traveling time by adding slack time,” Transportation Research Part C: Emerging Technologies, vol. 52, pp. 15-31, 2015.
[10] P. Fouilhoux, O. J. Ibarra-Rojas, S. Kedad-Sidhoum and Y. A. Rios-Solis, “Valid inequalities for the synchronization bus timetabling problem,” European Journal of Operational Research, vol. 2, no. 1, pp. 442-450, 2016.
[11] O. J. Ibarra-Rojas, F. López-Irarragorri and Y. A. Rios-Solis, “Multiperiod bus timetabling,” Transportation Science, vol. 50, no. 3, pp. 763-1138, 2016.
[12] T. Liu and A. Ceder, “Integrated public transport timetable synchronization and vehicle scheduling with demand assignment: A bi-objective bi-level model using deficit function approach,” Transportation Research Procedia, vol. 23, pp. 341-361, 2017.
[13] T. A. Feo and M. G. C. Resende, “Greedy randomized adaptive search procedure,” Journal of Global Optimization, vol. 6, pp. 109-133, 1995.
[14] S. A. MirHassani and A. J. Bashirzadeh, “A GRASP meta-heuristic for two-dimensional irregular cutting stock problem,” The International Journal of Advanced Manufacturing Technology, vol. 81, no. 1-4, p. 455–464, 2015.
[15] S. C. Ho and W. Y. Szeto, “GRASP with path relinking for the selective pickup and delivery problem,” Expert Systems with Applications, vol. 51, no. 1, pp. 14-25, 2016.
[16] F. Hooshmand and S. A. MirHassani, “Time dependent green VRP with alternative fuel powered vehicles,” Energy Systems (https://doi.org/10.1007/s12667-018-0283-y), p. 1–36, 2018.
[17] F. Glover and G. A. Kochenberger, Handbook of metaheuristics, Springer, 2003.
AUT Journal of Mathematics and Computing
Volume 1, Issue 1
February 2020
Pages 125-134

Files

Share

How to cite

Statistics