A unified matheuristic for solving multi-constrained traveling salesman problems with profits

Rahma Lahyani (), Mahdi Khemakhem () and Frédéric Semet ()
Additional contact information
Rahma Lahyani: Al Faisal University
Mahdi Khemakhem: Prince Sattam Bin Abdulaziz University
Frédéric Semet: Univ. Lille, CNRS, Centrale Lille, Inria

EURO Journal on Computational Optimization, 2017, vol. 5, issue 3, No 4, 393-422

Abstract: Abstract In this paper, we address a rich Traveling Salesman Problem with Profits encountered in several real-life cases. We propose a unified solution approach based on variable neighborhood search. Our approach combines several removal and insertion routing neighborhoods and efficient constraint checking procedures. The loading problem related to the use of a multi-compartment vehicle is addressed carefully. Two loading neighborhoods based on the solution of mathematical programs are proposed to intensify the search. They interact with the routing neighborhoods as it is commonly done in matheuristics. The performance of the proposed matheuristic is assessed on various instances proposed for the Orienteering Problem and the Orienteering Problem with Time Window including up to 288 customers. The computational results show that the proposed matheuristic is very competitive compared with the state-of-the-art methods. To better evaluate its performance, we generate a new testbed including instances with various attributes. Extensive computational experiments on the new testbed confirm the efficiency of the matheuristic. A sensitivity analysis highlights which components of the matheuristic contribute most to the solution quality.

Keywords: Profitable tour problem with compartments; Matheuristic; Exact loading neighborhoods; Approximate routing neighborhoods; Orienteering problem; Orienteering problem with time window; 90B06; 90C10; 90C59 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s13675-016-0071-1 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:eurjco:v:5:y:2017:i:3:d:10.1007_s13675-016-0071-1

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-016-0071-1

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().