This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Archetti, C. Articles by Savelsbergh, M.

The Trip Scheduling Problem

Department of Quantitative Methods, University of Brescia, 25122 Brescia, Italy
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
archetti{at}eco.unibs.it
mwps{at}isye.gatech.edu

The hours of service (HOS) regulations of the department of transportation severely restrict the set of feasible driver schedules. So much so that establishing whether a sequence of full truckload transportation requests, each with a dispatch window at the origin, can feasibly be executed by a driver is no longer a matter of simple forward simulation. We consider this problem and prove that the feasibility of a driver schedule can be checked in polynomial time by providing an O(n³) algorithm for establishing whether a sequence of full truckload transportation requests, each with a dispatch window at the origin, can be executed by a driver.

Key Words: truckload transportation; driver scheduling; hours of service; dispatch windows
History: Received: June 2007; revised: February 2008; accepted: March 2009.