EUVIMEDEUVIMED entdecken
Crossref

A branch‐and‐price‐and‐cut algorithm for the truck‐drone routing problem with simultaneously delivery and pickup

Dongwei Li, Joshua Ignatius, Dujuan Wang, Yunqiang Yin, T.C.E. Cheng

Naval Research Logistics (NRL) · 2024-03 · 71 (2) · 241-285

DOI: 10.1002/nav.22151 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Naval Research Logistics (NRL), online erschienen am 20.09.2023. Verfasst von Dongwei Li und 4 weiteren Autor:innen. Die Arbeit wurde bisher 41-mal zitiert (Crossref) und nennt 58 Literaturangaben. Gefördert von: National Natural Science Foundation of China, National Social Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Increasing environmental concerns and e‐commerce has attracted a growing focus on reverse logistics that not only delivers some goods to customers but also picks up other goods from customers. To achieve cost‐efficient and fast deliveries, integrating drones into the delivery and pickup services provides a competitive advantage, which however increases the operational challenges. We consider a truck‐drone routing problem with simultaneous delivery and pickup, where each truck carries a set of heterogeneous drones. Each truck can simultaneously perform its own delivery and pickup, and serve as an intermediate movable depot from which multiple drones can be dispatched to serve customers when the truck arrives at a customer, and the truck must wait until all the drones return. The energy consumption of drones is considered during their flights. All the delivery services must be performed, whereas the pickup services are optional with certain rewards. The objective is to find the synthetic‐routes of the truck‐drone combinations so as to minimize the sum of the assignment cost and the transport cost of the trucks and drones minus the total pickup revenue. To solve the problem, we devise a tailored branch‐and‐price‐and‐cut algorithm incorporating a specialized two‐stage bidirectional labeling algorithm to solve the challenging pricing problem. To enhance the efficiency of the algorithm, we use the subset‐row inequalities to tighten the lower bound, and apply some heuristic pricing strategies to quickly solve the pricing problem. We perform extensive numerical studies to assess the performance of the developed algorithm, analyze the merit of the truck‐drone cooperative service mode over the truck‐only service mode and the superiority of the configuration with heterogeneous drones, and ascertain the impacts of the key model parameters to generate managerial insights. We also show how our model would perform should it be used for the medical supply delivery and pickup in Shenzhen, China.

Förderung

  • National Natural Science Foundation of China
  • National Social Science Foundation of China

Zitieren

APA

Li, D., Ignatius, J., Wang, D., Yin, Y., & Cheng, T. (2024). A branch‐and‐price‐and‐cut algorithm for the truck‐drone routing problem with simultaneously delivery and pickup. Naval Research Logistics (NRL), 71(2), 241-285. https://doi.org/10.1002/nav.22151

Vancouver

Li D, Ignatius J, Wang D, Yin Y, Cheng T. A branch‐and‐price‐and‐cut algorithm for the truck‐drone routing problem with simultaneously delivery and pickup. Naval Research Logistics (NRL). 2024;71(2):241-285. doi:10.1002/nav.22151

BibTeX
@article{Li2024,
  author = {Li, Dongwei and Ignatius, Joshua and Wang, Dujuan and Yin, Yunqiang and Cheng, T.C.E.},
  title = {A branch‐and‐price‐and‐cut algorithm for the truck‐drone routing problem with simultaneously delivery and pickup},
  journal = {Naval Research Logistics (NRL)},
  year = {2024},
  volume = {71},
  number = {2},
  pages = {241--285},
  doi = {10.1002/nav.22151}
}
Kostenlos starten →