42 1 Introduction and Examples
satisfy the so-called triangle inequality:
c
ij
≤ c
ik
+ c
kj
∀i, j, k . (5.1)
The triangle inequality simply means that it is shorter (or at least not longer) to go
directly from i to j than through an intermediate node k . The distance matrix in
Table 7 satisfies the triangle inequality, but not always strictly. As an example, the
distance between A and C is equal to the distance between A and B plus that
between B and C . This is due to using small integer data.
The problem of finding the shortest route to visit all clients starting and ending
at the depot is known as the TSP (traveling salesperson problem). The optimal TSP
route is (0,A,B,C, D,0) of length 10 .
This is checked by using a TSP solver. This can also be checked by brute force
calculation of all routes. For a problem with n clients, there are n! routes. Indeed,
starting from the depot, there are n possible clients to be visited first. When the first
client is fixed, there remain (n −1) clients to be visited next and so on. By symme-
try, only half of the n! routes have to be checked. As an example, (0,D,C,B, A,0)
has the same length as (0, A,B,C,D,0) . Here, 12 routes have to be checked. Alter-
natively, you may trust the authors.
Finding the shortest distance or TSP route is not enough here: the vehicle has
a limited capacity of 10 and the demand at
C is random. The treatment of the
uncertainty depends on the moment when the information becomes available.
b. Wait-and-see solutions
A first case is when the level of the demand is known before starting the route.
This could be the case, for instance, if the delivered product is part of a just-in-time
production process. If the process works in batches, the number of batches required
in C may be 1 or 7 , depending on the production process. But the number of
batches may then be adequately forecasted.
Alternatively, the products may be wastes generated during the production pro-
cess. The amount to be collected can be known if an agreement exists with the client
or if the client is a subsidiary.
This is known as a situation of a priori information. The decision process corre-
sponds to the wait-and-see approach. It consists of making the choice of the route
after getting the information on the demand level.
The optimal solution in the wait-and-see situation is illustrated in Figure 11.
• Whenever client C requires a single unit to be collected, the vehicle’s capacity
is large enough to accommodate the demand of the four clients. It is optimal to
follow the TSP route of length 10 .
• Whenever client C requires 7 units, the total demand of 13 exceeds the vehicle’s
capacity. The vehicle must travel two successive routes. The combination of