Tours, traveling salesman problems and vehicle routing

Navigation:  Network and Location Analysis > Network Construction, Optimal Routes and Optimal Tours >

Tours, traveling salesman problems and vehicle routing

Previous pageReturn to chapter overviewNext page

The optimal tours described in Section 7.3.4, Shortest (network) path problems, are subsets of a more general class of problem, the traveling salesman problem (TSP). The TSP involves making a tour of every vertex in a given set, returning to the starting point, such that the tour length is minimized. Applications include: salesmen visiting customers; rubbish trucks servicing business premises; delivery trucks servicing retail outlets; security staff patrolling premises and many more. There are many non-geographic applications, ranging from VLSI design to the analysis of DNA sequences. The majority of geographic instances involve modest numbers of locations to visit (e.g. stores, cities) but variants of the problem (e.g. the need to dispatch multiple vehicles from a central depot on tours to visit their own subset of stores) can increase the problem complexity substantially. Pure TSP problems (i.e. based on a point set with no pre-defined network) are not supported within GIS packages. Where such networks are defined, very few GIS packages provide TSP functionality — one exception being TransCAD. An excellent introduction to TSP problems and solutions is provided by William Cook, one of the authors of the Concorde software package described later in this subsection) at: http://www.tsp.gatech.edu/index.html

Since every TSP tour involves visiting each location once, deleting one link from this tour will leave a spanning tree. This tree must be at least as long as the MST and will typically be longer (an upper bound for symmetric planar graphs is 1.5 times the MST length). The number, t, of possible tours with a symmetric (i.e. non-directed) graph consisting of n vertices is t=(n‑1)!/2. This number grows extremely rapidly with n and cannot realistically be systematically evaluated for large n. For example, with n=10, t=181,440. Solving the problem exactly is thus an O(n!) problem and has been shown to be NP-complete. An internationally collated set of test problems are provided in the dataset known as TSPLIB. These include test datasets for symmetric and asymmetric TSPs, HCPs, SOPs and CVRPs.

A formal statement of the basic TSP is:

where cij is the cost of travel from i to j (e.g. cost weighted distance), and xij=1 if a direct link exists from i to j in a tour, or 0 otherwise. Here n is the number of sites in the tour, where typically i=1 is the tour start point (e.g. a depot) and i=2,3,...n are the sites to be visited (e.g. customers).

Solutions of many TSP problems have certain attributes that may be used to assist algorithm development. These include the fact that the TSP for a point set, S, must lie entirely within the convex hull of the set, and any vertices located on this hull must be traversed such that their clockwise or anti-clockwise sequential arrangement is preserved. Clearly also the TSP must not be self-intersecting. Heuristic solutions, notably the Lin-Kernighan or LK-heuristic, which is a development of the n-opt heuristic, make use of any self-intersections that are found to generate an improved solution with the self-intersection removed by a form of symmetric resequencing or flipping of the order of visited nodes. The result is a very fast approximate algorithm that yields exact or near exact solutions for many problems. Exact algorithms also exist, some of which are fast. Concorde, cited earlier, uses a procedure based on linear programming and cutting plane techniques to obtain exact solutions to relatively large problems (many 1000s of vertices). This code, which is very fast with moderate-sized problems, is amongst the best available. However, users should be aware that rounding issues exist in its treatment of decimal coordinates - to avoid problems it is advisable to multiply all values by one or more powers of 10 before undertaking analyses.

There are close relationships between the generation of the Delaunay triangulations, the generation of MSTs and the solution of Euclidean (plane) TSPs. This was noted earlier on in the research into TSP heuristics, and forms the basis of some methods. To illustrate this linkage we will use a test dataset from TSPLIB consisting of n=130 vertices (CH130.TSP). Figure 7‑11 illustrates several aspects of these relationships. Figure 7‑11A shows the source point set and Figure 7‑11B gives the Delaunay triangulation (DT) of this set. The total length of the edges in the triangulation is 30157 units.

Figure 7‑11C and Figure 7‑11D show the minimum spanning tree (MST) for the point set, produced using the Concorde software and overlain on the DT. The MST consists of 129 edges with a total length of 5166 units. Figure 7‑11E and Figure 7‑11F show the same pair, but in this case showing the exact TSP solution obtained using the linear programming and cutting planes method that is implemented in Concorde. Processing on a modestly powered desktop PC was completed in a few seconds. The total number of edges in this case was 130 with a total length of 6110 units.

Finally, Figure 7‑12A shows the solution provided using the LK heuristic, which was generated almost instantly for this problem. Notice that the top right corner of this solution differs slightly from that of the exact solution in Figure 7‑11F. This solution also has 130 edges but a slightly greater length of 6124 units. In all cases edge weights were computed using symmetric Euclidean distances. Interestingly, with a random pattern of n points with an MBR that has area A, the expected length of the Euclidean TSP has been estimated as:

For the example illustrated in Figure 7‑11A n=130 and A=471,937 units, giving an expected tour length if the point set were random of 5874 units. The optimal result is slightly greater than this, reflecting the fact that the point set is slightly more uniform than random. With the Manhattan or L1 metric the expected tour length is greater, being the same general expression but with k19/20.

Figure 7‑11 MST, TSP and related problems

A. Source point set (130 vertices)

B. Delaunay triangulation (DT)

clip0370.zoom50

clip0371.zoom50

C. MST/DT

D. MST

clip0372.zoom50

clip0373.zoom50

E. TSP/DT

F. TSP — exact solution

clip0374.zoom50

clip0375.zoom50

Figure 7‑12 Heuristic solution and dual circuit TSP examples

A. TSP — LK solution

B. Dual TSP

clip0376.zoom50

clip0377.zoom50

Capacitated vehicle routing

Figure 7‑12B provides one instance of a solution to a more general problem, that of determining the optimal set of t>1 tours for a given point set. This class of problems is known as the Vehicle Routing Problem (VRP) or Capacitated VRP (CVRP) if vehicle capacity constraints are included in the problem formulation. In this example the point set has simply been divided into left and right halves and separate optimal tours generated for each subset. The combined length of these tours is 6349 units, but it is perfectly possible for the tour length to be less than that for a single tour. Multiple tours will often utilize the same starting vertex (e.g. a single depot) but this does not substantially alter the approaches used. Separate tours can be created by breaking (dividing) the original optimal tour into discrete parts (route first-cluster second) or by separating the point sets into clusters and computing optimal or near optimal tours for each subset (cluster first-route second). There is no guarantee that the resulting multiple tours will be globally optimal, so repeated alternative subdivisions may be necessary to achieve improved solutions. Such a procedure is extremely processor intensive and hence use of algorithms such as the LK-heuristic would generally be preferred for the TSP generation step.

The two circuit TSP problem raises a number of practical issues:

should the tours start at the same point (e.g. warehouse, bus depot…)?
what if demand varies across the target points?
the capacities of service vehicles may be limited and vary ― what mix would be optimal?
do tours/deliveries have to be made in certain time windows?

These questions relate to problem variants for which metaheuristics such as tabu search (see Section 7.2.2, Heuristic and meta-heuristic algorithms) have been shown to be effective, especially where time window constraints also apply (see Gendreau, Laporte and Potvin, 2002, for a fuller discussion). Problem variants such as these are addressed in several of the software packages referred to in the introduction to this chapter. Most seek optimal solutions for moderate sized problems, or provably good solutions that can be computed reasonably quickly — i.e. sub-optimal solutions, but much better than more arbitrary or user-defined plans. Individual packages vary in their approaches and often provide more than one option where complex real-world constraints and commercial criteria apply. This in turn requires careful formulation of the appropriate model, designing this using a standardized modeling structure or design tool, and then implementing the model using a high-level scripting language or code generator.

To illustrate this approach we shall use an example from the Xpress-MP optimization product with its Mosel scripting language. In this case the problem involves delivery of liquid chemicals by tanker from a refinery to 6 customer sites. The demand, DEM, from the sites is known (these might be regular fixed or varying amounts, delivered on a scheduled basis). Total demand in this example is 59000 liters. A symmetric shortest distance matrix is provided between all locations — map support is not provided within Xpress-MP so distance matrix creation and final display would benefit from a direct link to a GIS package or simple import/export facilities. Pairs of sites vary in separation from 12 kms to 180 kms. The capacity, CAP, of the delivery tanker is fixed at 36000 liters and the task is to deliver to all customers with the shortest overall distance driven. Note that a single tour would not be able to service the customers, as the tanker capacity is not sufficient, so capacity-related constraints must be added to the model formulation provided at the start of this subsection (Equations 1: to 4: in Section 7.3.5, Tours, traveling salesman problems and vehicle routing). The objective function in this instance is specified by Equation 1:, whilst the range of i and j in Equations 2: and 3: is from 2…n as site 1 is the depot itself. We need to define additional expressions to account for customer demand and tanker capacity. Let DEMi be the demand by customer i, and let qi be the cumulative amount of chemical in liters delivered to all customers during a tour, up to and including customer i. If customer i is the first in a particular tour, then DEMi=qi, which can be written as the condition:

If j comes after i in a tour then qi must be greater than the quantity delivered in the tour up to i plus the quantity to be delivered to j. This constraint can be written as:

Although this appears rather complicated, it picks up the various cases where i is not 1 and j may or may not follow or precede i. All that remains is to add the basic quantity and capacity constraints:

The scripting language for Xpress-MP accepts input in almost the form shown in Equations 1: to 8:, together with the data and distance matrices described above, followed by a simple command to minimize Equation 1:. The result in this example is a solution consisting of two tours, one delivering 22000 litres to two customers, and the other delivering 37000 liters to the remaining 4 customers, with a combined tour of just under 500 kms (Figure 7‑13).

Figure 7‑13 Tanker delivery tours

clip0378

Data-driven scripts that solve well-defined optimization problems may be subjected to extensive tests, and then used as the back-ends to form-based or graphical/map interfaces in order to provide solutions to a wide range of real-world problems. These higher-level interfaces can provide location, route matrix, attribute and parameter inputs (data) and submit these to the pre-built scripts for execution. Outputs (such as lists of edges comprising routes) can then be read back into the visual interface software and presented as reports, tables and maps. GIS packages such as TransCAD and ArcGIS provide a range of scripting and programming interfaces to facilitate such integration, either with the GIS package or using GIS-package facilities within another application, such as a vehicle dispatch and management system for the emergency services.