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

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 p...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Rahma Lahyani, Mahdi Khemakhem, Frédéric Semet
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2017
Materias:	90B06 90C10 90C59 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/ad883e1c87c84776842821d60537125e
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:ad883e1c87c84776842821d60537125e
record_format	dspace
spelling	oai:doaj.org-article:ad883e1c87c84776842821d60537125e2021-12-02T05:01:02ZA unified matheuristic for solving multi-constrained traveling salesman problems with profits2192-440610.1007/s13675-016-0071-1https://doaj.org/article/ad883e1c87c84776842821d60537125e2017-09-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000861https://doaj.org/toc/2192-4406In 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.Rahma LahyaniMahdi KhemakhemFrédéric SemetElsevierarticle90B0690C1090C59Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 5, Iss 3, Pp 393-422 (2017)
institution	DOAJ
collection	DOAJ
language	EN
topic	90B06 90C10 90C59 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90B06 90C10 90C59 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Rahma Lahyani Mahdi Khemakhem Frédéric Semet A unified matheuristic for solving multi-constrained traveling salesman problems with profits
description	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.
format	article
author	Rahma Lahyani Mahdi Khemakhem Frédéric Semet
author_facet	Rahma Lahyani Mahdi Khemakhem Frédéric Semet
author_sort	Rahma Lahyani
title	A unified matheuristic for solving multi-constrained traveling salesman problems with profits
title_short	A unified matheuristic for solving multi-constrained traveling salesman problems with profits
title_full	A unified matheuristic for solving multi-constrained traveling salesman problems with profits
title_fullStr	A unified matheuristic for solving multi-constrained traveling salesman problems with profits
title_full_unstemmed	A unified matheuristic for solving multi-constrained traveling salesman problems with profits
title_sort	unified matheuristic for solving multi-constrained traveling salesman problems with profits
publisher	Elsevier
publishDate	2017
url	https://doaj.org/article/ad883e1c87c84776842821d60537125e
work_keys_str_mv	AT rahmalahyani aunifiedmatheuristicforsolvingmulticonstrainedtravelingsalesmanproblemswithprofits AT mahdikhemakhem aunifiedmatheuristicforsolvingmulticonstrainedtravelingsalesmanproblemswithprofits AT fredericsemet aunifiedmatheuristicforsolvingmulticonstrainedtravelingsalesmanproblemswithprofits AT rahmalahyani unifiedmatheuristicforsolvingmulticonstrainedtravelingsalesmanproblemswithprofits AT mahdikhemakhem unifiedmatheuristicforsolvingmulticonstrainedtravelingsalesmanproblemswithprofits AT fredericsemet unifiedmatheuristicforsolvingmulticonstrainedtravelingsalesmanproblemswithprofits
_version_	1718400847490056192

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

Ejemplares similares