Ant Colony System for Dynamic Vehicle Routing Problem with Overtime

Traditionally, in a VRP the vehicles return to depot before the end of the working time. However, in reality several constraints can occur and prevent the vehicles from being at the depot on time. In the dynamic case, we are supposed to answer the requests the same day of their arrival. Nevertheless, it is not always easy to find a solution, which ensures the service while respecting the normal working time. Therefore, allowing the vehicle to use additional time to complete their service may be very useful especially if we have a large demand with a limited number of vehicles. In this context, this article proposes a mathematical modeling with an Ant Colony System (ACS) based approach to solve the dynamic vehicle routing problem (DVRP) multi-tours with overtime. To test the algorithm, we propose new data sets inspired from literature benchmarks. The competitiveness of the algorithm is proved on the classical DVRP.