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

Abstract

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 - 12th International Conference, ICCL 2021, Proceedings
EditorsMartijn Mes, Eduardo Lalla-Ruiz, Stefan Voß
PublisherSpringer Science + Business Media
Pages393-409
Number of pages17
ISBN (Print)9783030876715
DOIs
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
https://iccl2021.nl/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13004 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Conference on Computational Logistics, ICCL 2021
Abbreviated titleICCL 2021
CountryNetherlands
CityEnschede
Period27/09/2129/09/21
Internet address

Keywords

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

Fingerprint

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