Traveling salesman problem with drone under recharging policy

EŞ YÜREK E., Ozmutlu H. C.

COMPUTER COMMUNICATIONS, cilt.179, ss.35-49, 2021 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 179
  • Basım Tarihi: 2021
  • Doi Numarası: 10.1016/j.comcom.2021.07.013
  • Dergi Adı: COMPUTER COMMUNICATIONS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Social Sciences Citation Index (SSCI), Scopus, PASCAL, Aerospace Database, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, Library, Information Science & Technology Abstracts (LISTA), Metadex, Civil Engineering Abstracts
  • Sayfa Sayıları: ss.35-49
  • Bursa Uludağ Üniversitesi Adresli: Evet

Özet

The traveling salesman problem is one of the most studied problems in combinatorial optimization. An emerging variant of this problem, which is referred to as the traveling salesman problem with drone, focuses on deploying a drone and a delivery truck for last-mile delivery. This problem coordinates the truck and drone deliveries in both time and location because the drone requires the truck to refresh its battery and load the next customer's package on the drone. Previous studies assume that the drone battery is swapped with a new/fully recharged battery at the end of each drone flight. In contrast, this study investigates a flexible recharging policy. For this purpose, we develop a new mixed integer linear programming formulation into which remaining battery level consideration is incorporated. A computational study is provided to compare the recharging policy with the battery swapping policy in terms of delivery time. Due to the complexity of the problem, a heuristic approach is proposed to solve medium-sized instances.