The bus driver scheduling problem (BDSP) is one of the most important planning decision problems that public transportation companies must solve and that appear as an extremely complex part of the general transportation planning system. It is formulated as a minimization problem whose objective is to determine the minimum number of driver shifts, subject to a variety of rules and regulations that must be enforced, such as overspread and working time. In this article, a greedy randomized adaptive search procedure (GRASP) and a rollout heuristic for BDSP are proposed and tested. A new hybrid heuristic that combines GRASP and rollout is also proposed and tested. Computational results indicate that these randomized heuristics find near-optimal solutions.

A new meta-heuristic for the Bus Driver Scheduling Problem: GRASP combined with Rollout

FESTA, PAOLA;
2007

Abstract

The bus driver scheduling problem (BDSP) is one of the most important planning decision problems that public transportation companies must solve and that appear as an extremely complex part of the general transportation planning system. It is formulated as a minimization problem whose objective is to determine the minimum number of driver shifts, subject to a variety of rules and regulations that must be enforced, such as overspread and working time. In this article, a greedy randomized adaptive search procedure (GRASP) and a rollout heuristic for BDSP are proposed and tested. A new hybrid heuristic that combines GRASP and rollout is also proposed and tested. Computational results indicate that these randomized heuristics find near-optimal solutions.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/114067
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 5
social impact