# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**123**> 124 125 126 127 128 129 .. 156 >> Next

Step 4 The links picked form a solution to the vrp.

A number of comments about the above procedure must be made.

(a) In the parallel version, the final number of routes producedand their feasibility in terms of the vehicles availablecannot be guaranteed. Instead, one could impose the restriction that no more than M routes are being formed in parallel at any one time and test for a feasible vehicle assignment to these M (or less) routes at each stage. If the addition of a link would cause the number of routes to exceed M, the link is rejected.

(b) In the sequential procedure the partially completed list of routes must also be tested at each step for a feasible vehicle assignment.

If at the end of either sequential or parallel procedures some customers remain unrouted, new starting times can be computed for the vehicles and the procedure repeated. Alternatively, in the case of a sequential procedure a new starting time can be computed for a vehicle whenever its corresponding route is completed.

11.4.2 The Algorithm of Mole and Jameson (1976)

The algorithm of Mole and Jameson is a sequential procedure in which, for a given value of the two parameters A and p., the following two criteria are used to expand a route under construction:

e(i, /, i) = cd + cu - /xc,(

tr(i, l,j) = \col-e(i, l,j).

The algorithm then proceeds as follows:

Step 1 For each unrouted customer x, compute the feasible insertion in the emerging route R as:

e(i l,h) = minO(r, I, s)]

for all adjacent customers x,, xs e R, where x1( and xh are customers between which x, has the best insertion.

Step 2 The best customer x(. to be inserted in the route is computed as the one for which the following expression is maximized:

<r(ir, I*, h*) = max [o-(i,71, /,)]

for x, unrouted and feasible.

Step 3 Insert x,. in route R between Xjr and x^..

The Vehicle Routing Problem

329

Step 4 Optimize route R using r-optimal methods (Lin and Kernighan, 1973).

Step 5 Return to Step 1 to start a new route R (see Note (a)), either until all customers are routed or no more customers can be routed.

It is easy to see in the above definition of <r(i, l,j) and e(i, l,j) that by changing the values of A and p. it is possible to obtain different criteria to choose the best customer for insertion. For example:

A = 0, p = I insertion of the customer with minimum extra-mileage;

A = 0, p = 0 insertion of the customer with the minimum sum of

distances to the two nearest neighbours;

1«A^2, p = A-l generalized Gaskells criterion (Gaskell, 1967);

A0<p<°° insertion of the furthest customer from the depot.

Generally, as A grows, the shape of the emerging route tends to be circumferential, and as p grows the presence of long links is discouraged.

Notes

(a) The above description explains how a route R is expanded by the addition of customers. Initially (and each time a new route is to be started) some cutomer xs must be chosen to initialize the route R as (x0, xs, x0). Customer x, may be chosen in a variety of ways, e.g. the furthest unrouted customer, the customer with the largest demand q the customer with the most stringent delivery time restrictions (r,r'p = 1,. .., Pj, etc.

(b) Mole and Jameson describe the procedure for a fleet of identical vehicles. In this case the assignment of a vehicle to an emerging route is trivial except where vehicles are used for second, third, etc., tripsin which case the departure times of vehicles from the depot (for these additional trips) will be different for each vehicle and a choice exists as to what vehicle to assign to the current route. More generally, at some stage when a route R is being constructed, different size vehicles with different starting and ending times and different allowable working periods will be available and an assignment of vehicles to routes must be made.

11.4.3 The Sweep Algorithm of Glllet and Miller (Gillett and Miller, 1974; Gillett, 1976)

In contrast to the previous two algorithms, which require only cost and time matrices [c,,] and [t,r], the present algorithm requires geographical coordinates for each customer. The procedure can again be classified as a sequential method.

330

Nicos Christofides, Aristide Mingozzi, and Paolo Toth

We will assume that the customers are ordered according to increasing values of their polar coordinate angles 0, = d0(i, 1) (taking customer 1 as reference)- The construction of an emerging route R is as follows:

Step 1 Starting from the unrouted customer xl; with the smallest polar coordinate angle, include in the route consecutive customers x,j5 x,3,..., as long as the set {xM, x,3, Xj3,...} of customers included can be routed into a feasible route R.

The emerging route R is periodically optimized by applying 2-opt or 3-opt local optimization procedures as customers enter R. Let x, be the last customer that has entered R.

Step 2 Find the unrouted customer x, nearest to customer x, of the route. If the insertion of x, in the route is feasible and worthwhile, insert x, in the route, update X[ and repeat Step 2.

**123**> 124 125 126 127 128 129 .. 156 >> Next