Routing with time constraints: IP formulation, algorithmic strategies and polynomial cases in graphs
DOI:
https://doi.org/10.5753/reic.2023.3425Keywords:
Problema de Roteamento de Veículos, Restrições temporais, Programação Linear InteiraAbstract
This research consisted of investigating the Vehicle Routing Problem (VRP) with time constraints, seeking to incorporate the dynamic characteristics of the express delivery logistics chain. Theoretical aspects of modeling and algorithmic strategies were explored. A formulation in Integer Linear Programming (ILP) was proposed for the VRPRDD, an adaptation of instances of Brazilian cities for the VRPTW and an analysis of polynomial cases of VRPs involving special classes of graphs, such as paths, stars, subdivided stars and trees. Dynamic programming algorithms and binary search were applied, and their runtime complexities were determined.
Downloads
References
Archetti, C., Feillet, D., and Speranza, M. G. (2015). Complexity of routing problems with release dates. European journal of operational research, 247(3):797–803.
Clementino, T., Rosas, J., de Freitas, R., and Uchoa, E. (2022a). Contribuições na logística de entrega urbana expressa de última milha usando grandes instâncias reais de cidades brasileiras. In Anais do III Workshop Brasileiro de Cidades Inteligentes, pages 1–12. SBC.
Clementino, T., Rosas, J., De Freitas, R., and Uchoa, E. (2022b). Solving real urban vrptw instances by applying a branch-cut-and-price via vrpsolver. In 2022 XVLIII Latin American Computer Conference (CLEI), pages 1–8. IEEE.
Desaulniers, G., Madsen, O. B., and Ropke, S. (2014). Chapter 5: The Vehicle Routing Problem with Time Windows, pages 119–159.
Loggi (2021). loggibud: Loggi benchmark for urban deliveries. https://github.com/loggi/loggibud.
Pessoa, A., Sadykov, R., Uchoa, E., and Vanderbeck, F. (2020). A generic exact solver for vehicle routing and related problems. Mathematical Programming, 183(1):483–523.
Reyes, D., Erera, A. L., and Savelsbergh, M. W. (2018). Complexity of routing problems with release dates and deadlines. European journal of operational research, 266(1):29–34.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2):254–265.
Sun, X., Li, K., and Li, W. (2022). The vehicle routing problem with release dates and flexible time windows. Engineering Optimization, 54(12):2123–2139.
Yang, W., Ke, L., Wang, D. Z., and Lam, J. S. L. (2021). A branch-price-and-cut algorithm for the vehicle routing problem with release and due dates. Transportation Research Part E: Logistics and Transportation Review, 145:102167.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Os autores
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
