Network traversal problems

Navigation:  Network and Location Analysis > Arc Routing >

Network traversal problems

Previous pageReturn to chapter overviewNext page

A simple example of an arc routing problem is the need to clear snow from all streets in a town in the most efficient manner. This problem and its solution are illustrated in Figure 7‑19 and Figure 7‑20A and B. On completion of the optimization process the operator may be issued with a route plan as a list in addition/as an alternative to a map, as shown in Figure 7‑19. In this example, three depots have pre-assigned street areas to clear, as shown in Figure 7‑20A. A solution plan is then shown in Figure 7‑20B for one of the snow ploughs. The plan involves a systematic coverage of all streets, on both sides, with no streets being covered twice (if possible) and as few turns as possible, especially where these incur penalties. Minimizing coverage of streets that have been serviced already or have no demand for service is known as minimization of deadheading. Note that in this example U-turns are permitted, the solution involves no deadheading links (see Figure 7‑19), and no explicit turn penalty has been specified. The solution illustrated was implemented using TransCAD — similar facilities are not provided in other GIS packages but are provided in a number of logistics software packages (see Table 7‑4) and in add-ons to widely used GIS packages — for example, the eRouteLogistics and RouteSmart products built on the ESRI ArcGIS platform).

Figure 7‑19 Routing directions

clip0389

 

Another variant of this problem includes the so-called CARP or Capacitated Arc Routing Problem. This class of problems assumes that capacity constraints apply, for example the capacity of a rubbish collection or gritting vehicle, or the carrying capacity of a postman. Typically it is assumed that mean demand in constant across all routes, but clearly demand may vary depending on the type of routing service involved and neighborhood through which routes are sought (e.g. residential versus offices versus retail or a mix thereof). There may also be other considerations that are required for managing real-world arc-routing problems, such as: establishing route priorities (e.g. for clearance of main/emergency routes); multi-lane cleaning/clearing requirements; and flow issues (e.g. grit/salt spreading rate, collection/refill locations and rates). A range of exact and heuristic algorithms have been developed for the various classes of problem, often based on similar techniques to those used in solving the TSP. CARP, like the TSP, is known to be NP-complete. Yet another, closely related class of problem involves capacity constraints on the links, typically described as capacity constrained flow problems. Example applications include traffic planning, pipeline routing and some forms of telecommunications planning.

A formal statement of the uncapacitated uniform demand arc routing problem is as follows: Let E be a set of edges and V a set of vertices for the graph G(E,V) and denote by (i,j) the edge from vertex i to vertex j, with edge length dij. Then we have:

Here uij denotes the number of times that link (i,j) is used, with uij=1 when the problem is initialized, i.e. every edge must appear at least once in the solution. The objective function is simply minimization of overall tour length subject to constraints that ensure each edge is traversed at least once.

Figure 7‑20 Arc routing

A. Snow plough depots and service areas

clip0390

Figure 7‑20 Arc routing

B. Arc routing plan — zone 7310

clip0391

A solution to this problem can be obtained by a two-stage process:

Step 1: check to see if every vertex satisfies the necessary condition for an Eulerian circuit — i.e. do the number of inflows at every vertex equal the number of outflows. If the network is not directed this condition requires that the degree of every vertex is even. If the network satisfies this condition proceed to step 2. If not, then systematically add (directed) edges until the vertices do all satisfy the condition.

Step 2: Solve the ECP. This turns out to be a relatively straightforward task, although the resulting circuit is not necessarily unique. In fact there are O(kn) Eulerian circuits in any graph, where n is the number of vertices and k=K-1, where K is the minimum degree of vertices in V. A simple algorithm for solving the ECP is due to a little-known Frenchman called M. Fleury dating from 1885, although a perhaps better algorithm, due to Hierholzer (1873) is still widely used today. In Fleury’s algorithm the term bridge refers to an edge that, if removed, would result in the graph becoming disconnected, i.e. forming two unconnected subgraphs. The steps are as follows (for a connected Eulerian graph):

select any vertex as the starting point and any edge leaving that vertex, but only use a bridge if no other options are available (this requires determining whether a link is, in fact, a bridge). Add the chosen edge to the current set
move the current vertex to the end of the chosen edge and delete this edge from the graph. If this results in the previous vertex becoming isolated (having no links) then delete the vertex also
repeat the above steps until all edges have been deleted. The current set should now contain an Eulerian circuit

The capacitated version of this class of problems, CARP, can be solved in a similar manner. However, as it is known to be NP-complete much attention has been focused on finding good heuristics. Amongst the most effective of these is the so-called tabu search algorithm introduced by Hertz et al. (2000). Their procedure involves finding an initial feasible solution and seeking to improve on this by a process of systematic dropping and adding of edges. Computational tests show that this heuristic can solve medium sized problems (50 vertices, 100 edges) to within 1% of optimality in reasonable computation times, but that such times can be highly variable depending on the particular network configuration (variations of an order of magnitude in time for problems of similar size). Problems with much larger numbers of edges (e.g. detailed street networks) were also tested and solutions were obtained within 5% of the optimum on average within acceptable processing times.