Recent Survey on Bases Routing Problems : CPP, RPP and CARP

Recent Survey on Bases Routing Problems : CPP, RPP and CARP

Kawtar Akoudad

PhD student, Laboratory of Manufacturing, Energy and Sustainable Development, École Supérieure de Technologie, Road of Imouzzer BP: 2427 Fès

Fouad Jawab

Professor at Ecole Supérieure de Technologie, laboratoire de Management International de techniques de décision et de logistique Road of Imouzzer BP2427Fès

Abstract

Although they allow modelling a large number of real applications, arc routing problems were much less studied compared to nodes routing problems. The arc routing problem consists in determining, for a set of customers located along the streets or a set of street when itselves require a service, by which vehicle they will be visited and at which moment in the tour they will be. These problems have later known a tremendous interest by the scientists working in various fields such as applied mathematics, computer science, information technology, and the economics field etc., what gave rise to a very rich literature. Our contribution through this article consists of an extension of the surveys conducted until now with a focus on the three basic routing problems the CPP, the RPP and the CARP since there is an emergence of new models that take into account additional constraints without forgetting the new methods developed to solve them.

1. Introduction

   The transport activity is a very important post cost of logistics thus logistics organization is often dependent on the optimization of transport costs which is realized only through an organization of vehicle routing. Better organization of the latter presents a major potential of savings, hence the appearance of the vehicle routing problem (VRP). The standard form of the VRP consists of delivering, at a lower cost, the goods stored in a location (for example a warehouse) to a multiple clients (warehouses, companies, factories, villages, etc.). This distribution is carried out by a fleet of vehicles placed in a warehouse where each tour starts and ends. This problem is an extension of the classical traveling salesman problem. Moreover, each VRP can be considered as a set of multiple dependent

   TSP problems. In the classical problem, the number of vehicles is fixed, and the cost depends only on the kilometers traveled. The objective is to establish the itinerary of each vehicle so as to meet the demands of customers and minimize the total distance traveled by vehicles.

   Several variations of this problem have been defined. They form a vast field due to their theoretical and practical interest that has attracted the attention of many managers and business leaders as well as scientific researchers working in various areas such as applied mathematics, computer science, technology information and economics domain. Two types of VRP problem emerge depending on the position of the clients: i) the nodes vehicle routing problem where clients are represented by localities (vertices or nodes of the graph) in the network. ii) the arcs vehicle routing problem, where clients are represented by roads (arcs or edges of the graph) in the network.

   Given their complexity, arcs routing problems were much less studied, compared to nodes routing problems, although they can model many real-world applications such as postal delivery, waste collection, meter reading, and winter gritting.

   One of the pillars of the arc routing problems (ARP) is the Chinese postman problem (CPP) whose objective is to find a closed tour of minimal cost or length covering each arc at least once. The origin of the CPP is the Königsberg bridge problem solved by Euler (1736), which consists in determining whether there is any closed tour crossing each of the seven bridges exactly once. The second pillar is the rural postman problem (RPP), introduced by Orloff in 1974 [1], in which only a subset of links required must necessarily be crossed. The third basic problem is the capacitated arc routing problem (CARP), introduced by Golden and Wong (1981), which consists in finding tours at

   minimal cost so that: the total demands of all served arcs by a vehicle does not exceed its own capacity, every tour is ensured by a vehicle that leaves and returns to the depot, and each required edge, which has a strictly positive demand, is traversed by at least one vehicle.

   These problems have been addressed progressively by the scientific community, starting with simplified case and adding difficulties one by one. This has led to approach more and more, through extensions, real applications from the private and public world. Among the classic books that have treated these problems from a theoretical point of view, we find: Christofides [2], Fleischner [3], Evans and Minieka [4], and Assad and Golden [5]. The more recent book was edited by Dror [6]. Wöhlk [7] has reviewed the most recent research in the arc routing field focusing mainly on the CARP problem and its variants. Corberán and Prins [8] presented a bibliography gathering the arcs routing problems.

   Our contribution through this article consists of an extension of the surveys conducted until now with a focus on the three basic routing problems the CPP, the RPP and the CARP since there is an emergence of new models that take into account additional constraints without forgetting the methods developed to solve them. We consider interesting to include, beside the recent research, the previous works, whenever it became important. In order, in our opinion, to introduce the researcher to the arc routing field, allowing him to discover what already exists and to open ways to new aspects of research.

   This article is organized as follows. Section 2 is devoted to a detailed presentation of the basic problems (CPP, RPP, CARP) tackled and their extensions. Section 3 evokes real-world applications of these problems and their extensions from both the private and public world. Section 4 covers the exact and approximate methods of resolutions used to solve them.

2. Bases routing problems and their extensions

   1. The Chinese postman problem (CPP)

      The Chinese postman problem (CPP), so named in the honor of the Chinese mathematician Meigu Guan who introduced it in 1962[9], is the basic problem of the arc routing problems. It consists in finding a minimum length tour traversing at least once each edge of an undirected graph (UCPP). Later, this problem has been extended to directed graphs with arcs (DCPP) and to mixed graph (MCPP) containing arcs and edges. In literature, UCPP and DCPP have been well studied and

      resolved in polynomial time. However, the MCPP appears to be a NP-hard problem that still relatively unexplored. The CPP has several extensions which take origin from real applications. The Hierarchical Chinese Postman Problem (HCPP), introduced by Dror et al. (1987) [10], is one of those extensions where the arcs partitioned into priority classes are controlled by a precedence relation. Thus, the problem is to determine a tour from a depot that crosses all edges obeying to the precedence relation mentioned. Dror et al showed that, in general, the problem is NP-hard. When the cost of crossing edges depends on the direction, we found the Windy Postman Problem (WPP), introduced by Minieka [11]. Brucker [12] and Guan [13] showed that this problem is NP-hard but resolvable in polynomial time for an Eulerian graph. Another interesting variant of the CPP is the Chinese Postman Problem with Maximum Benefit (MBCPP), studied by Pearn and Wang [14], in which each edge of the network is associated with: a service cost when the crossing is accompanied by a servce, a cost for crossing without service, and a generated profit whenever an edge is traversed. The objective of MBCPP is to find a tour crossing a set of edges selected with a total net profit maximized. Another special case of the CPP is the Chinese Postman Problem with Time Window (CPPTW) tackled by Aminu and Eglese [15]. In this problem the constraints of time slots are introduced so that the departure time and the arrival time of a vehicle are specified for the performance of the service of each edge. Adding constraints of time windows makes the problem more difficult to solve. This also means that the problem is NP-hard Dror [6].

   2. The rural postman problem (RPP)

      In the previous section, we dealt with problems in which all the links on a given graph should be covered, here we consider the rural postman problem (RPP), introduced by Orloff [1] in which only a subset of links required to be compulsorily traversed. This problem may be solved in polynomial time if it is defined on an undirected (URPP) or directed (DRPP) graph, and that the edges or arcs required form a connected graph. Otherwise, the RPP is NP-hard in the general case, Lenstra and Rinnoy Kan [16]. As the CPP, RPP has several extensions including the Windy Rural Postman Problem (WRPP) introduced by Benavent et al. [17], which is a generalization of the WPP where only a subset of edges is to be treated. Another variant of the RPP is the Prize Collecting Rural Postman Problem (PCRPP) introduced by Araoz et al. [18]. The main difference is that instead of having edges required, there is a profit function that governs the edges. The benefit can only be obtained the first time an edge is

      traversed. The objective of PCRPP is to find a crossing that maximizes the following function: total profit obtained by using the edges minus the cost of the crossing. Taking into account the same objective but with restrictions on the maximum length of the crossing and the number of times the benefit can be obtained from an edge, Feuillet et al. [19] introduced another problem called Profitable Arc Tour Problem (PATP). The Rural Postman Problem with Turn Penalties (RPPTP), studied by Benavent and Soler [20] in a directed graph and Corberan and al. [21] in a mixed graph, also generalizes the RPP. This generalization consists in associating a non-negative penalty to every turn as well as taking into consideration the existence of forbidden turns. A solution tour must traverse all the required arcs and edges of the graph without producing any prohibited turn. The total cost of the tour is the sum of the costs of arcs and edges traversing and penalties associated with the turns. Arbib et al. [22] presented in their paper, a new extension of the RPP, which combines profitable arc routing with the facilities location problem. This extension is the Directed Profitable Location Rural Postman Problem (DPLRPP). In this problem, profitable arcs must be selected as well as the facilities located on the two ends points of the arc, and a tour must be identified in order to maximize the difference between the benefit collected along the arcs, the cost of crossing arcs and the cost of equipment installation. The RPP with Deadline Classes (RPPDC) is an extension of the RPP having specific time windows as a constraint. The problem was studied by Letchford and Eglese [23]. It entails finding minimum cost path crossing a subset of edges R of a graph where this subset is divided into a number of deadline classes R1, R2, …, RL, each class having its own service time: the customers in R1 must be serviced in the time T1, the customers in R2 must be serviced in the time T2, and so on. Another problem with time constraints is the Periodic RPP (PRPP), in which each required edge must be visited several times over a planning period of m-day so that the days of service are equally spaced. The problem introduced by Ghiani et al. [24] is to decide on which days each required edge must be served and to design a tour for each day of the planning period so that the total distance travelled during the m- day period is minimal.

   3. The Capacitated Arc Routing Problem (CARP)

      The CARP, introduced by Golden and Wong [25], consists in finding tours at minimal cost so that: the total demand of all arcs served by a vehicle does not exceed its own capacity, each route is provided by a

      vehicle that leaves and returns to the depot, and each required edge, which has a strict positive demand, is traversed by at least one vehicle. It can be defined either on an undirected, directed or mixed graph giving respectively the UCARP, DCARP or MCARP problems. CARP is a generalization of the Chinese Postman Problem with Capacity (CCPP) Christofides [26], this indicates that it is an NP-hard problem Dror [6]. The CARP has several variants arising from real applications. Among these variants we find the CARP with Profit (CARPP) introduced by Archetti et al. [27] in an undirected graph. In this problem, a profit and a demand are associated to each edge of a set of profitable edges, travel time is associated to each edge of the graph and a maximum travel time of every vehicle is also given. The edge profit can be collected by only one vehicle just when the crossing is accompanied by a service. The objective of this problem is to find a set of tours that satisfy the constraints on the duration of the road as well as the vehicle capacity and maximizes the total profit collected. A different type of the CARP extension, which takes into account the constraints of time, gather the CARP with Time Window (CARPTW) tackled by Wöhlk [28] and introduced in its oriented version by Mullaseril [29] and the Periodic CARP (PCARP) introduced by Lacomme et al. [30]. The CARPTW consist on serving a set of edges with the restriction that the service of each required edge must start in a preset time interval. While the PCARP resembles to the PRPP problem with as difference the capacity constraint. The CARP with Multiple Centers (CARPMC) studied by Amberg et al. [31], is a part of the CARP with multiple facilities. The problem is defined on an undirected network with vehicles departure takes place from several depots and/or with different requirements in terms of capacity. Del Pia and Filipi [32] addressed a problem whose originality lies in the need to make appointments between the vehicles along their routes so that small vehicles can discharge their contents into the large ones and continue their work. These vehicles can be qualified as a mobile depot. They called this problem CARP with Mobile Depots (CARP-MD). In the same sense, Amaya et al.

      [33] introduced the CARP with Refill Points (CARPRP) where there are two different types of vehicles: the first type, which has a finite capacity, is used to serve the arcs and the other type to replenish the first type at certain nodes. For technical reasons, the last ones must return to the depot after each appointment. The CARPRP can be considered as an arc routing problem with location (LARP) because besides crossing edges or arcs, refill points must be located on the graph. Ghiani et al. [34] introduced the CARP with intermediate facilities (CARPIF) where all

      the nodes of an undirected network include the depot as well as certain intermediate facilities. The objective is to design an itinerary for a single vehicle consisting of successive segments. The first segment begins from the depot and ends at an installation, optional intermediate segments bind two installations and the last segment binds the installation at the depot. Labadi et al. [35] discussed another type of extension by introducing the Split Delivery CARP (SDCARP) in a directed graph where each edge can be served by several vehicles. When the required edges have a demand for different products and these products should be kept separated during transportation, then the problem is called Multiple Compartment CARP (MCCARP). This problem was introduced by Muyldermans and Pang [36].

      Stochastic versions of the CARP (SCARP) introduced by Fleury et al. [37] have received very little attention. The SCARP is similar to the Deterministic CARP (DCARP), except that positive demands qij in the second problem becomes positive random variables Qij. All remaining aspects of the problem are assumed deterministic. This leads to the possibility of route failures whenever the realized demand exceeds the vehicle capacity. The stochastic demands make the SCARP different from the CARP with respect to two issues: i) at some point along a route, the actual accumulated demand might exceed the vehicle capacity. This event is denoted as a failure. ii) The objective is to find a collection of routes with minimum expected cost. If a failure occurs on some route, an action is taken in order to complete the originally planned route. The actual recourse action is based on a recourse strategy, which is decided upon a priori to the construction of the routes.

      The single objective CARP only deals with: minimizing the total cost of the trips, whereas, the real application of CARP may need to take into account several objectives such as the total cost of the trips and the cost of the longest trip (corresponding to the makespan in scheduling theory). The Multiobjective CARP (MOCARP) introduced by Lacomme et al. [38] is the logistic problem in which a set of clients is serviced by a fleet of vehicles, with the aim of minimizing several objectives.

      The Open Capacitated Arc Routing Problem (OCARP) is a NP-hard combinatorial optimization problem where the objective is to find a minimum cost set of tours which services a subset of edges with positive demand under capacity constraints. This problem introduced by Usberti et al. [39] is related to the CARP but differs from it since the tours are not constrained to form cycles, and therefore both open and closed tours are possible.

      In order to have a panoramic view that covers all bases problems and their extensions as well as the relationships between them, we considered interesting to regroup these elements in a schema (Figure 1). This schema is comprised of four columns: The first column on the left contains the basic problems of routing (CPP, RPP and CARP) besides the links of passages enter these problems. Thus the RPP is a CPP with a set of required links to treat, the CARP is a RPP with capacity constraints and the CARP is a CPP with both conditions. The second and third columns include constraints (generalized in the first and more detailed in the second) allowing to obtain extensions to the basic problems which led to the last column that contains problems (extensions) used to model several real applications.

      Figure 1. Basic routing problems and their extensions

3. Real Applications of the bases routing problems and their extensions

   The Konigsberg bridge problem solved by Euler in 1736 can be considered as the first application of arc routing view it mainly treats the crossing of a certain number of arcs in a transportation network. Since then, many applications concerning road networks have appeared. There are applications where it is necessary to maintain roads or offer them services such as the mail delivery, the waste collecting, the street cleaning, the milk collecting, the inspection of power lines, the meters readings of water and electricity, the roadsides mowing, the weeding, the snow removal, and the snow blowers itineraries, etc. Each of these applications may contain several constraints allowing it to be handled by the extensions of the bases routing problems namely CPP, RPP and CARP.

   The street cleaning as outlined by Bodin and Kursh

   [40] is a practical application of the arc routing, where each street must be cleaned in a specified time window. Eglese [41] tackled the problem of the snow blowers itinerary where some streets must be maintained within two hours, others in four hours etc. This problem can be clearly regarded as a CARPTW. Flights in an airline are scheduled and have a fixed start date and therefore can be considered to have zero- length/ short time windows, resulting in an extra complicated version CARPTW, Ericsson and al. [42].

   Lacomme and al. [30] gave as an example the spraying of herbicides on the rails: the amount and time spent per meter are fixed for the whole day. Another example of the PCARP is the waste collection. This collection is normally scheduled on one or two weeks, and the waste production of every street leads to a frequency of service during the period of the horizon (for example, twice a week). Monroy and al.

   [43] meanwhile studied the PCARP through the monitoring activities. Streets or roads to visit are divided into categories. Each road category has different monitoring requirements (number of crossings) during the sub-periods over the entire time horizon.

   In the context of private companies seeking to maximize their profits, an edge would not be served unless it leads to a profit for the company Palma [44], hence the necessity of modelling the problem by the PRPP. Examples where this principle is applied include the collection of recycling bins and mail service managed by a private entity. Feuillet et al. [19]

   studied a problem of tactical planning of freight arising from the automotive industry, where a series of trips must be made between plants. This problem expressed as profitable arc tour problem, is defined on a graph in which profits and travel costs are associated with arcs. Also the routing problems with profits have very interesting applications in the context of auctions in the transport field, as a tool for decision support for carriers. In this area the problem for a carrier becomes the problem of identifying the subset of potential customers that maximize the profit obtained while satisfying the constraint on the length of each route and the vehicle capacity. This problem can be modelled by the UCARPP, Archetti and al. [27].

   Regarding Arbib et al. [22], they discussed a new field of application which is the passenger /freight transport for medium / long distance, for example, the interurban bus services, the airlines and the interstate road transport. This type of problem modelled by the DPLRPP requires specific facilities such as vehicle depots, relay boxes, landfills or reorder points. It combines both the arc routing with profits and the facility location.

   Del Pia and al. [32] tackled the CARP-MD problem. The originality of the problem lies in the need for setting appointments between vehicles along their routes so that small vehicles can discharge their contents into the big ones (not having access to the narrow streets) during the waste collection. The road maintenance or road markings where there are specific operational conditions which oblige the truck to return to the depot whenever it encounters the vehicle road marking, Langevin and al. [45], is close to the previous problem. This problem is treated as CARPRP. A well-known application of the MCCARP is the collection of waste separated at the source (from households) by partitioned trucks, Muyldermans and Pang [36], instead of using specialized trucks for each type of waste. Other intermediate facilities are mainly present during the winter salting or the cleaning of streets to collect the salt or sand as well as the water and detergent. Ghiani and al. [34] treated this

   application as CARPIF problem.

   For some practical situations the demand of each edge is better described by a random variable. An example of this could be stochastic snow depths due to drifting or stochastic amount of refuse from households and industries. Hence the uses of SCRAP, Fleury et al.

   [37] in which all positive demands are described by random variables.

   The motivation behind the study of the MOCARP lies in the study of real situations where companies working in the logistic distribution field deal with complex operational strategies, in which different actors (trucks, drivers, and customers) have to be

   allocated within a unified framework by taking into account opposite needs and different employment contracts.

   The OCARP occurs naturally in many real-life situations, especially when the tasks are served by external logistics providers (Sariklis and Powell [46]; Pan et al. [47]). In this situation the vehicles are loaded into a depot, however once all required arcs are served, the vehicles hired from third-party logistics companies need not return to the start depot. OCARP also find an application in the Meter Reader Routing Problem (MRRP) which does not consider a depot since the employees responsible for metering are taken by auto from the office to the address of their first card, and after completing their routes, they take public transportation to return home.

4. Resolution methods of the bases routing problems

   1. The Chinese postman problem (CPP) and its extensions

      1. The Chinese postman problem (CPP)

         The Chinese postman problem (CPP) can be solved in polynomial time in both undirected (UCPP) and directed (DCPP) versions while it is NP-hard as it is set in a mixed graph (MCPP). It should be noted that except a few variations, most of the works treated the CPP has been done on the mixed version. It is possible to solve the MCPP in polynomial time if the graph is even, by proposing the so-called Even-MCPP algorithm, Edmonds and Johnson [48]. Frederickson

         [49] proposed two heuristics that can best lead in the worst case to a ratio of 5/3. Raghavachari and Veerasamy [50] proposed a modification to the algorithm which gave birth to a better ratio 3/ 2 through a new lower bound. Grötschel and Win [51] have proposed a cutting plane method to solve the Windy Postman Problem (WPP) which can also be applied to solve the MCPP. This method is also used by Nobert and Picard [52] to solve exactly the MCPP as long as the graph is Eulerian. Corberán et al. [4] presented a Greedy Random Adaptive Search Procedures (GRASP) for instances with up to 200 nodes and 600 links. In the same year, Yaoyuenyong et al. [53] have reviewed the algorithms of Frederickson [49], Pearn and Liu [54], and Pearn and Chou [55] and developed a new heuristic called the Shortest Additional Path Heuristic (SAPH), which uses at several times the Dijkstra algorithm with some modification to the costs in the graph looking for a possible improvement. Jiang et al. [56] have attempted to address the problem through a genetic algorithm that has proven to be effective and better than the existing approximation algorithms.

      2. The Windy Postman Problem (WPP)

         The Guan algorithm (1984) first considers a simple transformation that converts the WPP to a standard CPP (undirected one). The resulting CPP is then solved optimally using the matching algorithm. Win [57] considered a procedure which has improved the Guan algorithm and solved the WPP optimally on the resulting network. Grötschel and Win [51] showed that the best exact method to solve the WPP is the cutting plane method. In their article Pearn et al. [58] presented a modification to the Guan algorithm they called the modified Guan algorithm. They also introduced a resolution process called reverse Win algorithm to approximately solve the WPP. The calculation results indicated that the modified algorithm indeed improves the initial procedure by about 4%. Raghavachari et al. [50] also modified the Win algorithm in order to have a ratio of 3/2. Yan and Thompson [34] proposed exact and heuristic algorithms based on the branch and bound procedure. While Corberán et al. [59] proposed a Branch and cut procedure based on the cutting plane algorithm.

      3. The Hierarchical Chinese Postman Problem (HCPP)

         Lemieux and Campagna [60] proposed simple heuristic procedures for snow removal problem whose streets are classified into primary and secondary streets. Alfa and Liu [61] considered a lower precedence relationship which requires that the crossing of a class Ei begins before the crossing of Ei+1 and ends before the end of the crossing of Ei+1. Dror et

         al. [62] presented an algorithm of O (kn5) complexity,

         where k is the number of classes, for the HCPP whose graph is undirected and where all the sub graphs induced by the priority relation are connected. Ghiani and Improta [63] and Korteweg and Volgenant [64] described several algorithms for the same case and successfully attempted to improve the complexity from O (kn5) to O (kn4). Cabral et al. [65] described a transformation of the HCPP to the Rural Postman Problem (RPP). The HCPP is solved optimally using an exact algorithm branch and cut on the transformed problem (RPP).

      4. The maximum benefit Chinese postman problem (MBCPP)

         Malandraki and Daskin [66], who studied the problem in its oriented version, modelled the problem as a minimum cost flow with the constraint of removing the tour does not visit all the links. Based on

         this approach, they proposed a branch and bound procedure and solved instances with 25 nodes. Pearn and Wang [67] presented a sufficient condition for MBCPP solution to cover the entire network, and provided an upper bound. They proposed a procedure that applies the minimal spanning tree algorithm and the minimal cost matching algorithms. In 2005, the same authors proposed algorithms based on the method of construction and local search. They report the calculation results on graphs with up to 30 nodes and 780 arcs. Corberán et al. [68] proposed an integer programming formulation for the undirected MBCPP and, according to the description of its associated polyhedron, they proposed a branch and cut algorithm and presented the calculation results on instances with up to 1000 vertices and 3000 edges.

      5. The Chinese postman problem with time window (CPPTW)

         Aminu and Eglese [69] proposed two linear programming solutions. The first approach the problem directly, the second turns it into a problem of nodes routing with time window. The results are calculated on instances with a maximum number of 69 edges they indicate that optimal solutions can be obtained quickly when the time windows are tight.

         1. The Rural Postman Problem (RPP) and its extensions

            1. The Rural Postman Problem (RPP)

               The RPP has been addressed in several publications on the ARP and multiple algorithms have been developed to solve this problem in its undirected version (URPP) including exact algorithms introduced by Christofides et al. [70] and treated by divers other researchers: Corberán and Sanchis [71], Letchford [72], Ghiani and Laporte [73] and Fernandez et al. [74]. Also many heuristics have been developed in this area as the constructive heuristics proposed by Frederickson [49], with the best known approximation ratio for the RPP, Pearn and Wu [75], and Ghiani et al.

               [76] whose results are competitive with those of Frederickson without forgetting the improvement procedures described by Hertz et al. [77]. In a first, Rodrigues and Ferreira [78] tried to solve the problem by transforming it into a traveling salesman problem (TSP). The TSP has been solved by applying the Ant Colony Algorithm (ACS), Dorigo and Gambardella [79]. Finally, the TSP solution was transformed into a URPP one. The ACS was also used by Lagana et al.
               [80] and Pérez-Delgado [81] who developed the Rank- Based Ant System (RBAS) which was more efficient than the ACS algorithm. Baldoquín et al. [82]

               developed a meta-heuristic based on both GRASP and a genetic algorithm comparable to the Monte Carlo method, Fernández de Córdoba et al [83]. In 2004, Baldoquín [84] introduced a new hybrid approach to solve the URPP based on a Simulated annealing (SA), a GRASP and a genetic algorithm. An approach that has led to better results than those given by the Monte Carlo method. In recent years, neural models have been used to solve the traveling salesman problem, which inspired Perez-Delgado and Matos-Franco [85] who proposed a heuristic based on the application of the Self-Organizing Feature Map (SOFM) to solve the URPP after transforming it into a TSP. Holmberg [86] proposed heuristics that improve te one proposed by Freerickson as well as two heuristic of post-processing for the removal of unnecessary detours. Rodrigues et al. [87] present an original approach based on memetic algorithms which involves processes of cooperation and competition between the elements of the population and includes the social knowledge, using a local search procedure. In its direct Version (DRPP), Christofides et al. [88] presented a branch and bound algorithm based on bounds computed using the Lagrangian relaxation (with the minimum weight spanning tree) and on the comprehension of some of the tree nodes according to the solution of the minimal cost flow problem. Computed results are given for graphs with up to 80 vertices, 179 arcs including 71 required arcs. Several approaches RPP in its mixed Version MRPP can be found in various documents: Laporte [89], Corberan et al. [90] and Corberan et al. [91]. The first article describes the transformation of the MRPP into an asymmetric traveling salesman problem (ATSP). Then, the exact algorithms and heuristics used to solve the ATSP (see, for example, Laporte [92] can be applied to the resolution of the MRPP. The second article presents both a constructive and Tabu search algorithms. Finally, the study of the polyhedron associated with the MRPP is one of the subjects of the third article.

            2. The windy rural postman problem (WRPP)

               To our knowledge, the only papers dealing with the WRPP is that of Benavent et al. [17, 93]. The first article extends the formulation of WPP given by Grötschel and Win [51] to the rural case. The authors suggest a linear programming formulation beside several heuristics and bounds. Lower bounds are obtained by means of a cutting plane procedure. The upper bounds are calculated using three constructive heuristics and several improvement procedures. The cutting plane algorithm has been able to resolve 185 of the 288 cases tested. In the second article, the authors presented new heuristic algorithms improving

               constructive algorithms discussed in Benavent et al. [17]. They describe four multi-start procedures, which were obtained by randomizing some steps of the constructive algorithms. Also, they presented a scatter search algorithm that combines the best previous procedures.

            3. Prize-collecting Rural Postman Problem (PCRPP)

               Aráoz et al. [94] proposed the first algorithmic solution for PCRPP. Their algorithm contains two stages, each of the two phases using a different solver. The first phase gives an approximate solution to the PCRPP through a system of linear inequalities with a heuristic solution which is an adaptation of the 3T heuristic for the RPP, Fernandez et al. [74]. The second phase uses the first solution to obtain an optimal solution of the problem, while, Palma [44] developed a model based on Tabu search algorithm (TS) to solve the PCRPP. This algorithm has two phases. The first phase generates two possible solutions from two constructive algorithms. These algorithms are called Union of Connected Components and Successive Elimination of Connected Components. The second phase consists in applying the TS that improves the initial solutions.

            4. Directed Profitable Rural Postman Problem

               Archetti et al. [27] proposed a formulation of mathematical programming and integer linear programming (ILP-) refined through a Tabu Search to solve the DPRPP. A basic outline of the TS is improved through a process of reoptimization, intensification and diversification strategies. In addition, technical ILP-improvement is used to improve the best solution found by the TS algorithm. Arbib et al. [22] addresses the same problem but this time it combines the arc routing with profits and facility location Directed Profitable Location Rural Postman Problem. They presented a linear programming formulation and a branch-and-cut algorithm for solving the DPLRPP. The algorithm could solve instances with up to 140 vertices and 190 arcs and up to 50 vertices and 203 arcs.

            5. The Rural Postman Problem with turn penalties (RPPTP)

               Benavent and Soler [95] considered in their article the existence of prohibited tours in a search of an optimal solution of the rural postman problem directed. These authors propose to solve this problem optimally by turning it into an Asymmetric Traveling Salesman

               problem (ATSP). Several heuristics to solve it are presented and tested in 30 cases, six of them corresponding to areas of a real city. Special cases of the same problem in which all the U-turns are prohibited and where there is no penalty for the remaining visits are in Benavent and Soler [96] and Soler [97]. Corberan et al. [71], and in order to solve the problem in its mixed version MRPPTP, also turned the problem into a ATSP then solved transformed problem by using exact methods and classical heuristics for the ATSP. They also presented a heuristic that directly solves the MRPPTP.

            6. The rural postman problem with deadline classes (RPPDC)

               Routing problems with time windows in general are extremely difficult to solve, however, the time windows in a particular problem may have a special structure that can be exploited. Letchford and Eglese

               [23] considered a problem of arc routing with a single vehicle in which the arcs are divided into deadline classes and presented an optimization algorithm based on the use of valid inequalities such as cutting plane.

            7. Periodic Rural Postman Problem (PRPP)

         To our knowledge, the only methodological document about periodic arc routing problem is the one presented by Ghiani et al. [24]. In this paper, the authors have developed a heuristic which first selects the same combination of days of service for all the edges with a given frequency service then performs a local search in order to obtain cost savings. Local search phase allows the use of an innovative neighborhood structure.

         1. Capacitated arc routing problems (CARP) and its extensions

            1. Capacitated arc routing problems (CARP)

               Although the CARP is NP-hard, few exact algorithms were developed to solve small and medium instances. Hirabayashi et al. [98] as well as Kiuchi et al. [99] presented a Branch and Bound method while Belenguer and Benavent [100] developed a cutting planes algorithm that has been tested on instances with up to 50 nodes and 97 arcs. Transformations of the CARP into a capacitated vehicle-routing problem were described by Eglese and Letchford [101], Longo et al. [102], and Baldacci and Maniezzo [103] who developed a branch-and-cut algorithm to solve the problem. This algorithm is also used recently by Ghiani et al. [104] in order to solve the CARP. Branch- and-cut-and price algorithms were proposed by Gómez-Cabrero et al. [105] and by Letchford and

               Oukil [106] and lower bounding procedures were presented by Benavent et al. [107], Amberg and Voss[108], Wøhlk[28], and Belenguer and Benavent [109, 110]. Welz [111] has suggested a number of valid inequalities for a formulation based on flow variables.

               Considerable research has been devoted to the development of heuristic procedures which gives approximate solutions to the CARP; the current best approximation factor is 7/2-3/D, where D is the vehicle capacity. These heuristics (usually called constructive heuristics) provide good solutions in an acceptable time. To name a few, Golden and Wong [25] proposed a constructive heuristic called augment-merge. Then Golden et al. [112] proposed another heuristic called path scanning, which has been improved by Ulusoy

               [113] to form a new heuristic called the Ulusoy heuristic. Pearn [114] proposed an approximate algorithm and augment-insert heuristic in 1991 to solve the CARP. Mourao and Amado [115] proposed a heuristic method for mixed CARP and showed that it outperforms all previous heuristics. Amponsah and Salhi [116] proposed an effective constructive heuristics integrated into a strategy and into the improvement of the pre-analysis procedures. The compaison of computational performance between several heuristics for the CARP can be found in Coutinho-Rodrigues and al. [117].

               For 15 years, several meta-heuristics have been developed to solve the CARP. These include the Tabu Search algorithm (Eglese and Li [118] ; Hertz et al. [119]; Gierstorfer [120] ; Eglese and Brandão [121] and Mei et al. [122], the guided local search Beullens and al. [123], the memetic algorithms (genetic algorithms enhanced with a local search procedure) Lacomme et al. [124], and ant colony optimization ((Lacomme et al. [125] and Coutinho Rodrigues et al. [126]) used by Bautista et al. [127] to solve a problem of urban waste collection. In general, these meta- heuristics provide better solutions compared to constructive heuristics. Martinez and al. [128] developed an algorithm for the CARP based on local search and ideas of Biased Random Key Genetic Algorithm (BRKGA) proposed in Ericsson and al. [42] and Almeida and Goncalves [129]. BRKGA include improvements of genetic algorithms. Usberti et al. [39] gave a description of Greedy Randomized Adaptive Search Procedure (GRASP) proposed to solve the CARP, including the constructive phase, parameters reactive adjustments, local search, and the statistical solution filtering. To strengthen the search for high- quality solutions, a path-relinking was coupled to the GRASP.

            2. CARP with profit (CARPP)

               The undirected CARPP model was recently introduced by Archetti and al. [27]. To address the UCARPP, the authors propose an algorithm for Branch and price. In addition, they presented three local search heuristics: the first is a variable neighborhood search (VNS) implemented by Hansen and Mladenovic [130], while the other two algorithmic schemes use the Tabu Search (TS) (Glover, 1989). Both TS models differ on how the capacity and maximum duration constraints are handled.

               Whereas Zachariadis et al. [131] proposed a local search meta-heuristic. Two neighbor solutions are proposed, and the global search is coordinated by the use of the Promises Concept originally introduced for the vehicle routing problem with simultaneous delivery and relay services (Kiranoudis and Zachariadis [132]). Benavent et al. [133], meanwhile, presented and evaluated the formulations based on the Compact Flow for several mixed capacitated arc routing problems with profits.

            3. CARP with time window (CARPTW)

               Several studies have addressed the CARP with time window including three theses produced by Mullaseril [134], Gueguen [135] and Wöhlk [28]. The first two researchers proposed respectively heuristic approaches and a linear model to solve the problem after transforming it into a vehicle routing problem with time windows. Wöhlk, meanwhile, presented a dynamic programming model combined with a Simulated Annealing approach. Ramdane-Cherif [136] showed that the memetic algorithm can obtain good solutions to problems on arc routing with time windows compared to insertion heuristics. Later, Labadi and al. [137] proposed a Greedy Randomized Adaptive Search Procedure (GRASP), while Wöhlk and Johnson [138] proposed a method of Column Generation and a heuristic approach to solve it. Tagmouti et al. [139] studied a closely related problem, the CARP with service costs function of time. After transforming the problem on nodes routing, they used a method of Column Generation to solve it. The dynamic version of the problem was treated five years later, the dynamic aspect considered in this work stems from changes in time intervals of service. Tagmouti et al.

               1. proposed a heuristic variable neighborhood descent, originally developed for the static version of the problem and adapted to this dynamic variant. Afsar

               2. treated first CARP with flexible time window and proposed a Branch & Price algorithm to solve it.

            4. The Periodic CARP (PCARP)

               Lacomme and al. [142] described several versions of PCARP and presented a genetic algorithm to solve them without numerical results. Chu and al. [143] developed the first mathematical model and the first constructive heuristic approach to the problem. Lacomme et al. [144] proposed a memetic algorithm that is able to simultaneously change the tactical decisions such as the treatment days of each arc and operational decisions such as trips taking place each day. Chu and al. [145] have developed and tested a greedy heuristic as well as a Scatter Search (SS) on two sets of PCARP instances. Monroy et al. [146] presented a mathematical model and a heuristic approach to solve the periodic CARP with irregular services also they presented a cluster first, Route Second approach to solve large-scale cases.

            5. CARP with mobile depots (CARPMD)

               To solve the CARP with mobile depot, Filippi and Del Pia [32] suggested a local search heuristic obtained from a Variable Neighborhood procedure proposed by Hertz and Mittaz [147] for the CARP. CARP with refill points (CARP-RP) could be considered as a CARP with mobile depot where the depots are moving towards the vehicle to replenish it. Thus, a mathematical model and a cutting plane algorithm are suggested by Amaya et al. [33] in order to solve the problem. However, the method can be used to solve only small instances. Amaya et al. [148] presented an exact method and a constructive heuristic in two steps to solve the CARPRP with multiple loads. In this paper the replenishment vehicle must not return to the depot after each meeting with the service vehicle (as is the case in the CARP-RP), therefore there is a tour to determine to this vehicle. The heuristic used to solve CARP-RP with multiple loads based on the methods proposed in Hertz [149] for the CARP.

            6. Multi-depot Capacitated Arc Routing Problem (MDCARP)

               Amberg et al. [150] proposed the route-first-cluster- second algorithm to solve the CARP with multiple centers on an undirected graph, where the consolidation phase uses the following two concepts. First, to find the required arcs, the problem is modeled as a modified version of the Capacitated Minimum Spanning Tree problem (CMST) and a heuristic is applied to obtain initial solutions. Second, some meta- strategies, namely Simulated Annealing and Tabu Search will be applied to improve the tree solutions eventually leading to better roads. Xing et al. [151]

               discussed in their article the CARP with multiple depots. They extended the existing heuristics for CARP and integrated it into a new evolutionary framework: the initial population is constructed either by Random Generation, the improved Random Path- Scanning heuristic or the improved Ulusoy heuristic. Subsequently, several different operators are used to make a selection, crossover and mutation. Finally, the partial replacement procedure is implemented to maintain the diversity of the population. Ghiani et al.

               [31] discussed a variation of the MDCARP, called CARP with intermediate facilities (CARP-IF). The problem is defined as the CARP with a single depot, but has a set of nodes called intermediate facilities (IF) where the vehicle can replenish. They developed two lower bounds for CARPIF: The first is based on the Rural Postman Problem (RPP) and the second uses a relaxation of an entire linear formulation of the problem. Polacek et al. [152] proposed, meanwhile, a meta-heuristic called Variable Neighborhood Search (VNS). Ghiani et al. [153] treated a CARPIF with length restrictions (CLARPIF) where the length of a route cannot exceed a specified upper limit. Three heuristics are developed for CLARPIF: the first is a constructive procedure based on a partitioning approach, while the second and third procedures are an adapted Tabu Search.

            7. Split delivery CARP (SDCARP)

               The SDCARP was addressed in only four works. Mullaseril, Dror, and Leung [154] proposed an adaptation of local search of Dror and Trudeau (1990) to a SDCARP with time windows. Gueguen [135] introduced a transformation of the SDCARP with time windows in a node routing problem and solved it by adapting a Column eneration approach for split delivery vehicle routing problem (SDVRP). More recently, Labadi, Reghioui and Prins [155] designed for the SDCARP a Memetic Algorithm with Population Management (MAPM), a new meta- heuristic framework presented by Sevaux and Sörensen [156]. Belenguer et al. [157] presented the first lower bound for the SDCARP computed by a cutting plane algorithm and an evolutionary local search reinforced by a MultiStart procedure and Variable Neighborhood Descent. Another problem in relation with the SDCARP is the CARP with multiple compartments. To approach the problem, Muyldermans and Pang

               [158] used a resolution that starts with the Clarke and Wright algorithm (Clarke and Wright [159]) in order to obtain an initial solution. This solution is then improved through movements of local search: 2-opt, re-insertion, relocation, exchange and the crossing. To accelerate the researches, they applied neighbor lists

               and marking mechanisms. Finally, they combined their procedure with the Guided Local Search (Voudouris and Tsang [160]) to ensure high quality solutions.

            8. Stochastic CARP (SCARP)

               The SCARP was first considered in Fleury et al.

               1. and extended in [162]. The authors use simulation to evaluate a posteriori how solutions computed by heuristics for the DCARP are affected by random demand fluctuations. In particular, Fleury et al.

               2. contains a Memetic Algorithm (MA) proposed for the SCARP and compared with two deterministic versions based on average demands. In Fleury et al.

               3. the SCARP with Normal distributed demands was approached directly. The problem was restricted, thus a route could only fail once, and if a failure occurred on a route it would always be immediately before serving the last edge. To solve it, the authors customized the Hybrid Genetic Algorithm proposed by Lacomme et al. (2001) [164]. The framework proposed was composed of two steps: an optimization step and an evaluation of the robustness solution. Christiansen et al. [165] formulated the SCARP as a Set Partitioning Problem and solved it by a Branch-and-Price algorithm, which they applied without graph transformation. Laporte et al. [166] developed an adaptive Large-Scale Neighborhood Search heuristic (ALNS) to solve the SCARP. In this local search scheme, simple algorithms compete to modify the current solution. At each iteration an algorithm is chosen to destroy the current solution, and another one is selected to repair it. The new solution is accepted if it satisfies a criterion defined by a search paradigm applied at the master level.

            9. Multiobjective CARP (MOCARP)

               One of the first heuristic studies of the bi-objective CARP has been proposed by Lacomme et al. [167]. They approached the problem by means of a genetic algorithm inspired by the second version of the Non- dominated Sorted Genetic Algorithm framework (NSGA-II) in order to minimizing the total cost of the trips and the makespan (i.e., the cost of the longest route). This procedure is improved by using constructive heuristics to seed the initial population and by including a local search procedure. To solve the MOCARP, Mei et al. [168] proposed a memetic algorithm (MA) called Decomposition-based MA with Extended Neighborhood Search (D-MAENS). The algorithm combines the advanced features from both the MAENS approach for single-objective CARP and multiobjective evolutionary optimization. Grandinetti et al. [169] tackled a MO-UCARP with three

               competitive objectives to minimize at the same time: the total transportation cost, the longest route cost (makespan) and the number of vehicles (i.e., the total number of routes). An Approximation of the optimal Pareto front is determined through an optimization- based heuristic procedure. The E-constraint method is applied to the bi-objective version of the MO-UCARP. The third objective comes into play as a parameter of the optimization procedure.

            10. Open CARP (MOCARP)

         Usberti et al. [39] proposed a new integer linear programming formulation improving the one proposed by Golden and Wong [25] for the CARP. To solve the problem, a Reactive Path-Scanning heuristic, guided by a cost-demand edge-selection and ellipse rules, is proposed and compared with other successful CARP path-scanning heuristics from literature. One year later, Fung et al. [170] proposed an approach for solving the OCARP which Consist in transforming the problem into an equivalent closed VRP. Then proposing a mathematical formulation based on the Asymmetric Capacitated VRP with distance constraints in the graph which is transformed from the OCARP, followed by the setting of a lower bound and the development of a memetic algorithm (MA). It should be pointed out that the problem studied in Usberti et al. [39] and the one studied in Fung et al. [170] are different. Firstly, in Usberti et al. [39], it does not exist any depot, however, in the second problem each route must begin from a depot. Also, Usberti et al. [39] treated undirected connected graph, while in Fung et al. [170], the graph and the required tasks are directed.

5. Conclusion

   The ARPs form a very vast field on account of their theoretical and practical interest since they allow modeling many real applications. These applications are approached more and more by adding additional constraints to the basic problems, which are the CPP, RPP and CARP. These constraints can be time constraints, cost constraints, precedence relations that handle elements to serve, the appearance of several facility installations acting as depot, the split deliveries, the consideration of several objectives and other constraints. This gave rise to a rich literature in both modeling and solving methods. Many resolution methods have been inspired by other research areas such as neural models used by Perez-Delgado and Matos-Franco [85] to solve the RPP and several metaheuristics resulting of hybridization process have emerged as Rank-Based Ant System developed by Pérez-Delgado [81], which proved to be more efficient

   than the ant colony algorithm, the memetic algorithm (MA) called decomposition-based MA with extended neighborhood search (D-MAENS) proposed by Mei et al. [168] which combines the advanced features from both the MAENS approach for single-objective CARP, and multiobjective evolutionary optimization, the adaptive large-scale neighbourhood search heuristic ALNS developed by Laporte et al. [166] to solve the SCARP and several other methods. Divers constraints remain to be taken into consideration and may be subject to future research such as the quality of service proposed, consideration of environmental and safety parameters and various resolution methods can be developed taking into account the size of the instances to be treated, the time of execution and the quality of the results obtained.

6. References

1. C. S. Orloff, A fundamental problem in vehicle routing, Networks 4, 1974, pp. 35-64.

2. N. Christofides, Graph theory: An algorithmic approach (Computer science and applied mathematics), Academic Press, Inc. Orlando, FL, USA, 1975.

3. Fleishner, H., Eulerien graph and related topic, Annals of discret Mathematics 50, Amsterdam, 1991.

4. Evans, J., Minieka, E., Optimization algorithms for networks and graphs, 2nd ed., Marcel Dekker, USA, 1992.

5. Assad, A.A., and B.L. Golden, Arc routing methods and applications, In M.O Ball, T.L. Magnanti, C.L. Monma and

   G.L. Nemhauser, editors, Network Routing, Handbooks in Operations Research and Management Science 8, North- Holland, Amsterdam, 1995.

6. Dror, M., Arc routing: Theory, solutions and applications. Kluwer Academic Publishers, 2000.

7. Wøhlk S., B.L. Golden, S. Raghavan, and E. A. Wasil, A decade of capacitated arc routing. The Vehicle Routing Problem: Latest Advances and New Challenges Springer, 2008, pp. 2948

8. Corberán, A. an C. Prins, Recent results on arc routing problems: An annotated bibliography. Networks, 56(1), 2010, pp. 5069, doi: 10.1002 /net.20347.

9. M. Guan, Graphic programming using odd and even points, Chinese Mathematics 1, 1962, pp. 2737.

10. M. Dror, H. Stern, and P. Trudeau, Postman tour on a graph with precedence relation on arcs, Networks 17, 1987, pp. 283294.

11. E. Minieka, The Chinese postman problem for mixed networks, Management Science 25 (7), 1979, pp. 643-648.

12. P. Brucker, The Chinese postman problem for mixed graphs, Graph Theoretic Concepts in Computer Science Springer 100, 1981, pp. 354-366.

13. M. Guan, On the windy postman problem, Discrete Applied Mathematics, 1984, pp. 41-46.

14. W.L. Pearn, and K.H. Wang, On the maximum benefit chines postman problem, Omega 31, 2003, pp. 269273.

15. U.F. Aminu, and R.W. Eglese, A constraint programming approach to the Chinese postman problem with time windows, Comput Oper Res 33, 2006, pp. 34233431.

16. J. K. Lenstra, and K. Rinnooy, On general routing problems, Networks, 1976, pp. 273-280.

17. Benavent, E., A. Carrotta, A. Corberán, J.M. Sanchis, D. Vigo, Heuristics and lower bounds for the windy rural postman problem, DEIO technical report TR03-2003, 2003.

18. J. Araoz, E. Fernandez and C. Zoltan, Privatized rural postman problems, Computers & Operations Research 33, 2006, pp. 34323449.

19. D. Feillet, P. Dejax, and Gendreau, M., The Profitable Arc Tour Problem: Solution with a Branch-and-Price Algorithm, Transportation Science 39, 2005, pp. 539.

20. E. Benavent, and D. Soler, The directed rural postman problem with turn penalties, Transport Sci 33, 1999, pp. 408418.

21. A. Corberán, R. Marti, E. Martine, D. Soler, The Rural Postman Problem on mixed graphs with turn penalties, Computers & Operations Research 29, 2002, pp. 887-903.

22. C. Arbib, M. Servilio, C. Archetti, M. Grazia Speranza, The Directed Profitable Location Rural Postman Problem, European Journal of Operational Research, 2013, doi: http://dx.doi.org/10.1016/j.ejor.

23. A.N. Letchford, and R.W. Eglese, The rural postman problem with deadline classes, Eur J Oper Res 105, 1998, pp. 390400.

24. G. Ghiani, R. Musmanno, G. Paletta, and C.T riki A heuristic for the periodic rural postman problem, Comput Oper Res 32, 2005, pp. 219228.

25. B.L. Golden, R.T. Wong, Capacitated arc routing problems, Networks 11 (3), 1981, pp. 305315.

26. N. Christofides, The optimal traversal of a graph,

    Omega 1, 1973, pp. 719-732.

27. C. Archetti, D. Feillet, A. Hertz and M.G., Speranzaa, The undirected capacitated arc routing problem with profits. Computers & Operations Research 37, 2010, pp. 1860 1869.

28. Wøhlk, S., Contributions to Arc Routing. Ph.D. diss. PhD thesis, University of Southern Denmark, 2005.

29. Mullaseril, P.A, Capacitated Rural Postman Problem with Time Windows and Split Delivery, PhD thesis, MIS Department, University of Arizona, Tucson, Arizona 85721, 1997.

30. P. Lacomme, C. Prins, and W. Ramdane-Chérif, Evolutionary algorithms for periodic arc routing problems, European Journal of Operational Research 165, 2005, pp. 535553.

31. A. Amberg, W. Domschke, and S. Voss, Multiple center capacitated arc routing problems: A Tabu search algorithm using capacitated trees, Eur J Oper Res 124, 2000, pp. 360376.

32. A. Del Pia, and C. Filipi, A variable neighborhood descent algorithm for a real waste collection problem with mobile depots, Int Trans Oper Res 13, 2006, pp. 125141.

33. A. Amaya, A. Langevin, and M. Trépanier, The capacitated arc routing problem with refill points, Oper Res Let 35, 2007, pp. 4553.

34. G. Ghiani, G. Improta, and G. Laporte, The capacitated arc routing problem with intermediate facilities, Networks 37, 2001, pp. 134143.

35. N. Labadi, C. Prins, and M. Reghioui, An evolutionary algorithm with distance measure for the split delivery arc routing problem, Recent advances in evolutionary

    computation for combinatorial optimization, C. Cotta and J. van Hemert (Editors), Studies in Computational Intelligence 153. Springer, 2008, pp. 275294.

36. L. Muyldermans , and G. Pang, A guided local search procedure for the multi-compartment capacitated arc routing problem, Computers &Operations Research 37, 2010, pp. 16621673.

37. G. Fleury, P. Lacomme, C. Prins, Evolutionary algorithms for stochastic arc routing problems, in: G.R. Raidl, F. Rothlauf, G.D. Smith, G. Squillero, S. Cagnoni, J. Branke, D.W. Corne, R. Drechsler, Y. Jin, C.G. Johnson (Eds.), Applications of Evolutionary Computing, Springer- Verlag, Berlin and Heidelberg, 2004, pp. 501-512.

38. P. Lacomme, C. Prins, M. Sevaux, Agenetic algorithm for a bi-objective capacitated arc routing problem, Computers & Operations Research, Part Special Issue: Recent Algorithmic Advances for Arc Routing Problems 33(12), 2006, pp. 34733493.

39. F.L. Usberti, P.M. França, and A.L.M. França, The open capacitated arc routing problem, Computers & Operations Research 38 (11), 2011, pp. 15431555.

40. L.D. Bodin, and S. J. Kursh, A computer-assisted system for the routing and scheduling of street sweepers. Operations Research 26, 1987, pp. 525537.

41. R.W. Eglese, Routing Winter Gritting Vehicle,

    Discrete Applied Mathematics 48, 1994, pp. 231244.

42. M. Ericsson, M. Resende, and P. Pardalos, A genetic algorithm for the weight setting problem in OSPF routing, Journal of Combinatorial Optimization 6, 2002, pp. 299 333.

43. I.M. Monroy, C.A. Amaya, and A. Langevin, The periodic capacitated arc routing problem with irregular services, Discrete Applied Mathematics 161, 2013, pp. 691 701.

44. G. Palma, A Tabu Search Heuristic for the Prize- collecting Rural Postman Problem, Electronic Notes in Theoretical Computer Science 281, 2011, pp. 85100.

45. A. Langevin, A. Amaya, M. Trépanier, The capacitated arc routing problem with refill points, Operations Research Letters 35, 2006, pp. 45-53.

46. D. Sariklis, S. Powell, A heuristic method for the open vehicle routing problem, Journal of the Operational Research Society 51 (5), 2000, pp. 564573.

47. Z. Pan, J. Tang, R.Y.K. Fung, Synchronization of inventory and transportation under flexible vehicle constraint: a heuristics approach using sliding windows and hierarchical tree structure, European Journal of Operational Research 192 (3), 2009, pp. 824836.

48. J. Edmonds, and E.L. Johnson, Matching, Euler tours and the Chinese postman problem, Math Program 5, 1973, pp. 88124.

49. G.N. Frederickson, Approximation algorithms for some postman problems, J ACM 26, 1979, 538554.

50. Raghavachari, B., and J. Veerasamy, A 3/2- approximation algorithm for the windy postman problem, Technical Report, University of Texas, Dallas, 2001.

51. M. Grötschel, and Z. Win, A cutting plane algorithm for the windy postman problem, Math Program 55, 1992, 339358.

52. Y. Nobert and J.C. Picard, An optimal algorithm for the mixed Chinese postman problem, Networks 27, 1996, pp. 95108.

53. K. Yaoyuenyong, P. Charnsethikul, and V. Chankong, A heuristic algorithm for the mixed Chinese postman problem, Optim Eng 3, 2002, pp. 157187.

54. W.L. Pearn and C.M. Liu, Algorithm for the Chinese postman problem on mixed networks, Computer and operation research, 22, (1995), pp. 479 489.

55. W.L. Pearn and J.B. Chou, Improved solutions for the Chinese postman problem on mixed networks, Comput Oper Res 26, 1999, pp. 819827.

56. H. Jiang, L. Kang, S. Zhang, and F. Zhu, Genetic Algorithm for Mixed Chinese Postman Problem, Z. Cai et al. (Eds.): ISICA 2010, LNCS 6382, 2010, pp. 13199.

57. Z. Win, On the windy postman problem on eulerian graphs, Math Program 44, 1989, pp. 97112.

58. W.L. Pearn and M.L. Li, Algorithms for the windy postman problem, Computers Ops Res 21, 1994, pp. 641- 651.

59. Corberán, A., M. Oswald, I. Plana, G. Reinelt, and J.M. Sanchis, New results on the windy postman problem, Technical Report TR05-, University of Valencia, Spain, (2007).

60. P.F. Lemieux, and L. Campagna,The snow plowing problem solved by a graph theory algorithm, Civil Eng. Systems 1, 1984, pp. 337-341.

61. A.S. Alfa and D.Q. liu, Postman routing problem in a hierarchical network, Eng. Optim. 14, 1988, pp. 127-138.

62. M. Dror, H. Stern, and P. Trudeau, Postman tour on a graph with precedence relation on arcs, Networks 17, 1987, pp. 283-294.

63. G. Ghiani, and G. Improta, An algorithm for the hierarchical Chinese postman problem, Oper Res Lett 26, 2000, pp. 2732.

64. P. Korteweg, and T. Volgenant, On the hierarchical Chinese postman problem with linear ordered classes, Eur J Oper Res 169, 2006, 4152.

65. E. Cabral, M. Gendreau, G. Ghiani, and G. Laporte, Solving the hierarchical Chinese postman problem as a rural postman problem, Eur J Oper Res 155, 2004, pp. 4450.

66. C. Malandraki, and M.S. Daskin, The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem, Eur. J. Oper. Res. 65, 1993, pp. 218234.

67. W.L. Pearn and K.H. Wang, On the maximum benefit Chinese postman problem, Omega 31, 2003, pp. 269273.

68. A. Corberán, I. Plana, A.M. Rodríguez-chía and J.M. Sanchis, A branch-and-cut algorithm for the maximum benefit Chinese postman problem, Math. Program. Ser, 2011, A DOI 10.1007/s10107-011-0507-6.

69. U.F. Aminu, and R.W. Eglese, A constraint programming approach to the Chinese postman problem with time windows, Comput Oper Res 33, 2006, pp. 34233431.

70. N. Christofides, V. Campos, A. Corberán, and E . Mota, An algorithm for the rural postman problem, Imperial College Report IC.O.R.81.5, 1981.

71. A. Corberán, R. Mart, and J. Sanchis, A GRASP heuristic for the mixed chines postman problem, European Journal of Operational Research 142, 2002, pp. 7080.

72. A.N. Letchford, New inequalities for the general routing problem, European Journal of Operational Research 96, 1997, pp. 317322.

73. G. Ghiani, and G. Laporte, A branch-and-cut algorithm for the undirected rural postman problem, Mathematical Programming 87, 2000, pp. 46781.

74. E. Fernandez, R. Garfinkel, O. Meza, and M. Ortega, On the undirected rural postman problem: tight bounds based on a new formulation, Operations Research 51(2), 2003, pp. 28191.

75. W.L. Pearn, and T.C. Wu, Algorithms for the rural postman problem, Computers and Operations Research 22, 1995, pp. 81928.

76. G. Ghiani, D. Laganà, and R. Musmanno, A constructive heuristic for the Undirected Rural Postman Problem, Computers & Operations Research 33, 2006, pp. 34503457.

77. A. Hertz, G. Laporte, and P. Nanchen-Hugo, Improvement procedures for the undirected rural postman problem, INFORMS Journal on Computing 11, 1999, pp. 5362.

78. Rodrigues, A.M., and J.S. Ferreira, Solving the Rural Postman Problem by Memetic Algorithms, In: MIC 2001 – 4th Metaheuristics International Conference, Porto, Portugal, 2001.

79. M. Dorigo, and L. Gambardella, Ant Colony System: a Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transaction on Evolutionary Computation 1(1), 1997, pp. 5366

80. Laganà, D., G. Laporte, F. Mari, R. Musmanno, and O. Pisacane, An ant colony optimization metaheuristic for the undirected rural postman problem, Les Cahiers du GERAD, G-2007-106, 2007.

81. M.L. Perez-Delgado, A Solution to the Rural Postman Problem Based on Artificial Ant Colonies, In: Borrajo, D., Castillo, L., Corchado, J.M. (eds.) CAEPIA 2007. LNCS, vol. 4788 Springer, 2009, pp. 220228.

82. Baldoquín, M.G., G. Ryan, R. Rodrguez, A. Castellini, Un Enfoque Hbrido Basado en Metaheursticas para el Problema del Cartero Rural, In: XI CLAIO, Concepcion de Chile, Chile, 2002.

83. P. Fernandez de Cordoba, L.M. Garca Raffi, and J.M. Sanchis, A Heuristic Algorithm Based on Monte Carlo Methods for the Rural Postman Problem, Computers Ops. Res. 25(12), 1998, pp. 10971106.

84. Baldoquín, M.G, Heuristics and metaheuristics approaches used to solve the Rural Postman Problem: A Comparative Case Study. In Proceedings of the Fourth International ICSC Symposium on Engineering of Intelligent Systems (EIS), 2004.

85. M.L. Perez-Delgado, and J.C. Matos-Franco, Self- organizing Feature Maps to Solve the Undirected Rural Postman Problem, In: Moreno Daz, R., Pichler, F., Quesada Arencibia, A. (eds.) EUROCAST 2007. LNCS, vol. 4739 Springer, 2007, pp. 804811.

86. K. Holmberg, Heuristics for the rural postman problem, Computers & Operations Research 37, 2010, pp. 981-990.

87. A.M. Rodrigues, and J.S. Ferreira, Cutting path as a Rural Postman Problem: solutions by Memetic Algorithms,

    International Journal of Combinatorial Optimization Problems and Informatics 3 (1), 2012, pp. 22-37.

88. N. Chistofides, V. Campos, A. Corberán, E. Mota, An Algorithm for the Rural Postman Problem on a Directed Graph, Math. Programming Stud. 26, 1986, pp. 155166.

89. G. Laporte, Modeling and solving several classes of arc routing problems as travelling salesman problems, Computers & Operations Research 24, 1997, pp. 1057-1061.

90. A. Corberán, R. Martí, and A. Romero, Heuristics for the mixed rural postman problem, Computers & Operations Research 27, 2000, pp. 183-203.

91. Corberán, A., A. Romero, and J.M. Sanchis, The general routing problem on a mixed graph. Technical Report, Department of Statistics and Operations Research. University of Valencia, Spain, 1999.

92. G. Laporte, The travelling salesman problem: an overview of exact and approximate algorithms, European Journal of Operational Research 59, 1992, 231-247.

93. E. Benavent, A. Corberán, E. Piñana, I. Plana, and J.M. Sanchis, New heuristic algorithms for the windy rural postman problem, Comput Oper Res 32, 2005, pp. 3111 3128.

94. J. Aráoz, E. Fernández and O. Meza, Solving the prize- collecting rural postman problem, European Journal of Operational Research 196, 2009, pp. 886896.

95. E. Benavent, D. Soler, The directed rural postman problem with turn penalties, Transportation Science 33(4), 1999, pp. 408-18.

96. E. Benavent , D. Soler Searching for a strong double tracing in a graph, Top (A Journal of the Spanish Statistical and Operations Research Society) 6 (1), 1998, pp. 123-38.

97. D. Soler, Tour Euleria` sense Girs en U en un Graf Orientat Simple, QuK estiioH 22(3), 1998, pp. 471-489.

98. R. Hirabayashi, Y. Saruwatari, and N. Nishida, Tour construction algorithm for the capacitated arc routing problem, Asia-Pacific Journal of Operational Research 9, 1992, pp. 155175.

99. M. Kiuchi, Y. Shinano, R. Hirabayashi, and Y. Saruwatari, An exact algorithm for the capacitated arc routing problem using Parallel Branch and Bound method , Abstracts of the 1995 Spring National Conference of the Operational Research Society of Japan, 1995, pp. 2829.

100. J. Belenguer, and E. Benavent, A Cutting Plane algorithm for the capacitated arc routing problem, Computers and Operations Research 30, 2003, pp. 705720.

101. R.W. Eglese, and A. Letchford, Polyhedral theory for arc routing problems, M. Dror, ed. Arc Routing. Theory, Solutions, and Applications. Kluwer, Boston, 2000, pp. 199 230.

102. H. Longo, M.P. Aragão, E. Uchoa, Solving capacitated arc routing problems using a transformation to the CVRP, Computers and Operatons Research 33 (6), 2006, pp. 18231837.

103. R. Baldacci, and V. Maniezzo, Exact methods based on node-routing formulation for undirected arc-routing problems, Networks 47 (1), 2006, pp. 5260.

104. Ghiani, G., D. Laganà, G. Laporte, R. Musmanno, A branch- and-cut algorithm for the undirected capacitated arc routing problem, Working paper, HEC, Montreal, Quebec, Canada, 2009.

105. Gómez-Cabrero, D., J.M. Belenguer, and E. Benavent, Cutting plane and column generation for the capacitated arc routing problem, Presented at ORP3Valencia, Spain, 2005.

106. A.N. Letchford, A. Oukil, Exploiting sparsity in pricing routines for the capacitated arc routing problem, Comput Oper. Res. 36(7), 2009, pp. 23202327.

107. E. Benavent, V. Campos, A. Corberán, E. Mota, The capacitated arc routing problem: lower bounds, Networks 22, 1992, pp. 669690.

108. Amberg, A., and S.Voß, A hierarchical relaxations lower bound for the capacitated arc routing problem. In R.

     H. Sprague (Ed.), (DTIST02) (pp. 1 10). Proceedings of the 35th Annual Hawaii International Conference on System Sciences, IEEE, Piscataway, 2002.

109. J. Belenguer, and E. Benavent, The Capacitated Arc Routing Problem: Valid Inequalities and Facets, Computational Optimization and Applications 10, 1998, pp. 165187

110. J.M. Belenguer, E. Benavent, A cutting plane algorithm for the capacitated arc Routing problem. Computers and Operations Research 30 (5), 2003, pp. 705- 728.

111. Welz, S.A., Optimal solutions for the capacitated arc routing problem using integer programming, Unpublished doctoral dissertation, Department of Quantitative Analysis and Operations Management, University of Cincinnati, Cincinnat, 1994.

112. B.L. Golden, J. DeArmon, and E.K. Baker, Computational experiments with algorithms for a class of routing problems, Computers and Operations Research 10 (1), 1983, pp. 4759.

113. G. Ulusoy, The fleet size and mixed problem for capacitated arc routing, European Journal of Operational Research 22, 1985, pp. 329337.

114. W. Pearn, Approximate solutions for the capacitated arc routing problem, Computers Ops Res 16, 1989, pp. 589- 600.

115. M.C. Mourão, L. Amado, Heuristic method for a mixed capacitated arc routing problem: A refuse collection application, European Journal of Operational Research 160 (1), 2005, pp. 139153

116. S. K. Amponsah, and S. Salhi, The investigation of a class of capacitated arc routing problems: The collection of garbage in developing countries, Waste Management 24, 2004, pp. 711721.

117. J. Coutinho-Rodrigues, N. Rodrigues, and J. Clímaco, Solving an urban routing problem using heuristics: a successful case study, Belgian Journal of Operations Research, Statistics and Computer Science 33, 1993, pp. 19 32.

118. R.W. Eglese, and L.Y.O. Li, A tabu search based heuristic for arc routing with a capacity constraint and time deadline, In: Osman, I.H., Kelly, J.P. (Eds.), Metaheuristics: Theory and Apllications. Kluwer, 1996, pp. 633650.

119. A. Hertz, G. Laporte and M. Mittaz, A Tabu Search heuristic for the capacitated arc routing problem, Operations Research 48, 2000, pp. 129135.

120. P. Greistorfer, A tabu scatter search metaheuristic for the capacitated arc routing problem, Computers and Industrial Engineering 44 (2), 2003, pp. 249266.

121. J. Brandao, and R.W. Eglese, A deterministic tabu search algorithm for the capacitated arc routing problem, Computers and Operations Research 35(4), 2008, pp. 1112- 1126.

122. Y. Mei, K. Tang, and X. Yao, Improved memetic algorithm for capacitated arc routing problem, IEEE Congress on Evolutionary Computation, 2009, pp. 1699- 1706.

123. P. Beullens, L. Muyldermans, D. Cattrysse, and D. Oudheusden, A guided local search heuristic for the capacitated arc routing problem, European Journal of Operational Research 147 (3), 2003, pp. 629643.

124. P. Lacomme, C. Prins, and A. Tanguy, First Competitive Ant Colony Scheme for the CARP, Lecture Notes in Computer Science 3172, 2004, pp. 426427.

125. P. Lacomme, C. Prins, and W. Ramdane-Chérif, Competitive memetic algorithms for arc routing problems, Parallel Computing 30, 2004, pp. 377_387.

126. L. Santos, J. Coutinho-Rodrigues, J. R. Current, An improved ant colony optimization based algorithm for the capacitated arc routing problem, Transportation Research Part B: Methodologicale 44(2), 2010, pp. 246266.

127. J. Bautista, E. Fernández, and J. Pereira, Solving an urban waste collection problem using ants heuristics, Computers and Operations Research 35 (9), 2008, pp. 30203033.

128. C. Martinez, I. Loiseau, M.G.C. Resende, and S. Rodriguez, BRKGA Algorithm for the Capacitated Arc Routing Problem, Electronic Notes in Theoretical Computer Science 281 (2011), 2011, pp. 6983.

129. J. F. Goncalves, and J. R. D. Almeida, A hybrid genetic algorithm for assembly line balancing, Journal of Heuristics 8 , 2002, pp. 629642

130. P. Hansen, N. Mladenovi, Variable neighborhood search: Principles and applications, European Journal of Operational Research 130 (3), 2001, Pages 449467.

131. E.E. Zachariadis, and C.T. Kiranoudis, Local search for the undirected capacitated arc routing problem with profits, European Journal of Operational Research 210, 2011, pp. 358367.

132. E.E. Zachariadis, C.D. Tarantilis, and C.T. Kiranoudis, A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service, Expert Systems with Applications Volume 36 (2), 2009, pp. 10701081.

133. E. Benavent, Á. Corberán, L. Gouveia, M.C. Mourão, and L.S. Pinto, Profitable Mixed Capacitated Arc Routing and Related Problems, Centro de Investigacao Operacional CIO Working Paper 4/2013, 2013.

134. P.A. Mullaseril, M. Dror, and J. Leung, Split-delivery routing heuristics in livestock feed distribution, J. Oper. Res. Soc. 48(2), 1997, pp. 107116.

135. Gueguen, C., Exact solution methods for vehicle routing problems, Ph.D. thesis, Central School of Paris, 1999.

136. Ramdane-Cherif, W., evolutionary algorithms for capacitated arc routing problems with time windows, 12th IFAC Symposium on Information Control Problems in Manufacturing INCOM, 2006.

137. N. Labadi, C. Prins, and M. Reghioui, Grasp with path relinking for the capacitated arc routing problem with time

     windows, Lecture Notes in Computer Science 4448, 2007, pp. 722731.

138. Johnson, E.L., and S. Wöhlk, Solving the capacitated arc routing problem with time windows using column generation, Coral working papers, University of Aarhus, Aarhus School of Business, Department of Business Studies, 2009.

139. Tagmouti, M., Gendreau, M., Potvin, J.-Y., 2007. Arc routing problems with time dependent service costs, European Journal of Operational Research 181, pp. 3039.

140. M. Tagmouti, M. Gendreau, J.Y. Potvin, A dynamic capacitated arc routing problem with time-dependent service costs, Transportation Research Part C 19, 2011, pp. 2028.

141. H.M. Afsar, A Branch-and-Price Algorithm for Capacitated Arc Routing Problem with Flexible Time Windows, Electronic Notes in Discrete Mathematics 36, 2010, pp. 319326.

142. P. Lacomme, C. Prins, W. Ramdane-Chérif, Evolutionary algorithms for multiperiod arc routing problems, in: Proc. of the 9th Int. Conf. on Information Processing and Management of Uncertainty in Knowledge- Based systems, France, ESIA-University of Savoie, 2002, pp. 845852.

143. F. Chu, N. Labadi, and C. Prins, Periodic arc routing problems: linear programming model and heuristics, in: A. Dolgui, et al. (Eds.), Proceedings of the 9th International Multiconference on Advanced Computer Systems, ACS02: Miedzyzdroje, Informa Publishing, Szczecin, Poland, 2002, pp. 409418.

144. P. Lacomme,C. Prins, W. Ramdane-Chérif, Evolutionary algorithms for periodic arc routing problems, European Journal of Operational Research 165, 2005, pp. 535553.

145. F. Chu, N. Labadi, and C. Prins, A Scatter Search for the periodic capacitated arc routing problem, European Journal of Operational Research 169, 2006, pp. 586605.

146. I.M. Monroy, C.A. Amaya, and A. Langevin, The periodic capacitated arc routing problem with irregular services, Discrete Applied Mathematics 161, 2013, pp. 691- 701.

147. A. Hertz, and M. Mittaz, Heuristics algorithms. In: Dror M (ed). Arc Routing: Theory, Solutions and Applications, Kluwer Academic Publishers: Boston, 2000, pp. 327386.

148. A. Amaya, A. Langevin, and M. Trepanier, A heuristic method for the capacitated arc routing problem with refill points and multiple loads, Journal of the Operational Research Society 61, 2011, pp. 1095 1103.

149. A. Hertz, Recent trends in arc routing, In: Golumbic MC and Ben-Arroyo Hartman I (eds). Graph Theory, Combinatorics and Algorithmics: Interdisciplinary Applications. Springer, 2005, pp. 215236.

150. A. Amberg , W. Domschke , and S. Voû, Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees, European Journal of Operational Research 124, 2000, pp. 360-376.

151. L. Xing, P. Rohlfshagen, Y. Chen, and X. Yao, IEEE Fellow, An Evolutionary Approach to the Multidepot Capacitated Arc Routing Problem, IEEE Transactions On Evolutionary Computation 14(3), 2010.

152. M. Polacek, K.F. Doerner, R.F. Hartl, and V. Maniezzo, A variable neighborhood search for the capacitated arc routing problem with intermediate facilities, J Heuristics 14, 2008, pp. 405423.

153. G. Ghiani, F. Guerriero, G. Laporte, and R. Musmanno, Tabu Search Heuristics for the Arc Routing Problem with Intermediate Facilities under Capacity and Length Restrictions, Journal of Mathematical Modelling and Algorithms 3, 2004, pp. 209223.

154. P. A. Mullaseril, M. Dror, and J. Leung, Split- delivery routing in livestock feed distribution, J. Oper. Res.

     Soc. 48, 1997, pp. 107116

155. N. Labadi, C. Prins, and M. Reghioui, An evolutionary algorithm with distance measure for the split delivery capacitated arc routing problem. C. Cotta, J. Van Hemert, eds. Recent Advances in Evolutionary Computation for Combinatorial Optimization, Vol. 153, Studies in Computational Intelligence Springer, 2008, pp. 275294.

156. K. Sörensen, and M. Sevaux, MAPM: Memetic algorithms with population management, Comput. Oper. Res. 33(5), 2006, 12141225.

157. J.M. Belenguer, E. Benavent, and N. Labadi, C. Prins, and M. Reghioui, Split-Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic, Transportation Science 44(2), 2010, pp. 206220.

158. L. Muyldermans, and G. Pang, A guided local search procedure for the multi-compartment capacitated arc routing problem, Computers &Operations Research 37, 2010, pp. 16621673.

159. G. Clarke, and J.W. Wright, Scheduling of vehicles from a central depot to a number of delivery points, Operations Research 12, 1964, pp. 568581.

160. C. Voudouris, E. Tsang, Guided local search and its application to the traveling salesman problem, European Journal of Operational Research 113, 1999, pp. 469499

161. G. Fleury, P. Lacomme, C. Prins, W. Ramdane-Chérif, Robustness evaluation of solutions for the capacitated arc routing problem, in: Conference, AI Simulation and Planning in High Autonomy Systems, 2002, pp. 290-295.

162. G. Fleury, P. Lacomme, C. Prins, W. Ramdane-Chérif, Improving robustness of solutions to arc routing problems, Journal of the Operational Research Society 56, 2005, pp. 526-538.

163. Fleury G., P. Lacomme, C. Prins, Stochastic capacitated arc routing problem, Research Report LIMOS/RR-0512, Université Blaise Pascal, Clermont- Ferrand, France, 2005.

164. P. Lacomme, C. Prins and W. Ramdane-Cherif , A genetic algorithm for the capacitated arc routing problem and its extensions, In: Applications of evolutionnary computing (E.J.W. Boers, Ed.), Lecture Notes in Computer Sciences, 2037, Springer, 2001, pp. 473483.

165. C. H. Christiansen, J. Lysgaard, and S. Wøhlk, A Branch-and-Price Algorithm for the Capacitated Arc Routing Problem with Stochastic Demands, Operations Research Letters 37, 2009, pp. 392-398

166. G. Laporte, R. Musmanno, and F. Vocaturo, An Adaptive Large Neighbourhood Search Heuristic for the Capacitated Arc Routing Problem With stochastic Demands, Transportation Science 44(1), 2010, pp. 125 135.

167. P. Lacomme, C. Prins , and M. Sevaux, Agenetic algorithm for a bi-objective capacitated arc routing problem, Computers & Operations Research, Part Special Issue: Recent Algorithmic Advances for Arc Routing Problems 33(12), 2006, pp. 347393.

168. Y. Mei, K. Tang, X. Yao, Decomposition-based memetic algorithm for multi- objective capacitated arc routing problem, IEEE Transactions on Evolutionary Computation 15(2), 2011, pp. 151165.

169. L. Grandinetti, F. Guerriero, and D. Lagana, O. Pisacane, An optimization-based heuristic for the Multi- objective Undirected Capacitated Arc Routing Problem, Computers & Operations Research 39, 2012, pp. 23002309.

170. R.Y.K. Fung, R. Liu, and Z. Jiang, A memetic algorithm for the open capacitated arc routing problem, Transportation Research Part E 50, 2013, pp. 536.