A transformation technique for the clustered generalized traveling salesman problem with applications to logistics

Pouya Baniasadi, Mehdi Foumani*, Kate Smith-Miles, Vladimir Ejov

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

94 Citations (Scopus)

Abstract

The clustered generalized traveling salesman problem (CGTSP) is an extension of the classical traveling salesman problem (TSP), where the set of nodes is divided into clusters of nodes, and the clusters are further divided into subclusters of nodes. The objective is to find the minimal route that visits exactly one node from each subcluster in such a way that all subclusters of each cluster are visited consecutively. Due to the additional flexibility of the CGTSP compared to the classical TSP, CGTSP can incorporate a wider range of complexities arising from some practical applications. However, the absence of a good solution method for CGTSP is currently a major impediment in the use of the framework for modeling. Accordingly, the main objective of this paper is to enable the powerful framework of CGTSP for applied problems. To attain this goal, we first develop a solution method by an efficient transformation from CGTSP to TSP. We then demonstrate that not only the solution method provides far superior solution quality compared to existing methods for solving CGTSP, but also it enables practical solutions to far larger CGTSP instances. Finally, to illustrate that the modeling framework and the solution method apply to some practical problems of realistic sizes, we conduct a computational experiment by considering the application of CGTSP to two modern logistics problems; namely, automated storage and retrieval systems (logistics inside the warehouse) and drone-assisted parcel delivery service (logistics outside the warehouse).

Original languageEnglish
Pages (from-to)444-457
Number of pages14
JournalEuropean Journal of Operational Research
Volume285
Issue number2
DOIs
Publication statusPublished - 1 Sept 2020
Externally publishedYes

Keywords

  • Drones
  • Logistics
  • Transformation technique
  • Traveling salesman problem
  • Warehousing

Fingerprint

Dive into the research topics of 'A transformation technique for the clustered generalized traveling salesman problem with applications to logistics'. Together they form a unique fingerprint.

Cite this