Titre :

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

Auteur(s) :

Lahyani, Rahma [Auteur]
Alfaisal University
LOgistique, Gestion Industrielle et Qualité [LOGIQ]
Khemakhem, Mahdi [Auteur]
Prince Sattam Bin Abdul-Aziz University [PSAU]
Semet, Frédéric [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Integrated Optimization with Complex Structure [INOCS]

Titre de la revue :

EURO Journal on Computational Optimization

Pagination :

393 - 422

Éditeur :

Springer

Date de publication :

2017-09

ISSN :

2192-4406

Mot(s)-clé(s) en anglais :

Orienteering Problem
Matheuristic
Orienteering Problem with Time Window
Approximate Routing Neighborhoods
Profitable Tour Problem with Compartments
Exact Loading Neighborhood

Discipline(s) HAL :

Informatique [cs]
Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL