A matheuristic for the driver scheduling problem with staff cars

Shyam S.G. Perumal*, Jesper Larsen, Richard M. Lusby, Morten Riis, Kasper S. Sørensen

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

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.
Original languageEnglish
JournalEuropean Journal of Operational Research
Volume275
Issue number1
Pages (from-to)280-294
ISSN0377-2217
DOIs
Publication statusPublished - 2019

Keywords

  • Transportation
  • Driver scheduling problem
  • Heuristics

Cite this

@article{6f8b959f5d8a4fad9f1d8f43bf90176e,
title = "A matheuristic for the driver scheduling problem with staff cars",
abstract = "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.",
keywords = "Transportation, Driver scheduling problem, Heuristics",
author = "Perumal, {Shyam S.G.} and Jesper Larsen and Lusby, {Richard M.} and Morten Riis and S{\o}rensen, {Kasper S.}",
year = "2019",
doi = "10.1016/j.ejor.2018.11.011",
language = "English",
volume = "275",
pages = "280--294",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "1",

}

A matheuristic for the driver scheduling problem with staff cars. / Perumal, Shyam S.G.; Larsen, Jesper; Lusby, Richard M.; Riis, Morten; Sørensen, Kasper S.

In: European Journal of Operational Research, Vol. 275, No. 1, 2019, p. 280-294.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - A matheuristic for the driver scheduling problem with staff cars

AU - Perumal, Shyam S.G.

AU - Larsen, Jesper

AU - Lusby, Richard M.

AU - Riis, Morten

AU - Sørensen, Kasper S.

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Transportation

KW - Driver scheduling problem

KW - Heuristics

U2 - 10.1016/j.ejor.2018.11.011

DO - 10.1016/j.ejor.2018.11.011

M3 - Journal article

VL - 275

SP - 280

EP - 294

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -