showing 21 related works from this author
The Hierarchical Mixed Rural Postman Problem: Polyhedral analysis and a branch-and-cut algorithm
2017
[EN] The Hierarchical Mixed Rural Postman Problem is defined on a mixed graph where arcs and edges that require a service are divided into clusters' that have to be serviced in a hierarchical order. The problem generalizes the Mixed Rural Postman Problem and thus is NP-hard. In this paper, we provide a polyhedral analysis of the problem and propose a branch-and-cut algorithm for its solution based on the introduced classes of valid inequalities. Extensive computational experiments are reported on benchmark instances. The exact approach allows to find the optimal solutions in less than 1 hour for instances with up to 999 vertices, 2678 links, and five clusters.
The stacker crane problem and the directed general routing problem
2015
[EN] This article deals with the polyhedral description and the resolution of the directed general routing problem (DGRP) and the stacker crane problem (SCP). The DGRP contains a large number of important arc and node routing problems as special cases, including the SCP. Large families of facet-defining inequalities for the DGRP are described and a branch-and-cut algorithm for these problems is presented. Extensive computational experiments over different sets of DGRP and SCP instances are included.
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.
On the Distance-Constrained Close Enough Arc Routing Problem
2021
[EN] Arc routing problems consist basically of finding one or several routes traversing a given set of arcs and/or edges that must be serviced. The Close-Enough Arc Routing Problem, or Generalized Directed Rural Postman Problem, does not assume that customers are located at specific arcs, but can be serviced by traversing any arc of a given subset. Real-life applications include routing for meter reading, in which a vehicle equipped with a receiver travels a street network. If the vehicle gets within a certain distance of a meter, the receiver collects its data. Therefore, only a few streets which are close enough to the meters need to be traversed. In this paper we study the generalization…
New facets and an enhanced branch-and-cut for the min-max K -vehicles windy rural postman problem
2011
[EN] The min-max windy rural postman problem is a multiple vehicle version of the windy rural postman problem, WRPP, which consists of minimizing the length of the longest route to find a set of balanced routes for the vehicles. In a previous paper, an ILP formulation and a partial polyhedral study were presented, and a preliminary branch-and-cut algorithm that produced some promising computational results was implemented. In this article, we present further results for this problem. We describe several new facet-inducing inequalities obtained from the WRPP, as well as some inequalities that have to be satisfied by any optimal solution. We present an enhanced branch-and-cut algorithm that t…
A branch-and-cut algorithm for the Orienteering Arc Routing Problem
2016
[EN] In arc routing problems, customers are located on arcs, and routes of minimum cost have to be identified. In the Orienteering Arc Routing Problem (OARP),in addition to a set of regular customers that have to be serviced, a set of potential customers is available. From this latter set, customers have to be chosen on the basis of an associated profit. The objective is to find a route servicing the customers which maximize the total profit collected while satisfying a given time limit on the route.In this paper, we describe large families of facet-inducing inequalities for the OARP and present a branch-and-cut algorithm for its solution. The exact algorithm embeds a procedure which builds…
Aesthetic considerations for the min-max K-Windy Rural Postman Problem
2017
[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 sever…
Time-dependent asymmetric traveling salesman problem with time windows: Properties and an exact algorithm
2019
Abstract In this paper, we deal with the Time-Dependent Asymmetric Traveling Salesman Problem with Time Windows. First, we prove that under special conditions the problem can be solved as an Asymmetric Traveling Salesman Problem with Time Windows, with suitable-defined time windows and (constant) travel times. Second, we show that, if the special conditions do not hold, the time-independent optimal solution provides both a lower bound and (eventually) an upper bound with a worst-case guarantee for the Time-Dependent Asymmetric Traveling Salesman Problem with Time Windows. Finally, a branch-and-bound algorithm is presented and tested on a set of 4800 instances. The results have been compared…
GRASP and path relinking for the matrix bandwidth minimization
2004
In this article we develop a greedy randomized adaptive search procedure (GRASP) for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix, which keeps the nonzero elements in a band that is as close as possible to the main diagonal. The proposed method may be coupled with a Path Relinking strategy to search for improved outcomes. Empirical results indicate that the proposed GRASP implementation compares favourably to classical heuristics. GRASP with Path Relinking is also found to be competitive with a recently published tabu search algorithm that is considered one of the best currently available for band…
The Chinese Postman Problem with Load-Dependent Costs
2018
[EN] We introduce an interesting variant of the well-known Chinese postman problem (CPP). While in the CPP the cost of traversing an edge is a constant (equal to its length), in the variant we present here the cost of traversing an edge depends on its length and on the weight of the vehicle at the moment it is traversed. This problem is inspired by the perspective of minimizing pollution in transportation, since the amount of pollution emitted by a vehicle not only depends on the travel distance but also on its load, among other factors. We define the problem, study its computational complexity, provide two mathematical programming formulations, and propose two metaheuristics for its soluti…
A New Branch-and-Cut Algorithm for the Generalized Directed Rural Postman Problem
2016
The generalized directed rural postman problem, also known as the close-enough arc routing problem, is an arc routing problem with some interesting real-life applications, such as routing for meter reading. In this article we introduce two new formulations for this problem as well as various families of new valid inequalities that are used to design and implement a branch-and-cut algorithm. The computational results obtained on test bed instances from the literature show that this algorithm outperforms the existing exact methods
A Branch-Price-and-Cut Algorithm for the Min-Max k -Vehicle Windy Rural Postman Problem
2013
[EN] The min-max k -vehicles windy rural postman problem consists of minimizing the maximal distance traveled by a vehicle to find a set of balanced routes that jointly service all the required edges in a windy graph. This is a very difficult problem, for which a branch-and-cut algorithm has already been proposed, providing good results when the number of vehicles is small. In this article, we present a branch-price-and-cut method capable of obtaining optimal solutions for this problem when the number of vehicles is larger for the same set of required edges. Extensive computational results on instances from the literature are presented.
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…
Drone arc routing problems
2018
[EN] In this article, we present some drone arc routing problems (Drone ARPs) and study their relation with well-known postman ARPs. Applications for Drone ARPs include traffic monitoring by flying over roadways, infrastructure inspection such as by flying along power transmission lines, pipelines or fences, and surveillance along linear features such as coastlines or territorial borders. Unlike the postmen in traditional ARPs, drones can travel directly between any two points in the plane without following the edges of the network. As a consequence, a drone route may service only part of an edge, with multiple routes being used to cover the entire edge. Thus the Drone ARPs are continuous o…
The min-max close-enough arc routing problem
2022
Abstract Here we introduce the Min-Max Close-Enough Arc Routing Problem, where a fleet of vehicles must serve a set of customers while trying to balance the length of the routes. The vehicles do not need to visit the customers, since they can serve them from a distance by traversing arcs that are “close enough” to the customers. We present two formulations of the problem and propose a branch-and-cut and a branch-and-price algorithm based on the respective formulations. A heuristic algorithm used to provide good upper bounds to the exact procedures is also presented. Extensive computational experiments to compare the performance of the algorithms are carried out.
An ILS-Based Metaheuristic for the Stacker Crane Problem
2012
[EN] In this paper we propose a metaheuristic algorithm for the Stacker Crane Problem. This is an NP-hard arc routing problem whose name derives from the practical problem of operating a crane. Here we present a formulation and a lower bound for this problem and propose a metaheuristic algorithm based on the combination of a Multi-start and an Iterated Local Search procedures. Computational results on a large set of instances are presented.
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 directed profitable rural postman problem with incompatibility constraints
2017
[EN] In this paper, we study a variant of the directed rural postman problem (RPP) where profits are asso- ciated with arcs to be served, and incompatibility constraints may exist between nodes and profitable arcs leaving them. If convenient, some of the incompatibilities can be removed provided that penalties are paid. The problem looks for a tour starting and ending at the depot that maximizes the difference between collected profits and total cost as sum of traveling costs and paid penalties, while satisfying remaining incompatibilities. The problem finds application in the domain of road transportation service, and in particular in the context of horizontal collaboration among carriers …
Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem
2017
[EN] The generalized directed rural postman problem is an arc routing problem with many 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 closer than a certain distance to 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, to get close enough to each meter. We study an extension of this problem in which a fleet of vehicles is available. Given the characteristics of the mentioned application, the vehicles have no capacities but there is a maximum distan…
A matheuristic for the Team Orienteering Arc Routing Problem
2015
In the Team OrienteeringArc Routing Problem (TOARP) the potential customers are located on the arcs of a directed graph and are to be chosen on the basis of an associated profit. A limited fleet of vehicles is available to serve the chosen customers. Each vehicle has to satisfy a maximum route duration constraint. The goal is to maximize the profit of the served customers. We propose a matheuristic for the TOARP and test it on a set of benchmark instances for which the optimal solution or an upper bound is known. The matheuristic finds the optimal solutions on all, except one, instances of one of the four classes of tested instances (with up to 27 vertices and 296 arcs). The average error o…
Arc routing problems: A review of the past, present, and future
2020
[EN] Arc routing problems (ARPs) are defined and introduced. Following a brief history of developments in this area of research, different types of ARPs are described that are currently relevant for study. In addition, particular features of ARPs that are important from a theoretical or practical point of view are discussed. A section on applications describes some of the changes that have occurred from early applications of ARP models to the present day and points the way to emerging topics for study. A final section provides information on libraries and instance repositories for ARPs. The review concludes with some perspectives on future research developments and opportunities for emergin…