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

Rahma Lahyani 1, 2 Mahdi Khemakhem 3 Frédéric Semet 4, 5
1 LOGIQ - LOgistique, Gestion Industrielle et Qualité
2 Alfaisal University
3 PSAU - Prince Sattam Bin Abdul-Aziz University
4 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
5 CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
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 Orienteer-ing 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 : Approximate Routing Neighborhoods Profitable Tour Problem with Compartments Exact Loading Neighborhood Orienteering Problem with Time Window Matheuristic Orienteering Problem
Type de document :
Article dans une revue
EURO Journal on Computational Optimization, Springer, 2017, 5 (3), pp.393 - 422. 〈10.1007/s13675-016-0071-1〉
Liste complète des métadonnées

Littérature citée [58 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01663624
Contributeur : Frédéric Semet <>
Soumis le : jeudi 14 décembre 2017 - 10:12:56
Dernière modification le : mercredi 25 avril 2018 - 15:42:33

Fichier

Version1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | INRIA2017 | CRISTAL

Citation

Rahma Lahyani, Mahdi Khemakhem, Frédéric Semet. A unified matheuristic for solving multi-constrained traveling salesman problems with profits. EURO Journal on Computational Optimization, Springer, 2017, 5 (3), pp.393 - 422. 〈10.1007/s13675-016-0071-1〉. 〈hal-01663624〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

108

Téléchargements de fichiers

37

Contact


archive-ouverte@inria.fr