中國郵遞員模型研究

1、 13/13中國郵遞員模型研究 中國郵遞員模型研究 一、 中國郵遞員問題概述 著名圖論問題之一。郵遞員從郵局出發(fā)送信，要求對轄區(qū)內(nèi)每條街， 都至少通過一次，再回郵局。在此條件下，怎樣選擇一條最短路線? 關(guān)于郵遞員最優(yōu)投遞路線問題最早是由管梅谷首先提出并進行研究的, 國際上現(xiàn)在統(tǒng)稱之為中國郵遞員問題。管梅谷給出了這一問題的奇偶點圖上作業(yè)法。Edmonds 等給出了中國郵遞員問題的改進算法, 較前者的計算更為有效。管梅谷對有關(guān)中國郵遞員問題的研究情況進行了綜述。早期關(guān)于中國郵遞員問題的討論總是基于無向圖展開的,事實上,由于單行線或上下行路線的坡度等原因, 這一問題有時必須借助于有向圖來進行研究和解

2、決。到目前為止,對中國郵遞員問題的研究主要是從圖論角度展開的, 給出的多數(shù)都是各種啟發(fā)式算法或遞推算法。本文從數(shù)學規(guī)劃的角度進行研究。數(shù)學規(guī)劃建模具有借助軟件包求解方便、 易于修改和推廣等多方面的優(yōu)點,即使對于大型問題也易于建模分析和解決的優(yōu)點。 1、 傳統(tǒng)中國郵遞員問題的建模 一些基本概念: 定義 經(jīng)過G 的每條邊的跡叫做G 的Euler 跡；閉的Euler 跡叫做Euler 回路或E 回路；含Euler 回路的圖叫做Euler 圖。 直觀地講，Euler 圖就是從一頂點出發(fā)每邊恰通過一次能回到出發(fā)點的那種圖，即不重復(fù)地行遍所有的邊再回到出發(fā)點。 定理（i ）G 是Euler 圖的充分必要條

3、件是G 連通且每頂點皆偶次。 （ii ）G 是Euler 圖的充分必要條件是G 連通且 d i i C G 1=，i C 是圈， )()()(j i C E C E j i = 。 （iii ）G 中有Euler 跡的充要條件是G 連通且至多有兩個奇次點。 問題（管梅谷，1960） ：一位郵遞員從郵局出發(fā)投遞郵件，經(jīng)過他所管轄的每條街道至少一次，然后回到郵局。請為他選擇一條路線，使其所行路程盡可能短。 圖論模型：求賦權(quán)連通圖中含有所有邊的權(quán)最小的閉途徑。這樣的閉途徑稱為最優(yōu)回路。 思想： （1）若 G 是 Euler 圖，則 G 的 Euler 環(huán)游便是最優(yōu)回路，可用 Fleury 算法求得；

4、 （2）若 G 不是 Euler 圖，則含有所有邊的閉途徑必須重復(fù)經(jīng)過一些邊，最優(yōu)回路要求重復(fù)經(jīng)過的邊的權(quán)之和達到最小。閉途徑重復(fù)經(jīng)過一些邊，實質(zhì)上可看成給圖 G 添加了一些重復(fù)邊（其權(quán)與原邊的權(quán)相等） ，最終消除了奇度頂點形成一個 Euler 圖。因此，在這種情況下求最優(yōu)回路可分為兩步進行：首先給圖 G 添加一些重復(fù)邊得到 Euler 圖*G ，使得添加邊的權(quán)之和()e F w e 最 小， （其中()()*F E G E G = ） ；然后用 Fleury 算法求*G 的一條 Euler 環(huán)游。這樣便得到 G 的最優(yōu)回路。 問題是：如何給圖 G 添加重復(fù)邊得到 Euler 圖*G ，使得添

5、加邊的權(quán)之和 ()e F w e 最??？ 方法一（圖上作業(yè)法） 定理1設(shè) C 是一條經(jīng)過賦權(quán)連通圖 G 的每條邊至少一次的回路，則 C 是 G 的最優(yōu)回路 當且僅當 C 對應(yīng)的Euler 圖*G 滿足： （1）G 的每條邊在*G 中至多重復(fù)出現(xiàn)一次； （2）G 的每個圈上在*G 中重復(fù)出現(xiàn)的邊的權(quán)之和不超過該圈總權(quán)的一半。 奇偶點圖上作業(yè)法： 先分奇偶點，奇點對對聯(lián)；聯(lián)線不重迭，重迭要改變；圈上聯(lián)線長，不得過半圈。 基本步驟： 1、確定第一個可行方案。找到圖中所有奇頂點（必有偶數(shù)點）將它們兩兩配對。新圖中無奇頂點，得到第一個可行方案。 2、調(diào)整可行方案，使重復(fù)邊總長度下降。 3 檢查圖中的每個

6、圈，如果每個圈重復(fù)邊總長度不超過該圈總長度的一半，則已求得最優(yōu)解。否則進行調(diào)整：將這個圈的重復(fù)邊去了，而將原來沒有重復(fù)邊的各邊加上重復(fù)邊，其他各圈的邊不變，根據(jù) 2 再一次調(diào)整。 奇偶點圖上作業(yè)法雖然通俗易懂，但使用時需要檢查圖的每個圈，對于有很多圈的圖，計算量很大，實際當中用得較少。 方法二（Edmonds-Johnson 方法） 定理2設(shè) G 是賦權(quán)連通圖，G 中有2k 個奇度頂點。設(shè) |,e A e e E =求最優(yōu)回路時被添加重復(fù)邊 則G A 是以G 的奇度頂點為起點和終點的k 條無公共邊的最短路。 基于此定理，Edmonds 和 Johnson 于 1973 年給出了求解郵遞員問題的

7、有效算法。 Edmonds-Johnson 算法： 對于非Euler 圖，1973年，Edmonds 和Johnson 給出下面的解法： 設(shè)G 是連通賦權(quán)圖。 （i ）求)2(mod 1)(),(|0=v d G V v v V 。 （ii ）對每對頂點0,V v u ，求),(v u d （),(v u d 是u 與v 的距離，可用Floyd 算法求得）。 （iii ）構(gòu)造完全賦權(quán)圖|0V K ，以0V 為頂點集，以),(v u d 為邊uv 的權(quán)。 （iv ）求|0V K 中權(quán)之和最小的完美對集M 。 （v ）求M 中邊的端點之間的在G 中的最短軌。 （vi ）在（v ）中求得的每條最短軌

8、上每條邊添加一條等權(quán)的所謂“倍邊”（即共端點共權(quán)的邊）。 （vii ）在（vi ）中得的圖G 上求Euler 回路即為中國郵遞員問題的解。 若此連通賦權(quán)圖是Euler 圖，則可用Fleury 算法求Euler 回路，此回路即為所求。 Fleury 算法： （1）任取()()0v V G ，令00P v =. （2）設(shè)0112 .i i i P v e v e e v =已經(jīng)行遍，按下面方法來從()12,.,i E G e e e -中選取1i e +： （a ）1i e +與i v 相關(guān)聯(lián)； （b ）除非無別的邊可供行遍，否則1i e +不應(yīng)該為12,.,i i G G e e e =-中的橋

9、。 （3）當（2）不能再進行時，算法停止。 2、 利用LINGO 中國郵遞員0-1規(guī)劃求解 在中國郵遞員問題中，不算出地點，n 個郵局有(n-1)!種排列方法，每一種投遞路線是排列中的一種，當n 變大時，計算量呈指數(shù)增長，窮舉法所費時間是難以承受的。 我們把中國郵遞員問題轉(zhuǎn)化為0-1規(guī)劃，然后用LINGO 來求解。 (1). 判斷各邊包含在投遞路線中 引入0-1整數(shù)變量i j x (且i j ):i j x =1表示路線從i 到j(luò) ，即邊i-j 在旅行路線中，而i j x 0則表示不走i-j 路線。 目標函數(shù)： 首先必須滿足約束條件：對每個投遞點訪問一次且僅一次。從投遞點i 出發(fā)一次(到其它投

10、遞點去),表示為 從某個投遞點到達j 一次且僅一次，表示為 以上建立的模型類似于指派問題的模型，對中國郵遞員問題只是必要條件，并不充分。 例如，用圖示路線連接六個點，滿足以上兩個約束條件，但這樣的路線出現(xiàn)了兩個子回路，兩者之間不通，不構(gòu)成整體巡回路線。 11 min n n ij ij i j z c x =11,1,2,n i j j x i n j i = 1 1,1,2,n i j i x j n i j = 為此需要考慮增加充分的約束條件以避免產(chǎn)生子巡回 增加變量i u ,i=2,3,n ，（它的大小可以取整數(shù)：例如從起點出發(fā)所達到的投遞點u=2,依此類推）。 1,1,.,2,.,i

11、j i j u u nx n i n j n i j -+-=附加約束條件： 證明： (1)任何含子巡回的路線都必然不滿足該約束條件（不管i u 如何取值）； (2)全部不含子巡回的整體巡回路線都可以滿足該約束條件（只要i u 取適當值）。 用反證法證明(1),假設(shè)存在子巡回，則至少有兩個子巡回。那么（必然）至少有一個子巡回中不含起點1，如上圖中的4564，則必有 4554641,1,1u u n n u u n n u u n n -+-+-+- 把這三個不等式加起來得到1n n -，不可能，故假設(shè)不能成立。而對整體巡回，因為附加約束中j 2,不包含起點投遞點1，故不會發(fā)生矛盾。 對于整體巡

12、回路線，只要ui 取適當值，都可以滿足該約束條件： ()對于總巡回上的邊，1i j x =, i u 可取訪問投遞點i 的順序數(shù)，則必有 1i j u u -=-，約束條件1i j i j u u nx n -+-變成： -1+n n-1，必然成立。 ()對于非總巡回上的邊，因為0i j x = ，約束條件1i j i j u u nx n -+-變成-1n-1，肯定成立。 綜上所述，該約束條件只限止子巡回，不影響其它，于是中國郵遞員問題轉(zhuǎn)化成了一個混合整數(shù)線性規(guī)劃問題。 中國郵遞員問題可以表示為規(guī)劃： 例1 有一個縣城，有五個鄉(xiāng)郵局，現(xiàn)在又一個郵車從縣郵局出發(fā)派送物品，如何為這個郵車設(shè)計一條

13、最短的派送路線（從駐地出發(fā)，經(jīng)過每個投遞點恰好一次，最后返回駐地）？（數(shù)據(jù)在下表中） 11 min n n ij ij i j z c x =1 11,1,2,1,1,2,1,1,2,0,1,1,2,0,1,2,n i j i n i j j i j i j ij i x j n i j x i n j i u u nx n i n j n i j x i j n u i n =?=? =? -+-=?=? （單位：千米） Lingo代碼： model: sets: country/1,2,3,4,5,6/:u;！定義6個點 link(country,country): dist,！距離矩陣

14、x;！決策變量 endsets n= size( country); data: ！距離矩陣 dist=0 3 4 7 9 5 3 0 6 22 11 16 4 6 0 33 21 55 7 11 33 0 17 10 9 16 21 17 0 13 5 22 55 10 13 0; enddata ！目標函數(shù) min=sum(link:dist*x); FOR( country(K): ！進入郵局 sum( country( I)| I #ne# K: x(I,K)=1; ！離開郵局 sum( country( j)| J #ne# K: x(K,J)=1; ); ！保證不出現(xiàn)子圈 FOR(

15、 country(I) | I #gt# 1: FOR( country( J)| j #gt# 1: u(I)-u(J)+n*x(I,J)=n-1); ); FOR( country(I) : u(I)=n-1); FOR( link:bin(x);！定義0-1變量 END 運算結(jié)果： Objective value: 53.00000 X( 1, 3) 1.000000 4.000000 X( 2, 4) 1.000000 11.00000 X( 3, 2) 1.000000 6.000000 X( 4, 6) 1.000000 10.00000 X( 5, 1) 1.000000 9.0

16、00000 X( 6, 5) 1.000000 13.00000 由此可以看出最優(yōu)解為 53千米 路線為：1-3-2-4-6-5-1 2.對投遞點進行排序，找出最優(yōu)排序 在現(xiàn)實中的交通圖中，有些投遞點之間有直接道路，有些則沒有，如果兩點之間沒有直接的通路，則兩點之間的距離取最短路（經(jīng)過其它點），即用任意兩C作為圖的距離矩陣，于是該圖可以看成是一個完全圖（即任點之間的最短路 i j 意一對頂點都有一條邊相連的圖），此時形式上的環(huán)形巡回路線實際上個別點有可能不止經(jīng)過一次。 設(shè)從某個郵局為投遞的出發(fā)地和終點（相當于總部所在地），郵遞員從該點出發(fā)到其它n 個各一次且僅一次，最后回到出發(fā)地。我們把行進路

17、線分成n 步，每一步到一個投遞點（第n+1步返回出發(fā)地），于是一條旅行路線就相當于n 個投遞點的一種排列，n 個投遞點共有n!種排列方式。排序不同則總里程可能不同，總里程最小的排序就是要尋找的最優(yōu)路。 引入0-1型決策變量k j X ，下標k 表示旅行的步數(shù)，下標j 表示到達哪一個投遞點，1k j X =表示旅行者第k 個目的地（到達點）是投遞點j ，0k j X =則表示否。用j l 表示總部到各投遞點的距離，用i j C 表示投遞點i 與投遞點j 之間的最短路。 從出發(fā)地到第1個點的路程為： 從最后一個點返回出發(fā)地的里程為 ： 假設(shè)在第k 步郵車達到投遞點i ，在第k +1步達到支局j ，

18、即1,1ki k j X X +=，則走過的里程為： 1,i j ki k j C X X +? 從第1點到第n 點走過的總里程為： 目標函數(shù)為： =?n j j j X l 1 1=?n j nj j X l 1 -=+?1111 ,1n k n i n j j k i k ij X X C 約束條件： (1) 每一步到達一個投遞點，即 (2) 每一個投遞點必須到一次且只需一次 可以把郵遞員問題轉(zhuǎn)化成如下非線性0-1 規(guī)劃 例 2 某縣郵局和四個鄉(xiāng)鎮(zhèn)支局組成該縣的郵政運輸網(wǎng)絡(luò)，已知縣局到各支局的距離和支局之間的距離矩陣。用一輛郵車完成郵件運輸任務(wù)，郵車從縣局出發(fā)到各支局去一次且只需一次，最后

19、回到縣局，求總路程最短的行 -=+=?+=1111 ,11 1)(min n k n i n j j k i k ij n j nj j j X X C X X l Z =n j kj n k X 1 ,2,1,1 =n k kj n j X 1 ,2,1,1 1 11,1 111 1 1 min ()11s.t.011,2,1,2,n n n n j j nj i j k i k j j k i j n kj j n kj k kj L l X X C X X X X X k n j n -+=+?=? =?=?=? 或 駛路線。（數(shù)據(jù)在下表中） （單位：千米） 程序： MODEL: SET

20、S: COUNTRY /1,2,3,4/:JL; STEP/1,2,3,4/; LINE(STEP, COUNTRY):X; LINKS(COUNTRY, COUNTRY):C; ENDSETS DATA: JL=71 56 27 30; C=0 15 44 47 15 0 29 32 44 29 0 20 47 32 20 0 ; ENDDATA FOR(LINE : BIN(X); M1=SIZE(STEP); FOR(COUNTRY (I):SUM(STEP(N):X(N,I)=1); FOR(STEP(N):SUM(COUNTRY (I):X(N,I)=1); L1=SUM(COUNT

21、RY (I):(X(1,I)+X(M1,I)*JL(I); LX=SUM(STEP(N)|N#LT#M1:SUM(LINKS(I,J):C(I,J)*X(N,I)*X(N +1,j); MIN=L1+LX; END 運算結(jié)果： Objective value: 148.0000 X( 1, 4) 1.000000 0.000000 X( 2, 1) 1.000000 35.99985 X( 3, 2) 1.000000 0.4100000E-04 X( 4, 3) 1.000000 0.000000 由此可以看出最優(yōu)解： 148 最優(yōu)解路線為：1-4-3-2-1。 3. 多郵遞員問題 在現(xiàn)實中

22、問題中，有時候不是由一人走遍所有點，而是由幾個人分工合作，每個人只到其中部分投遞點，每個點都有人來過一次且只需一次，事先不指定誰到哪些點，求出使總路程最小的投遞規(guī)劃（每個人的行走路線）。 為了在允許的時間內(nèi)完成郵件運輸任務(wù)，縣局的郵車往往不止1輛，而是用若干輛郵車分工運輸，只要保證每個支局有郵車來過即可，為了節(jié)省行駛費用，需要規(guī)劃幾輛郵車的最佳路線。 問題：有n+1個投遞點，相互間的路程為已知，有k個郵遞員都從總部所在郵局出發(fā)，赴其它投遞點投遞，分工遍歷其余n個投遞點，即每個投遞點各有任意一名郵遞員來過一次且僅一次，最后都回到出發(fā)地，目標是總路程最短。 多郵遞員問題在物流配送、郵路優(yōu)化等方面具

23、有較高的實用價值，而在現(xiàn)實問題中，研究對象往往不是單純的郵遞員問題，而要考慮各種約束條件，例如時間約束、載重量約束等等。研究這一類帶約束條件的多郵遞員問題具有很強的現(xiàn)實意義。 例3 某縣郵政局管轄16個支局，已知縣局到各支局的距離以及16個支局之 間的距離矩陣。寄達各支局和各支局收寄的郵件如下表所示： （單位：袋） 每一輛郵車最多裝載65袋郵件，郵車的運行成本為3元/公里。試用最少郵車，并規(guī)劃郵車的行駛路線使總費用最省。（距離數(shù)據(jù)在下表） 支1 支2 支3 支4 支5 支6 支7 支8 支9 支10 支11 支12 支13 支14 支15 支16 支1 0 31 27 38 51 58 71

24、67 57 47 52 48 21 41 52 61 支2 31 0 19 33 27 32 45 64 53 47 61 57 52 48 56 63 支3 27 19 0 14 27 34 47 49 39 29 42 38 38 29 38 44 支4 38 33 14 0 13 20 33 35 25 15 33 32 32 15 24 30 支5 51 27 27 13 0 9 21 37 26 26 43 45 45 28 29 38 支6 58 32 34 20 9 0 13 32 32 35 47 52 52 35 33 42 支7 71 45 47 33 21 13 0 19

25、 30 39 50 65 65 48 44 40 支8 67 64 49 35 37 32 19 0 11 20 31 54 61 34 25 21 支9 57 53 39 25 26 32 30 11 0 10 20 43 51 24 14 13 支10 47 47 29 15 26 35 39 20 10 0 18 36 41 14 9 18 支11 52 61 42 33 43 47 50 31 20 18 0 23 46 25 14 23 支12 48 57 38 32 45 52 65 54 43 36 23 0 27 22 33 42 支13 21 52 38 32 45 52 6

26、5 61 51 41 46 27 0 39 48 57 支14 41 48 29 15 28 35 48 34 24 14 25 22 39 0 11 20 支15 52 56 38 24 29 33 44 25 14 9 14 33 48 11 0 9 支16 61 63 44 30 38 42 40 21 13 18 23 42 57 20 9 0 (單位：千米) 考慮最少郵車數(shù)量，由題目所給表中數(shù)據(jù)，寄達16個支局的郵件總數(shù)為176袋，從各支局收寄的郵件總數(shù)170為袋，每一輛郵車最多容納65袋郵件，至少需要176/65 2.7，由于郵車的數(shù)量是整數(shù)所以需要3輛郵車。 運輸費用與行駛里程成

27、正比，總里程最短對應(yīng)總費用最省。把16個支局放在一起作為一個整體考慮，找出3條郵路，每條郵路都從縣局出發(fā)，到若干支局進行卸裝，最后回到縣局。各郵車路過的支局數(shù)量未知，合理安排各郵車的行駛路線，由3輛郵車分別承包運輸，在滿足運載量約束前提下，把3條巡回路線的總里程最小作為優(yōu)化的目標。該問題相當于附帶約束條件的多郵遞員模型。 引入0-1型決策變量,k j k j k j X Y Z ，分別表示3輛郵車第k 步到達支局j ，下標k 表示郵車行走的步數(shù)，下標j 表示到達哪一個支局，當決策變量,k j k j k j X Y Z 等于1時分別表示某郵車第k 個裝卸點是支局j ，等于0時表示否。設(shè)各郵車管

28、轄的支局數(shù)量分別為123,m m m ，則12310m m m +=。 約束條件： (1) 任何一輛車在任何一步到達一個支局 ： 16 111,1,2,kj j X k m = 16 21 1,1,2,kj j Y k m = 16 31 1,1,2,kj j Z k m = (2) 任何一個支局必須有一輛郵車到達一次且只需要一次： 3 1 21 1 1 1,1,2,16m m m k j k j k j k k k X Y Z j =+= (3) 在郵車行進的任何路段上，裝載的郵件不超過47袋： 設(shè)寄達各支局的郵件量為j P ，各支局收寄的郵件量為j Q 。 裝載量是動態(tài)變化的，以第1輛郵車

29、為例，出發(fā)時的裝載量為： 1 16 01 1 ()m x j k j j k W P X =? 到第1個支局卸裝以后，裝載量變?yōu)椋?16 1011 ()x x j j j j W W P Q X =-? 在行駛過程中，裝載量的遞推公式為： 16 ,11 1 (),2,3,xk x k j j kj j W W P Q X k m -=-?= 數(shù)量的約束條件 165,0,1,2,xi W i m = 建立多郵遞員問題的0-1規(guī)劃模型如下： 31 2 12312316 1616 1 11 1 11161616112131111 1,min 1,1,1,1,2,1,1,2,16 (),(),()s.

30、t.x y z k j k j k j i j j j m m m k j k j k j k k k j j m j j j m j j j m j j j j x ij ki k j j S L L L L L L X Y Z k m X Y Z j L l X X L l Y Y L l Z Z L C X X =+=+=+=?+=?+=?+=? 31211116161616 16161,1,111111111,65,65,65,0,1,2,01 m m m y ij ki k j z ij ki k j k i k i j k i j xk yk zk i k j k j k j L

31、C Y Y L C Z Z W W W k m X Y Z +=? ? ? =?=? ?=?=? 或 12316 0111601116 01116 1 011 16101116101116 ,111,1() () ()()()()(),2,3,(m x j k j j k m y j k j j k m z j k j j k x x j j j j y y j j j j z z j j j j xk x k j j k j j y k y k j W P X W P Y W P Z W W P Q X W W P Q Y W W P Q Z W W P Q X k m W W P =-=-

32、=?=?=?=-?=-?=-?=-?=- 162116,131),2,3,(),2,3,j k j j z k z k j j n j j Q Y k m W W P Q Z k m =-=? ? ? ? ? ? ? ? ?-?=?=-?=? 程序如下： MODEL : SETS : STATION/1.16/: JL,P,Q; STEPX/1.6/:WX; STEPY/1.5/:WY; STEPZ/1.5/:WZ; LINEX( STEPX, STATION): X; LINEY( STEPY , STATION): Y; LINEZ( STEPZ, STATION): Z; LINKS(S

33、TATION,STATION):C; ENDSETS DATA : JL=27 36 17 11 24 31 44 40 30 20 25 21 21 18 27 36; P=10 15 6 9 13 6 11 4 13 17 11 2 11 21 13 14; Q=9 14 5 10 9 10 13 9 15 9 6 7 13 15 10 16; C= 0 31 27 38 51 58 71 67 57 47 52 48 21 41 52 61 31 0 19 33 27 32 45 64 53 47 61 57 52 48 56 63 27 19 0 14 27 34 47 49 39 2

34、9 42 38 38 29 38 44 38 33 14 0 13 20 33 35 25 15 33 32 32 15 24 30 51 27 27 13 0 9 21 37 26 26 43 45 45 28 29 38 58 32 34 20 9 0 13 32 32 35 47 52 52 35 33 42 71 45 47 33 21 13 0 19 30 39 50 65 65 48 44 40 67 64 49 35 37 32 19 0 11 20 31 54 61 34 25 21 57 53 39 25 26 32 30 11 0 10 20 43 51 24 14 13

35、47 47 29 15 26 35 39 20 10 0 18 36 41 14 9 18 52 61 42 33 43 47 50 31 20 18 0 23 46 25 14 23 48 57 38 32 45 52 65 54 43 36 23 0 27 22 33 42 21 52 38 32 45 52 65 61 51 41 46 27 0 39 48 57 41 48 29 15 28 35 48 34 24 14 25 22 39 0 11 20 52 56 38 24 29 33 44 25 14 9 14 33 48 11 0 9 61 63 44 30 38 42 40

36、21 13 18 23 42 57 20 9 0; ENDDATA FOR( LINEX : BIN( X); FOR( LINEY : BIN( Y); FOR( LINEZ : BIN( Z); M1=SIZE(STEPX); M2=SIZE(STEPY); M3=SIZE(STEPZ); FOR(STATION(I):SUM(STEPX(N):X(N,I)+SUM(STEPY(N):Y(N,I)+SU M(STEPZ(N): Z(N,I) = 1); FOR(STEPX(N):SUM(STATION(I):X(N,I)=1); FOR(STEPY(N):SUM(STATION(I):Y(N,I)=1); FOR(STEPZ(N):SUM(STATION(I):Z(N,I)=1); WX0=SUM(STATION(I):P*SUM(STEPX(N):X(N,I); WY0=SUM(STATION(I):P*SUM(STEPY(N):Y(N,I); WZ0=SUM(STATION(I):P*SUM(STEPZ(N):Z(N,I); WX(1)=WX0-SUM(STATION(J):(P(J)-Q(J)*X(1,J); WY(1)=WY0-SUM(STATION(J):(P(J)-Q(J)*Y