Figure 7‑11B 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 utilise 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.4) 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 modelling 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 optimisation 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 litres. 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 litres 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). 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 DEM_i be the demand by customer i, and let q_i be the cumulative amount of chemical in litres delivered to all customers during a tour, up to and including customer i. If customer i is the first in a particular tour, then DEM_i=q_i, which can be written as the condition:

If j comes after i in a tour then q_i 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 litres to the remaining 4 customers, with a combined tour of just under 500 kms (Figure 7‑12).

Figure 7‑12 Tanker delivery tours

Data-driven scripts that solve well-defined optimisation 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.