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

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

European Journal of Operational Research, 2020, vol. 285, issue 2, 444-457

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

Keywords: Traveling salesman problem; Transformation technique; Logistics; Warehousing; Drones (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720300904
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:285:y:2020:i:2:p:444-457

DOI: 10.1016/j.ejor.2020.01.053

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().