Um Algoritmo Híbrido para o Problema de Roteamento de Veículos com Frota Heterogênea Robusto

• Carlos Neves UFPB
• Anand Subramanian UFPB
• Pedro Munari UFSCar

DOI: https://doi.org/10.5753/etc.2023.230923

Abstract

We address the Fleet Size and Mix Vehicle Routing Problem under demand uncertainty, which seeks an optimal fleet composition, as well as a set of routes with minimal cost. We treat the problem under the perspective of robust optimization by assuming that variations in customer demands belong to a well-defined uncertainty set. To solve the problem, we combine the Iterated Local Search algorithm with an exact Set Partitioning procedure. We also devise efficient data structures to perform local search efficiently. Computational experiments show that the proposed method is effective as we not only found the best known upper bound for most benchmark instances, but also improve existing upper bounds for some of them.

References

Ben-Tal, A. and Nemirovski, A. (1999). Robust solutions of uncertain linear programming. Operations Research Letters, 25:1–13.

Bertsimas, D. and Sim, M. (2004). The price of robustness. Operations Research, 52(1):35–53.

Golden, B., Assad, A., Levy, L., and Gheysens, F. (1984). The fleet size and mix vehicle routing problem. Computers & Operations Research, 11(1):49–66.

Lourenço, H. R., Martin, O. C., and Stützle, T. (2019). Iterated Local Search: Framework and Applications, pages 129–168. Springer International Publishing, Cham.

Penna, P. H. V., Subramanian, A., Ochi, L. S., Vidal, T., and Prins, C. (2019). A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet. Annals of Operations Research, 273(1):5–74.

Savelsbergh, M. W. P. (1985). Local search in routing problems with time windows. Annals of Operations Research, 4(1):285–305.

Subramanyam, A., Repoussis, P. P., and Gounaris, C. E. (2018). Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty. arXiv:1810.04348 [cs, math].

Subramanyam, A., Repoussis, P. P., and Gounaris, C. E. (2020). Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty. INFORMS Journal on Computing, 32(3):661–681.

Vidal, T., Crainic, T. G., Gendreau, M., and Prins, C. (2014). A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research, 234(3):658–673.