Search results for "Arc Routing"

New Heuristic Algorithms for the Windy Rural Postman Problem

2005

[EN] In this paper we deal with the windy rural postman problem. This problem generalizes several important arc routing problems and has interesting real-life applications. Here, we present several heuristics whose study has lead to the design of a scatter search algorithm for the windy rural postman problem. Extensive computational experiments over different sets of instances, with sizes up to 988 nodes and 3952 edges, are also presented. (c) 2004 Elsevier Ltd. All rights reserved.

A branch-and-cut algorithm for the Profitable Windy Rural Postman Problem

2016

[EN] In this paper we study the profitable windy rural postman problem. This is an arc routing problem with profits defined on a windy graph in which there is a profit associated with some of the edges of the graph, consisting of finding a route maximizing the difference between the total profit collected and the total cost. This problem generalizes the rural postman problem and other well-known arc routing problems and has real-life applications, mainly in snow removal operations. We propose here a formulation for the problem and study its associated polyhedron. Several families of facet-inducing inequalities are described and used in the design of a branch-and-cut procedure. The algorithm…

The Windy clustered prize-collecting arc-routing problem

2011

This paper introduces the windy clustered prize-collecting arc-routing problem. It is an arc-routing problem where each demand edge is associated with a profit that is collected once if the edge is serviced, independent of the number of times the edge is traversed. It is further required that if a demand edge is serviced, then all the demand edges of its component are also serviced. A mathematical programming formulation is given and some polyhedral results including several facet-defining and valid inequalities are presented. The separation problem for the different families of inequalities is studied. Numerical results from computational experiments are analyzed. © 2011 INFORMS.

Solving the length constrained K-drones rural postman problem

2021

[EN] In this paper we address the Length Constrained K-Drones Rural Postman Problem (LC K-DRPP). This is a continuous optimization problem where a fleet of homogeneous drones have to jointly service (traverse) a set of (curved or straight) lines of a network. Unlike the vehicles in classical arc routing problems, a drone can enter a line through any of its points, service a portion of that line, exit through another of its points, then travel directly to any point on another line, and so on. Moreover, since the range of the drones is restricted, the length of each route is limited by a maximum distance. Some applications for drone arc routing problems include inspection of pipelines, railwa…

Preface: Special issue on arc routing problems and other related topics

2020

Some recent contributions to routing and location problems

2003

CORAL 2003, a Conference on Routing and Location, washeld in Puerto de la Cruz (Tenerife, Spain) from February24–26, 2003. A wonderful place, close to the black sand ofthe beach, and a nice temperature welcomed a group ofsenior and young researchers from Canada, England,France, Germany, and Spain. Social activities were alsoprovided and sponsored by the Cabildo Insular de Tenerife(the local government) and TITSA (the public bus transpor-tation company on the island). The conference corre-sponded to the third annual meeting of a research project,funded by the Spanish Ministry of Science and Technology,developing a Decision Support System for Vehicle Routingand Facility Location Problems (SAD…

The mixed general routing polyhedron

2003

[EN] In Arc Routing Problems, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the…

In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem

2015

Recently, Bode and Irnich [Bode C, Irnich S (2012) Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60(5):1167–1182] presented a cut-first branch-and-price-second algorithm for solving the capacitated arc-routing problem (CARP). The fundamental difference to other approaches for exactly solving the CARP is that the entire algorithm works directly on the typically sparse underlying graph representing the street network. This enables the use of highly efficient dynamic programming-based pricing algorithms to solve the column-generation subproblem also known as the pricing problem. The contribution of this paper is the in-depth analysis of the CARP pricing…

The Capacitated Arc Routing Problem: Lower bounds

1992

In this paper, we consider the Capacitated Arc Routing Problem (CARP), in which a fleet of vehicles, based on a specified vertex (the depot) and with a known capacity Q, must service a subset of the edges of a graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity. New lower bounds are developed for this problem, producing at least as good results as the already existing ones. Three of the proposed lower bounds are obtained from the resolution of a minimum cost perfect matching problem. The fourth one takes into account the vehicle capacity and is computed using a dynamic programming algorithm. Computational results, in which these bounds…

Split-Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic

2010

International audience; This paper proposes lower and upper bounds for the split-delivery capacitated arc-routing problem (SDCARP), a variant of the capacitated arc-routing problem in which an edge can be serviced by several vehicles. Recent papers on related problems in node routing have shown that this policy can bring significant savings. It is also more realistic in applications such as urban refuse collection, where a vehicle can become full in the middle of a street segment. This work presents the first lower bound for the SDCARP, computed with a cutting plane algorithm and an evolutionary local search reinforced by a multistart procedure and a variable neighborhood descent. Tests on …