New mixed integer linear programming models and an iterated local search for the clustered traveling salesman problem with relaxed priority rule

Thanh Tan Doan, Nathalie Bostel, Minh Hoàng Hà () and Vu Hoang Vuong Nguyen
Additional contact information
Thanh Tan Doan: Université de Nantes
Nathalie Bostel: Université de Nantes
Minh Hoàng Hà: Phenikaa University
Vu Hoang Vuong Nguyen: VNU University of Engineering and Technology

Journal of Combinatorial Optimization, 2023, vol. 46, issue 1, No 1, 27 pages

Abstract: Abstract The Traveling Salesman Problem (TSP) is a well known problem in operations research with various studies and applications. In this paper, we address a variant of the TSP in which the customers are divided into several priority groups and the order of servicing groups can be flexibly changed with a rule called the d-relaxed priority rule. The problem is called the Clustered Traveling Salesman Problem with Relaxed Priority Rule (CTSP-d). We propose two new Mixed Integer Linear Programming (MILP) models for the CTSP-d and a metaheuristic based on Iterated Local Search (ILS) with operators designed for or adapted to the problem. The experimental results obtained on the benchmark instances show that two new models performs better than previous ones, and ILS also proves its performance with 13 new best known solutions found and significant stability compared to existing metaheuristics.

Keywords: Traveling Salesman Problem; d-relaxed priority rule; Mixed integer linear programming; Iterated local search (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01066-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:46:y:2023:i:1:d:10.1007_s10878-023-01066-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01066-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().