# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**120**> 121 122 123 124 125 126 .. 156 >> Next

A forward branching from some stage h involves the choice of a customer Xjh^eFh and the generation of a list P(x,h]) of all single routes (feasible for some vehicle) passing through this customer. It is quite apparent that the smaller the number of branching possibilities at any stage h the more efficient the tree search, and it is therefore obvious that Xjh , should be

320

Nicos Christofides, Aristide Mingozzi, and Paolo Toth

LIS1 P ( //2 ) 01'

feasible single roules passing ihrojgh */2 ond other customers Irom F,

State represented

by I.St L

Figure 11.1 Direct tree-search algorithm

chosen from Fh so as to make the list P(x,ki) as short as possible. This would tend to be the case if xih^i is chosen to be an isolated customer far from the depot. Moreover, not all nodes produced by P(Xih^) need be kept, and, in general, it may be possible to show that a specific node represented by S^(x,hM)e P(xihi) can be rejected. This could be done in the following circumstances.

(i) If the set of routes already in L together with route ^ m) fails the feasible-vehicle-assignment test mentioned above.

(ii) Let F?+i be the set of free customers implied by the routes in list L and route and let lb(F?+1) be a lower bound on the total cost needed

to supply F?+! Then, if the total cost of the routes in L plus the cost of SL,(*!., J Plus ^ (^+1) is greater than z*.

(iii) If in the case of objectives (i), (ii), and (iii) it could be shown that the remaining free vehicles i.e. those not used for the routes in L or for route S^(x^,), are not capable of supplying the customers in F?+1 (e.g. because of insufficient capacity).

The Vehicle Routing Rroblem

321

(iv) Let ub(F?+1) be an upper bound on the total cost needed to supply the customers in F?+1. Let ) e P(xlki) be another node of the tree

produced by P(xiKJ. If

aSJ^1(x^,)] + uB(F+1)^C[S1^i(xlh_i)]+LB(F^+1) (11.9)

where C(S) is the cost of the single feasible route S, then node S^/x,^ ^ dominates node S,~ (x, ) and the latter can be removed from the list

Jh+l

P^J-

In the above tests it was assumed that upper and lower bounds on the remaining subproblem defined by the free customers could be calculated at any stage. Upper bounds could be calculated by solving this subproblem by one of the heuristic methods described in the following sections. This provides, in addition to the bound, a possibility of improving the best solution obtained so far, and also other information which could aid the forward branching. Lower bounds could be calculated by relaxing some or all of the constraints and either solving the problem optimally or calculating a lower bound to the solution of the relaxed problem. Any of the available lower bounds for the tsp could be used in this respect (Christofides, 1975; Eilon, Watson-Gandy, and Christofides, 1971; Held and Karp, 1970, 1971).

In the tree search algorithm described above, C(S) has been used to denote the cost of route S. Once more, a suitable choice of C(S) enables the algorithm to solve the basic vrp with any of the objectives mentioned in the Introduction.

11.3 General Principles of Heuristic Procedures and Practical vrps

Almost all the heuristic methods suggested for solving the vehicle routing problem are constructive in nature in the sense that at any given stage one (or more) incomplete route exists which is extended in the following stages until it becomes the final route. This approach is dictated to a large extent by the very large number of constraints that apply to the vehicle routing problem and is in complete contrast to the majority of proceduresboth exact and many of the approximate onesthat are used in the case of the unconstrained travelling salesman problem. However, once a constructive method is used to produce a solution to the vehicle routing problem, this solution can be improved by applying local optimization techniques which maintain the feasibility of the solution.

Before proceeding with a description and computational comparison of the various heuristic procedures available for solving vrps, we will extend the basic vrp described in Section 11.1.1 by introducing a few of the most usual additional constraints that are found in real-world problems. For any heuristic procedure to be practically useful, it must be able to deal with most

322

Nicos Christofides, Aristide Mingozzi, and Paolo Toth

(if not all) of the following list of constraints. It perhaps should be pointed out here that this list is by no means exhaustive. In order to distinguish this problem from the basic vrp, we will refer to it as the extended, vrp.

11.3.1 The Extended vrp

Again we consider a set X of customers, a depot x0, and a set V of vehicles.

A customer x, has the following requirements:

Cl. A set of L, different types of products to be delivered by a vehicle. With each product type (i,l), 1 = 1,..., L, is associated a quantity qa and a label irt (See later for the meaning of this label).

C2. A time u, required to visit the customer and to unload the total quantity

**120**> 121 122 123 124 125 126 .. 156 >> Next