In this paper we consider the Bounded Length Median Path Problem which can be defined as the problem of locating a path-shaped facility that departures from a given origin and arrives at a given destination in a network. The length of the path is assumed to be bounded by a given maximum length. At each vertex of the network (customer-point) the demand for the service is given and the cost to reach the closest service-point is computed. The objective is to minimize the sum of these costs over all the customer-points in the network. We consider two local search metaheuristics, the well known Tabu search and the Old bachelor acceptance and we propose a comparative analysis of the performances of the two procedures. We implement streamlined versions of Tabu search and Old bachelor acceptance. Our main concern is to provide knowledge about the intrinsic strategy adopted by each metaheuristic and to know whether one is more appropriate than the other for our problem. (C) 2007 Elsevier B.V. All rights reserved.
Comparing different metaheuristic approaches for the median path problem with bounded length / Lari, Isabella; Ricca, Federica; Andrea, Scozzari. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - STAMPA. - 190:3(2008), pp. 587-597. [10.1016/j.ejor.2007.07.001]
Comparing different metaheuristic approaches for the median path problem with bounded length
LARI, Isabella;RICCA, Federica;
2008
Abstract
In this paper we consider the Bounded Length Median Path Problem which can be defined as the problem of locating a path-shaped facility that departures from a given origin and arrives at a given destination in a network. The length of the path is assumed to be bounded by a given maximum length. At each vertex of the network (customer-point) the demand for the service is given and the cost to reach the closest service-point is computed. The objective is to minimize the sum of these costs over all the customer-points in the network. We consider two local search metaheuristics, the well known Tabu search and the Old bachelor acceptance and we propose a comparative analysis of the performances of the two procedures. We implement streamlined versions of Tabu search and Old bachelor acceptance. Our main concern is to provide knowledge about the intrinsic strategy adopted by each metaheuristic and to know whether one is more appropriate than the other for our problem. (C) 2007 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.