Publications of S. Ricciardelli

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  ALL, with author Ricciardelli S., in the category IASI Research Reports (or show them all):


IASI Research Report n. 354  (Previous    Next)


Bianco L., Mingozzi A., Navoni M., Ricciardelli S.

An exact algorithm for combining truck trips

ABSTRACT
We consider a vehicle scheduling problem arising in some freight transport system where a vehicle fleet of different classes, split among different depots, must be used to perform a set of trips over a time period horizon minimizing a given cost function. The set of trips must be partitioned in a number of disjoint sequences (called duties) and each duty must be assigned to a vehicle satisfying time window and vehicle-trip objection constraints. Moreover, a vehicle can perform only one duty and must return to the starting depot. This problem is an extension of a simpler problem known as Multiple Depot Vehicle Scheduling Problem (MD-VSP) that is NP hard. In this paper we formulate the problem as Set Partitioning Problem with side constraints (SPP) where each column is a feasible vehicle duty. We describe a procedure for computing a lower bound to the optimal cost by finding an heuristic solution of the dual of the linear relaxation of the SPP formulation, without generating the entire SPP matrix. The dual solution obtained and an upper bound to the optimal solution cost are used to reduce the number of variables in the SPP in such a way that the resulting SPP can be solved by a branch and bound algorithm. The computational results show that the proposed method can be used to solve large size problems.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -