Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Aesthetic considerations for the min-max K-Windy Rural Postman Problem

  • Corberán, A.
  • Golden, Bruce
  • Lum, Oliver
  • PLANA, ISAAC
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] The aesthetic quality of routes is a feature of route planning that is of practical importance, but receives relatively little attention in the literature. Several practitioners have pointed out that the visual appeal of a proposed set of routes can have a strong influence on the willingness of a client to accept or reject a specific routing plan. While some work has analyzed algorithmic performance relative to traditional min-sum or min-max objective functions and aesthetic objective functions, we are not aware of any work that has considered a multi-objective approach. This work considers a multi-objective variant of the Min-Max K-Vehicles Windy Rural Postman Problem, discusses several formulations of the problem, and presents computational experiments with a heuristic algorithm. After exploring several formulations, we choose to study the problem with a bi-objective function that includes contributions from the route overlap index and average task distance aesthetic measures. The heuristic extends the cluster-first procedure presented in Lum et al. (Networks 69 (2017), 290-303) by incorporating the new objective function into the improvement phase and adding a perturbation routine. (c) 2017 Wiley Periodicals, Inc., Contract grant sponsor: Spanish Ministerio de Economia y Competitividad and Fondo Europeo de Desarrollo Regional (FEDER); Contract grant number: project MTM2015-68097-P (MINECO/FEDER). Contract grant sponsor: Generalitat Valenciana; Contract grant number: project GVPROMETEO2013-049
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

A matheuristic for the Distance-Constrained Close-Enough Arc Routing Problem

  • Corberán, A.
  • PLANA, ISAAC
  • Reula, Miguel
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] The Close-Enough Arc Routing Problem, also called Generalized Directed Rural Postman Problem, is an arc routing problem with interesting real-life applications, such as routing for meter reading. In this application, a vehicle with a receiver travels through a series of neighborhoods. If the vehicle gets within a certain distance of a meter, the receiver is able to record the gas, water, or electricity consumption. Therefore, the vehicle does not need to traverse every street, but only a few, in order to be close enough to each meter. In this paper we deal with an extension of this problem, the Distance-Constrained Generalized Directed Rural Postman Problem or Distance-Constrained Close Enough Arc Routing Problem, in which a fleet of vehicles is available. The vehicles have to leave from and return to a common vertex, the depot, and the length of their routes must not exceed a maximum distance (or time). For solving this problem we propose a matheuristic that incorporates an effective exact procedure to optimize the routes obtained. Extensive computational experiments have been performed on a set of benchmark instances and the results are compared with those obtained with an exact procedure proposed in the literature., This work was supported by the Spanish Ministerio de Economia y Competitividad and Fondo Europeo de Desarrollo Regional (FEDER) through Project MTM2015-68097-P (MINECO/FEDER). Authors want to thank two anonymous referees for their suggestions and comments that have contributed to improve the paper.