Books
in black and white
Main menu
Share a book About us Home
Books
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics
Ads

Combinatorial Optimization - Cristofides N.

Cristofides N. Combinatorial Optimization - Wiley publishing , 2012. - 212 p.
Download (direct link): сombinatorialoptimi2012.pdf
Previous << 1 .. 114 115 116 117 118 119 < 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
Previous << 1 .. 114 115 116 117 118 119 < 120 > 121 122 123 124 125 126 .. 156 >> Next