On unified solution approach for solving ...
Document type :
Autre communication scientifique (congrès sans actes - poster - séminaire...): Communication dans un congrès avec actes
Title :
On unified solution approach for solving multi-constraint travelling salesman problems with profits
Author(s) :
Lahyani, Rahma [Auteur correspondant]
Laboratoire d'Automatique, Génie Informatique et Signal [LAGIS]
Khemakhem, Mahdi [Auteur]
SEMET, Frédéric [Auteur]
LAGIS-OSL
Laboratoire d'Automatique, Génie Informatique et Signal [LAGIS]
Khemakhem, Mahdi [Auteur]
SEMET, Frédéric [Auteur]

LAGIS-OSL
Conference title :
ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision
Conference organizers(s) :
Société française de recherche opérationnelle et d'aide à la décision
City :
Bordeaux
Country :
France
Start date of the conference :
2014-02-26
English keyword(s) :
Profitable Tour Problem with Compartments
Math
heuristic
Exact and Approximate Neighborhoods
Orienteering Problem
Orienteering Problem with Time Windows.
Orienteering Problem with Time Windows
Math
heuristic
Exact and Approximate Neighborhoods
Orienteering Problem
Orienteering Problem with Time Windows.
Orienteering Problem with Time Windows
HAL domain(s) :
Informatique [cs]/Recherche opérationnelle [cs.RO]
English abstract : [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 ...
Show more ><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>Show less >
Show more ><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>Show less >
Language :
Français
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
Source :