# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**133**> 134 135 136 137 138 139 .. 156 >> Next

size Oj1 5 10 15 20 30 30 40 40

level yL- 0 10 10 15 0 0 20 0

crude

type

0

1

0

0

Initial state1 ={4}./^ ={2,3},/^ = {7},fQ= {l,5,6,8}

/7 = 3 crudes, m = 8 tanks, N-11 operations

4>-- {l,2,4,7,10,1l} , ip = {3,5,6,8,9}

operation ?123456789 10 11 crude X( ?)1 3223 132 1 12

Figure 12.5 An example of a loading/unloading problem. Amount to be loaded/unloaded at each operation is shown under the corresponding bar

Loading Problems

355

We assume that there are N loading and unloading operations that must take place and that these are known. At the 1th operation, (1 = 1,..., N), either a loading or unloading of an amount q, takes place starting at time r( and finishing at time T, (t, and Tt are related by the amount to be loaded/unloaded and the rate of loading/unloading). In total there are n different types of liquid i (i = 1,.. ., n) each of which can appear in the sequence of loading/unloading operations more than once. Liquids of different types must be kept in different tanks and cannot be mixed.

Let 4> and ip be the index sets of the loading and unloading operations respectively, and let A (I) be the type of liquid involved in the 1th operation. There are m tanks available of capacities Qu ..., Qm and corresponding costs Vm.

Let E, be the set of tanks that are empty after the 1th operation takes place, Fj be the set of tanks holding liquid i and y| be the amount of liquid in tank j at the end of the Ith operation. When 1 = 0, E0, FJ, n),

yo (/ = 1,..., m) define the initial condition of the tanks.

We first recall the two assumptions ((i) and (ii) in the Introduction) relating to the dynamic loading and unloading problem considered in this part. The objective considered is to minimize

where pi is a weight given to the Ith operation. If we indicate by k the first operation following 1 for which A(fc) = A (I), then one way of defining p. is:

In this case expression (12.15) becomes an integral criterion which gives the average cost of tanks holding crude during the period in which the loading and unloading operations take place.

If 1 is the last operation involving crude A(l) then p, can be set to Tf -t, if 1 e <f> or Tf - T, if I e if/ where Tf is some final time at which the sequence of loading and unloading operations is considered finished. For the problem shown in Figure 12.5, p, and p10 (for example) are shown in that figure.

We should also, perhaps, note here that if pi is set to 0 for all operations I except for the last operation of each crude, and set to 1 for all last operations, then expression (12.15) becomes an objective depending only on the terminal state.

N

2 = I P, E V,--

1=1 ieft'

(12.15)

p, = tk -1, if I, ke<t>

= Tk-ti if I e <f>, k e ip

= Tk - Tt if I, k e

= tk-Ti if I e ip, k e <p

(12.15a)

356

Nicos Christofides, Aristide Mingozzi, ana Paolo Toth

It may be worthwhile to note here that with a given set of tanks, and initial conditions of the liquid in these tanks, it may not be feasible to execute a given sequence of loading and unloading operations.

12.2.2 The Problem

Let = 1 if tank / contains liquid A(Z) at the end of the Zth operation and 0 otherwise, and let y{ be the amount of liquid in tank j. (We have ?{ = 1 iff

jeFi(,).)

A simple mixed integer programming formulation of the problem in terms of the above two vectors can be written down immediately. However, the structure of this formulation is not pronounced enough to lead to any special algorithm other than the general integer programming procedures. An alternative formulationwhich is the one on which the tree search procedure of the following sections is basedis described below.

Definitions

A set Sc{l,...,m) of tanks is called weak minimal with respect to quantities q and q' of liquid if:

q'=s XQ <q + max[Q,-]. (12.16)

ies ies

It is called weak maximal with respect to q, q', and a set S' 3 S if either X Qj > q' 5s X Q > d ~ max [QJ (12.17)

jeS' jeS jeS'-S

or

S = S' and q' = X Q

/ eS'

Let the operations be numbered in ascending order of time t, where for 16 <(>, r, = t, and for I e tp, t, = T(. Ties for cases where rt = rk for two operations I and k are broken arbitrarily except when I e <f> and k e i/< when k is ordered before I.

Let a, be the total quantity of liquid A (I) that exists in the system after operation (, that is:

1= X y'o+ X <?k- X dk- (12.18)

l'eFS<n k <t> keti/

kl k<(

\(k) = \(l) A.(k) = A (I)

Loading Problems

357

Let tt(1, i) be the maximum value of k < I for which A(k) = i. If no such k exists we will assume ir(l, i) = i. We will also write tt(7, A(Tj) as tt(1) for short.

Consider the situation just before operation I The set S' = F*j of tanks contains liquid A.(I)- If / ? 4> only an amount qh q, 3^ q, 5s qf = di Ejes Oj(!)] needs to be loaded into new tanks. It is quite obvious that for any sequence of operations to be optimal (for any objective function 2 for which: S^Sa-the set of tanks into which q, is loaded must form a weak minimal set as defined by (12.16) with q' = q( and q = q,.

**133**> 134 135 136 137 138 139 .. 156 >> Next