Exact Methods for the Multi-Trip Vehicle Routing Problem

The Multi-Trip Vehicle Routing Problem (MTVRP) is an extension of the Capacitated Vehicle Routing Problem (CVRP) where each vehicle is allowed to perform more routes during its working period. A route is a simple circuit visiting the depot and some customers and such that the total request of the customers served does not exceed the vehicle capacity. The cost (working time) of a route is defined as the sum of the travel costs (travel times) of the edges traversed. A schedule for a vehicle is a subset of routes having total working time not exceeding a maximum time, and visiting each customer at most once. The cost of a schedule is the sum of the costs of its routes. The objective of the MTVRP is to design a set of schedules of minimum total cost such that all customers are visited exactly once. In this work, we present two exact methods for the MTVRP using two different formulations. The computational results show that instances with up to 100 customers can be consistently solved to optimality.