The Parallel Drone Scheduling Traveling Salesman Problem with Collective Drones

References

• Afifi S, Dang D-C, Moukrim A (2016) Heuristic solutions for the vehicle routing problem with time windows and synchronized visits. Optim. Lett. 10(3):511–525.Crossref, Google Scholar
• Applegate D, Bixby R, Chvátal V, Cook W (2003) Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems. Math. Programming 97(1):91–153.Crossref, Google Scholar
• Blazewicz J, Drabowski M, Weglarz J (1986) Scheduling multiprocessor tasks to minimize schedule length. IEEE Trans. Comput. 35(5):389–393.Crossref, Google Scholar
• Boyle A (2016) Amazon seeks patent for system that links up drones to create a borg for deliveries. Accessed August 30, 2021, https://www.geekwire.com/2016/amazon-patent-collective-uav-borg-drones/.Google Scholar
• Breiman L, Friedman J, Stone CJ, Olshen RA (1984) Classification and Regression Trees (CRC Press, Boca Raton, FL).Google Scholar
• Chen Y, Baek D, Bocca A, Macii A, Macii E, Poncino M (2018) A case for a battery-aware model of drone energy consumption. 2018 IEEE Internat. Telecommunications Energy Conf. (INTELEC) (IEEE, Piscataway, NJ), 1–8.Google Scholar
• Dell’Amico M, Montemanni R, Novellani S (2020) Matheuristic algorithms for the parallel drone scheduling traveling salesman problem. Ann. Oper. Res. 289(2):211–226.Crossref, Google Scholar
• Dinh QT, Do DD, Hà MH (2021) Ants can solve the parallel drone scheduling traveling salesman problem. Proc. Genetic Evolutionary Comput. Conf. (Association for Computing Machinery, New York), 14–21.Google Scholar
• Doerffel D, Sharkh SA (2006) A critical review of using the Peukert equation for determining the remaining capacity of lead-acid and lithium-ion batteries. J. Power Sources 155(2):395–400.Crossref, Google Scholar
• Etherington D (2019) UPS gets FAA approval to operate an entire drone delivery airline. Accessed August 20, 2021, https://techcrunch.com/2019/10/01/ups-gets-faa-approval-to-operate-an-entire-drone-delivery-airline/.Google Scholar
• FFA (2019) Package delivery by drone (part 135). Accessed August 20, 2021, https://www.faa.gov/uas/advanced_operations/package_delivery_drone/.Google Scholar
• Grimault A, Bostel N, Lehuédé F (2017) An adaptive large neighborhood search for the full truckload pickup and delivery problem with resource synchronization. Comput. Oper. Res. 88:1–14.Crossref, Google Scholar
• Guglielmo C (2013) Turns out Amazon, touting drone delivery, does sell lots of products that weigh less than 5 pounds. Forbes (December 2), https://www.forbes.com/sites/connieguglielmo/2013/12/02/turns-out-amazon-touting-drone-delivery-does-sell-lots-of-products-that-weigh-less-than-5-pounds/?sh=189b914b455e.Google Scholar
• Hà MH, Nguyen TD, Duy TN, Pham HG, Do T, Rousseau L-M (2020) A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints. Comput. Oper. Res. 124:105085.Crossref, Google Scholar
• Khoufi I, Laouiti A, Adjih C (2019) A survey of recent extended variants of the traveling salesman and vehicle routing problems for unmanned aerial vehicles. Drones 3(3):66.Crossref, Google Scholar
• Kwok Y-K, Ahmad I (1999a) Benchmarking and comparison of the task graph scheduling algorithms. J. Parallel Distributed Comput. 59(3):381–422.Crossref, Google Scholar
• Kwok Y-K, Ahmad I (1999b) Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput. Surveys 31(4):406–471.Crossref, Google Scholar
• Liu R, Tao Y, Xie X (2019) An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits. Comput. Oper. Res. 101:250–262.Crossref, Google Scholar
• Liu Z, Sengupta R, Kurzhanskiy A (2017) A power consumption model for multi-rotor small unmanned aircraft systems. 2017 Internat. Conf. Unmanned Aircraft Systems (ICUAS) (IEEE, Piscataway, NJ), 310–315.Google Scholar
• López-Ibáñez M, Dubois-Lacoste J, Cáceres LP, Birattari M, Stützle T (2016) The irace package: Iterated racing for automatic algorithm configuration. Oper. Res. Perspect. 3:43–58.Crossref, Google Scholar
• Ma X (2018) Using Classification and Regression Trees: A Practical Primer (Information Age Publishing, Charlotte, NC).Google Scholar
• Macrina G, Di Puglia Pugliese L, Guerriero F, Laporte G (2020) Drone-aided routing: A literature review. Transportation Res. Part C Emerging Tech. 120:102762.Crossref, Google Scholar
• Mbiadou Saleu RG, Deroussi L, Feillet D, Grangeon N, Quilliot A (2018) An iterative two-step heuristic for the parallel drone scheduling traveling salesman problem. Networks 72(4):459–474.Crossref, Google Scholar
• McNabb M (2019) How Zipline became a $1.2 billion drone company. Accessed September 18, 2021, https://dronelife.com/2019/05/21/how-zipline-became-a-1-2-billion-drone-company/.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
• Murray CC, Raj R (2020) The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones. Transportation Res. Part C Emerging Tech. 110:368–398.Crossref, Google Scholar
• Nguyen MA, Pham T-HG, Hà MH, Pham M-T (2022) The min-cost parallel drone scheduling vehicle routing problem. Eur. J. Oper. Res. 299(3):910–930.Crossref, Google Scholar
• Paczan NM, Elzinga MJ, Hsieh R, Nguyen LK (2016) Collective unmanned aerial vehicle configurations. US Patent Application 14/626,376.Google Scholar
• Poikonen S, Golden B (2020) Multi-visit drone routing problem. Comput. Oper. Res. 113:104802.Crossref, Google Scholar
• Power Tech (2022) 12V lithium-ion battery pack – PowerBrick+. Accessed August 20, 2021, https://www.powertechsystems.eu/home/products/12v-lithium-battery-pack-powerbrick/.Google Scholar
• Premack R (2019) UPS just beat out Amazon, FedEx, and Uber to make America’s first revenue-generating drone delivery. Insider (March 26), https://www.businessinsider.com/ups-first-revenue-generating-drone-delivery-with-matternet-2019-3.Google Scholar
• Raj R, Murray C (2020) The multiple flying sidekicks traveling salesman problem with variable drone speeds. Transportation Res. Part C Emerging Tech. 120:102813.Crossref, Google Scholar
• Raj R, Lee D, Lee S, Walteros J, Murray C (2021) A branch-and-price approach for the parallel drone scheduling vehicle routing problem. Preprint, submitted July 8, http://dx.doi.org/10.2139/ssrn.3879710.Google Scholar
• Robert Y (2011) Task graph scheduling. Padua D, ed. Encyclopedia of Parallel Computing (Springer US, Boston), 2013–2025.Crossref, Google Scholar
• Rubin BF (2017) Amazon Prime air drone completes its first U.S. public delivery. CNET (March 24), https://www.cnet.com/news/amazon-prime-air-first-drone-delivery-us-public-sunscreen-mars/.Google Scholar
• Sanchez-Diaz I, Palacios-Argüello L, Levandi A, Mardberg J, Basso R (2020) A time-efficiency study of medium-duty trucks delivering in urban environments. Sustainability 12(1):425.Crossref, Google Scholar
• Schrimpf G, Schneider J, Stamm-Wilbrandt H, Dueck G (2000) Record breaking optimization results using the ruin and recreate principle. J. Comput. Phys. 159(2):139–171.Crossref, Google Scholar
• Shaw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. Maher M, Puget J-F, eds. Proc. 4th Internat. Conf. Principles Practice Constraint Programming (Springer, Berlin), 417–431.Google Scholar
• Sherr I (2020) UPS, Amazon delivery drones a step closer to reality with new US rules. CNET (December 29), https://www.cnet.com/news/ups-amazon-delivery-drones-a-step-closer-to-reality-with-new-us-rules/.Google Scholar
• Sinnen O (2007) Task Scheduling for Parallel Systems, vol. 60 (John Wiley & Sons, New York).Crossref, Google Scholar
• Terence P, Prince G (2020) How to visualize decision trees. Accessed August 3, 2021, https://explained.ai/decision-tree-viz/.Google Scholar
• Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, Subramanian A (2017) New benchmark instances for the capacitated vehicle routing problem. Eur. J. Oper. Res. 257(3):845–858.Crossref, Google Scholar
• U.S. Census Bureau (2015) Commodity flow survey: United States: 2012. Accessed August 20, 2020, https://www.census.gov/library/publications/2015/econ/ec12tcf-us.html.Google Scholar
• Weisberger M (2017) Amazon’s ‘mothership’: Retailer gets patent for mega-drone. Accessed August 30, 2021, https://www.livescience.com/57416-amazon-patents-flying-mega-drone.html.Google Scholar
• Whitley D (1989) The GENITOR algorithm and selection pressure: Why rank-based allocation of reproductive trials is best. Proc. Third Internat. Conf. Genetic Algorithms (Morgan Kaufmann Publishers Inc., San Francisco), 116–121.Google Scholar
• Zhang J, Campbell JF, Sweeney DC II, Hupman AC (2021) Energy consumption models for delivery drones: A comparison and assessment. Transportation Res. Part D Transport Environ. 90:102668.Crossref, Google Scholar