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 emerging applications.
•We focus on the periodic rural postman problem with irregular services.•We propose an algorithm that combines heuristics and mathematical programming.•Multi-start heuristics are used to construct ...initial solutions.•Some parts of these solutions are recombined through a model-based approach.•The results of an extensive computational study are presented.
In this article we address the periodic rural postman problem with irregular services (PRPP–IS), where some arcs and/or edges of a mixed graph must be traversed (to be serviced) a certain number of times in some subsets of days of a given time horizon. The goal is to define a set of minimum cost tours, one for each day or period of the time horizon, that satisfy the service requirements. For this problem we propose a two-phase algorithm that combines heuristics and mathematical programming. In the first phase, two different procedures are used to construct feasible solutions: a multi-start heuristic based on feasibility pump and a multi-start constructive heuristic. From these solutions, some fragments (parts of tours associated with the different days) are extracted. The second phase determines a solution for the PRPP–IS by combining the fragments by means of a mathematical model. We show the effectiveness of this solution approach through an extensive experimental phase on different sets of instances.
The min-max close-enough arc routing problem Bianchessi, Nicola; Corberán, Ángel; Plana, Isaac ...
European journal of operational research,
08/2022, Letnik:
300, Številka:
3
Journal Article
Recenzirano
Odprti dostop
•We study the min-max close enough arc routing problem.•We propose two new mathematical formulations for the problem.•We design and implement a branch-and-cut and a branch-and-price algorithm to ...solve the problem.•Extensive computational experiments are carried out to assess the performance of the proposed algorithms.
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.
•We study the length-constrained K-drones arc routing problem.•We propose a new mathematical formulation for the problem.•We present several new families of valid inequalities and some procedures for ...their separation.•We propose a branch-and-cut algorithm and a matheuristic to solve the problem.
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, railway or power transmission lines and traffic monitoring.
To deal with this problem, LC K-DRPP instances are digitized by approximating each line by a polygonal chain with a finite number of points and allowing drones to enter and exit each line only at these points. In this way we obtain an instance of the Length Constrained K-vehicles Rural Postman Problem (LC K-RPP). If the number of points used to discretize the lines is large, the LC K-RPP instance can be extremely large and, hence, very difficult to solve optimally. Even heuristic algorithms can fail in providing feasible solutions in reasonable computing times. An alternative is to generate smaller LC K-RPP instances by approximating each line with few but “significant” segments.
We present a formulation and some valid inequalities for the LC K-RPP. Based on this, we have designed and implemented a branch-and-cut algorithm for its solution. Moreover, in order to be capable of providing good solutions for large LC K-RPP instances, we propose a matheuristic algorithm that begins by finding good solutions for the LC K-RPP instance obtained by approximating each line by a single segment. Then, to find better solutions, some promising intermediate points are sequentially incorporated. Extensive computational experiments to assess the performance of both algorithms are performed on several sets of instances from the literature.
•We study the Distance-Constrained Close Enough Arc Routing Problem.•We propose a new mathematical formulation for the problem.•We present several new families of valid inequalities and some ...procedures for their separation.•We propose a branch-and-cut algorithm to solve the problem and compare it with the best exact procedure in the literature.
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 of this problem to the case in which a fleet of vehicles is available. This problem, the Distance-Constrained Close Enough Arc Routing Problem, consists of finding a set of routes with minimum total cost such that their length does not exceed a maximum distance.
In this article, we propose a new formulation for the Distance-Constrained Close Enough Arc Routing Problem and present some families of valid inequalities that we use in a branch-and-cut algorithm for its solution. Extensive computational experiments have been performed on a set of benchmark instances and the results are compared with those obtained with other heuristic and exact methods.
•We deal with the periodic rural postman problem with irregular services.•An interesting application of the problem refers to the road network surveillance.•We propose an integer programming ...formulation for the problem.•The solution framework is based on branch-and-cut.•Extensive computational experiments on different sets of instances are presented.
In this paper, we deal with an extension of the rural postman problem in which some links of a mixed graph must be traversed a given number of times over a time horizon. These links represent entities that must be serviced a specified number of times in some subsets of days (or periods) of the time horizon. The aim is to design a set of minimum-cost tours, one for each day/period of the time horizon, that satisfy the service requirements. We refer to this problem as the periodic rural postman problem with irregular services (PRPP–IS). Some practical applications of the problem can be found in road maintenance operations and road network surveillance, for example. In order to solve the PRPP–IS, we propose a mathematical model and a branch-and-cut algorithm. As far as we know, this is the first exact method devised for a periodic arc routing problem. In the solution framework, constraints ensuring connectivity and other valid inequalities are identified by using specific separation procedures. Most valid inequalities consider the particular nature of the PRPP–IS. We show the effectiveness of the solution approach through an extensive experimental phase.
In this paper we propose a heuristic for the Uncapacitated r-Allocation p-Hub Median Problem. In the classical p-hub location problem, given a set of nodes with pairwise traffic demands, we must ...select p of them as hub locations and route all traffics through them at a minimum cost. We target here an extension, called the r-allocation p-hub median problem, recently proposed by Yaman 19, in which every node is assigned to r of the p selected hubs (r≤p) and we are restricted to route the traffic of the nodes through their associated r hubs.
As it is usual in this type of problems, our method has three phases: location, assignment and routing. Specifically, we propose a heuristic based on the GRASP methodology in which we consider three local search procedures. The combinatorial nature of this problem makes them time-consuming. We therefore propose a filtering mechanism to discard low-quality constructions and skip its improvement, saving its associated running time. We perform several experiments to first determine the values of the key-search parameters of our method and then to compare with previous algorithms. Computational results on 465 instances show that while only small instances can be optimally solved with exact methods, the heuristic is able to find high-quality solutions on larger instances in short computing times. Moreover, when targeting the classical p-hub versions (with r=1 or r=p), our heuristic is competitive with the state of the art methods.
The facility location problem with capacity transfers Corberán, Ángel; Landete, Mercedes; Peiró, Juanjo ...
Transportation research. Part E, Logistics and transportation review,
06/2020, Letnik:
138
Journal Article
Recenzirano
This paper explores the concept of capacity transfer in the context of capacitated facility location problems. This is accomplished by assuming that facilities with surplus capacity/production can ...cooperate with those facing shortage by transferring part of that capacity/production. Such a transfer incurs a cost that nonetheless may be compensated by savings both in the installation costs and in the distribution costs. Mixed-integer mathematical programming models are proposed for the problem. A distinction is made between the case in which the triangle inequality holds for the transfer costs and the case in which it does not. We present compact models, which are enhanced with valid inequalities that are separated in a branch-and-cut fashion. A comprehensive computational study with several hundreds of instances is reported showing the value of transferring capacities. Overall, this work investigates a problem that is at the core of more comprehensive models emerging in the context of logistics network design.
•We have studied a hub location problem in which the capacity of the edges between hubs is increased in a modular way.•Heuristic methods producing high-quality solutions in short computing times are ...proposed.•A comparison among the proposed methods and existing heuristics on a set of benchmark instances is provided.
In this paper we study the hub location problem, where the goal is to identify an optimal subset of facilities (hubs) to minimize the transportation cost while satisfying certain capacity constraints. In particular, we target the single assignment version, in which each node in the transportation network is assigned to only one hub to route its traffic. We consider here a realistic variant introduced previously, in which the capacity of edges between hubs is increased in a modular way. This reflects the practical situation in air traffic where the number of flights between two locations implies a capacity in terms of number of passengers. Then, the capacity can be increased in a modular way, as a factor of the number of flights. We propose heuristic methods to obtain high-quality solutions in short computing times. Specifically, we implement memory structures to create advanced search methods and compare them with previous heuristics on a set of benchmark instances. Memory structures have been widely implemented in the context of the tabu search methodology, usually embedded in local search algorithms. In this paper we explore an alternative design in which the constructive method is enhanced with frequency information and the local search is coupled with a path relinking post-processing. Statistical tests confirm the superiority of our proposal with respect to previous developments.
PDF
