A Combined Transportation and Scheduling Problem

We consider a problem in which a given good has to be delivered from some origins (say production plants), to some destinations (say nodes at which the transportation mode is changed, or simply customers), during a workday, by means of a given fleet of trucks, at minimum cost. For the purpose of solution the problem is split into two levels, where, at the first level, the decision concerns the planning of trips in order to deliver goods, while, at the second level, the vehicles needed to operate the trips have to be scheduled. The solution approach presented here is based on Lagrangean Decomposition and makes use of a new algorithm for the approximate solution of the Lagrangean Dual. Computational results from a set of real life problems are presented. Keywords: Lagrangean Relaxation; Optimisation; Transportation; Vehicle Scheduling Revised January 1996 1 This research has been supported by "Progetto Finalizzato Trasporti 2" of the Italian National Research Council (C.N.R.) and by Fon..