Constraint Programming (CP) [Shaw 1998] is a paradigm for representing and solving a wide variety of problems. Problems are expressed in terms of variables, domains for those variables and constraints between the variables. The problems are then solved using complete search techniques such as depth-first search (for satisfaction) and branch and bound (for optimisation). The richness of the language used to express problems in CP makes it an ideal candidate for VRPs. This way very general expressions can be used as constraints. In addition to expressions involving the usual arithmetic and logical operators, complex symbolic constraints can be used to describe a problem. CP enhances search using constraint propagation. If bounds or constraints on a variable can be inferred, or are tentatively set, these changes are “propagated” through all the constraints to reduce the domains of constrained variables.
At each node in the search tree, the propagation mechanism removes values from the domains of constrained variables that are inconsistent with other variables. If the propagation mechanism removes all values from any variable, then there cannot be a solution in this subtree and the search backtracks making a different decision at the backtrack point. Backtracking is chronological: decisions can only be undone in the opposite order to which they were made. Moreover, the domains of constrained variables can only be reduced as search progresses down the tree. The domains of all constrained variables can be restored by backtracking to a previous node, but general enlargement (or relaxation) of domains is not supported. This has important implications for the way in which vehicle routing problems are solved.
In the particular case of solving VRP, a decision variable ${R_{i}}$ is associated with each customer visit ${i}$, representing the next visit performed by the same vehicle. For each vehicle ${k}$, there are additional visits ${S_{k}}$ marking the start of the route, and ${E_{k}}$ marking the end of the route. To read off the itinerary for a vehicle ${k}$, start at ${S_{k}}$ and follow the “next” pointers through to ${E_{k}}$.
The set of customer visits will be referred to as ${N}$, starting visits as ${S}$, and ending visits as ${E}$. ${A =_{def} N \bigcup S \bigcup E}$ is all visits. Regarding ${R}$ as a function, ${R}$ maps ${N \bigcup S}$ onto ${N \bigcup E}$.
To model VRP it is desirable to have a special constraint type for dealing with constraints along paths. The constraints are of the form ${R_{i} = j \Rightarrow Q_{j} \ge Q_{i} + q_{ij}}$.
Thus, if visit ${j}$ immediately follows visit ${i}$, quantity ${Q}$ is accumulated. For example, setting ${q_{ij}}$ equal to the travel time between ${i}$ and ${j}$ means would be the arrival time at ${j}$. Setting ${q_{ij}}$ to be the demand at ${i}$ would accumulate load on the vehicle. This specification allows other real-world constraints to be expressed succinctly.
In each case a fixed point (boundary condition) must be supplied, for example ${Q_{i} = 0 \forall i \in S}$ in the case of load constraints. A single constraint of this type which contains an upper bound also has the effect of eliminating subtours (routes that do not include a ${S_{k}}$ and ${E_{k}}$ visit).
Constraints for VRP
Core Constraints
The core constraints in VRP are related to:
- Time: It is restricted both by the working day and by time windows at customers.
- Capacity: It may be restricted in terms of weight, volume, number of pallet places, etc.
A path constraint can be used to propagate the start time of the customer service along each vehicle route. In this case, ${q_{ij}}$ is the service time at ${i}$, plus the travel time from ${i}$ to ${j}$.
Single or multiple service time windows could be set by further constraining the start of service variable for each visit. The start and end of the working day for each vehicle can be represented by imposing time windows on visits in ${S}$ and ${E}$.
A method of modeling capacity constraints on vehicles is to propagate (via the path constraint) the free space in the vehicle along each vehicle route. To model ${F_{i}}$ as the free space on arrival at visit ${i}$, ${q_{ij}}$ is the change in free space associated with ${i}$ visit. To indicate that all vehicles must not be overfilled at any time, constraints of the form ${F_{i} \ge 0 \forall i \in A}$ are imposed. For vehicle ${k}$ with capacity ${c_{k}}$, the fixed point ${F_{k} = c_{k}}$ for ${k \in S}$ can be set. Simultaneous pickups and deliveries can be modeled in a similar way, but this is not discussed here.
Side Constraints
One of the significant benefits of CP techniques is that side constraints can be incorporated into the model with comparative ease. For example, some visits may require special equipment, or some vehicles may be simply too large to enter the premises. Therefore, we need to be able to disallow a visit being made by particular vehicles.
We model this by propagating a vehicle tag ${\tau_{k}}$ for each visit ${k}$ along each route, using a constraint similar to the path constraint for which ${R_{i} = j \rightarrow \tau_{j} = \tau_{i}}$ with ${\tau_{i} = i}$ for ${i \in S}$. Thus customer visits served by vehicle ${k}$ will have tag ${k}$. Vehicle ${k}$ is then forbidden from making visit ${i}$ by imposing a constraint of the form ${\tau_{i} \neq k}$. A conjunction of such expressions can be used to exclude more than one vehicle.
The requirement that two visits ${i}$ and ${j}$ must be made by the same (different) vehicles can also be specified using tags: ${\tau_{i} = (\neq) \tau_{j}}$
Implementing a length capacity for vehicles provides one final example that demonstrates a powerful use of vehicle tags. A length restriction is different from a capacity constraint because it does not accumulate over a route. If visit ${i}$ involves goods of length ${l}$, and ${L_{k}}$ is the length of vehicle ${k}$, then the constraint ${L(\tau_{i}) \ge l}$ defines the length constraint.
Search Strategy
Solutions to CP problems are usually found using complete methods such as depth-first search and branch and bound. However, for routing problems of practical size, complete search methods cannot produce solutions in a short and reliable time period. By contrast, iterative improvement methods have proved very successful in this regard. Iterative improvement methods operate by changing small parts of the solution, for instance moving a visit from one route to another. This type of operation involves retracting previous decisions and making new ones. In contrast to depth-first search, retraction can be done in any order, not simply in the opposite order the decisions were made. In general the overhead of implementing this type of non-chronological retraction mechanism in CP frameworks is very high.
To overcome this problem, the CP system is only used to check the validity of solutions and determine the values of constrained variables, not to search for solutions. The search is performed by an iterative improvement procedure. When the procedure needs to check the validity of a potential solution, it is handed to the CP system. As a part of checking, constraint propagation using all constraints still takes place. This adds value to the constraint check, as the iterative improvement method can then take advantage of the reduced domains to speed up search by performing fast legality checks.
The implementation relies on two representations of the solution. There is a passive representation, which is the template against which new solutions are constructed, and which holds the âcurrent solutionâ (not necessarily the best solution). The second is an active representation that holds the constrained variables, and within which constraint propagation takes place. Variable states in the active representation are âcheckpointedâ (current domains are saved) before any changes are made, so that domains can be restored later.
When the CP system performs propagation and validity checks it instantiates the set of decision variables R using the itinerary in the passive representation. The constraints then propagate and constrained variables (such as time and capacity variables) have their domains reduced. If any variable has no legal values, the solution is illegal.