Ir al contenido

Documat

Reoptimisation strategies for dynamic vehicle routing problems with proximity‑dependent nodes

  • Tiria Andersen [1] ; Shaun Belward [1] ; Mangalam Sankupellay [1] ; Trina Myers [2] ; Carla Chen [1]
    1. [1] James Cook University

      James Cook University

      Australia

    2. [2] Queensland University of Technology

      Queensland University of Technology

      Australia

  • Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 32, Nº. 1, 2024, págs. 1-21
  • Idioma: inglés
  • DOI: 10.1007/s11750-023-00656-6
  • Enlaces
  • Resumen

    • Autonomous vehicles create new opportunities as well as new challenges to dynamic vehicle routing. The introduction of autonomous vehicles as information-collecting agents results in scenarios, where dynamic nodes are found by proximity. This paper presents a novel dynamic vehicle-routing problem variant with proximitydependent nodes. Here, we introduced a novel variable, detectability, which determines whether a proximal dynamic node will be detected, based on the sight radius of the vehicle. The problem considered is motivated by autonomous weed-spraying vehicles in large agricultural operations. This work is generalisable to many other autonomous vehicle applications. The frst step to crafting a solution approach for the problem is to decide when reoptimisation should be triggered. Two reoptimisation trigger strategies are considered—exogenous and endogenous. Computational experiments compared the strategies for both the classical dynamic vehicle routing problem as well as the introduced variant. Experiments used extensive standardised vehicle-routing problem benchmarks with varying degrees of dynamism and geographical node distributions. The results showed that for both the classical problem and the novel variant, an endogenous trigger strategy is better in most cases, while an exogenous trigger strategy is only suitable when both detectability and dynamism are low. Furthermore, the optimal level of detectability was shown to be dependent on the combination of trigger, degree of dynamism, and geographical node distribution, meaning practitioners may determine the required detectability based on the attributes of their specifc problem.

  • Referencias bibliográficas
    • Akaike H (1974) A new look at the statistical model identifcation. IEEE Trans Autom Control 19(6):716–723. https://doi.org/10.1109/TAC.1974.1100705...
    • Al-Kanj L, Powell WB, Bouzaiene-Ayari B (2016) The information-collecting vehicle routing problem: stochastic optimization for emergency storm...
    • Bofey B, García FRF, Laporte G, Mesa JA, Pelegrín BP (1995) Multiobjective routing problems. Top 3(2):167–220. https://doi.org/10.1007/BF02568585...
    • Boysen N, Schwerdfeger S, Weidinger F (2018) Scheduling last-mile deliveries with truck-based autonomous robots. Eur J Oper Res 271(3):1085–1099....
    • Braekers K, Ramaekers K, Van Nieuwenhuyse I (2016) The vehicle routing problem: state of the art classifcation and review. Comput Ind Eng...
    • Bsaybes S, Quilliot A, Wagler AK (2019) Fleet management for autonomous vehicles using fows in time-expanded networks. Top 27(2):288–311....
    • Chen C, Demir E, Huang Y (2021) An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery...
    • Dror M, Laporte G, Trudeau P (1989) Vehicle routing with stochastic demands: properties and solution frameworks. Transp Sci 23(3):166–176....
    • Eglese R, Zambirinis S (2018) Disruption management in vehicle routing and scheduling for road freight transport: a review. Top 26(1):1–17....
    • Ferrucci F (2013) Pro-active dynamic vehicle routing: real-time control and request-forecasting approaches to improve customer service, 1st...
    • Ferrucci F, Bock S (2015) A general approach for controlling vehicle en-route diversions in dynamic vehicle routing problems. Transp Res Part...
    • Ferrucci F, Bock S, Gendreau M (2013) A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery...
    • Gendreau M, Guertin F, Potvin JY, Taillard É (1999) Parallel Tabu search for real-time vehicle routing and dispatching. Transp Sci 33(4):381–390....
    • Gendreau M, Jabali O, Rei W (2016) Future research directions in stochastic vehicle routing. Transp Sci 50(4):1163–1173
    • Hyland M, Mahmassani HS (2017) Dynamic autonomous vehicle feet operations: optimization-based strategies to assign AVs to immediate traveler...
    • Ichoua S, Gendreau M, Potvin JY (2000) Diversion issues in real-time vehicle dispatching. Transp Sci 34(4). https://doi.org/10.1287/trsc.34.4.426.12325...
    • Karasakal O (2016) Minisum and maximin aerial surveillance over disjoint rectangles. Top 24(3):705– 724. https://doi.org/10.1007/s11750-016-0416-1...
    • Larsen A (2000) The dynamic vehicle routing problem, Phd. Technical University of Denmark
    • Larsen A, Madsen OBG, Solomon MM (2007) Classifcation of dynamic vehicle routing systems. Springer, Boston, pp 19–40. https://doi.org/10.1007/978-0-387-71722-7_2...
    • Lorini S, Potvin JY, Zuferey N (2011) Online vehicle routing and scheduling with dynamic travel times. Comput Oper Res 38(7):1086–1090. https://doi.org/10.1016/j.cor.2010.10.019...
    • Lund K, Madsen OBG, Rygaard JM (1996) VRPs with varying degrees of dynamism. Tech. rep, Institute of Mathematical Modelling, Lyngby
    • Margolis JT, Song Y, Mason SJ (2022) A Markov decision process model on dynamic routing for target surveillance. Comput Oper Res 141:105699....
    • Moretti Branchini R, Amaral Armentano V, Løkketangen A (2009) Adaptive granular local search heuristic for a dynamic vehicle routing problem....
    • Pillac V, Gendreau M, Guéret C, Medaglia AL (2013) A review of dynamic vehicle routing problems. Eur J Oper Res 225(1):1–11. https://doi.org/10.1016/j.ejor.2012.08.015...
    • Poikonen S, Wang X, Golden BL (2017) The vehicle routing problem with drones: extended models and connections. Networks 70(1):34–43. https://doi.org/10.1002/net.21746...
    • Psaraftis HN (1995) Dynamic vehicle routing: status and prospects. Ann Oper Res 61:143–164
    • Psaraftis HN, Wen M, Kontovas CA (2016) Dynamic vehicle routing problems: three decades and counting. Networks 67:3–31. https://doi.org/10.1002/net.21628...
    • Regan AC, Mahmassani HS, Jaillet P (1998) Evaluation of dynamic feet management systems simulation framework. Transp Res Rec 1645(1645):176–184....
    • Ritzinger U, Puchinger J, Hartl RF (2016) A survey on dynamic and stochastic vehicle routing problems. Int J Prod Res 54(1):215–231. https://doi.org/10.1080/00207543.2015.1043403...
    • Savelsbergh MWP, Van Woensel T (2016) 50th anniversary invited article-city logistics: challenges and opportunities. Transp Sci 50(2):579–590....
    • Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265. https://doi.org/10.1287/opre.35.2.254...
    • Thomas BW (2011) Dynamic vehicle routing. In: Wiley Encyclopedia of Operations Research and Management Science. Wiley, Hoboken. https://doi.org/10.1002/9780470400531.eorms0278...
    • Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, Subramanian A (2017) New benchmark instances for the capacitated vehicle routing problem. Eur...
    • Ulmer MW, Heilig L, Voß S (2017) On the value and challenge of real-time information in dynamic dispatching of service vehicles. Bus Inf Syst...
    • Van Woensel T, Kerbache L, Peremans H, Vandaele N (2008) Vehicle routing with dynamic travel times: a queueing approach. Eur J Oper Res 186(3):990–1007....
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno