EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

A new MILP formulation for the flying sidekick traveling salesman problem

Maurizio Boccia, Andrea Mancuso, Adriano Masone, Claudio Sterle

Networks · 2023-10 · 82 (3) · 254-276

DOI: 10.1002/net.22172 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Networks, online erschienen am 05.07.2023. Verfasst von Maurizio Boccia und 3 weiteren Autor:innen. Die Arbeit wurde bisher 29-mal zitiert (Crossref) und nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: Ministero dell'Università e della Ricerca.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Nowadays, truck‐and‐drone problems represent one of the most studied classes of vehicle routing problems. The Flying Sidekick Traveling Salesman Problem ( FS‐TSP ) is the first optimization problem defined in this class. Since its definition, several variants have been proposed differing for the side constraints related to the operating conditions and for the structure of the hybrid truck‐and‐drone delivery system. However, regardless the specific problem under investigation, determining the optimal solution of most of these routing problems is a very challenging task, due to the vehicle synchronization issue. On this basis, this work provides a new arc‐based integer linear programming formulation for the FS‐TSP . The solution of such formulation required the development of a branch‐and‐cut solution approach based on new families of valid inequalities and variable fixing strategies. We tested the proposed approach on different sets of benchmark instances. The experimentation shows that the proposed method is competitive or outperforms the state‐of‐the‐art approaches, providing either the optimal solution or improved bounds for several instances unsolved before.

Förderung

  • Ministero dell'Università e della Ricerca

Zitieren

APA

Boccia, M., Mancuso, A., Masone, A., & Sterle, C. (2023). A new MILP formulation for the flying sidekick traveling salesman problem. Networks, 82(3), 254-276. https://doi.org/10.1002/net.22172

Vancouver

Boccia M, Mancuso A, Masone A, Sterle C. A new MILP formulation for the flying sidekick traveling salesman problem. Networks. 2023;82(3):254-276. doi:10.1002/net.22172

BibTeX
@article{Boccia2023,
  author = {Boccia, Maurizio and Mancuso, Andrea and Masone, Adriano and Sterle, Claudio},
  title = {A new MILP formulation for the flying sidekick traveling salesman problem},
  journal = {Networks},
  year = {2023},
  volume = {82},
  number = {3},
  pages = {254--276},
  doi = {10.1002/net.22172}
}
Kostenlos starten →