Pasar al contenido principal

Resultados relacionados

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

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

New Results on the Mixed General Routing Problem

  • Corberán, Angel
  • Mejía, Gustavo
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In this paper, we deal with the polyhedral description and the resolution of the Mixed General Routing Problem. This problem, in which the service activity occurs both at some of the nodes and at some of the arcs and edges of a mixed graph, contains a large number of important arc and node routing problems as special cases. Here, a large family of facet-defining inequalities, the Honeycomb inequalities, is described. Furthermore, a cutting-plane algorithm for this problem that incorporates new separation procedures for the K-C, Regular Path-Bridge, and Honeycomb inequalities is presented. Branch and bound is invoked when the final solution of the cutting-plane procedure is fractional. Extensive computational experiments over different sets of instances are included., The contribution by A. Corberán and J. M. Sanchis has been partially supported by the Ministerio de Ciencia y Tecnología of Spain (Ref: TIC2003-05982-C05-01) and by the AVCiT de la Generalitat Valenciana (Ref: GRUPOS03/189).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Zigzag inequalities:a new class of facet-inducing inequalities for Arc Routing Problems

  • Corberán, A.
  • Plana, I.
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In this paper we introduce a new class of facet-inducing inequalities for the Windy Rural Postman Problem and the Windy General Routing Problem. These inequalities are called Zigzag inequalities because they cut off fractional solutions containing a zigzag associated with variables with 0.5 value. Two different types of inequalities, the Odd Zigzag and the Even Zigzag inequalities, are presented. Finally, their application to other known Arc Routing Problems is discussed., The authors wish to thank the Ministerio de Ciencia y Tecnología of Spain (project TIC2003-05982-C05-01) and the Generalitat Valenciana (Ref: GRUPOS03/189) their support.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A comparison of two different formulations for Arc Routing Problems on Mixed graphs

  • Corberán, A.
  • Mota, E.
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] Arc routing problems on mixed graphs have been modelled in the literature either using just one variable per edge or associating to each edge two variables, each one representing its traversal in the corresponding direction. In this paper, and using the mixed general routing problem as an example, we compare theoretical and computationally both formulations as well as the lower bounds obtained from them using Linear Programming based methods. Extensive computational experiments, including some big and newly generated random instances, are presented., Authors want to thank two anonymous referees for their careful reading of the manuscript. Also we thank the support given by the Ministerio de Ciencia y Tecnología of Spain through Grant TIC2003-05982-C05-01 and by the Generalitat Valenciana (Grupos 03/189).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Lower bounds and heuristics for the Windy Rural Postman Problem

  • Benavent, E.
  • Carrotta, A.
  • Corberán, A.
  • Vigo, D.
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In this paper we present several heuristic algorithms and a cutting-plane algorithm for the Windy Rural Postman Problem. This problem contains several important Arc Routing Problems as special cases and has very interesting real-life applications. Extensive computational experiments over different sets of instances are also presented., The contribution by E. Benavent, A. Corberán and J.M. Sanchis has been supported by the Ministerio de Ciencia y Tecnología of Spain through grant TIC2003-05982-C05-01 (partially financed with FEDER funds) and by the Generalitat Valenciana (Ref: GRUPOS03/174 and GRUPOS03/ 189). A. Carrotta and D. Vigo thank the Ministero Dell Istruzione, dell Università e della Ricerca (M.I.U.R.) and the Consiglio Nazionale delle Ricerche (C.N.R.), Italy, for the support given to this project.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation

  • Albiach, José
  • Soler Fernández, David
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In this paper we deal with an extended version of the Asymmetric Traveling Salesman Problem with Time Windows (ATSPTW) that considers time-dependent travel times and costs, for a more accurate approximation of some routing problems inside large cities, in which the time or cost of traversing certain streets (e.g. main avenues) depends on the moment of the day (for example rush-hours). Unlike other existing papers about time-dependent routing problems, we focus on an exact method for solving this new problem. For this end we first transform the problem into an Asymmetric Generalized TSP and then into a Graphical Asymmetric TSP. In this way, we can apply a known exact algorithm for the Mixed General Routing Problem, which seems to run well with our resulting instances. Computational results are presented on a set of 270 adapted instances from benchmark ATSPTW instances., This work has been partially supported by the Ministerio de Ciencia y Tecnología of Spain (project TIC2003-05982-C05-01) and the Generalitat Valenciana (Ref: GRUPOS03/189). Thanks are due to Michel Gendreau, Alain Hertz, Gilbert Laporte and Mihnea Stan for providing us the set of benchmark ATSPTW instances, and to Matteo Fischetti and Norbert Ascheuer for their suggestions and help about the computational experiments. Last we are also indebted to the three anonymous referees for their valuable comments.