An Exact Algorithm for Heterogeneous Drone-Truck Routing Problem

References

• Agatz N, Bouman P, Schmidt M (2018) Optimization approaches for the traveling salesman problem with drone. Transportation Sci. 52(4):965–981.Link, Google Scholar
• Augerat P (1995) Approche polyèdrale du problème de tournées de véhicules. Ph.D. thesis, Institut National Polytechnique de Grenoble-INPG.Google Scholar
• Balakrishnan A, Magnanti TL, Wong RT (1995) A decomposition algorithm for local access telecommunications network expansion planning. Oper. Res. 43(1):58–76.Link, Google Scholar
• Bektas T (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3):209–219.Crossref, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4:238–252.Crossref, Google Scholar
• Boysen N, Briskorn D, Fedtke S, Schwerdfeger S (2018) Drone delivery from trucks: Drone scheduling for given truck routes. Networks 72(4):506–527.Crossref, Google Scholar
• Bürkle A, Essendorfer B (2010) Maritime surveillance with integrated systems. 2010 Internat. WaterSide Security Conf. (IEEE, Piscataway, NJ), 1–8.Google Scholar
• Cattaruzza D, Absi N, Feillet D, Vidal T (2014) A memetic algorithm for the multi trip vehicle routing problem. Eur. J. Oper. Res. 236(3):833–848.Crossref, Google Scholar
• Cheng C, Adulyasak Y, Rousseau LM (2018) Formulations and exact algorithms for drone routing problem. Technical Report. CIRRELT-2018-31, CIRRELT .Google Scholar
• Cheng C, Adulyasak Y, Rousseau LM, Sim M (2020) Robust drone delivery with weather information. http://www.optimization-online.org/DB_HTML/2020/07/7897.html.Google Scholar
• Corréa AI, Langevin A, Rousseau LM (2007) Scheduling and routing of automated guided vehicles: A hybrid approach. Comput. Oper. Res. 34(6):1688–1707.Crossref, Google Scholar
• CPLEX-User’s-Manual (1987) IBM ILOG CPLEX Optimization Studio. Version. 12:1987–2020.Google Scholar
• Cuda R, Guastaroba G, Speranza MG (2015) A survey on two-echelon routing problems. Comput. Oper. Res. 55:185–199.Crossref, Google Scholar
• Daknama R, Kraus E (2017) Vehicle routing with drones. Preprint submitted May 18, https://arxiv.org/abs/1705.06431.Google Scholar
• Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management Sci. 6(1):80–91.Link, Google Scholar
• Dell’Amico M, Montemanni R, Novellani S (2020) Matheuristic algorithms for the parallel drone scheduling traveling salesman problem. Ann. Oper. Res. 289:211–226.Crossref, Google Scholar
• DHL (2014) DHL parcelcopter launches initial operations for research purposes. Accessed December 10, 2020, https://www.dhl.com/en/press/releases/releases_2014/group/dhl_parcelcopter_launches_initial_operations_for_research_purposes.html.Google Scholar
• Drexl M, Schneider M (2015) A survey of variants and extensions of the location-routing problem. Eur. J. Oper. Res. 241(2):283–308.Crossref, Google Scholar
• Errico F, Crainic TG, Malucelli F, Nonato M (2017) A Benders decomposition approach for the symmetric TSP with generalized latency arising in the design of semiflexible transit systems. Transportation Sci. 51(2):706–722.Link, Google Scholar
• Flammini F, Naddei R, Pragliola C, Smarra G (2016) Toward automated drone surveillance in railways: State-of-the-art and future directions. Internat. Conf. Adv. Concepts Intelligent Vision Systems (Springer), 336–348.Google Scholar
• Gaba F, Winkenbach M (2020) A systems-level technology policy analysis of the truck-and-drone cooperative delivery vehicle system. Working paper, MIT Center for Transportation & Logistics, Cambridge, MA.Google Scholar
• Gendreau M, Laporte G, Séguin R (1995) An exact algorithm for the vehicle routing problem with stochastic demands and customers. Transportation Sci. 29(2):143–155.Link, Google Scholar
• Gendreau M, Laporte G, Séguin R (1996) Stochastic vehicle routing. Eur. J. Oper. Res. 88(1):3–12.Crossref, Google Scholar
• Ha QM, Deville Y, Pham QD, Ha MH (2018) On the min-cost traveling salesman problem with drone. Transportation Res. Part C: Emerging Tech. 86:597–621.Crossref, Google Scholar
• Hooker JN (2007) Planning and scheduling by logic-based Benders decomposition. Oper. Res. 55(3):588–602.Link, Google Scholar
• Hooker JN, Ottosson G (2003) Logic-based Benders decomposition. Math. Programming 96(1):33–60.Crossref, Google Scholar
• Infanger G (1992) Monte Carlo (importance) sampling within a Benders decomposition algorithm for stochastic linear programs. Ann. Oper. Res. 39(1):69–95.Crossref, Google Scholar
• Johnson DS, Garey MR (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (WH Freeman, New York).Google Scholar
• Jones T (2017) International Commercial Drone Regulation and Drone Delivery Services (Rand Corporation, Santa Monica, CA).Google Scholar
• Kim S, Moon I (2019) Traveling salesman problem with a drone station. IEEE Trans. Systems Man Cybernetic Systems 49(1):42–52.Crossref, Google Scholar
• Kitjacharoenchai P, Ventresca M, Moshref-Javadi M, Lee S, Tanchoco JM, Brunese PA (2019) Multiple traveling salesman problem with drones: Mathematical model and heuristic approach. Comput. Indust Engrg. 129:14–30.Crossref, Google Scholar
• Laporte G, Louveaux FV (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Oper. Res. Lett. 13(3):133–142.Crossref, Google Scholar
• Laporte G, Louveaux FV, Van Hamme L (2002) An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Oper. Res. 50(3):415–423.Link, Google Scholar
• Laporte G, Nickel S, da Gama F, eds. (2019) Location Science (Springer, Cham, Switzerland).Google Scholar
• Lee C, Han J (2017) Benders-and-Price approach for electric vehicle charging station location problem under probabilistic travel range. Transportation Res. Part B: Methodological 106:130–152.Crossref, Google Scholar
• Lee C, Lee K, Park S (2013) Benders decomposition approach for the robust network design problem with flow bifurcations. Networks 62(1):1–16.Crossref, Google Scholar
• Lithia F (2017) UPS tests residential delivery via drone launched from atop package car. https://www.globenewswire.com/news-release/2017/02/21/925955/0/en/UPS-Tests-Residential-Delivery-Via-Drone-Launched-From-Atop-Package-Car.html.Google Scholar
• Liu Rl, Zhang Zj, Jiao Yf, Yang Ch, Zhang Wj (2019) Study on flight performance of propeller-driven UAV. Internat. J. Aerospace Engrg., ePub ahead of print April 21, http://dx.doi.org/10.1155/2019/6282451.Google Scholar
• Macrina G, Pugliese LDP, Guerriero F, Laporte G (2020) Drone-aided routing: A literature review. Transportation Res. Part C: Emerging Tech. 120:102762.Google Scholar
• Malandraki C, Daskin MS (1992) Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms. Transportation Sci. 26(3):185–200.Link, Google Scholar
• Martello S, Hoboken PT (1990) Knapsack Problems (Wiley-Interscience, NJ).Google Scholar
• McKinnon A, Browne M, Whiteing A, Piecyk M (2015) Green Logistics: Improving the Environmental Sustainability of Logistics (Kogan Page Publishers, London).Google Scholar
• Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulation of traveling salesman problems. J. ACM 7(4):326–329.Crossref, Google Scholar
• Mogili UR, Deepak B (2018) Review on application of drone systems in precision agriculture. Procedia Comput. Sci. 133:502–509.Crossref, Google Scholar
• Murray CC, Chu AG (2015) The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Res. Part C: Emerging Tech. 54:86–109.Crossref, Google Scholar
• Nielsen SS, Zenios SA (1997) Scalable parallel Benders decomposition for stochastic linear programming. Parallel Comput. 23(8):1069–1088.Crossref, Google Scholar
• Ordóñez F (2010) Robust vehicle routing. Hasenbein JJ, ed. Risk and Optimization in an Uncertain World, INFORMS Tutorials on Operations Research (INFORMS, Catonsville, MD), 153–178.Link, Google Scholar
• Otto A, Agatz N, Campbell J, Golden B, Pesch E (2018) Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey. Networks 72(4):411–458.Crossref, Google Scholar
• Paradiso R, Roberti R, Laganá D, Dullaert W (2020) An exact solution framework for multitrip vehicle-routing problems with time windows. Oper. Res. 68(1):180–198.Google Scholar
• Parragh SN, Doerner KF, Hartl RF (2008) A survey on pickup and delivery problems. J. Betriebswirtschaft 58(1):21–51.Crossref, Google Scholar
• Perboli G, Tadei R, Vigo D (2011) The two-echelon capacitated vehicle routing problem: Models and math-based heuristics. Transportation Sci. 45(3):364–380.Link, Google Scholar
• Poikonen S, Golden B (2019) Multi-visit drone routing problem. Comput. Oper. Res. 113:104802.Google Scholar
• Popper B (2015) Drones could make Amazon’s dream of free delivery profitable. http://www.theverge.com/2015/6/3/8719659/amazon-prime-air-drone-delivery-profit-free-shipping-small-items.Google Scholar
• Rahmaniani R, Ahmed S, Crainic TG, Gendreau M, Rei W (2020) The Benders dual decomposition method. Oper. Res. 68(3):878–895.Link, Google Scholar
• Rosenkrantz DJ, Stearns RE, Lewis PM II (1977) An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6(3):563–581.Crossref, Google Scholar
• Roshanaei V, Luong C, Aleman DM, Urbach D (2017) Propagating logic-based Benders’ decomposition approaches for distributed operating room scheduling. Eur. J. Oper. Res. 257(2):439–455.Crossref, Google Scholar
• Russell RA (1977) An effective heuristic for the m-tour traveling salesman problem with some side conditions. Oper. Res. 25(3):517–524.Link, Google Scholar
• Sacramento D, Pisinger D, Ropke S (2019) An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transportation Res. Part C: Emerging Tech. 102:289–315.Crossref, Google Scholar
• Savelsbergh MW, Sol M (1995) The general pickup and delivery problem. Transportation Sci. 29(1):17–29.Link, Google Scholar
• Schermer D, Moeini M, Wendt O (2019) The traveling salesman drone station location problem. World Congress on Global Optimization (Springer, Cham, Switzerland), 1129–1138.Google Scholar
• Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2):166–324.Link, Google Scholar
• Staudt CL, Sazonovs A, Meyerhenke H (2016) Networkit: A tool suite for large-scale complex network analysis. Network Sci. 4(4):508–530.Crossref, Google Scholar
• Sungur I, Ordónez F, Dessouky M (2008) A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Trans. 40(5):509–523.Crossref, Google Scholar
• Taccari L (2016) Integer programming formulations for the elementary shortest path problem. Eur. J. Oper. Res. 252(1):122–130.Crossref, Google Scholar
• Toth P, Vigo D (2002) The Vehicle Routing Problem (SIAM, Philadelphia).Crossref, Google Scholar
• Tseng CM, Chau CK, Elbassioni KM, Khonji M (2017) Flight tour planning with recharging optimization for battery-operated autonomous drones. Preprint, submitted March 29, https://arxiv.org/abs/1703.10049v1.Google Scholar
• Vásquez SA, Angulo G, Klapp MA (2020) An exact solution method for the TSP with drone based on decomposition. Comput. Oper. Res. 127:105127.Google Scholar
• Vidová H, Babčanová D, Witkowski K, Saniuk S (2012) Logistics and its environmental impacts. 7th Internat. Sci. Conf. Bus. Management, 1007–1014.Google Scholar
• Yurek EE, Ozmutlu HC (2018) A decomposition-based iterative optimization algorithm for traveling salesman problem with drone. Transportation Res. Part C: Emerging Tech. 91:249–262.Crossref, Google Scholar