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

Giovanni Campuzano; Eduardo Lalla-Ruiz; Martijn Mes

doi:10.1007/978-3-030-87672-2_26

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 proceeding › Conference contribution › Academic › peer-review

4 Citations (Scopus)

104 Downloads (Pure)

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 language	English
Title of host publication	Computational Logistics
Subtitle of host publication	12th International Conference, ICCL 2021, Enschede, The Netherlands, September 27–29, 2021, Proceedings
Editors	Martijn Mes, Eduardo Lalla-Ruiz, Stefan Voß
Place of Publication	Cham
Publisher	Springer
Pages	393-409
Number of pages	17
ISBN (Electronic)	978-3-030-87672-2
ISBN (Print)	978-3-030-87671-5
DOIs	https://doi.org/10.1007/978-3-030-87672-2_26
Publication status	Published - 22 Sept 2021
Event	12th International Conference on Computational Logistics, ICCL 2021 - University of Twente (online), Enschede, Netherlands Duration: 27 Sept 2021 → 29 Sept 2021 Conference number: 12 https://iccl2021.nl/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	13004
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Conference on Computational Logistics, ICCL 2021
Abbreviated title	ICCL 2021
Country/Territory	Netherlands
City	Enschede
Period	27/09/21 → 29/09/21
Internet address	https://iccl2021.nl/

Keywords

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

Access to Document

10.1007/978-3-030-87672-2_26

Campuzano2021multi-startFinal published version, 421 KBLicence: Taverne

Cite this

Campuzano, G., Lalla-Ruiz, E., & Mes, M. (2021). A Multi-start VNS Algorithm for the TSP-D with Energy Constraints. In M. Mes, E. Lalla-Ruiz, & S. Voß (Eds.), Computational Logistics: 12th International Conference, ICCL 2021, Enschede, The Netherlands, September 27–29, 2021, Proceedings (pp. 393-409). (Lecture Notes in Computer Science; Vol. 13004). Springer. https://doi.org/10.1007/978-3-030-87672-2_26

Campuzano, Giovanni ; Lalla-Ruiz, Eduardo ; Mes, Martijn. / A Multi-start VNS Algorithm for the TSP-D with Energy Constraints. Computational Logistics: 12th International Conference, ICCL 2021, Enschede, The Netherlands, September 27–29, 2021, Proceedings. editor / Martijn Mes ; Eduardo Lalla-Ruiz ; Stefan Voß. Cham : Springer, 2021. pp. 393-409 (Lecture Notes in Computer Science).

@inproceedings{bf69d948e2074fc9ab8eff12ffb40a51,

title = "A Multi-start VNS Algorithm for the TSP-D with Energy Constraints",

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.",

keywords = "Drones, Last-mile delivery, Multi start, Traveling salesman problem, UAV, Variable neighbourhood search",

author = "Giovanni Campuzano and Eduardo Lalla-Ruiz and Martijn Mes",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 12th International Conference on Computational Logistics, ICCL 2021, ICCL 2021 ; Conference date: 27-09-2021 Through 29-09-2021",

year = "2021",

month = sep,

day = "22",

doi = "10.1007/978-3-030-87672-2_26",

language = "English",

isbn = "978-3-030-87671-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "393--409",

editor = "Martijn Mes and Eduardo Lalla-Ruiz and Stefan Vo{\ss}",

booktitle = "Computational Logistics",

address = "Germany",

url = "https://iccl2021.nl/",

}

Campuzano, G, Lalla-Ruiz, E & Mes, M 2021, A Multi-start VNS Algorithm for the TSP-D with Energy Constraints. in M Mes, E Lalla-Ruiz & S Voß (eds), Computational Logistics: 12th International Conference, ICCL 2021, Enschede, The Netherlands, September 27–29, 2021, Proceedings. Lecture Notes in Computer Science, vol. 13004, Springer, Cham, pp. 393-409, 12th International Conference on Computational Logistics, ICCL 2021, Enschede, Netherlands, 27/09/21. https://doi.org/10.1007/978-3-030-87672-2_26

A Multi-start VNS Algorithm for the TSP-D with Energy Constraints. / Campuzano, Giovanni; Lalla-Ruiz, Eduardo ; Mes, Martijn.
Computational Logistics: 12th International Conference, ICCL 2021, Enschede, The Netherlands, September 27–29, 2021, Proceedings. ed. / Martijn Mes; Eduardo Lalla-Ruiz; Stefan Voß. Cham: Springer, 2021. p. 393-409 (Lecture Notes in Computer Science; Vol. 13004).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Campuzano, Giovanni

AU - Lalla-Ruiz, Eduardo

AU - Mes, Martijn

N1 - Conference code: 12

PY - 2021/9/22

Y1 - 2021/9/22

N2 - 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.

AB - 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.

KW - Drones

KW - Last-mile delivery

KW - Multi start

KW - Traveling salesman problem

KW - UAV

KW - Variable neighbourhood search

UR - http://www.scopus.com/inward/record.url?scp=85116335904&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-87672-2_26

DO - 10.1007/978-3-030-87672-2_26

M3 - Conference contribution

AN - SCOPUS:85116335904

SN - 978-3-030-87671-5

T3 - Lecture Notes in Computer Science

SP - 393

EP - 409

BT - Computational Logistics

A2 - Mes, Martijn

A2 - Lalla-Ruiz, Eduardo

A2 - Voß, Stefan

PB - Springer

CY - Cham

T2 - 12th International Conference on Computational Logistics, ICCL 2021

Y2 - 27 September 2021 through 29 September 2021

ER -

Campuzano G, Lalla-Ruiz E , Mes M. A Multi-start VNS Algorithm for the TSP-D with Energy Constraints. In Mes M, Lalla-Ruiz E, Voß S, editors, Computational Logistics: 12th International Conference, ICCL 2021, Enschede, The Netherlands, September 27–29, 2021, Proceedings. Cham: Springer. 2021. p. 393-409. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-87672-2_26

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Autonomous Multimodal Last-Mile Delivery Systems

Cite this