×

zbMATH — the first resource for mathematics

A matheuristic for the driver scheduling problem with staff cars. (English) Zbl 1430.90287
Summary: In the public bus transport industry, it is estimated that the cost of a driver schedule accounts for approximately 60% of a transport company’s operational expenses. Hence, it is important for transport companies to minimize the overall cost of driver schedules. A duty is defined as the work of a driver for a day and the driver scheduling problem (DSP) is concerned with finding an optimal set of driver duties to cover a set of timetabled bus trips. Numerous labor regulations and other practical conditions enforce drivers to travel within the city network to designated bus stops to start/end duty, to take a break or to takeover a bus from another driver. This paper focuses on the driver scheduling problem with staff cars (DSPSC), where staff cars can be utilized by the drivers to fulfill their travel activities. However, staff cars should always be returned to the depot and can perform multiple round trips during the day. The problem is restricted by the number of cars available at the depot. We present a matheuristic for solving the DSPSC and the proposed method is tested on instances from Danish and Swedish companies. A comparison with a state-of-the-art mixed integer programming (MIP) solver indicates that the matheuristic provides better solutions, with comparable computation times, for 6 out of 10 large instances. For instances that have more than 6 staff cars and 1200 bus trips, the improvement is 13-15% on average.
MSC:
90B35 Deterministic scheduling theory in operations research
90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming
Software:
SPOT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ball, M.; Bodin, L.; Dial, R., A matching based heuristic for scheduling mass transit crews and vehicles, Transportation Science, 17, 1, 4-31, (1983)
[2] Birattari, M.; Yuan, Z.; Balaprakash, P.; Stützle, T., F-race and iterated f-race: An overview, Experimental methods for the analysis of optimization algorithms, 311-336, (2010) · Zbl 1204.68280
[3] Blum, C.; Puchinger, J.; Raidl, G. R.; Roli, A., Hybrid metaheuristics in combinatorial optimization: A survey, Applied Soft Computing, 11, 4135-4151, (2011)
[4] Borndörfer, R.; Löbel, A.; Weider, S., A bundle method for integrated multi-depot vehicle and duty scheduling in public transit, Lecture Notes in Economics and Mathematical Systems, 600, 3-24, (2008) · Zbl 1168.90424
[5] Boschetti, M. A.; Maniezzo, V.; Roffilli, M.; Bolufe Roehler, A., Matheuristics: Optimization, simulation and control, Lecture Notes in Computer Science, 5818, 171-177, (2009)
[6] Cordeau, J.-F.; Laporte, G.; Mercier, A., A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society, 52, 928-936, (2001) · Zbl 1181.90034
[7] Darby-Dowman, K.; Jachnik, J. K.; Lewis, R. L.; Mitra, G., Integrated decision support systems for urban transport scheduling: Discussion of implementation and experience, Proceedings of the fourth international workshop on computer-aided scheduling of public transport, (1988)
[8] De Leone, R.; Festa, P.; Marchitto, E., A bus driver scheduling problem: A new mathematical model and a grasp approximate solution, Journal of Heuristics, 17, 441-466, (2011) · Zbl 1233.90152
[9] De Leone, R.; Festa, P.; Marchitto, E., Solving a bus driver scheduling problem with randomized multistart heuristics, International Transactions in Operational Research, 18, 6, 707-727, (2011) · Zbl 1267.90058
[10] Desaulniers, G.; Hickman, M. D., Public transit, Handbook in operations research and management science, Vol. 14, 69-127, (2007), Elsevier
[11] Desrochers, M.; Soumis, F., A column generation approach to the urban transit crew scheduling problem, Transportation Science, 23, 1, 1-13, (1989) · Zbl 0668.90043
[12] Dumitrescu, I.; Stützle, T., Combinations of local search and exact algorithms, Lecture Notes in Computer Science, 2611, 211-223, (2003) · Zbl 1033.68622
[13] Fischetti, M.; Martello, S.; Toth, P., The fixed job schedule problem with spread-time constraints, Operations Research, 35, 6, 849-858, (1987) · Zbl 0638.90055
[14] Freling, R.; Huisman, D.; Wagelmans, A., Models and algorithms for integration of vehicle and crew scheduling, Journal of Scheduling, 6, 1, 63-85, (2003) · Zbl 1154.90449
[15] Huisman, D.; Freling, R.; Wagelmans, A., Multiple-depot integrated vehicle and crew scheduling, Transportation Science, 39, 4, 491-502, (2005)
[16] Ibarra-Rojas, O.; Delgado, F.; Giesen, R.; Muñoz, J., Planning, operation, and control of bus transport systems: A literature review, Transportation Research Part B, 77, 38-75, (2015)
[17] Jourdan, L.; Basseur, M.; Talbi, E.-G., Hybridizing exact methods and metaheuristics: A taxonomy, European Journal of Operational Research, 199, 620-629, (2009) · Zbl 1176.90499
[18] Laporte, G.; Musmanno, R.; Vocaturo, F., An adaptive large neighborhood search heuristic for the capacitated arc-routing problem with stochastic demands, Transportation Science, 44, 1, 125-135, (2010)
[19] Li, H.; Wang, Y.; Li, S.; Li, S., A column generation based hyper-heuristic to the bus driver scheduling problem, Discrete Dynamics in Nature and Society, 2015, 1-10, (2015)
[20] Li, J.; Kwan, R. S., A fuzzy genetic algorithm for driver scheduling, European Journal of Operational Research, 147, 334-344, (2003) · Zbl 1037.90528
[21] Lourenço, H. R.; Paixão, J. P.; Portugal, R., Multiobjective metaheuristics for the bus driver scheduling problem, Transportation Science, 35, 3, 331-343, (2001) · Zbl 1069.90530
[22] Lusby, R. M.; Schwierz, M.; Troels, M. R.; Larsen, J., An adaptive large neighborhood search procedure applied to the dynamic patient admission scheduling problem, Artificial Intelligence in Medicine, 74, 21-31, (2016)
[23] Ma, J.; Ceder, A. A.; Yang, Y.; Liu, T.; Guan, W., A case study of Beijing bus crew scheduling: a variable neighborhood-based approach, Journal of Advanced Transportation, 50, 4, 434-445, (2016)
[24] Mauri, G.; Lorena, L., A new hybrid heuristic for driver scheduling, International Journal of Hybrid Intelligent Systems, 4, 1, 39-47, (2007) · Zbl 1130.90023
[25] Muller, L. F.; Spoorendonk, S.; Pisinger, D., A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times, European Journal of Operational Research, 218, 614-623, (2012) · Zbl 1244.90170
[26] Pisinger, D.; Røpke, S., A general heuristic for vehicle routing problems, Computers & Operations Research, 34, 2403-2435, (2007) · Zbl 1144.90318
[27] Pisinger, D.; Røpke, S., Large neighborhood search, (Gendreau, M., Handbook of metaheuristics (2nd ed.), (2010), Springer), 399-420
[28] Portugal, R.; Lourenço, H. R.; Paixão, J. P., Driver scheduling problem modelling, Public Transport, 1, 2, 103-120, (2009)
[29] Røpke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40, 4, 455-472, (2006)
[30] Shaw, P., Using constraint programming and local search methods to solve vehicle routing problems, Proceedings of the 4th international conference on principles and practice of constraint programming, 417-431, (1998)
[31] Smith, B. M.; Wren, A., A bus crew scheduling system using a set covering formulation, Transportation Research Part A, 22, 2, 97-108, (1988)
[32] Wren, A.; Fores, S.; Kwan, A.; Kwan, R.; Parker, M.; Proll, L., A flexible system for scheduling drivers, Journal of Scheduling, 6, 437-455, (2003) · Zbl 1154.90502
[33] Yunes, T.; Moura, A.; de Souza, C., Hybrid column generation approaches for urban transit crew management problems, Transportation Science, 39, 2, 273-288, (2005)
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.