# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**147**> 148 149 150 151 152 153 .. 156 >> Next

we will obtain a way of treating side constraints and answering some of the questions which have been posed in Section 14.2.

14.4 Travelling Salesman Tours as Penalized Assignments

When a tsp is formulated as a linear assignment problem, it is well known that to an optimal solution of the latter does not necessarily correspond a

394 Franco Giannessi and Bernardo Nicoletti

Hamiltonian circuit of G. It can be shown that, either by suitably modifying the objective function, or by setting to zero some variables, a Hamiltonian circuit can be obtained as the optimal solution to the assignment problem.

Consider the real variables p.,, i = 1,..., n, associated with the vertices

Nu , Nn, and binary variables ai( e B = {0,1}, associated with

the arcs of G*; set

V- = Or, , M-n) = (12, , In, , n.n-l)

and consider the set

e j.R": - s=0, and

--------------*-3= l,if a = l[.

n I

Another n(n l)-uple of binary values

0 =(012, , Pin, ? , Pn,n-l) P,j 6 5

will be considered. Let M be a large positive real, and consider the

penalized distances!

' C;y +(1 if

Cij(aiy)-? M if i =; = 0, 1,.. ., n

. ciy otherwise

Finally the binary vector

b = (b0= 1, bu ..., bn), k<=B

is introduced.

Now consider the problem

(14.1a)

(14.1b)

(14.1c) (14.Id) (14.le)

min ] z (x,a) ^ Cyy (oci(-) -V,, |

I i,j =0 -*

iU= K i = 0,1, . .., n

1=0

b j = 0,1,.. ., n

i=0

jc.^0 i, ]=0, 1,..., n

/A Jo 5

+ It is assumed that G has no loops, otherwise trivial variants are necessary.

The Crew Scheduling Problem: A Travelling Salesman Approach 395

and call it ^(a,/3, fa); call the corresponding minimum and an optimal solution Z(a, (3, b) and x(a, /3, b), respectively. Moreover, denote by R((3,b) the feasible region of (14.1), i.e. the polyhedron defined by (14.1b)-(14.1e).

We remark that a and /3 play the same role: a = 0 penalizes arc (i, j), so that one expects Xy = 0 in an optimal solution of (14.1); the same fact is obtained from /3y = 0. Thus, such two kinds of penalties will be used alternatively; their introduction is motivated by the need to obtain different results. Thus, if eh denotes a vector of h unit components, the general problem (14.1) will be considered alternatively in the particular cases as:

0>(a, en<n_1); b) and Pie^, /3, b).

We also note that fa, = 0 implies x,, = x^ = 0, i = 0, 1,..., n, in a feasible solution of (14.1). This means that every path through Nt is considered infeasible, i.e. N, is cancelled, and the tsp is considered on the remaining graph. Thus

h=Ifa, (h 25 1)

J=1

is the number of vertices of G which it is legal to visit, so that a constraint of the form I"=1fa, & h imposes the need to visit at least h vertices in order to have a feasible circuit. When fa = n all the vertices of G must be visited, and the problem becomes the classical tsp.

First we will study problemt 3P(a, en(_lj, e) with the aim of characterizing a Hamiltonian circuit.

Remark that an optimal solution of 3P(a, 1, 1) has n +1 elements equal to 1, and n 1 of them are Xjj having I^jV/sSh. If aeB'1(n_1) has been chosen having more than (n -1)2 elements equal to zero, then for at least an arc (i,j), with l=si^/=?n, we have atl = 0 and in an optimal solution of (14.1a) is Xj, = 1, so that the minimum in ^(a, 1,1) is 5*M, and it does not correspond to a total distance of a path of G. For this reason we assume that a satisfies the constraint (assuming that n > 2)

Z <*;,- = n-1. (14-2)

1 5* j

Even if (14.2) is satisfied, there is not necessarily a feasible solution to problem i?(a, 1,1) with total distance less than M. In fact, if there are n - 1 of the a,, equal to 1, and if they have the same row index or the same column index, then there is no feasible solution of Sf(a, 1,1) with total distance <M. For this reason we are led to consider the set of all a e Bn("_1)

t For the sake of simplicity, and without fear of confusion, e,lfrl._ri and e will be replaced symbolically by 1, when considered as arguments of (*, *, *), R(*, *), Z(*. *, *), x(*, *, *).

396

Franco Giannessi and Bernardo Nicoletti

which satisfy (14.2) and which correspond to intersections of different rows and different columns. Let this set be Ht:

H1 = {aeBn(r,~1): ... =aj.1 = 1; I* il5..., is; h = k+1;

s = 1,..., n -1; al(, = 0, otherwise}.

It is easy to show that S'(a, 1,1) has feasible solutions with total distance less than M, iff a e Ht.

Unfortunately, the set Hl does not characterize the set of problems 9P(a, 1,1) which have optimal solutions corresponding to Hamiltonian circuits. To obtain this we consider the set of all a efl"1"-11 and such that

/*()# 0; (14.3)

Theorem 14.1 Let a e Hl. Every Hamiltonian circuit of G corresponds to an optimal solution of 2P(ot, 1, 1), iff ae H2.

Proof. Sufficiency. Let x* be an optimal solution of SP(a, 1,1) which always exists. (14.1b)-(14.1d) ensure that, for every vertex, there is only one arriving arc; (14.1c)-(14.1d) that there is only one departing arc. If follows that the set of arcs corresponding to the nonzero elements of x* form a circuit, which is not necessarily Hamiltonian, i.e. it may be composed of subcircuits which do not contain N0. Assume that there are at least two such subcircuits, so that there exists a circuit defined by fc < n vertices different from N0. Call 3 the set of arcs (/, j) of indices of the k variables corresponding to such a circuit. We have

**147**> 148 149 150 151 152 153 .. 156 >> Next