A Multi-start VNS Algorithm for the TSP-D with Energy Constraints

Giovanni Campuzano*, Eduardo Lalla-Ruiz, Martijn Mes

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
17 Downloads (Pure)


The Traveling Salesman Problem (TSP) is a well-known optimization problem with a wide range of extensions and applications in delivery systems. In this paper, we consider a recent extension of the TSP where a truck in collaboration with a single drone should visit a set of customers while minimizing the transportation times. We propose a Variable Neighbourhood Search (VNS) and a Multi-Start VNS (MS-VNS) algorithm, develop new neighbourhood structures, and compare the solutions against an existing mixed-integer linear programming (MILP) formulation. We take a set of instances based on existing benchmarks from the related literature. Results point out that the new neighbourhood structures substantially improve the performance of the VNS algorithms. Furthermore, results also show that the exact method is only able to find competitive solutions for small sets of instances, whereas our MS-VNS approach reaches better solution quality for large instances.

Original languageEnglish
Title of host publicationComputational Logistics
Subtitle of host publication12th International Conference, ICCL 2021, Enschede, The Netherlands, September 27–29, 2021, Proceedings
EditorsMartijn Mes, Eduardo Lalla-Ruiz, Stefan Voß
Place of PublicationCham
Number of pages17
ISBN (Electronic)978-3-030-87672-2
ISBN (Print)978-3-030-87671-5
Publication statusPublished - 22 Sep 2021
Event12th International Conference on Computational Logistics, ICCL 2021 - University of Twente (online), Enschede, Netherlands
Duration: 27 Sep 202129 Sep 2021
Conference number: 12

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference12th International Conference on Computational Logistics, ICCL 2021
Abbreviated titleICCL 2021
Internet address


  • Drones
  • Last-mile delivery
  • Multi start
  • Traveling salesman problem
  • UAV
  • Variable neighbourhood search


Dive into the research topics of 'A Multi-start VNS Algorithm for the TSP-D with Energy Constraints'. Together they form a unique fingerprint.

Cite this