Program > By author > Vigo Daniele

In this paper we study the Minimum Multiple Trip Vehicle Routing Problem (MMTVRP) introduced in Battarra et al, 2009. The MMTVRP is a variant of the Multi-Trip VRP with time windows, where different incompatible commodities need to be delivered to customers. Incompatible means that they cannot be transported together into the same vehicles. On the other side, vehicles can be loaded with all the commodities, meaning that subsequent trips made by the same vehicle can transport different commodities. The problem is strategic rather than operational since the size of the fleet needs to be minimized, breaking ties in favor of solutions with shorter travelled distance. We propose a simple and effective iterated local search (ILS) to face the problem. Solutions are encoded as permutations of customers and obtained by an adaptation of the split procedure (Prins, 2004). Results outperform those previously published in the literature.

A further analysis is conducted on the impact of introducing the multi trip aspect in fleet dimensioning problems. We run the ILS on instances proposed by Solomon, 1987, and on those proposed by Gehring and Homberger, 1999, allowing vehicles to perform several serving trips. Results are compared with the best known VRPTW solutions available in the literature. On some instances, less than half vehicles are needed to serve all the customers. Moreover, results analysis gives insights on when fleet size can likely be reduced by letting vehicles perform several serving trips.