An integrated algorithm for shift scheduling problems for local public transport companies

Claudio Ciancio, Demetrio Laganà, Roberto Musmanno and Francesco Santoro

Omega, 2018, vol. 75, issue C, 139-153

Abstract: This paper presents an integrated approach to solve two shift scheduling problems for local public bus companies: the first one aims at finding a schedule for vehicles, given a set of rides to do; the second one aims at assigning drivers to vehicle schedules. The first subproblem to be faced is the Multiple Depot Vehicle Scheduling Problem that is known to be NP-hard. Therefore, heuristic algorithms are needed to find feasible solutions for real-life instances. In this work a starting solution for this problem is found by using a greedy algorithm. This solution is then improved by a simulated annealing strategy that exploits several local search techniques. The second problem to deal with is the Crew Scheduling Problem where each trip is assigned to a driver. This problem is still NP-Hard. In this paper an initial solution for the Crew Scheduling Problem is firstly found with a classical sequential approach. This solution is then modified by changing the allocation of trips on vehicles in order to minimize the combined objective function. Both the problems have been modeled taking into account as more real-world constraints as possible. Several constraints take into account the European Union restrictions related to how the driver shifts must be composed. The proposed problem is different from the ones presented in the literature, as the mathematical model, and the related algorithm, are designed based on real world-requirements. Computational results have been carried out on large real-word instances. The results show that the proposed algorithm is able to find quickly good solutions within a limited computational time.

Keywords: Vehicle scheduling; Crew scheduling; Simulated annealing; Local search (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048316304789
Full text for ScienceDirect subscribers only

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:eee:jomega:v:75:y:2018:i:c:p:139-153

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2017.02.007

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().