The paper proposes a mathematical model and a heuristic solution for planning optimal pickup and delivery routes in drone operations. In the proposed system, the drone is synchronized with the docking station for a charge during pickup and delivery services within a definite set distance radius. The optimization model presented here minimizes the distance traveled by the drone to complete the scheduled services. It also ensures the optimal use of the drone’s battery capacity, ensuring the safe return of the drone without running out of battery during operations. The solution quality and the computational performance of the Mixed-Integer Linear Programming (MILP) model proved satisfactory in addressing a variety of problems. A real-world case study is conducted to enumerate the practical implications which will be of benefit to drone service providers in the field of logistics.
MurrayC. C.ChuA. G.The Flying Sidekick Traveling Salesman Problem: Optimization of Drone-Assisted Parcel Delivery. Transportation Research Part C: Emerging Technologies, Vol. 54, 2015, pp. 86–109.
2.
CarlssonJ. G.SongS.Coordinated Logistics with a Truck and a Drone. Management Science, Vol. 64, No. 9, 2018, pp. 4052–4069.
3.
Moshref-JavadiM.LeeS.WinkenbachM.Design and Evaluation of a Multi-Trip Delivery Model with Truck and Drones. Transportation Research Part E: Logistics and Transportation Review, Vol. 136, 2020, p. 101887.
4.
StolaroffJ. K.SamarasC.O’NeillE. R.LubersA.MitchellA. S.CeperleyD.Energy Use and Life Cycle Greenhouse Gas Emissions of Drones for Commercial Package Delivery. Nature Communications, Vol. 9, No. 1, 2018, pp. 1–13.
5.
KirschsteinT.Comparison of Energy Demands of Drone-Based and Ground-Based Parcel Delivery Services. Transportation Research Part D: Transport and Environment, Vol. 78, 2020, p. 102209.
ChauhanD.R.UnnikrishnanA.FigliozziM.BoylesS. D.Robust Maximum Coverage Facility Location Problem with Drones Considering Uncertainties in Battery Availability and Consumption. Transportation Research Record: Journal of the Transportation Research Board, 2020. 2675: 25–39.
HaQ.M.DevilleY.PhamQ. D.HaM. H.On the Min-Cost Traveling Salesman Problem with Drone. Transportation Research Part C: Emerging Technologies, Vol. 86, 2018, pp. 597–621.
11.
Moshref-JavadiM.HemmatiA.WinkenbachM.A Truck and Drones Model for Last-Mile Delivery: A Mathematical Model and Heuristic Approach. Applied Mathematical Modelling, Vol. 80, 2020, pp. 290–318.
12.
ArslanA. M.AgatzN.KroonL.ZuidwijkR.Crowdsourced Delivery—A Dynamic Pickup and Delivery Problem with Ad Hoc Drivers. Transportation Science, Vol. 53, No. 1, 2019, pp. 222–235.
13.
SextonT. R.BodinL. D.Optimizing Single Vehicle Many-To-Many Operations with Desired Delivery Times: I. Scheduling. Transportation Science, Vol. 19, No. 4, 1985, pp. 378–410.
14.
OmidshafieiS.Agha-mohammadiA. A.AmatoC.LiuS. Y.HowJ. P.VianJ. L.Health-Aware Multi-UAV Planning Using Decentralized Partially Observable Semi-Markov Decision Processes. AIAA Infotech@ Aerospace, 2016, p. 1407.
15.
KimY.GuD. W.PostlethwaiteI.Real-time optimal mission scheduling and flight path selection. IEEE Transactions on Automatic Control, Vol. 52, No. 6, 2007, 1119–1123.
16.
BalochG.GzaraF.Strategic Network Design for Parcel Delivery with Drones Under Competition. Transportation Science, Vol. 54, No. 1, 2020, pp. 204–228.
17.
Van der BruggenL. J. J.LenstraJ. K.SchuurP. C.Variable-Depth Search for the Single-Vehicle Pickup and Delivery Problem with Time Windows. Transportation Science, Vol. 27, No. 3, 1993, pp. 298–311.
18.
SteinD. M.An Asymptotic, Probabilistic Analysis of a Routing Problem. Mathematics of Operations Research, Vol. 3, No. 2, 1978, pp. 89–101.
19.
SavelsberghM. W.SolM. (1995). The General Pickup and Delivery Problem. Transportation Science, Vol. 29, No. 1, 1995, pp. 17–29.
20.
MosheiovG.The Travelling Salesman Problem with Pick-Up and Delivery. European Journal of Operational Research, Vol. 79, No. 2, 1994, pp. 299–310.
21.
XiangZ.ChuC.ChenH.A Fast Heuristic for Solving a Large-Scale Static Dial-a-Ride Problem Under Complex Constraints. European Journal of Operational Research, Vol. 174, No. 2, 2006, pp. 1117–1139.
22.
XuH.ChenZ. L.RajagopalS.ArunapuramS.Solving a Practical Pickup and Delivery Problem. Transportation Science, Vol. 37, No. 3, 2003, pp. 347–364.
23.
DorlingK.HeinrichsJ.MessierG. G.MagierowskiS.Vehicle Routing Problems for Drone Delivery. IEEE Transactions on Systems, Man, and Cybernetics: Systems, Vol. 47, No. 1, 2016, pp. 70–85.
24.
ChengC.AdulyasakY.RousseauL. M.Drone Routing with Energy Function: Formulation and Exact Algorithm. Transportation Research Part B: Methodological, Vol. 139, 2020, pp. 364–387.
25.
KimS. J.LimG. J.ChoJ.Drone Flight Scheduling Under Uncertainty on Battery Duration and Air Temperature. Computers & Industrial Engineering, Vol. 117, 2018, pp. 291–302.
26.
KimS. J.LimG. J.ChoJ.CôtéM. J.Drone-Aided healthcare services ices for Patients with Chronic Diseases in Rural Areas. Journal of Intelligent & Robotic Systems, vol. 88, No. 1, 2017, 163–180.
27.
LinC. K. Y.A Vehicle Routing Problem with Pickup and Delivery Time Windows, and Coordination of Transportable Resources. Computers & Operations Research, Vol. 38, No. 11, 2011, pp. 1596–1609.
28.
CoindreauM. A.GallayO.ZuffereyN.Vehicle Routing with Transportable Resources: Using Carpooling and Walking for On-Site Services. European Journal of Operational Research, Vol. 279, No. 3, 2019, pp. 996–1010.
29.
LinC. K. Y.A Cooperative Strategy for a Vehicle Routing Problem with Pickup and Delivery Time Windows. Computers & Industrial Engineering, Vol. 55, No. 4, 2008, pp. 766–782.
30.
SchneiderM.StengerA.GoekeD.The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations. Transportation Science, Vol. 48, No. 4, 2014, pp. 500–520.
31.
TaşD.Electric Vehicle Routing with Flexible Time Windows: A Column Generation Solution Approach. Transportation Letters, Vol. 13, No. 2, 2020, pp. 1–7.
32.
ZhangS.ChenM.ZhangW.ZhuangX.Fuzzy Optimization Model for Electric Vehicle Routing Problem with Time Windows and Recharging Stations. Expert Systems with Applications, Vol. 145, 2020, p. 113123.
33.
KeskinM.ÇatayB.Partial Recharge Strategies for the Electric Vehicle Routing Problem with Time Windows. Transportation Research Part C: Emerging Technologies, Vol. 65, 2016, pp. 111–127.
34.
KeskinM.LaporteG.ÇatayB.Electric Vehicle Routing Problem with Time-Dependent Waiting times at Recharging Stations. Computers & Operations Research, Vol. 107, 2019, pp. 77–94.
35.
JungJ.JayakrishnanR.High-Coverage Point-To-Point Transit: Electric Vehicle Operations. Transportation Research Record: Journal of the Transportation Research Board, 2287: 44–53.
36.
Gonzalez-RP.L.CancaD.Andrade-PinedaJ. L.CalleM.Leon-BlancoJ. M.Truck-Drone Team Logistics: A Heuristic Approach to Multi-Drop Route Planning. Transportation Research Part C: Emerging Technologies, Vol. 114, 2020, pp. 657–680.
37.
MurrayC. C.RajR.The Multiple Flying Sidekicks Traveling Salesman Problem: Parcel Delivery with Multiple Drones. Transportation Research Part C: Emerging Technologies, Vol. 110, 2020, pp. 368–398.
38.
PuglieseL. D. P.GuerrieroF.MacrinaG.Using Drones for Parcels Delivery Process. Procedia Manufacturing, Vol. 42, 2020, pp. 488–497.
39.
DayarianI.SavelsberghM.ClarkeJ. P.Same-Day Delivery with Drone Resupply. Transportation Science, Vol. 54, No. 1, 2020, pp. 229–249.
40.
PoikonenS.GoldenB.WasilE. A.A Branch-and-Bound Approach to the Traveling Salesman Problem with a Drone. Informs Journal on Computing, Vol. 31, No. 2, 2019, pp. 335–346.
41.
AgatzN.BoumanP.SchmidtM.Optimization Approaches for the Traveling Salesman Problem with drone. Transportation Science, Vol. 52, No. 4, 2018, pp. 965–981.
42.
BoumanP.AgatzN.SchmidtM.Dynamic Programming Approaches for the Traveling Salesman Problem with Drone. Networks, Vol. 72, No. 4, 2018, pp. 528–542.
43.
KimS.MoonI.Traveling Salesman Problem with a Drone Station. IEEE Transactions on Systems, Man, and Cybernetics: Systems, Vol. 49, No. 1, 2018, pp. 42–52.
44.
KitjacharoenchaiP.VentrescaM.Moshref-JavadiM.LeeS.TanchocoJ. M.BruneseP. A.Multiple Traveling Salesman Problem with Drones: Mathematical Model and Heuristic Approach. Computers & Industrial Engineering, Vol. 129, 2019, pp. 14–30.
45.
HaQ. M.DevilleY.PhamQ. D.HàM. H.A Hybrid Genetic Algorithm for the Traveling Salesman Problem with Drone. Journal of Heuristics, Vol. 26, No. 2, 2020, pp. 219–247.
46.
OttoA.AgatzN.CampbellJ.GoldenB.PeschE.Optimization Approaches for Civil Applications of Unmanned Aerial Vehicles (UAVs) or Aerial Drones: A Survey. Networks, Vol. 72, No. 4, 2018, pp. 411–458.
47.
Manitta, S. U.S. Patent Application No. 14/793,708. 2016.
48.
LuoZ.LiuZ.ShiJ.A Two-Echelon Cooperated Routing Problem for A Ground Vehicle and Its Carried Unmanned Aerial Vehicle. Sensors, Vol. 17, No. 5, 2017, p. 1144.
49.
SalamaM.SrinivasS.Joint Optimization of Customer Location Clustering and Drone-Based Routing for Last-Mile Deliveries. Transportation Research Part C: Emerging Technologies, Vol. 114, 2020, pp. 620–642.
SundarK.RathinamS.Algorithms for Routing an Unmanned Aerial Vehicle in the Presence of Refueling Depots. IEEE Transactions on Automation Science and Engineering, Vol. 11, No. (1), 2013, pp. 287–294.
56.
KimS. J.LimG. J.Drone-Aided Border Surveillance with an Electrification Line Battery Charging System. Journal of Intelligent & Robotic Systems, Vol. 92, No. (3–4), 2018, pp. 657–670.
57.
HongI.KubyM.MurrayA. T.A Range-Restricted Recharging Station Coverage Model for Drone Delivery Service Planning. Transportation Research Part C: Emerging Technologies, Vol. 90, 2018, pp. 198–212.
58.
Otero ArenzanaA.Escribano MaciasJ. J.AngeloudisP.Design of Hospital Delivery Networks Using Unmanned Aerial Vehicles. Transportation Research Record: Journal of the Transportation Research Board, 2020, 2674: 405–418.
59.
Van BrummelenG.Heavenly Mathematics: The Forgotten Art of Spherical Trigonometry. Princeton University Press, 2012.
