An Exact Algorithm for Combining Vehicle Trips

We consider a vehicle scheduling problem arising in freight transport systems 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.