Solving Dynamic Delivery Services Using Ant Colony Optimization

Martins, Miguel S. E.; Coito, Tiago; Firme, Bernardo; Viegas, Joaquim; Sousa, João M. C.; Figueiredo, João; Vieira, Susana M.

This article presents a model for courier services designed to guide a fleet of vehicles over a dynamic set of requests. Motivation for this problem comes from a real-world scenario in an ever-changing environment, where the time to solve such optimization problem is constrained instead of endlessly searching for the optimal solution. First, a hybrid method combining Ant Colony Optimization with Local Search is proposed, which is used to solve a given static instance. Then, a framework to handle and adapt to dynamic changes over time is defined. A new method pairing nearest neighbourhood search with subtractive clustering is proposed to improve initial solutions and accelerate the convergence of the optimization algorithm. Overall, the proposed strategy presents good results for the dynamic environment and is suitable to be applied on real-world scenarios.