Models and Algorithms for Single-Depot Vehicle Scheduling

Freling, Richard; Wagelmans, Albert P. M.; Paixão, José M. Pinto
May 2001
Transportation Science;May2001, Vol. 35 Issue 2, p1
Academic Journal
Vehicle scheduling is the process of assigning vehicles to a set of predetermined trips with fixed starting and ending times, while minimizing capital and operating costs. This paper considers modeling, algorithmic, and computational aspects of the polynomially solvable case in which there is a single depot and vehicles are identical. A quasiassignment formulation is reviewed and an alternative asymmetric assignment formulation is given. The main contributions of the paper area new two-phase approach which is valid in the case of a special cost structure, an auction algorithm for the quasiassignment problem, a core-oriented approach, and an extensive computational study. New algorithms are compared with the most successful algorithms for the vehicle-scheduling problem, using both randomly generated and real-life data. The new algorithms show a significant performance improvement with respect to computation time. Such improvement can, for example, be very important when this particular vehicle-scheduling problem appears as a subproblem in more complex vehicle- and crew-scheduling problems.


Related Articles

  • An Exact Algorithm for the Simplified Multiple Depot Crew Scheduling Problem. Boschetti, M. A.; Mingozzi, A.; Ricciardelli, S. // Annals of Operations Research;Mar2004, Vol. 127 Issue 1-4, p177 

    The Multiple Depot Crew Scheduling Problem (MD-CSP) appears in public transit systems (e.g., airline, bus and railway industry) and consists of determining the optimal duties for a set of crews (or vehicles) split among several depots in order to cover a set of timetabled trips satisfying a...

  • Solving large multiple-depot multiple-vehicle-type bus scheduling problems in practice. Gintner, Vitali; Kliewer, Natalia; Suhl, Leena // OR Spectrum;Aug2005, Vol. 27 Issue 4, p507 

    We consider the multiple-depot multiple-vehicle-type scheduling problem (MDVSP) which arises in public transport bus companies and aims to assign buses to cover a given set of timetabled trips with consideration of practical requirements, such as multiple depots and vehicle types as well as...

  • Dispatching vehicles in a mega container terminal. Bish, Ebru; Chen, Frank; Leong, Yin; Nelson, Barry; Ng, Jonathan; Simchi-Levi, David // OR Spectrum;Aug2005, Vol. 27 Issue 4, p491 

    We consider a container terminal discharging and uploading containers to and from ships. The discharged containers are stored at prespecified storage locations in the terminal yard. Containers are moved between the ship area and the yard using a fleet of vehicles, each of which can carry one...

  • AN EXACT ALGORITHM FOR SOLVING A CAPACITATED LOCATION-ROUTING PROBLEM. Laporte, G.; Nobert, Y.; Arpin, D. // Annals of Operations Research;1986, Vol. 6 Issue 1-4, p293 

    In location-routing problems, the objective is to locate one or many depots within a set of sites (representing customer locations or cities) and to construct delivery routes from the selected depot or depots to the remaining sites at least system cost. The objective function is the sum of depot...

  • On the design and development of object-oriented scheduling systems. Pinedo, Michael; Yen, Benjamin P.-C. // Annals of Operations Research;1997, Vol. 70 Issue 1-4, p359 

    In this paper, we describe the architecture of an object-oriented scheduling system. First, a mathematical framework is presented that is based on set theory and graph theory. Then a number of basic as well as more specialized methods are defined which can be applied on the entities of any...

  • SEQUENCING OPERATIONS TO MINIMIZE IN-PROCESS INVENTORY COSTS. Gapp, William; Mankekar, P. S.; Mitten, L. G. // Management Science;Jan1965, Vol. 11 Issue 3, p476 

    A solution is presented for the problem of determining the sequence in which a set of manufacturing operations should be carried out in order to minimize in-process inventory costs while meeting a variety of technological constraints. Both strict precedence constraints and contiguity constraints...

  • BOUNDS FOR THE OPTIMAL SCHEDULING OF n JOBS ON m PROCESSORS. Eastman, W. L.; Even, S.; Isaacs, I. M. // Management Science;Nov64, Vol. 11 Issue 2, p268 

    The problem of scheduling n jobs on m identical processors has been introduced by R. McNaughton, but as yet no efficient algorithm has been found for determining an optimal sequencing of jobs. In this paper lower and upper bounds are given for the cost of an optimal schedule. Since the two...

  • Scheduling Trains and Containers with Due Dates and Dynamic Arrivals. Yano, Candace A.; Newman, Alexandra M. // Transportation Science;May2001, Vol. 35 Issue 2, p1 

    We consider the problem of scheduling trains and containers (or trucks and pallets) between a depot and a destination. Goods arrive at the depot dynamically over time and have distinct due dates at the destination. There is a fixed-charge transportation cost for each vehicle, and each vehicle...

  • Multiple-Depot Integrated Vehicle and Crew Scheduling. Huisman, Dennis; Freling, Richard; Wagelmans, Albert P. M. // Transportation Science;Nov2005, Vol. 39 Issue 4, p491 

    This paper presents two different models and algorithms for integrated vehicle and crew scheduling in the multiple-depot case. The algorithms are both based on a combination of column generation and Lagrangian relaxation. Furthermore, we compare those integrated approaches with each other and...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics