Locating optimal timetables and vehicle schedules in a transit line.

*(English)*Zbl 1303.90069Summary: This paper deals with the Transit Network Timetabling and Scheduling Problem (TNTSP) in a public transit line. The TNTSP aims at determining optimal timetables for each line in a transit network by establishing departure and arrival times of each vehicle at each station. We assume that customers know departure times of line runs offered by the system. However, each user, traveling after or before than their desired travel time, will give rise to an inconvenience cost, or a penalty cost if that user cannot be served according to the scheduled timetable. The provided formulation allocates each user to the best possible timetable considering capacity constraints. The problem is formulated using a p-median based approach and solved using a clustering technique. Computational results that show useful applications of this methodology are also included.

##### MSC:

90C10 | Integer programming |

90B35 | Deterministic scheduling theory in operations research |

90B80 | Discrete location and assignment |

PDF
BibTeX
XML
Cite

\textit{J. A. Mesa} et al., Ann. Oper. Res. 222, 439--455 (2014; Zbl 1303.90069)

Full Text:
DOI

##### References:

[1] | Brannlund, U.; Lindberg, P. O.; Nou, A.; Nilsson, J.-E., Railway timetabling using Lagrangian relaxation, Transportation Science, 32, 358-369, (1998) · Zbl 1004.90035 |

[2] | Bunte, S.; Kliewer, N., An overview on vehicle scheduling models, Public Transport, 1, 299-317, (2009) |

[3] | Cadarso, L.; Marín, A., Integration of timetable planning and rolling stock in rapid transit networks, Annals of Operations Research, 199, 113-135, (2012) · Zbl 1251.90082 |

[4] | Cai, X.; Goh, C. J., A fast heuristic for the train scheduling problem, Computers & Operations Research, 21, 499-510, (1994) · Zbl 0799.90068 |

[5] | Caprara, A.; Fischetti, M.; Toth, P., Modeling and solving the train timetabling problem, Operations Research, 50, 851-861, (2002) · Zbl 1163.90482 |

[6] | Caprara, A.; Monaci, M.; Toth, P.; Guida, P. L., A lagrangian heuristic algorithm for a real-world train timetabling problem, Discrete Applied Mathematics, 154, 738-753, (2006) · Zbl 1120.90324 |

[7] | Castelli, L.; Pesenti, R.; Ukovich, W., Scheduling multimodal transportation systems, European Journal of Operational Research, 155, 603-615, (2004) · Zbl 1049.90007 |

[8] | Ceder, A.; Wilson, N. H. M., Bus network design, Transportation Research. Part B: Methodological, 20, 331-344, (1986) |

[9] | Chakroborty, P.; Deb, K.; Sharma, R. K., Optimal fleet size distribution and scheduling of transit systems using genetic algorithms, Transportation Planning and Technology, 24, 209-226, (2001) |

[10] | Chang, S.-C.; Chung, Y.-C., From timetabling to train regulation-a new train operation model, Information and Software Technology, 47, 575-585, (2005) |

[11] | Chew, K.; Pang, J.; Liu, Q.; Ou, J.; Teo, C., An optimization based approach to the train operator scheduling problem at Singapore MRT, Annals of Operations Research, 108, 111-118, (2001) · Zbl 0993.90501 |

[12] | Cordeau, J.-F.; Laporte, G.; Potvin, J.-Y.; Savelsbergh, M. W.; Barnhart, C. (ed.); Laporte, G. (ed.), Transportation on demand, No. 14, 429-466, (2007), Amsterdam |

[13] | Cordeau, J.-F.; Laporte, G.; Savelsbergh, M. W.; Vigo, D.; Barnhart, C. (ed.); Laporte, G. (ed.), Vehicle routing, No. 14, 367-428, (2007), Amsterdam |

[14] | Palma, A.; Lindsey, R., Optimal timetables for public transportation, Transportation Research. Part B: Methodological, 35, 789-813, (2001) |

[15] | Espejo, I.; Marín, A.; Rodríguez-Chía, A. M., Closest assignment constraints in discrete location problems, European Journal of Operational Research, 219, 49-58, (2012) · Zbl 1244.90127 |

[16] | Fosgerau, M., The marginal social cost of headway for a scheduled service, Transportation Research. Part B: Methodological, 43, 813-820, (2009) |

[17] | Grosfeld-Nir, A.; Bookbinder, J., The planning of headways in urban public transit, Annals of Operations Research, 60, 145-160, (1995) · Zbl 0839.90030 |

[18] | Guihaire, V.; Hao, J.-K., Transit network design and scheduling: a global review, Transportation Research. Part A, Policy and Practice, 42, 1251-1273, (2008) |

[19] | Guihaire, V.; Hao, J.-K., Transit network timetabling and vehicle assignment for regulating authorities, Computers & Industrial Engineering, 59, 16-23, (2010) |

[20] | Guo, Z.; Wilson, N. H., Assessing the cost of transfer inconvenience in public transport systems: a case study of the London underground, Transportation Research. Part A, Policy and Practice, 45, 91-104, (2011) |

[21] | Hakimi, S., Optimum locations of switching centers and the absolute centers and medians of a graph, Operations Research, 12, 450-459, (1964) · Zbl 0123.00305 |

[22] | Hakimi, S., Optimum distribution of switching centers in a communications network and some related graph theoretic problems, Operations Research, 13, 462-475, (1965) · Zbl 0135.20501 |

[23] | Higgins, A.; Kozan, E.; Ferreira, L., Optimal scheduling of trains on a single line track, Transportation Research. Part B: Methodological, 30, 147-161, (1996) |

[24] | Liebchen, C.; Schachtebeck, M.; Schöbel, A.; Stiller, S.; Prigge, A., Computing delay resistant railway timetables, Computers & Operations Research, 37, 857-868, (2010) · Zbl 1177.90172 |

[25] | Liu, Z.-G.; Shen, J.-S., Regional bus operation bi-level programming model integrating timetabling and vehicle scheduling, Systems Engineering - Theory & Practice, 27, 135-141, (2007) |

[26] | Magnanti, T.; Wong, R., Network design and transportation planning: models and algorithms, Transportation Science, 18, 1-55, (1984) |

[27] | Oliveira, E., & Smith, B. M. (2000). A job-shop scheduling model for the single-track railway scheduling problem (Tech. rep. 2000.21). University of Leeds, Leeds, UK. · Zbl 1251.90082 |

[28] | Quak, C. (2003). Bus line planning. Ph.D. thesis, Delft University of Technology, The Netherlands. · Zbl 1120.90324 |

[29] | Small, K. A., The scheduling of consumer activities: work trips, The American Economic Review, 72, 467-479, (1982) |

[30] | Stern, R. (1996). Passenger transfer system review. Synthesis of transit practice. Transportation research board, vol. 19. |

[31] | Wagner, J. L.; Falkson, L. M., The optimal nodal location of public facilities with price-sensitive demand, Geographical Analysis, 7, 69-83, (1975) |

[32] | Zhou, X.; Zhong, M., Bicriteria train scheduling for high-speed passenger railroad planning applications, European Journal of Operational Research, 167, 752-771, (2005) · Zbl 1077.90033 |

[33] | Zhou, X.; Zhong, M., Single-track train timetabling with guaranteed optimality: branch-and-bound algorithms with enhanced lower bounds, Transportation Research. Part B: Methodological, 41, 320-341, (2007) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.