A model of "nonadditive" routing problem where the costs depend on the set of pending tasks

The paper investigates the problem of sequentially walking through a set of megalopolises, where the cost is aggregated in a nonadditive way and the walk is restricted by precedence constraints. The cost functions, which measure the quality of the steps of the process, depend on the list of "pending" tasks. The mentioned dependence may arise in real-world problems connected with movement through a radiation field, for example, while dismantling ionizing radiation sources. Other applications are possible as well.

The obvious prototype of the considered problem is the well-known intractable [1] travelling salesman problem (TSP); see [2–4] et alia. Note papers [5,6] devoted to dynamic programming solutions of the "additive variety" of the TSP. Branch-and-bound methods (see [7]) and various approximate methods (see [4, 8] et alia) are widely used.

In real-world applications, there exist problem statements conceptually resembling TSP, however, marked by peculiarities of a specific task; see [2]. Along with the most studied "additive" TSP and its analogs, problems with nonadditive cost aggregation are of interest; see [9,10] et alia. In particular, it is of interest to provide for dynamic programming solutions of the mentioned "nonadditive" problems with constraints; our paper serves to continue the research in that direction for a more sophisticated bottleneck problem. We study a sequential process made of a finite number of steps; we optimize the cost of the most costly step, which leaves us with a minimax problem. In connection with this, let us consider a more substantive instance of the theoretical problem studied below.

Consider the following example of movement cost functions dependent on the list K of pending tasks: for given megalopolises Mk, k E K, assume exterior movement c(x, y, K) = p(x, y) + a(K) maxkGK p(y, Mk), interior jobs Cj(x,y,K) = (p(x,aj) + p(aj,y) + b(K) maxkGK\{j} p(y,K \ {j})), where p(^, •) is a metric (distance), and a(K) and b(K) are nonnegative functions. These cost functions reflect the demand to construct a route such that in case of an emergency call from some megalopolis that is not yet traversed it would be possible to arrive there as quickly as possible after completing of the current task. Such circumstances may arise in the operations of a repair brigade that conducts planned repairs of the objects (megalopolises) and – in case of an emergency – rescue and reconstruction; the task that is in process at the time of an emergency call is not forfeited because the costs associated with the deployment of the brigade on site (viz., megalopolis) are high, yet comparable with the losses associated with idle time of the object that has suffered an emergency.

1.    General Notation and Definitions

We employ the standard set-theoretic notation (quantifiers, propositional connectives, etc.); symbol = denotes equality by definition. Each set, all elements of which are sets themselves, is called a family. For every two objects a and b, denote by { a; b } the (unique) set that contains a, b, and nothing else. In the case a = b, this yields a singleton { a } = { b } . If u and v are objects, then (u,v) = {{ u } ; { u; v }} [11, p. 67] is the ordered pair (OP), the first element of which is u and the second one is v. For an OP z, notation pr 1 (z) denotes its first element and pr ₂ (z) denotes its second element; these are uniquely defined by the condition z = (pr 1 (z), pr ₂ (z)); in case z E A x B , where A and B are sets, we have pr 1 (z) E A and pr ₂ (z) E B. As usual [12, p. 17], for any three objects a, b, and c, we assume (a,b, c) = ((a, b),c), which yields the triple with the elements a, b, and c. For any three sets A, B , and C , we use the traditional [12, p. 17] convention A x B x C = (A x B ) x C ; it obviously means that (x, y) E A x B x C V x E A x B V y E C .In connection with this, let us also recall the convention we would need later [13, p. 61], which concerns the notation for values of function of three variables: for sets A, B , C, and D, function h : A x B x C ^ D and elements p E A x B and v E C , in accordance with the abovementioned representation of A x B x C , it is valid to consider the element h(p, v) E D to be defined.

As usual, [0, to[ = { £ E R | 0 С C } ( R is the real line). For each nonempty set S , denote by R ₊ [S] the set of all (nonnegative) functions from S to [0, ^ [. As usual, N = { 1; 2;... } . Assume N ₀ = { 0 } U N and pTq = { i E N ₀ | (p С i)&(i С q) } V p E N ₀ V q E N ₀ .

For a nonempty finite set K , let | K | E N denote the power of the set K ; then, let (bi)[K] denote the set of all bijections of the "interval" 1, | K | onto K . In particular, for a fixed N E N , let P = (bi)[1, N ] be the set of all permutations of the "'interval" 1, N ; for each A E P , there exists a permutation A ^-1 E P such that A (A ^-1 (k)) = A ^-1 (A(k)) = k V k E 1, N.

Denote by P (H ) ( P ‘ (H )) the family of all (all nonempty) subsets of set H ; let Fin(H) be the family of all finite sets from P ‘ (H ).

2.    Problem Statement

Here and below, fix a nonempty set X, a point x ⁰ E X , which is called the base, a natural number N , N ^ 2, sets M ₁ E Fin X,..., M N E Fin X, referred to as megalopolises, and relations

M l EP ‘ (M l x M 1 ),..., M n EP ‘ (M N x M n ). (2.1)

For j E 1,N, OP z E M j describes the possible ways of conducting the interior jobs inside the megalopolis M j : pr ₁ (z) determines the entry point and pr ₂ (z) determines the exit point . We study the issue of organizing of a system of movements

(x ⁰ ) ^ (pr i (z ⁽¹⁾ ) E M a(1) ^ pr 2 (z ⁽¹⁾ ) E M a(1) ) ^ ^ (pr 1 (z ⁽²⁾ ) E M a(2) ^ pr 2 (z ⁽²⁾ ) E M a(2) ) ^

(2.2)

→........................ →

^ (pr1(z(N)) E Ma(N) ^ pr2(z(N)) E Ma(N)), where a is a permutation of indices from 1, N and OPs z(1),..., z(N) satisfy the conditions

z ⁽¹⁾ E M a(1) ,...,Z ^(N) E M a(N) .

(2.3)

In (2.2), we choose the permutation a, in our terms, the route, and a tuple (z ⁽¹⁾ ,..., z ^(N) ) that agrees with the route in the sense of (2.3); this tuple is called a track . Let us stress that the choice of α may be restricted by precedence constraints , which would be introduced below. Let us hereinafter assume

(x ⁰ E M j V j E 1, N )&(M p П M q = 0 V p E 1,N V q E 1,N \ { p } ).       (2.4)

Conditions (2.4) are relatively common in applications, see [13, Pt. 1,2]. In connection with (2.1), let us make the following conventions:

M j. A { pr 2 (z) : z E M j } V j E 1, N.

(2.5)

In terms of megalopolises and sets (2.5), let us introduce two nonempty finite subsets of

X:

X A { x ⁰ } и

(UM)

X A { x ⁰ } U Qj M i ) ;

(2.6)

cle arly, X ⊂ X . To define precedence constraints, let us first introduce the set K ∈ P (1,N x 1,N) and call its elements address pairs. In an address pair h E K , the first element pr ₁ (h) E 1,N is called a sender, and the second one pr ₂ (h) E 1,N is called a receiver . The essence of precedence constraints is that for each pair the sender must be visited before the receiver. The case K = 0 is not excluded and corresponds to lack of precedence constraints.

Recall that P = (bi)[1,N] is the set of all (complete) routes; it is a nonempty set of cardinality | P | = N !. Clearly [13, Pt. 2],

A A { a E P | a ¹ ( pr ₁ (h) ) < a ¹ ( pr ₂ (h) ) V h E K ^                (2.7)

is the set of all routes from P that are feasible in the sense of precedence. Let us assume

V K o G P ‘ ( K ) 3 z o G K o : pr i (z o ) = pr 2 (z) V z G K q .

(2.8)

Assumption (2.8) implies that, in particular, pr _i (z) = pr ₂ (z) V z G K . It also implies [13, Pt. 2] that A = 0 and, consequently, A G P ‘ ( P ). Clearly, A is the set of all routes a G P such that

(( pr i (z) = a(t i ) ) & ( pr 2 (z) = a(t 2 )^ ^ (t i <  t 2 )

for an address pair z G K and "times" t _i G 1,N and t ₂ G 1,N. In addition to the route, we also choose the track, or trajectory, which is determined in the sense (2.2) by the OPs z ⁽ⁱ⁾ ,..., z ^(N) , supplemented with the initial OP (x ⁰ , x ⁰ ). To formally define the set of tracks tha t ag ree with some route in the sense of (2.2), denote by Z the set of all tuples (z i ) _iG0N ^: 0, N ^ X x X . For a G P , assume

Z a — { (Z i ) _i6o;N G Z | ( z o = (x ⁰ ,x ⁰ ) ) & ( z t G M a(t) V t G 1,N ) j ;

(2.9)

evidently, Za G Fin(Z). On the set X x X x N, where N — P‘(1, N) (we call an element of N a task list or just a list), we consider N + 1 cost functions c G R+(X x X x N),ci G R+(X x X x N),..., cN g R+(X x X x N).

For a G P and ( z i ' ,. ₀ N G Z _a , assume

C a [ ^(z i ⁾ i_G0,N ] —

max   c(pr2(zt), pri(zt+i), {a(s) : s G t + 1, N}) + tG0,N-i

(2.10)

+ c a(t+i) ⁽z t+i , ^{{ a(s) : s G} t + 1, ^{N } )}] .

We consider (2.10) a criterion of the quality for a solution (a, iz,G ₀ N ) (see (2.2)). Since our choice of the route is restricted by precedence, let feasible solutions (FS) be the OPs (a, (z i ) _iG Q" N ), a G A , (z i ) _iG Q" N G Z _a . From the mentioned properties A = 0 and Z _a G Fin( Z ) for a G A , we know that FSs form a nonempty finite set. We can now consider the problem

C a [^{( z} i ⁾ iG0,N] ^ ^min, ^{a G} A , ^(z i ) iG0,N ^G Z a .                     (2.1¹)

To this problem, we assign its value (its extremum)

V ^— min min   C al^iGO^N ] ^G t^0, ^ [                 ⁽2.1²⁾

aGA (zi)i^0,N GZa and a nonempty set of optimal FS; an FS (a0, (zQ)iGQ”N), a0 G A, (zQ)iGQ”N G Zao, is considered optimal for problem (2.11) if Cao [(zQ)iGQ_N] = V•

Let us explore the idea of problem (2.11). Process (2.2) is a number of steps, and at each of them the "system" suffers harmful effects. The latter occur both throughout exterior movements and interior jobs (which take place inside megalopolises). Those steps are x0 ^ (z(1) G Ma(1)), pr2(z(1)) ^ (z(2) G Ma(2)),..., pr2(z(N 1)) ^ (z(N) G Ma(N)) (2-13)

(obviously, (2.13) pertains to the case of N > 3). At the end of each step, all harmful effects suffered throughout it are "reset": the system is "decontaminated". It is considered to be important for the doses suffered at each step to not exceed the given threshold connected with the normal operation of the "system".

The objective of movements (2.13) is to "turn off" the sources of harmful effects. In case of movement through radiation fields it may consist of sequential dismantlement of ionizing radiation sources (read disaster cleanup operations similar to those carried out in Chernobyl or Fukushima). Such circumstances may arise when dismantling a decommissioned nuclear power unit if the process is carried out by a special robot that should first of all "survive" to complete the dismantlement of all radiation sources.

3.    Extension of the Full Problem and the Dynamic Programming Method

In this section, following [14] and (conceptually) [13, § 4.9], let us consider a natural extension of problem (2.11), which would serve as a base for the necessary version of dynamic programming; the constructions are intentionally abridged. For K ∈ N, let S[K] = {z G K | (pr 1 (z) G K )&(pr ₂ (z) G K )}. Based on this, define the mapping I on N by the rule

I (K ) = K \ { p^(z) : z G S[K] } V K G N. (3.1)

Condition (2.8) directly implies that S[ { t } ] = 0 for t G 1,N; consequently, I ( { t } ) = { t } . In terms of I (3.1), define the partial routes that are feasible in the sense of a crossingout operation connected with I : For K ∈ N, let

( I - bi)[K] = {a G (bi)[K] | a(s) G I ({ a(t) : t G s, | K | }) V s G 1, | K|} =

=< a G (bi)[K] | a(s) G I ( K \ { a(t) : t G ={ a G (bi)[K] | ( a(1) G I (K) ) & ( a(s) G

1,s - 1 }) V s G 1, | K || =

I ( K \ { a(t) : t G I77 —T }) V s G 2^K \ ) };

(3.2)

we assume 1, 0 = 0 (for p G N ₀ , q G N ₀ , and q < p, we generally have p,q = 0 ; see Section 1). Using properties stated in [13, Pt. 2], in particular, we obtain

A = ( I - bi)[1,N] =

= {a G P | ⁽ a(1) G I (1,N) ⁾ & ⁽ a(s) G I (1,N \ ^{ a(t) : t G 1,s - 1 ^}) V s G 2^N ⁾ }. ^^

It is a special case of (3.2) that corresponds to the main, i.e., "full" problem. Returning to (3.2), let us note (see [13], [14]) that ( I - bi)[K] = 0 V K G N. Thus, crossing-out feasible partial routes do exist.

Let us now define a partial track. For K E N, let Z K be the set of all tuples (z i ) i_c0 । K| : 0, | K | ^ X x X ; if, in addition, x E X and a E (bi)[K], let

Z(x,K,a) ^ {(^ад E Z k I ( z q = (x,x) ) & ( z t E M a(t) V t E 1, | K | )} E Fin( Z n ). (3.4)

In view of the definitions just given, define the partial (shortened) quality criterions: if x E X , K E N, a E (bi)[K], and (z^ i^K E Z (x,K,a), let

C K [ (z i ⁾ ieQ 7m 1 “ ^max [^c ( Pr^z t ), P^r 1 (z t+1 ), { ^{a(s) : s E} t +^{1, | K} | }) + ’        te^Q|K|-1 L                                                                    (3.5)

+ c a(t+1) zZ t+E { ^{a(s) : s E} t + 1,

In terms of (3.5), we define partial routing problems (roughly speaking, subproblems ): for x ∈ X and K ∈ N, the problem is

C n Jz- ' , .-,/ ^ ^{min,a E ( I - bi)[K]}, (-'ni.n ^{E Z(x,K,a)}.        (3.6)

Recall that (see, in particular, (3.4)) constraints of each and every problem (3.6) are consistent; each problem has its value (its extremum)

v(x, K ) = min aG( I -bi)[K]

min

^{(z i )} i e o, | K| ^{G Z ( x,n,a )}

C K [ ^{(z i )} i6Q,|K| 1 ^{E [0}, ^ '

(3.7)

and a nonempty set of optimal solutions. For x ∈ X and K ∈ N, FS

(a*, (Х^ОТ^), a* E A, (zOiEQXi E Z(x,K,a*), is optimal in some problem (3.6) if CK ) [(zDieOnKJ 1 = v(x, K).

Note that in (3.6) and (3.7) we may as well assume x = x ^Q and K = 1,N. For a E P (which means a E (bi)[1,N]), by (2.9) and (3.4), we obtain the equality

Z a = Z (x ^Q , 1?N,a)                             (3.8)

(note that Z = Z ^ n ). Moreover, A = ( I — bi)[1,N] (see [13, Pt. 2]). Then, by (2.12),(3.7), and (3.8), we have the equality

V = v(x ^Q , 1,N).                                  (3.9)

In connection with (3.9), note the obvious consequence of (2.10) and (3.5): for α ∈ P and (zi)iGQ^N E Za, we have Ca[(zi)iGQN 1 = C1N[(zi)iGQ;N 1, where we also take into account (3.8). Set v(x, 0) = 0 Vx E X. Thus, we have defined the Bellman function v : X xP(1,N) ^ [0, ^[.                         (3.10)

Theorem 1. For x ∈ X and K ∈ N , we have the equality

v(x, K ) = jinin min sup ^ {^c( x, pr i ^(z),K ) + c j (zK ) ; v( pi 2 ^(z),K \ ^{ j } )}) .   (3.1¹)

Proof. Fix x G X and K G N; then, n = | K | G 1, N and (n = 1) V (n G 2, N ). These cases are examined separately.

• 1)    In case n = 1, we have the equality K = { t } for a certain t G 1,N ; consequently, I (K) = { t } . Further reasoning is essentially obvious (in the case of n = 1); it leads to the conclusion that

(n = 1) ^ ^v ( x,K ) =

(3.12)

= min min sup je i (K) zeM j

+ c j

• 2)    Let n G 2,N. Then, n — 1 G 1,N — 1, K \ { j } G N, and

| K \{ j }| = n — 1 V j G I (K).

(3.13)

By (3.7) and (3.13), we have the following equalities:

v( P^r 2 ⁽Z^),K \ ^{ j}) =

min

min

^ae( I -^bi)[K\^{j}] (z i ) i e 0:n - i G^Z(P^r 2 ^(z),K\{^j},^a)

C K\{j} [ ^{(z i )} iea,n-i ]

(3.14)

V j G I (K) V z G M j .

This system of equalities is used in the two constructions that follow.

2 ‘ ) In view of (3.7), pick a ^a G ( I — bi)[K] and (z ^a ) _iGQ-n G Z(x,K,a ^a ) such that ^v(x, K ) = C K? ⁰ ) [ ⁽z ^{a )} ie o^ n ] .

(3.15)

In connection with (3.15), note that

C K 0 [ (z ° ka n = ^suP

c (x;pr i (z ^a ),K) + C a o (i) (z 0 ,K);

max ^c(P^r 2 ⁽z ^{a )}, pr^z f+i ), ^{{ a} 0 ^{(s) :} s ^G t + ^1,n}) + tei,n-i L

(3.16)

+ c a ⁰ (t+i) ( z t+i , ^{{ a} 0 ^{(s) : s G} t + 1,^{n }} )

.

It is of use to remark that a0(1) G I(K) and z0 G Mao(i). Then, min min sup jei(K) zeMj

+ c j

<

(3.17)

< sup

+ C _a o

where K = K \ { a ^a (1) } . Expression (3.14) now yields the following equality:

v(pr 2 (z ⁰ ), K ) =

min

min

^{ae( I —bi)[ K ]} (z i ) _{i G 0} -_n -₁ 6Z(pr 2 (z ⁰ ),K,a)

C K) [ ^(z i ⁾ ieo,n-i ] .

(3.18)

Note that since |K| = n, we have a0 : 1,n : K (aa is surjective), thus aa(t + 1) G K for t G 1,n — 1. Moreover, since aa is injective, aa(1) = aa(t) Vt G 2,n. Then, aa(1) = a°(t + 1) Vt E 1,n — 1. Finally, a0 = (a0(t + 1))1 n-1 maps 1,n — 1 onto K, i.e., a0 :

1,n — 1 : K. Moreover, in view of [15, Proposition 3], ao E (I — bi)[K].

(3.19)

According to (3.4), (z O ) ieon E Z K and, in addition,

( z ° = (x,x) ) & ( z f E M _a 0 (_t) V t E 1,n ) .                       (3.20)

Then, pr ₂ (z ⁰ ) E X and hence, in view of (3.4) and (3.19) and the equality | K | = n — 1, we have

^{Z (}P^r 2 ⁽z ⁰ ), ^{K ,a} o ⁾ = {⁽ z i ⁾ i_G o; n-T ^E Z K | ( ^z o = ⁽P^r 2 ⁽z ^{0 )}, P^r 2 ⁽z ⁰ )) ) & &(z t E M a ₀ (t) V t E 1, n — 1 )} .

Consider a tuple (z ° ) _{tG 0 n - 1} : 0, n — 1 ^ X x X defined in the following way:

( ^z 0 = ( P^r 2 ^{(z 0 ),} P^r 2 ⁽z ⁰ ) )) & ( ^z t = ^z t+1 ^{Vt E 1,n —} 1 ) .

Since | K | = n — 1, taking into account (3.21) and (3.22), we obtain

(z ⁰ ' /. 0,n . ^{E Z} ( P^r 2 Cz ⁰ ), ^{K ,a} o ) .

From (3.18), (3.19), and (3.23), it follows that v^Cz0), K) < CK 0) J -Vh- 0,n / = max

^c( P^r 2 ^(Z t^{0 ),} P^r 1 C^Z t⁰+1 ^{), { a} o ^{(s) :}

tG0,n-2

s ^E t + 1, n ^{— 1 }} ) + c a ₀ (t+1) ( z t +D ^{{ a} 0 ^{(s) : s E} t +^{1,n — 1}

(3.21)

(3.22)

(3.23)

(3.24)

Since { a ₀ (s) : s E t + 1, n — 1 } = { a ⁰ (s + 1) : s E t + 1, n — 1 } = { a ⁰ (1) : 1 E t + 2, n } , the expression in the right-hand side of (3.24) takes the form

^{(a o )}Tf £⁰A  _

C K   |_^(Zt ) tG0,n

1 ] = ^max [c ( P^r 2 ^(Z t^{0 ),} P^r 1 ^(Z t+1 ^{), { a 0 (1) : 1 E} t + ^{2,n }} ) + tG0,n-2 L

+c a ⁰ (t+2) (^ +1 , ^{{ a 0 (1) : 1 E} t + ², n ^} )] •

(3.25)

Expression (3.25) implies the following obvious property:

(T^{(a o )} l72⁰)

C K   |_^(Zt ) tG0,n

1 ] = ^max [c ( P^r 2 ^(z t⁰+1 ⁾, P^r 1 ^(z t+2 ), ^{{ a 0 (l) : 1 E} t + ^{2,n }} ) + tG0,n-2 L

+c a 0 (t+2) (^zt+2 ^,

{ a ⁰ (l) : l E t + 2,n } ) = max

A     9G1,n-1

^c( P^r 2 ^{(z 0 )}, P^r 1 ^(z °+1 ), ^{{ a 0 (l) :}

(3.26)

l ^E 9 + 1, n ^} ) + c a ⁰ (9+1) ( ^{z 0}+1 , ^{{ a 0 (1) : 1 E} 9 + 1, n ^} ) .

From (3.24) and (3.26), we obtain the estimate

v(Pr 2 (z ⁰ ), K ) <  max [ c ( Pr 2 (z ° ), Pf x (z °₊₁ ), { a ⁰ (1) : 1 E 9 + 1,n } ) +

0G1,n-1 L

(3.27)

+c a ⁰ (9+1) (^z 9+1 , ^{a°^{(1) : 1 E 9} + 1, ^{n }} ) .

From (3.17) and (3.27), we have minJei(K) minzGMj sup

+ c j

<

< sup

+ c a 0 (1) ^(z 0 , K ); ^max t_Gpn-i [c ( РГ 2 U 0 ). pr i (z^),

(3.28)

{ a ⁰ (l) : l G t + 1, n } ) + c _a o (t+i) ( z °+i , { a ⁰ (l) : l G t + 1, n

Expressions (3.16) and (3.28) yield the inequality

. minminsup (l^c(x, p^r i ^(z),K) + c j ^(z,K ); v ( p^r 2 ^(z),K \ ^{ j Щ) <  ck^{0 )} [ ^{(z 0 )} t_e od - jeI(K ) z€M j       у к                                                            > у

(3.29)

From (3.15) and (3.29), we obtain the estimate min min sup jEi(K) zeMj

+ c j

< v(x, K ).

(3.30)

Choose and fix an index q and its OP of entry and exit points z q G I(K),

Z G M q ,

(3.31)

(3.32)

such that sup

+ c q

(3.33)

= min min sup je i (K) zeM j

+ c j

For brevity, set

Q = K \{ q } .

(3.34)

1 >  1.

Expression (3.31) implies that, in particular, q G K, whence (see (3.34)) | Q | = n —

From (3.33) and (3.34) it follows that sup I U(x, pri(z),K) + Cq (z,K); v( pi2(z),Q)} ) =

(3.35)

= min min sup I i c (x, pr _i (z),K) + c j (z,K ); vfpr ₂ (z),K \ { j}) > 1. je i (K) zeM j       \ I                                   ^x                      )

From (3.32), we now obtain pr2(z) G Mq                                   (3.36)

and, in particular, pr ₂ ( z ) G X ; see (2.6),(3.36). Then,

(pr 2 ( z ),Q) G X x N.                              (3.37)

Thus, according to (3.7) and (3.37),

v⁽p^r 2 ^{( z ),Q)}=  .min^.. min _{M n} .CQ^UW -i J ;       (3.38)

ae(I-bi)[Q] (zi)ieojn-1eZ(pr2(z),Q,a)                                      V / here, in view of (3.5), we have the equalities

^{( a )}

C _Q

(z i ) iG0,n-1

max teo,n-2

c(pr 2 (z t ), pr i (z t+i ), { a(s)

s G t + 1, n — 1 } ) +

⁺ c a(t+1) ( z t+1 , ^{{ a(s) : s G} t + 1, ^{n —} 1

(3.39)

V a G ( I - bi)[Q] V (z i ) _ieo^n-i G Z (pr 2 ( z ),Q,a).

In accordance with (3.38), let us choose and fix a route в and a track (h i ) _{iG o n - 1}

в G ( I — bi)[Q],                            (3.40)

(hiko/ n-T G Z (pr 2 ( z ),Q,e),                          (3.41)

such that

^v(p^r 2 ^{( z ),Q)} = C Q [ (h ikon-l ] ,                         ⁽³.4²⁾

where (see (3.39),(3.40),(3.41))

v(pr2(z),Q) = max teo,n-2

c( pr 2 ^(h t ⁾, pMh t+1 ), ^{{ e(s)}

s G t + 1, n — 1 } ) +

+c e(t+1) ( h t+1 , ^{{ в(s) : s G} t + 1, n ^{— 1}

(3.44)

C Qe) (h i ) iGo,n-1 = max, L                    teo,n-2

c ( pr 2 (h t ),pr 1 (h t+1 ), { в (s) : s G t + 1,n — 1 } ) + (3.43) +c e(t+1) ( h t+1 , { в(s) : s G t + 1,n — 1 } ) j .

From (3.42) and (3.43), we obtain the following equality

Expressions (3.33), (3.35), and (3.44) imply that min min sup jei(K) zeMj

({ c ⁽x, pr 1 ⁽z^),K) + c^(z,K ); v ( p^r 2 ^(z),K \ ^{ j ^} )

= sup ( s c (x, pr 1 ( z ),K) + c q ( z ,K); max

c( pr 2 (h t ), pr 1 (h t+1 ),

(3.45)

\ I                                   teo,n-2

^{{ в(s)} : s ^G t + 1, n ^{— 1 }} ) + c e(t+1) ( h t+1 , ^{{ e(s) :} s ^G t + ^1, n ^—

Note that q G K and, moreover (see (3.34),(3.40)), в (j ) G K V j G 1,n — 1. In view of that, let us introduce a mapping

/3 : 1, n ^ K,                                    (3.46)

defined by the following conditions:

(/3(1) ^ q)&(/(j ) = /(j — 1) V j G 2,^ ) .                    (3.47)

Zs

Let us show that в G (bi)[K]. To this end, let us start by noticing that, since в maps 1,n — 1 onto Q, we have V j G Q 3 s G 2,n : j = в(j)• In view of (3.34) and (3.47), we

Zs                             ____________ Zs                             ____________ obtain K С {в(1) : l G 1,n}, i.e., K = {в(l) : l G 1,n} (we also took into account (3.46)).

Thus, в is (see (3.46)) a surjection of 1,n onto K . Let us check the injectivity of в. Fix indices j * E 1, n and j* E 1, n such that

Zs                          Zs в (j*) = в (j *).                                      (3.48)

Let v = /3(j * ). Then, v E K and в(у * ) = v. The two cases below are mutually exclusive:

(v = q) V (v E Q).                                 (3.49)

• a)    Let v = q. Since in view of (3.37), (3.40), and (3.47) we have в(,7') E Q for j E 2,n, we now see that в(l) = q V Z E 2, n. As в (j * ) = в (j * ) = q in the considered case, we obtain j * = 1 = j ^* . We proved that

(v = q) ^ (j * = j * ).                                (3.50)

• b)    Let v E Q. Note that in this case (в(j * ) E Q)& (в(j * ) E Q). We can therefore conclude from (3.34) and (3.47) that j * = 1 and j * = 1. Then, ( j * E 2, n ) & ( j * E 2,n ) and hence (see (3.48)) в(j * - 1) = ви * ) = ЗС? * ) = в(j * - 1); since в is injective (see (3.40)), j * = j * . Thus, (v E Q) ^ (j * = j * ). Taking into account (3.49) and (3.50), we obtain the equality j _* = j ^* for all cases. Thus (see (3.48)), (/3(j * ) = в(.7 * ) ) ^ (j * = j * ). Since the choice of j ∗ and j ^∗ was arbitrary, we have proved the injectivity of β , whence, finally,

в E (bi)[K],                                     (3.51)

i.e., в is a partial route. Let us prove that it is crossing-out feasible:

в E ( I - bi)[K].                                 (3.52)

Indeed, let y E 1,n (recall that | K | = n); consider the set Г = {в№ : t E Y,n } The two following cases are mutually exclusive:

(Y = 1) V (Y E 2/n).                                (3.53)

a’) Firstly, let y = 1. Then, y, n = 1,n and, by virtue of surjectivity of в, we have Г = { в(t) ^: t E 1,n } = K; hence, in view of (3.31), q E I (F) and, according to (3.47), в(1) E I (F), where в(1) = в (y ). Thus, we have proved the implication

Zs

(y = 1) ^ (в(Y) E I (F)).                            (3.54)

b’) Now, let y E 2, n. Then, y — 1 E 1,n — 1. Therefore, we can consider the index

Zs

в (y ) = в(Y — 1) E Q                           (3.55)

(see (3.40)). Then, according to (3.2), (3.40), and (3.55),

/5⁽Y) ^{E i} ({ ^{/ (t) :} t ^E Y ^{— 1,n —} ! }) •                         ⁽³.5⁶⁾

Let us introduce the set

F o 4 { в(t) : t E Y — 1,n — 1 } E P ‘ (Q).                     (3.57)

Show that Г = Г ₀ . Indeed, let y * G Г and let t * G Y,n be such that

y * = в(t * ).                                        (3.58)

Then, since 2 ^ y , we also know that t * G 2, n, t * — 1 G 1,n — 1, and /3(t * ) = в(t * — 1), i.e., y * = в (t * - 1) in view of (3.58). On the other hand, we chose t * such that t * — 1 G Y — 1,n — 1, whence (see (3.57)) в(t * — 1) G Г 0 and, therefore, y * G Г 0 . Since the choice of y _∗ was arbitrary, we have found out that

Г С Г 0 .                                     (3.59)

Now, let y ₀ G Г ₀ and let t o G Y — 1,n — 1 implement the equality

У о = в (t o ).                                        (3.60)

In addition, t ₀ + 1 G Y, n and, by definition of Г, we have the inclusion

в(^ + 1) G Г.                                  (3.61)

In addition to this, 2 ^ y ^ t o + 1 and, therefore, t ₀ + 1 G 2,n, hence (see (3.47)) в^ ₀ + 1) = в(t o ) and, by (3.60), y ₀ = в(£ о + 1); therefore, (3.61) implies that y ₀ G Г. Since the choice of y ₀ was arbitrary, we have proven that Г ₀ С Г, and hence, in view of (3.59), we obtain the desired

Г = Г о ,                                     (3.62)

where, in accordance with (3.56) and (3.57), we have the inclusion /(y ) G 1 (Г ₀ ), which means (see (3.62)) that /(y) G 1 (Г) for y G 2,n as well. Thus, we have proven the implication (y G 2, n) ^ (в (y ) G Т (Г)). In view of (3.53) and (3.54), we have the inclusion /(y) G 1 (Г) in all possible cases, i.e., /(y ) G T ( {/ 3(t) : t G Y,n } ) . Since the choice of y was arbitrary, we have proven that

/ ( s ) G l ( {/3(t) : t G s, n } ) V s G 1,n.                         (3.63)

From (3.51) and (3.63), we obtain (see (3.2)) the desired property (3.52), i.e., now в G ( I — bi)[K]. Note that (3.4) and (3.41) imply that (h i ) _{iG 0} , _{n - 1} G Z q , i.e.,

(h i ) i_Ge;n-T : '         ^ X x X .                          (3.64)

According to (3.4) and (3.41),

^ h o = ( pr 2 ( z ),pi 2 ( z ) )^ & ^ h t G M e(t) V t G 1,n - 1 ) .              (3.65)

Note that from (3.65) we have the OPs ht-1 G Me(t-i) Vt G 2,n                            (3.66)

We also have (see (3.47),(3.66)) the following property:

h t-1 G M _e(t) V t G 2,n.                               (3.67)

Note that 1, n = {1} U 2, n and 0, n = {0} U 1, n = {0} U {1} U 2, n. In view of (3.64), we Zs                            ____________ may now consider a tuple (ht)tGo"n : 0, n ^ X x X defined by conditions

( h ₀ = (x,x) ) & ( h ₁ = z ) & ( h _t = h _t-1 V t E 2,n).                (3.68)

Clearly (since n = | K | ),

(h t ⁾ teo,n ^E Z K .

(3.69)

Zs

Then, (3.32) and (3.68) imply that h1 E Mq, whence, taking into account (3.47), we obtain hi E Мв(1).                                     (3.70)

Then, (3.4) and (3.41) imply that ht E Me(t) Vt E 1,n — 1. Then, expression (3.68), yields ht E Me(t-1) Vt E 2,n. Using (3.47), we conclude that ht E Me(t) Vt E 2,n. In view of (3.70) and the last property, we obtain the system of inclusions ht E M^t) Vt E 1,n.                             (3.71)

From (3.68), (3.69), and (3.71), we conclude that

(h t )^ E Z k : ( h o = (x,x) ) & ( h t E M^ V t E Tn).           (3.72)

But in this case, (3.4) and (3.72) imply that

(h tWn E Z(х,К,в)                        (3.73)

In accordance with (3.52) and (3.73), we see that the OP (Д (ht)teo~n) is an FS of the considered partial problem, therefore (see (3.7)), z z v(x,K) < CK

(3.74)

In view of (3.5),(3.52), and (3.73), we have z g(e) CK

Zs

⁽h t ⁾ t_Go;n = max

tE0,n-1

,                Zs                         Zs                        Zs                               _________________________ .

c( pr 2 (h t ),pr 1 (h t+1 ), { e (s) : s E t + 1,n})

+c /3(t+1) ( ^h t+1 ^{, {} /5^{(s) :} s ^E t + ^{1,n }} )] E [0, ro [.

Consequently, from (3.68) and (3.75), we conclude that

(3.75)

z g^(e) C _K

Zs

(h tWn = sup

^c ( x,pr 1 ^(h 1 ), ^{ /3^(s) : s ^{E 1,n }} ) + ^c_/ з(1) ( ^h 1 ^{, {} /3^(s) : s ^{E 1,n }} ) ;

max tG1,n-1

c( pr 2 (h t ), pr 1 (h t+1 ), { в (s) : s E t + 1,n}) + C g(_t+1) (h t+1 , { в(s) : s E t + 1,n

} .

In view of n = | K | , expression (3.51) yields { /3(s) : s E 1,n } = K . Using that, from (3.46), (3.68), (3.74), and (3.75), we obtain the inequality

v(x, K ) <  sup

^c ( x, pr 1 ( z ),K ) + C q ( z ,K ) ; _t^ max ₁

[c ( p^r 2 ^(h t ), P^r 1 ^(h t+1 ^),

Zs                                     ______________________________ .                                            . Zs                         Zs

^{{ в(s): s E} t +1 ,^n}) + c z(t+1) (h t+1 , ^{{ в(s)}

s E t + 1, n

} .

(3.76)

Consider the transformation of the expression

I .               Zs                         Zs                        Zs                            _________________________ .                                   VS                   Zs                            _________________________ .

c (pr 2 (h t ), pr i (h t +i ), { в(s): s G t + 1,n}) +c e ( _t+ i) (h t +i , { в(s): s G t + 1, n}) G [0, w [. ^{e( +} )

To this end, note that, according to (3.68),

c ( pr 2 (h 1 ), pr i (h 2 ), ^( s) : s G 2,n } ) = c ( pr 2 ( z ),pr i (h i ), ^( s) : s G 2,n } ) .     ⁽³.7⁷⁾

However, (3.65) implies that pr ₂ ( z ) = pr ₂ (h ₀ ). Then, (3.77) yields the equality

c ( pr 2 (h i ), pr i (h 2 ), ^( s) : s G 2,n } ) = c ( pr 2 (h o ), pr i (h i ), { в^ ) : s G 2,n } ) .     ⁽³.7⁸⁾

Moreover, (3.65) implies that (see (3.47)) с д^Сг) ( h 2 , ^{{ e(s) :} s ^{G 2}, n } ) = C e(_i) ( h i ,^{{в (s) :} s G 2,n}). Taking into account (3.78), we obtain

c ( pr 2 (h i ),pr i (h 2 ), { в^) : s G 2,n } ) + C p(2) (h 2 , { в^) : s G 2,n } ) =

= c(pr 2 (h o ), pr i (h i ), { в(s) : s G 2,n}) + c e(i) (h i , { в(s) : s G 2,n}).

This equality can be transformed into the following expression: if t G 1,n — 1, then, for t = 1,

^c( p^r 2 ^(h t ⁾, p^r i ^(h t+i ), ^{{ в(s) : s G} t ^{+ 1,n}}) ⁺ c S(t+i) (h t+i , ^{{ в(s) :} s ^G t ^{+ 1,n}}) = _s

(3.79)

= c( pr 2 (h t-i ), pr i (h t ), { в(s) : s G t + 1,n}) + c e(t) (h t , { в(s) : s G t + 1,n }) .

Choose arbitrary т G 2,n — 1. Then, т — 1 G 1,n — 2 and т + 1 G 3,n. From (3.47), we now have, in particular,

Zs в (т +1) = в (т) G K.

Then, (3.68) implies the following representations:

(3.80)

^h T ) •

(3.81)

( h _T = h _T-i ) & ( h

Thus (see (3.80),(3.81)) we obtain

/                Zs                          ZS                         ZS                               __________________________ -                                   z Zs                      zs

^c( p^r 2 ^(h T ), pr i ^(h T+i ), ^{{ в(s) : s G т + 1,n}}) ⁺ c^ +i) (^h T+i , ^{{ в(s)} Zs                                                                                                                                         Zs

: s G т + 1, n

= c(pr 2 (h T-i ), pr i (h T ), { в(s) : s G т + 1,n}) + с в(т) (h T , { в(s) : s G т + 1,n }) .

Since the choice of τ was arbitrary, we proved that

c(pr 2 (h t ), pr i (h t+i ), { в(s) : s G t + 1,n}) + C e(_t+i) (h t+i , { в(s) : s G t + 1,n}) = c(pr 2 (h t-i ),pr i (h t ), { в(s) : s G t + 1,n}) +

⁺ c e(t) ( h t , ^{{ в (}^ ^{: s G} t ⁺ 1,^{n }} ) ^ t ^{G 2},^{n —} 1.

From (3.79) and (3.83), we conclude that

(3.82)

(3.83)

c( pr 2 (h t ), pr i (h t+i ), { в(s) : s G t + 1,n}) +c e(_t+i) (h t+i , { в(s) : s G t + 1,n}) =

= c ( pr 2 (h t-i ), pr i (h t ), {/ 3(s) : s G t + 1,n } ) +                                            ⁽³.8⁴⁾

^+c e(t) ( h t , ^{{ в (}^ ^{: s G} t ⁺ 1,^{n }} ) ^ t ^G 1,^{n —} 1.

Let us now consider the set { в(s) : s G t + 1,n } for t ^ G 1,n — 1. Then, for s G t + 1,n, we have s G 2,n, whence (see (3.47)) в(s) = в(s - 1), where s — 1 G t ^ ,n — 1. In particular, we have s — 1 G 1,n — 1 V s G t ^ + 1,n. Thus (see(3.40)) we may define the indices

в(s - 1) G Q V s G t ^ + 1,n. (3.85)

Therefore, we have the set {в(s — 1) : s G t^ + 1,n} G P‘(Q); recall that t^ + 1 < n. Returning to (3.85), note that t\n — 1 is a nonempty subset of 1,n — 1 (by the choice of t^), thus в(l) G Q Vl G t\n — 1. Therefore, we also have the set B = {в(l) : l G t\n — 1} G P‘(Q) and the set B = {вЮ : l G t^ + 1,n} G P‘(K). In any case, B and B are not empty. Let us prove that they are identical. Let p ∈ B. Then, p ∈ Q and, for a certain l* G t\n — 1, p = в(l*). (3.86)

Then, l * G 1,n — 1, l * = l * + 1 G 2,n and, according to (3.46), в^ * ) G K ; however, (3.47) implies that в^ * ) = в(l * — 1) = в(l * ) = p. Nevertheless, l * G t ^ + 1,n, whence j3(l* ) G B . Thus p ∈ B , which completes the testing of the inclusion

B ⊂ B .

(3.87)

Now, let p G B. Then, p G K and, for a certain l* G t^ + 1, n, we have the equality p = в(l*).                                        (3.88)

In particular, l * G 2,n, l * = l * — 1 G 1,n — 1 and, according to (3.47), p = в(М = в(l * — 1) = в(l * ). However, by the choice of l * , we have l * = l * — 1 G t^n — 1, whence (see (3.88)) p = в(l * ) G B . We established the inclusion

B ⊂ B .                                  (3.89)

In view of (3.87) and (3.89), we obtain the desired equality

B = B .                                  (3.90)

In other words, (3.90) implies that {/3(s) : s G t ^ + 1,n } = { в(l) : l G t ^ ,n — 1 } . Since the choice of t ^ was arbitrary, we have established that { в(s) : s G t + 1,n } = { в(l) : l G t,n — 1 } V t G 1,n — 1. But in this case, (3.84) implies that

c( pr 2 (h t ), pr i (h _t+i ), { в(s) : s G t + 1,n}) + c ep+i) (h t+1 , { в(s) : s G t + 1,n}) =

c ( pr 2 (h t-i ),pr i (h t ), { в(l) : l G t,n — 1 } ) + c _P(t) (h t , { в (l) : l G t,n — 1 } ) V t G 1,n — 1.

In view of that, we have the following equality:

_t max [c ( pr 2 (h t ), pr i (h t+i ), {/ 3(s) : s G t + 1,n } ) + C g(_t+1) ( h t+i , {/ 3(s) :

s G t + 1,n })] = mgix |^c ( pr 2 (h g ), pr i (h ₅+i ), { в(l) : l G £ + 1,n — 1 } ) +      (3.91)

+ ^c e(€+i) ( h ^+i , ^{{ в(l) :} l ^{G £} + 1,^{n — 1 }} ) .

From (3.43) and (3.91), we have tiriaxi [c(pr2(ht), pri(ht+i), {/3(s) : s G t + 1,n}) + ce(t+1) (ht+i, {/3(s) : s

^(в) Гг/г             1

= C Q ^(h i ⁾ i E 0,n-i •

Then, (3.76) implies the estimate v(x,K)    ^ sup ^ |c (x,pr 1 ( z ),K) + c q ( z ,K);

C Q [ ⁽h i ⁾ i_Go;n-T ]}), whence, in its own turn, we obtain, in view of (3.42), the inequality

v(x,K) <  sup ( ^c (x, pr i ( z ),K) + C q ( z , K); v(pr 2 ( z ),Q) J У

(3.92)

Now, taking into account (3.35), we obtain

v(x, K ) <  min ^ m i n sup (|c(x,pr _i (z), K ) + C j (z, K ); v ( pr ₂ (z), K \ { j } ) }).    (3.93)

From (3.30) and (3.93), we get the desired equality

v(x, K ) = min ^ m i n sup (|c(x, pr _i (z),K) + C j (z, K ); v ( pr ₂ (z), K \ { j }) })

for the case of n G 2, N . In other words, ^ n G 2,N ^ ^

v(x, K) = min min sup    c (x, p

+ c j

j E 1 (П) zEM j       \ I

In view of (3.12), we have equality (3.11) in all possible cases.

□

From (3.9) and Theorem 1, it follows that

V = min_ min sup ( {^c(x ⁰ , p^r i ⁽z),^{1,N) +} C j ⁽z,^1,N ); v ( p^r 2 ⁽z),^1,N \ ^{ j ^} ) } ). (3.94) je i (i,N) zeM j        \ I                                                  ^{x                          7         v 7}

4.    Economical Dynamic Programming

In this section, we use the construction from [16], which stems from constructions of [13, § 4.9]; however, in [13] and [16], the criterion was additive, whence the need to adapt the mentioned construction of [16] to the problem considered in this paper. Following [13, 16], let us introduce the family

G = { K G N | V z G K (pr i (z) G K ) ^ (pr 2 (z) G K ) j,

(4.1)

elements of which (finite subsets of 1,N) are called feasible (task) lists. Assume G _s = {K G G | s = | K|} V s G TN The tuple ( G s ) sEiN evidently defines an (ordered) partition of G (4.1). Under this partition, G N = { 1,N } (the singleton reflecting the complete task list) and G 1 = {{ t } : t G 1,N \ { K _i }}, where K _i = { pr _i (z) : z G K } ; thus, G _i contains singletons corresponding to "nonsenders". In addition,

G s-1 = {K \ { t } : K EG s ,t E I (K)} V s E 2, N ;                (4.2)

see [16].

In view of (4.2), we obtain the recurrence relation GN —> GN-1 —> ... —> G1, which provides for construction of family (4.1) (recall that GN is known). It is also known [16] that Gs = 0 Vs E 1, N. If s E 1, N — 1 and K E Gs, then [16], in terms of the set

J s (K ) = { j E 1,N \ K |{ j } U K E G s₊i } E P ‘ (1, N \ K ),           (4.3)

construct M _s [K] in the form of union of all M , , j E J _s (K ); let us also construct a cell D s [K ] = {(x,K) : x E M _s [K]} of the position space. Then, as in [16], assume

D s = J D s [K] EP ‘ ( X x G s ) V s E 1,N — 1;                (4.4)

K∈Gs we have defined (intermediate) layers of the position space. Let us also define the two (nonempty) "border" layers: D0 = {(x, 0) : x E M}, where M is the union of all the sets M,, j E 1,N \ K1 and DN = {(x0,1,N)} (the singleton that contains the position (x0, 1, N)). The tuple (Ds)sG0"N possesses the following important property (see [13, §4.9]):

( y, K \ { k } ) E D s-i V s E 1Л V K EG s V k E I (K ) V y E M k . (4.5)

In connection with (4.5), recall that, acco rding to (2.5), pr ₂ (z) E M k V k E 1, N V z E M k . In addition, (4.4) implies that, for s E 1,N — 1 and (x, K) E D s , we definitely have K E G s (by definition of cells of the space of positions ); in case (x, K) E D N , we have K = 1,N E G N . Thus, K E G s V s E 1,N V (x,K ) E D s . Taking into account (4.5), we consequently obtain the property

⁽ pr 2 (z), K \ { k } ⁾ E D s-i V s E 1Л V (x, K ) E D s V k E I (K) V z E M k . (4.6)

Now, bearing in mind the fact that D0 E P‘(XxP(1, N)), D1 E P‘(XxP(1, N)), ..., and DN EP ‘ (X x P (1, N)) (we also have to consider N C P (1, N)),we define the restrictions of the Bellman function onto the layers of the space of positions. Namely, for s E 0, N, we assume vs E R+[Ds] to be a function such that vs(x, K) = v(x, K) V(x, K) E Ds. Property (4.6) now implies that, for s E 1,N and (x, K) E Ds, we have vs-1( pr2(h),K \ {k}) E [0, ro[ Vk E I(K) Vh E Mk; hence, we can determine the value min min sup jei(K) zeMj

({ ^c(^x, pr 1 (^z )^,K)

+ c , (z,K); v ,-i (pr 2 (z),K \{ j } )}) E [0, ro [.

Now, Theorem 1 implies, in view of (4.5), the following proposition:

Proposition 1. If s E 1,N, then the function vs is obtained from the function vs-1 by the rule vs(x, K)

= min min sup ,G I (K) zG M j

({ c (x, pr 1 (z),K)+c , (z,K)

v ,-1 (pr 2 (z),K \{ j } )} )V (x,K) E D s .

Note that the function v0 is known: v0(x, 0) = 0 Vx E M. Therefore, Proposition 1 defines the recurrent procedure v0 —> v1 —> ... —> vN.

(4.7)

Implementation of (4.7) would yield (see (3.94)) the value of problem (2.11):

V = V N (x ⁰ ,1,N) =

min min sup je i (i,N) zeM j

({c(x ⁰ , pr i (z),1,N) + c j (z, 1,N);v N-i ( pr ₂ (z), ^N \ ^{{ j} } )}).

(4.8)

This value may be used to check if movements (2.2) are possible. Namely, we might be given a tolerance threshold d of harmful effects, effective on each step of process (2.2). Indeed, if V C d , then, in compliance with (2.11) and (2.12), we may organize the motion (2.2) such that

c ( pr 2 (z ^(t) ), pr i (z ^(t+1) ), { a(s) : s G t + 1,N } ) +

(4.9)

+ c _a(t+i) ( z ^(t+1) , { a(s) : s G t + 1, N } ) C d V s G 0, N — 1.

However, in case d < V , it is not possible to provide (4.9). Thus, the implementation of (4.7), which is completely defined by Proposition 1, already yields useful data.

Optimal solutions are also constructed based on Proposition 1. Assume z ⁽⁰⁾ = (x ⁰ ,x ⁰ ); this is an OP from X x X . Then, using (4.8), choose j 1 G I (1, N ) and z ⁽¹⁾ G Mj 1 such that

V = sup ({^c( x ⁰ ,p^r i ⁽ z ⁽¹⁾ ), 1, N ) + c 1 ( z ⁽¹⁾ , 1, N ) ; V N -1 ( p^r 2 ⁽ z ⁽¹⁾ ),^1,N \ ti 1 ^} )}) (4-10)

(find the minimum in (4.8)). By (4.6), we have (since (x ⁰ , 1,N ) G D N )

(pr 2 ( z ⁽¹⁾ ), 1Л \ti 1 } ) G D n -i ;                          (4.11)

hence, Proposition 1 implies that

V N -i ^ pr 2 ( z ⁽¹⁾ ), 1, N \ ti 1 } ) = mi n min sup je i (i,N\{j 1 }) zeM j

И ^c(p^r 2 ⁽ z ^{(1) )}, pr i ^(z),^1,N \ ti i ^{} )}+             (4.12)

+ C j ^(z, ^1,N \ ^{ji 1 ^{} )}; v N -2 (p^r 2 ^(z), ^1,N \ {j 1 ,j^}

(take into account 1,N \ {j i ; j } = (1, N \ ti i }) \ { j } for j G I (1,N \ {ji i })). Now, find the minimum in (4.12): find ,]j₂ G I (1, N \ {j _i } ) and z® G Mj 2 such that

VN-i(pr2(z(1)), 1,N \ti 1}) = sup ^| c(pr2(z(1)),pri(z(2)),1,N \ tii}) + c2(z(2),1,N \ tii});         (4.13)

vN-2^ pr2(z(2)), 1,N \ ti 1,.j2}) }У where (see (4.6)) the property

( p^r 2 ⁽ z ^{(2) )}, ^1,N \ ti 1;. Ы) = ( p^r 2 ⁽ z ^{(2) )}, ^1,N \ ti k ^: k ^G 1, ^{2 }} ) ^G d n -2          ⁽4.1⁴⁾

holds. Expressions (4.10) and (4.13) imply that, in particular,

V = sup

« max c( kei,2

pr 2 ( z ⁽k 1) ), pr i ( z ^(k) ), 1,N \ {ji 1 : l G 1,k - 1}) +

+ c k (z^(k) , 1,N \{j i : l G 1,k — 1})

; v N -2

(p^r 2 ⁽ z ⁽²⁾ ),^1,N \{j i : l ^G 1,^{2 }} )j>),

(4.15)

where we use the following obvious property: if k = 1, then 1,k — 1 = 1,0 = 0 and, therefore, 1,N \ {jl : l G 1,k — 1} = 1,N. Further on, we continue finding the minima from Proposition 1 until we exhaust the task list. This will result in a feasible route

П = (j s ) _sGT,N G A and track ( z ^(s) ) _sGo;N G Z n such that C n ( z ^(s) ) _sGo;N

= V . For N = 2,

the optimality of this FS already follows from (4.15).

5.    A Model Problem

A model problem was considered on Euclidean space X = R x R for N = 30 megalopolises with | K | =25 precedence constraints and 25 points in each megalopolis; each point could serve both as an exit point and an entry point. The cost of exterior movement was specified as Euclidean distance in X multiplied by the coefficient a( | K | ) = 1 + ^N N^{K |} ; the coefficient decreased as the power of the list of pending tasks decreased and served as a rough estimate of harmful effect of radiation sources not yet processed. The cost of interior jobs was the Manhattan norm ||-|| of movement from the "'entry point" into the megalopolis to the "'exit point" through its center (for two plane vectors x = (x 1 ,x ₂ ),y = (y 1 ,y ₂ ), the Manhattan norm is || x — y || = | x 1 — y ₁ | + | x ₂ — y ₂ | ). Megalopolises were modeled as equal radius disks, points were placed on the circumference with equal angular distances between them (which, obviously, depended on the number of points in the megalopolis). Precedence constraints in the form of address pairs are specified below: (1,10); (12,2); (2,13); (13,15); (6,16); (15,16); (18,27); (9,27); (10,9); (11,19); (20,19); (25,26); (23,22); (21,20); (24,22); (14,16); (7,10); (8,2); (1,9); (14,26); (2,27); (3,6); (3,19); (18,17); (14,25).

13                6

:-^

0 0              200             400             600             800             1000

Optimal route and track for the tour of 30 megalopolises. Optimal value: 376.63

The calculations were conducted on the "Uran" supercomputer (see in 64-bit environment of Scientific Linux 6.4. Our programming language of choice was C++11 (compiler GCC 4.4.7, optimization level -O2),

r-^

'4

21    22

F

the parallelization was made with the aid of shared memory multiprocessing API OpenMP 3.0 . The calculation took 1h. 46min. 34sec. on 12 cores.

Conclusion

The paper proposes an unorthodox variant of the dynamic programming method to solve precedence-constrained routing problems with nonadditive cost aggregation (the bottleneck cost aggregation) and dependence on the list of pending tasks. A method of obtaining the optimal solutions is specified, and the (optimal) algorithm is implemented in the form of a parallel computer program.

Acknowledgements. This work was partially supported by Russian Science Fund, grant № 14-11-00109.