In recent years, e-commerce has become increasingly popular, and consumers expect quick and affordable delivery, placing additional pressure on city logistics activities. An innovative approach is proposed to coordinate ground vehicles and drones for delivery services, which has gained tremendous attention from academia and logistic service providers. This paper introduces a variant of this problem: the two-echelon truck and drone routing problem, characterized by stochastic demand existence and soft time windows. A Markov chain is used to model the problem, and a linear mathematical model is presented. This work employs a hybrid large-neighborhood search approach. Numerous computational experiments are conducted to evaluate the performance of the proposed solution method, and the results demonstrate its efficacy.
EnthovenD.L.J.U., JargalsaikhanB., RoodbergenK.J., BroekandM.A.J. and SchrotenboerA.H., The two-echelon vehicle routing problem with covering options: City logistics with cargo bikes and parcel lockers, Computers and Operations Research (2020), doi: https://doi.org/10.1016/j.cor.2020.104919.
2.
AsadiA., PinkleyS.N. and MesM., A Markov decision process approach for managing medical drone deliveries, Expert Systems with Applications204 (2022), 117490. https://doi.org/10.1016/j.eswa.2022.117490.
3.
Moshref-JavadiM. and WinkenbachM., Applications and Research avenues for drone-based models in logistics: A classification and review, Expert Systems with Applications177(February) (2021), Article 114854. https://doi.org/10.1016/j.eswa.2021.114854.
4.
LuoZ., PoonM., ZhangZ., LiuZ. and LimA., The multi-visit traveling salesman problem with multi-drones, Transportation Research Part C: Emerging Technologies128 (2021), 103172, ISSN 0968-090X, https://doi.org/10.1016/j.trc.2021.103172.
5.
WangD., HuP., DuV., ZhouP., DengT. and HuM., Routing and scheduling for hybrid truck-drone collaborative parcel delivery with independent and truck-carried drones, IEEE Internet of Things Journal6(6) (2019), 10483–10495. doi: 10.1109/JIOT.2019.2939397.
6.
FreitasJ.C. and PennaP.H.V., A variable neighborhood search for flying sidekick traveling salesman problem, International Transactions in Operational Research00 (2019), 1–24, DOI: 10.1111/itor.12671
7.
ChenC., DemirE. and HuangY., An adaptive large-neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots, European Journal of Operational Research294 (2021), 1164–1180.
8.
MurrayC.C. and ChuA.G., The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery, Transportation Research Part C: Emerging Technologies54 (2015), 86–109, ISSN 0968-090X, https://doi.org/10.1016/j.trc.2015.03.005.
9.
JeongH.Y., SongB.D. and LeeS., Truck-drone hybrid delivery routing: Payload-energy dependency and No-Fly zones, International Journal of Production Economics214 (2019), 220–233, ISSN 0925-5273..
10.
MurrayC.C. and RajR., The multiple flying sidekicks travelingsalesman problem: Parcel delivery with multiple drones, Transportation Research Part C: Emerging Technologies110 (2020), 368–398, ISSN 0968-090X, https://doi.org/10.1016/j.trc.2019.11.003.
11.
RajR. and MurrayC., The multiple flying sidekicks traveling salesman problem with variable drone speeds, Transportation Research Part C: Emerging Technologies120 (2020), 102813, ISSN 0968-090X, https://doi.org/10.1016/j.trc.2020.102813.
12.
BoumanP., AgatzN. and SchmidtM., Dynamic programming approaches for the traveling salesman problem with drone, Networks72 (2018), 528–542. https://doi.org/10.1002/net.21864
13.
PoikonenS. and GoldenB., The mothership and drone routing problem, INFORMS Journal on Computing32(2) (2019), 249–262. https://doi.org/10.1287/ijoc.2018.0879
Moshref-JavadiM., LeeS. and WinkenbachM., Design and evaluation of a multi-trip delivery model with truck and drones Transportation Research Part E: LogisTransportation Research Part E: Logis, Transportation Research Part E: Logistics and TransportationReview136 (2020), 101887, ISSN 1366-5545, https://doi.org/10.1016/j.tre.2020.101887
16.
Moshref-JavadiM., HemmatiA. and WinkenbachM., A truck and drones model for last-mile delivery: a mathematical model and heuristic approach, Applied Mathematical Modelling (2019), doi: https://doi.org/10.1016/j.apm.2019.11.020
17.
SchermerD., MoeiniM. and WendtO., A matheuristic for the vehicle routing problem with drones and its variants, Transportation Research Part C: Emerging Technologies106 (2019), 166–204, ISSN 0968-090X, https://doi.org/10.1016/j.trc.2019.06.016.
18.
PoikonenS., GoldenB. and WasilE., A branch-and-bound approach to the traveling salesman problem with a drone, INFORMS Journal on Computing31(2) (2019), 335–346.
19.
LeeS.Y., HanS.R. and SongB.D., Simultaneous cooperation of Refrigerated Ground Vehicle (RGV) and Unmanned Aerial Vehicle (UAV) for rapid delivery with perishable food, Applied Mathematical Modelling106 (2022), 844–866. https://doi.org/10.1016/j.apm.2022.02.024.
20.
LuoZ., LioZ. and ShiJ., A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle, Sensors17 (2017), 1144; doi: 10.3390/s17051144.
21.
KarakA. and AbdelghanyK., The hybrid vehicle-drone routing problemfor pick-up and delivery services, Transportation Research Part C: Emerging Technologies102 (2019), 427–449, SSN 0968-090X, https://doi.org/10.1016/j.trc.2019.03.021.
22.
OyolaJ., ArntzenH. and WoodruffD.L., The stochastic vehicle routing problem, a literature review, part I: models, EURO Journal on Transportation and Logistics7(3) (2018), 193–221.
23.
LiuZ., LiX. and KhojandiA., The flying sidekick traveling salesman problem with stochastic travel time: A reinforcement learning approach, Transportation Research Part E: Logistics and Transportation Review164 (2022), 2022.
24.
GhelichiZ., GentiliM. and MirchandaniP.B., Drone logistics for uncertain demand of disaster-impacted populations, Transportation Research Part C: Emerging Technologies141 (2022), 103735.
25.
SawadsitangS., NiyatoD., TanP. and WangP., Joint ground and aerial package delivery services: a stochastic optimization approach, IEEE Transactions on Intelligent Transportation Systems20(6) (2019), 2241–2254.
26.
MathewN., SmithS.L. and WaslanderS.L., Planning paths for package delivery in heterogeneous multirobot teams, IEEE Transactionson Automation Science and Engineering12(4) (2015), 1298–1308, doi: 10.1109/TASE.2015.2461213.
27.
CarlssonJ.G. and SongS., Coordinated logistics with a truck and a drone, Management Science64(9) (2017), 4052–4069.
28.
ChangY.S. and LeeH.J., Optimal delivery routing with wider drone-delivery areas along a shorter truck-route, Expert Systems with Applications (2018), doi: 10.1016/j.eswa.2018.03.032.
29.
KitjacharoenchaiP., MinB. and LeeS., Two echelon vehicle routing problem with drones in last mile delivery, International Journal of Production Economics225 (2020), 107598, ISSN 0925-5273, https://doi.org/10.1016/j.ijpe.2019.107598.
30.
SacramentoD., PisingerD. and RopkeS., An adaptive large-neighborhood search metaheuristic for the vehicle routing problem with drones, Transportation Research Part C: Emerging Technologies102 (2019), 289–315.
31.
LiH., WangH., ChenJ. and BaiM., Two-echelon vehicle routing problem with time windows and mobile satellites, Transportation Research Part B: Methodological138 (2020), 179–201, ISSN 0191-2615, https://doi.org/10.1016/j.trb.2020.05.010.
32.
Pina-PardoJ.C., SilvaD.F. and SmithA.E., The traveling salesman problem with release dates and drone resupply, Computers & Operations Research129 (2021), 105170, ISSN 0305-0548, https://doi.org/10.1016/j.cor.2020.105170.
33.
Leon-BlancoJ.M., Gonzalez-RP.L., Andrade-PinedaJ.L., CancaD. and CalleM., A multi-agent approach to the truck multi-drone routing problem, Expert Systems with Applications195 (2022), 116604, ISSN 0957-4174, https://doi.org/10.1016/j.eswa.2022.116604.
34.
KyriakakisN.A., StamadianosT., MarinakiM. and MarinakisY., The electric vehicle routing problem with drones: An energy minimization approach for aerial deliveries, Cleaner Logistics and Supply Chain4 (2022), 100041, ISSN 2772-3909, https://doi.org/10.1016/j.clscn.2022.100041
