Titre :

On unified solution approach for solving multi-constraint travelling salesman problems with profits

Auteur(s) :

Lahyani, Rahma [Auteur correspondant]
Laboratoire d'Automatique, Génie Informatique et Signal [LAGIS]
Khemakhem, Mahdi [Auteur]
SEMET, Frédéric [Auteur]
LAGIS-OSL

Titre de la manifestation scientifique :

ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision

Organisateur(s) de la manifestation scientifique :

Société française de recherche opérationnelle et d'aide à la décision

Ville :

Bordeaux

Pays :

France

Date de début de la manifestation scientifique :

2014-02-26

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

Profitable Tour Problem with Compartments
Math
heuristic
Exact and Approximate Neighborhoods
Orienteering Problem
Orienteering Problem with Time Windows.
Orienteering Problem with Time Windows

Discipline(s) HAL :

Informatique [cs]/Recherche opérationnelle [cs.RO]

Résumé en anglais : [en]

<p>Although the Traveling Salesman Problem with Profits (TSP with profits) has been explored quite broadly as a field of study and practice, only very attention has been paid to multi-attribute TSP with profits, despite ...
Lire la suite ><p>Although the Traveling Salesman Problem with Profits (TSP with profits) has been explored quite broadly as a field of study and practice, only very attention has been paid to multi-attribute TSP with profits, despite its large applicability. In this paper, we introduce a rich variant [1] of the TSP with profits dealing with a large class of temporal and physical incompatibility characteristics. This problem is too hard to be solved by exact methods. We therefore introduce a general multi-purpose hybrid math-heuristic based on routing heuristics and exact loading neighborhoods. To build and improve the customers' sequences, we propose a multi start-construction heuristic, a portfolio of removal and insertion heuristics and a broad range of local search procedures. A special attention has been paid to the loading aspect of the problem which was barely considered in previous works by solving the resulting loading problem exactly. Several data sets with instances of up to 288 customers were used to evaluate the unified math-heuristic from the Orienteering Problem [2,3] and the Orienteering Problem with Time Window literature [4,5]. Experimental results demonstrate that the proposed math-heuristic may compete with the best known state-of-the-art methods proposed for these problems. Expanded computational experiments on more complex generated instances substantiate the effectiveness of the proposed approach. Sensitivity analysis follows and reveals the importance of some algorithmic setups and loading neighborhoods components for reaching high quality solutions.</p> <p> </p> <p>[1] Lahyani R, Khemakehm M, Semet F, (2013) Rich vehicle routing problems: From a taxonomy to a definition. submitted for publication.</p> <p>[2] Campos V, Marti R, Sanchez O, Duarte A (2012) Grasp with path relinking for the orienteering problem. Submitted to Journal of Operational Research Society.</p> <p>[3] Chao I, Golden B, Wasil E (1996) A fast and effective heuristic for the orienteering problem. European Journal of Operational Research 88:475-489.</p> <p>[4] Labadie N, Mansini R, Melechovsk J, Calvo R (2012) The team orienteering problem with time windows: An lp-based granular variable neighborhood search. European Journal of Operational Research 220:15-27.</p> <p>[5] Righini G, Salani M (2009) Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers & Operations Research 36:1191-1203.</p>Lire moins >

Langue :

Français

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