Minimizing customers’ waiting time in a vehicle routing problem with unit demands

In this paper we study a new variant of the unit demand vehicle routing problem with the aim of minimizing the sum of customers waiting times to receive service. These kinds of problems are relevant in applications where the customers’ waiting time is essential or is more important than the vehicles’ travel time. We modify a known formulation for the multiple traveling salesman problem adapting it to the addressed problem. The derived mixed integer formulation is able to solve to optimality instances up to 40 nodes. We also develop a metaheuristic algorithm based on Iterated Greedy approach. We implement two variants of the metaheuristic algorithm using two different strategies in the constructive phase. For instances up to 40 nodes the proposed algorithms found almost all the optimal solutions and outperformed the results obtained by the formulation for instances with unknown optimal solution. In general, both versions of the metaheuristic algorithm are very fast and have a good performance too for instances ranging from 50 to 100 nodes.