New heuristic algorithms for the windy rural postman problem

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.     

Lower bounds for the mixed capacitated arc routing problem

Capacitated arc routing problems (CARP) arise in distribution or collecting problems where activities are performed by vehicles, with limited capacity, and are continuously distributed along some pre-defined links of a network. The CARP is defined either as an undirected problem or as a directed problem depending on whether the required links are undirected or directed. The mixed capacitated arc routing problem (MCARP) models a more realistic scenario since it considers directed as well as undirected required links in the associated network. We present a compact flow based model for the MCARP. Due to its large number of variables and constraints, we have created an aggregated version of the original model. Although this model is no longer valid, we show that it provides the same linear programming bound than the original model. Different sets of valid inequalities are also derived. The quality of the models is tested on benchmark instances with quite promising results.     

Solving capacitated arc routing problems using a transformation to the CVRP

A well-known transformation by Pearn, Assad and Golden reduces a capacitated arc routing problem (CARP) into an equivalent capacitated vehicle routing problem (CVRP). However, that transformation is regarded as unpractical, since an original instance with r   required edges is turned into a CVRP over a complete graph with 3r+1$3r+1$ vertices. We propose a similar transformation that reduces this graph to 2r+1$2r+1$ vertices, with the additional restriction that a previously known set of r pairwise disconnected edges must belong to every solution. Using a recent branch-and-cut-and-price algorithm for the CVRP, we observed that it yields an effective way of attacking the CARP, being significantly better than the exact methods created specifically for that problem. Computational experiments obtained improved lower bounds for almost all open instances from the literature. Several such instances could be solved to optimality.     

Network service scheduling and routing

Real‐life vehicle routing problems generally have both routing and scheduling aspects to consider. Although this fact is well acknowledged, few heuristic methods exist that address both these complicated aspects simultaneously. We present a graph theoretic heuristic to determine an efficient service route for a single service vehicle through a transportation network that requires a subset of its edges to be serviced, each a specified (potentially different) number of times. The times at which each of these edges are to be serviced should additionally be as evenly spaced over the scheduling time window as possible, thus introducing a scheduling consideration to the problem. Our heuristic is based on the tabu search method, used in conjunction with various well‐known graph theoretic algorithms, such as those of Floyd (for determining shortest routes) and Frederickson (for solving the rural postman problem). This heuristic forms the backbone of a decision support system that prompts the user for certain parameters from the physical situation (such as the service frequencies and travel times for each network link as well as bounds in terms of acceptability of results) after which a service routing schedule is suggested as output. The decision support system is applied to a special case study, where a service routing schedule is sought for the South African national railway system by Spoornet (the semi‐privatised South African national railways authority and service provider) as part of their rationalisation effort, in order to remain a lucrative company.     

Lower and upper bounds for the mixed capacitated arc routing problem

This paper presents a linear formulation, valid inequalities, and a lower bounding procedure for the mixed capacitated arc routing problem (MCARP). Moreover, three constructive heuristics and a memetic algorithm are described. Lower and upper bounds have been compared on two sets of randomly generated instances. Computational results show that the average gaps between lower and upper bounds are 0.51% and 0.33%, respectively.     

A deterministic tabu search algorithm for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a difficult optimisation problem in vehicle routing with applications where a service must be provided by a set of vehicles on specified roads. A heuristic algorithm based on tabu search is proposed and tested on various sets of benchmark instances. The computational results show that the proposed algorithm produces high quality results within a reasonable computing time. Some new best solutions are reported for a set of test problems used in the literature.     

A tabu search algorithm for the min–max k-Chinese postman problem

In this paper we present a tabu search algorithm for the min–max k-Chinese postman problem (MM k-CPP). Given an undirected edge-weighted graph and a distinguished depot node, the MM k  -CPP consists of finding k>1$k>1$ tours (starting and ending at the depot node) such that each edge is traversed by at least one tour and the length of the longest tour is minimized. A special emphasis is put on investigating the trade-off between running time effort and solution quality when applying different improvement procedures in the course of the neighborhood construction. Furthermore, different neighborhoods are analyzed. Extensive computational results show that the tabu search algorithm outperforms all known heuristics and improvement procedures.     

Plowing with precedence: A variant of the windy postman problem

In winter, a common problem is to determine the route that a snowplow should take in order to minimize the distance traveled. We propose a variant of this arc routing problem that is motivated by the fact that deadhead travel over streets that have already been plowed is significantly faster than the time it takes to plow the street. This problem differs from most arc routing problems because the cost of traversing a street changes depending on the order of the streets on a route. We develop a method that generates near-optimal solutions to instances as large as 200 nodes.     

Exploiting sparsity in pricing routines for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a well-known and fundamental vehicle routing problem. A promising exact solution approach to the CARP is to model it as a set covering problem and solve it via branch-cut-and-price. The bottleneck in this approach is the pricing (column generation) routine. In this paper, we note that most CARP instances arising in practical applications are defined on sparse graphs. We show how to exploit this sparsity to yield faster pricing routines. Extensive computational results are given.     

An improved heuristic for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is an important and practical problem in the OR literature. In short, the problem is to identify routes to service (e.g., pickup or deliver) demand located along the edges of a network such that the total cost of the routes is minimized. In general, a single route cannot satisfy the entire demand due to capacity constraints on the vehicles. CARP belongs to the set of NP-hard problems; consequently numerous heuristic and metaheuristic solution approaches have been developed to solve it. In this paper an “ellipse rule” based heuristic is proposed for the CARP. This approach is based on the path-scanning heuristic, one of the mostly used greedy-add heuristics for this problem. The innovation consists basically of selecting edges only inside ellipses when the vehicle is near the end of each route. This new approach was implemented and tested on three standard datasets and the solutions are compared against: (i) the original path-scanning heuristic; (ii) two other path-scanning heuristics and (iii) the three best known metaheuristics. The results indicate that the “ellipse rule” approach lead to improvements over the three path-scanning heuristics, reducing the average distance to the lower bound in the test problems by about 44%.