2007年全國數(shù)學(xué)建模競賽優(yōu)秀選郵政運輸

1、第四屆研究生數(shù)學(xué)建模競賽題 目郵政網(wǎng)絡(luò)中的郵路規(guī)劃和郵車調(diào)度摘要：本題是一道 VRP 問題,它涉及到最短路線、最小費用等條件下的優(yōu)化問題.首先利用 Dijkstra 算法求出任意點的最短距離,然后針對每一個小問題,提出了具體的求解策略:論證出最少需要 3 輛郵車才能滿足要求.然后對 X1 區(qū)域根據(jù)問題一中,裝載量、時間要求遍歷出所有的可行路線,最后選出因空車率而減小的收入最小的郵路，具體的路線安排見文中表 1.4. 其減少的收入為 49.35 元.問題二中,對地市局發(fā)車數(shù)進行,將整個區(qū)域進行劃分,在每個小區(qū)域應(yīng)用分枝定界法求出運行成本的路線.從而得到近似最優(yōu)解,再通過對區(qū)域的微調(diào)出使郵車數(shù)目更

2、小的、更節(jié)省運行成本的郵路規(guī)劃和調(diào)度方案.在不同的方案下得到的最優(yōu)值如下:問題三中,在允許區(qū)級郵車上、下午停留的支局不同的情況下,Z56,Z57 由縣局 X1 負責(zé)運送,Z27 由縣局 X2 負責(zé)運送,這樣只需要 10 輛郵車,并使每天節(jié)省 354 元,具體的行車路線見文中表 3.2 .問題四是一個選址問題.借助于中心點算法，考慮各支局在本縣區(qū)域內(nèi)的位置，并結(jié)合與地市局的距離,提出了相應(yīng)的選址方案：將 X1 縣局移到 Z4,X2縣局移到Z21,X5 縣局移到Z52,每天將節(jié)省 789 元的運行成本,具體調(diào)度方案見文中表 4.4.參賽隊號 1029301參賽學(xué)校 郵電大學(xué)于參賽隊員參賽（由填寫）

3、方案郵車數(shù)運行成本(元)區(qū)級郵車上、下午停留的支局相同1210197區(qū)級郵車上、下午停留的支局不同119771題號 D一、問題重述：某地區(qū)的郵分為地市中心局（簡稱地市局）、縣級中心局（簡稱縣局）和支局三級機構(gòu)，該地區(qū)的郵政網(wǎng)絡(luò)由區(qū)級郵政網(wǎng)和縣級郵政網(wǎng)構(gòu)成。區(qū)級郵政網(wǎng)由從地市局出發(fā)并最終返回地市局的區(qū)級郵車所行駛的全部郵路，縣級郵政網(wǎng)由從縣局出發(fā)并最終返回縣局的縣級郵車所行駛的全部郵路。為使郵政企業(yè)實現(xiàn)低成本運營和較高的服務(wù)質(zhì)量，需要對該地區(qū)的郵政網(wǎng)絡(luò)進行重構(gòu)，確定合適的郵路規(guī)劃方案并進行郵車的合理調(diào)度。為了滿足郵政的時限要求，必須盡可能地保證各縣局、支局在營業(yè)時間內(nèi)收寄的多數(shù)郵件能當(dāng)天運送回地

4、市局進行分揀封發(fā)等處理，以及每天到達地市局的多數(shù)郵件能當(dāng)天運送到目的地縣局、支局。該地區(qū)從地市局到縣局每天兩班車，從縣局到支局每天僅有一班車。該地區(qū)的郵政流程及時限規(guī)定如下：Step1:區(qū)級第一班次郵車從地市局D出發(fā)將郵件運送到各縣局Xi和沿途支局，并將各縣局Xi和沿途支局收寄的郵件運送回地市局D；區(qū)級第一班次郵車出發(fā)時間必須在06:00之后，返回地市局D時間必須在11:00之前。Step2:縣局Xi將當(dāng)天區(qū)級第一班次郵車及前一天的區(qū)級第二班次郵車所送達的本縣郵件進行集中處理，按寄達支局裝上相應(yīng)的縣級郵車；縣局Xi對郵件的集中處理時間為1小時（包括郵件的卸裝、分揀封發(fā)等處理時間）。Step3:

5、各縣級郵車將郵件運送到其負責(zé)的支局并將這些支局收寄的郵件運送回縣局Xi；Step4: 區(qū)級第二班次郵車從地市局D出發(fā)將郵件運送到各縣局Xi和沿途支局，并將各縣局Xi收寄的郵件（包括當(dāng)日各縣級郵車運回縣局Xi的郵件）和沿途支局收寄的郵件運送回地市局D；請注意區(qū)級第二班次郵車在縣局Xi卸裝完郵件后的出發(fā)時間必須在縣局Xi的全部縣級郵車返回縣局并集中處理1小時以后，最終返回地市局D的時間必須在18:00之前。假設(shè)區(qū)級兩個班次郵車的行駛路線相同，要求區(qū)級郵政網(wǎng)必須至少覆蓋該地市附近的16個支局Z58, Z59, , Z73和5個縣局X1，X5。各縣級郵政網(wǎng)必須覆蓋本縣內(nèi)區(qū)級郵車不到達的支局。該地區(qū)郵局

6、間公路網(wǎng)分布見表1，并且縣級郵車平均時速為30km/h，區(qū)級郵車的平均時速為65km/h，郵車在各支局卸裝郵件耗時5分鐘，在各縣局卸裝郵件耗時10分鐘。問題1：以縣局X1及其所轄的16個支局Z1, Z2, , Z16為研究對象，假設(shè)區(qū)級第一班次郵車08:00到達縣局X1，區(qū)級第二班次郵車16:00從縣局X1再出發(fā)返回地市局 D，若每輛縣級郵車最多容納65袋郵件，試問最少需要多少輛郵車才能滿足該縣的郵件需求？同時，為提高郵政效益，應(yīng)如何規(guī)劃郵路和如何安排郵車的運行？（郵件量見表2，空車率=(郵車最大承運的郵件量(袋)-郵車運載的郵件量(袋)/郵車最大承運的郵件量(袋)，單車由于空車率而減少的收入

7、為（空車率*2元/公里）.問題2：采用盡可能少、盡可能短的郵路可以減少郵政部門車輛和等的投入，從而顯著降低全區(qū)郵政網(wǎng)的總運行成本?？紤]投入車況較好的郵車，通常每條郵路只需要一輛郵車即能滿足運載能力要求，試問應(yīng)如何構(gòu)建該地區(qū)的郵政網(wǎng)絡(luò)（縣的劃分不能變更），請你給出郵路規(guī)劃和郵車調(diào)度方案。請注意郵車的1調(diào)度必須滿足上文中有關(guān)該地區(qū)的郵政成本為3元/公里）問題3：流程及時限規(guī)定。（每條郵路的運行考慮到部分縣與縣交界地帶的支局，其郵件由鄰縣縣局負責(zé)運送可能會降低全區(qū)的運行成本，帶來可觀的經(jīng)濟效益。若允許在一定程度上打破行政區(qū)域的限制，你能否給出更好的郵路規(guī)劃和郵車調(diào)度方案？（在此同樣不必考慮郵車的運載

8、能力的限制，每條郵路的運行成本為3元/公里）問題4：縣局選址的合理與否對構(gòu)建經(jīng)濟、快速的郵政網(wǎng)絡(luò)起到?jīng)Q定性的作用。假設(shè)圖 2 中縣局 X1，X5 均允許遷址到本縣內(nèi)任一支局處，同時原來的縣局弱化為普通支局。設(shè)想你是該地區(qū)網(wǎng)運部門，請你重新為各個縣局選址，陳述你的遷址理由并以材料形式提交省局網(wǎng)運處。2二、問題假設(shè)與符號說明2.1、問題假設(shè)：1、郵車在的速度總是一定，不會出現(xiàn)拋錨或阻塞而耽誤時間；2、分組之后，各小組只能走自己組內(nèi)的路，不能走其它組的路；3、各個小組的郵車行駛速度一樣；4、卸車寄達該局的所有郵件；上車該局收寄的所有郵件；5、縣局需對郵件處理 1 小時，且不包括區(qū)局郵車裝卸郵件的時間

9、；2.2 符號說明：3符號符號說明D區(qū)局Xi第i 個縣局Zi第i 個支局Di, j從支局點 Zi 到支局點 Zj 路徑的距離u(i) 從支局點 Z1 到支局點 Zi 已選取的最小距離r(i)從支局點 Z1 到支局點 Zi 已選取的最小路徑Ii第i 個支局需寄達的郵件數(shù)量Oi第i 個支局收寄的郵件數(shù)量Q寄達郵件總量n郵車數(shù)量縣局 X1 所轄支局的分為三個區(qū)域，劃分的集合Wi每輛郵車離開第i 個支局時所裝郵件數(shù)量Ti區(qū)級郵車到縣局 Xi 花費的時間K郵車的空車率S總的空車損失費用Si第i 輛車的空車損失費用4Ai第i 輛車所經(jīng)過的所有局的全排列pk一輛郵車所經(jīng)過局的全排列的第k 個全排列W i,

10、j表示第i 種分區(qū)方式下從第 j 個支局出發(fā)郵車上所裝郵件數(shù)量K i, j郵車從第i 個局到第 j 個局郵車的空車率t郵車出行一共花費的時間tl郵車第l 種運行方式一共花費的時間mi第i 輛郵車一共經(jīng)過的支局數(shù)目v縣級郵車的行駛速度，為已知常量三、模型求解準(zhǔn)備3.1 Dijkstra 算法：為了求解整個區(qū)域中，任意 2 點之間的距離，是使用了 Dijkstra 算法，算法如下：由題中給定的任意兩個局（包括區(qū)局、縣局、支局）之間的距離，根據(jù)圖論的模型來求解任意兩個局之間的最短距離。設(shè)有圖G ，頂點集V 表示所有局的集合；邊集 E 表示某兩個局之間的距離的集合。圖 1.1 縣局 X1 及所轄支局示

11、意圖圖G 中，求固定一點到其它頂點的最短距離，可以引入圖論中對所有在點調(diào)用 Dijkstra 算法不妨固定點 Z1 表示的點：設(shè) Di, j 表示從支局點 Zi 到支局點 Zj 路徑的距離；u(i) 表示從 Z1 到 Zi 選取的路徑的距離； r(i) 表示 Zi 的上一個節(jié)點，用來確定最短路徑； j 表示新加入集得支局點， j 0 表示縣局。算法的過程就是在每一步改進這兩個標(biāo)記的值，使最終u(i) 表示從 Z1 到 Zi 的最小距離。算法過程：（1）、賦初值：令u(i) D1, j ； r(i) 1； j 0 ；過的點，如果有u(i) u( j) Dj,i ，則令u(i) （2）、所有未u(

12、 j) Dj,i ， r(i) j ；（3）、令 j* 是使得l(i) 取得最小值的支局點，則令第 j* 個支局點為已考察， j j* ；（4）、如果從 1 到 16 所有支局點都已完畢，則算法結(jié)束；否則，執(zhí)行（2）繼續(xù)未過點的情況。5最后求得固定點 Z1 到任意點 Zi 間得的最小距離，用u(i) 表示；該最小距離經(jīng)過的路徑可以從數(shù)組r(i) 得到。求得圖G 任意兩點之間的最短距離，結(jié)果列表：表 1.1縣局 X1 及所轄的 16 個支局之間最短距離3.2 分枝定界算法為了得到給定起始點的回路的最短路徑，使用了分枝定界算法。算法如下：以 X1 縣來看，采用分枝定界法，設(shè)無向圖G有 17 個點（

13、包括作為起點及終點的縣局 X1 ）， dis （ i,j ）為圖中頂點 Vi 與頂點 Vj的距離； path Vk1,Vk2 Vki 表 示 經(jīng) 過 的 點 的 路 徑 ； 經(jīng) 過 路 徑 的 長 度i1cos t dis Vk ,Vk；Lmin 為所有路徑中最短路徑的長度；left（i,j）保存 j 1jj1點Vi 到點Vj 的邊是否已被選?。怀跏蓟?Lmin=INF（即一個極大的數(shù)）：1、以 X1 點為出發(fā)點，遍歷每一條分枝X1,Vki 作為路徑到達 Vki 點（對于此圖，這樣的分枝有 16 條），記 left0， k1 1， cos t dis0, k1 ；再以點Vk1 作6Z1Z2Z

14、3Z4Z5Z6Z7Z8Z9Z10Z11Z12Z13Z14Z15Z16X1Z1031273851587167574752482141526127Z2310193327324564534761575248566336Z32749392942383829384417Z43833251533323215243011Z551272713092137262643454528293824Z658323420901332323547525235334231Z77145473321656548444044Z86764493537326134252140Z95753392526323011010204351241

15、41330Z10474729152635392010020Z115261423343475031202325Z12485738324552655443362302722334221Z13215238324552656151414627039485721Z144148291528354834242018Z1552563824293344250927Z16616344303842402113036X1273617112431444030202521211827360為出發(fā)點， 遍歷與點 Vk1 相連的每一條邊，記 left k1 ， k2 1 ，cos t cos t disk1, k2 ；如此下

16、去。2、每到達一個新的點Vk j ，如果 costLmin，則進行定界，終止該分枝的分枝操作，返回到點Vk j-1 ，繼續(xù)其它分枝的分枝操作。3、如果 j 又回到值 0，則表明到達了終點，完成了一個回路。4、如果Lmincost，則令 Lmin=cost，并經(jīng)過的點的路徑 path Vk1,Vk2 Vkj 。5、返回點Vkj 1 ，取下一個分枝，返回（2），以新的 Lmin 作為比較的標(biāo)準(zhǔn)，進行新的分枝操作。7四、問題 1 的模型建立與求解首先分析該縣的郵件要求：1、每輛縣級郵車最多容納 65 袋郵件，即Wi 65 ， i 0,1, 2,16式（1.1）2、每輛縣級郵車運行時間t 必須在第一班

17、區(qū)級郵車到來之后和第二班區(qū)級郵車離開之前，其中包含了區(qū)級郵車的裝卸時間，即t (16 8) 2 6式（1.2）4.1最小郵車數(shù)的求解定理 1.1：每輛縣級郵車最多容納 65 袋郵件，縣局該縣的郵件及其所轄的 16 個支局，最少需要 3 輛郵車才能滿足 X1 縣的郵件需求 X1需求。證明：已知各支局的郵件量表（包括寄達郵件量和寄出郵件）；每輛縣級郵車最多容量為 65。設(shè) Ri 分別表示支局 Zi ， i 1, 2,16 的郵件寄達量；設(shè)縣局X1 至少需要郵車n 輛。由各支局寄達郵件量 Ri 求得縣局需要寄達支局的郵件總量Q ：16Q Ii1式（1.3）根據(jù)式（1.3）求得Q 176 ；因為要保證

18、完成當(dāng)天的送達郵件的任務(wù)，所以需送達的郵件總量必須小于所有郵車的最大送達能力，即Q 65n ， n N176 65n ， n N176 n ， n N653 n ， n N式（1.4）式（1.5）式（1.6）式（1.7）證畢所以所以所以下面通過找到問題的可行解，確定最小郵車數(shù)的最小上界。定理 1.2：設(shè)縣局 X1 只要 3 輛郵車數(shù)就可以完成郵件寄達任務(wù)。證明：不妨將縣局 X1 的 16 個支局分成 3 個區(qū)域，分別為：區(qū)域 1（包括支局：Z1 ，Z2 ，Z3 ，Z4 ，Z13 ）；區(qū)域 2（包括支局：Z5 ，Z6 ，Z7 ，Z8 ，Z9 ，Z10 ）；區(qū)域 3（包括支局： Z11 ， Z12

19、 ， Z14 ， Z15 ， Z16 ）；8圖 1.2 X1 縣的區(qū)域 1，2，3 分區(qū)說明圖為每一個區(qū)域分配一輛郵車，三輛郵車分別完成三個區(qū)域的任務(wù)。如果每一輛郵車都能完成該區(qū)域的任務(wù)，則總的縣局 X1 的任務(wù)可以完成；對于每一輛郵車設(shè)定一種運行計劃如表 1.2：表 1.2三輛郵車運行計劃對于每輛郵車的運行計劃可行性，如果該郵車運行計劃可以完成，則該郵車的任務(wù)可以完成。將每輛郵車在每個到達站點的所裝郵件數(shù)量和一共運行時間列表如表 1.3：表 1.3三輛郵車按計劃運行情況9郵車到達站點及郵件數(shù)量Wi一共時間T郵車 1X1514.60小時Z1353Z152Z251Z350Z451郵車 2X164

20、4.87小時Z1056Z958Z863Z761Z557Z661郵車郵車運行計劃1X1 Z13 Z1 Z2 Z3 Z4 X12X1 Z10 Z9 Z8 Z7 Z5 Z6 X13X1 Z Z Z Z Z X對每輛郵車的出行情況進行，滿足該縣的郵件要求，即式（1.1）和式（1.2）。所以 3 輛郵車可以完成該縣的郵件寄達任務(wù)。證畢由問題分析可知該縣所需郵車數(shù)不大于 3 輛，即n 3又由定理 1.1 得：3 n 3 ， n N所以n 3 ，即最少需要 3 輛郵車才能滿足該縣的郵件式（1.8）需求。4.2 最佳郵路的規(guī)劃設(shè) A 1, 2,16，為所有支局的集合。設(shè) ( A1, A2 , A3 ) | A

21、1 A2 , A1 A3 , A2 A3 。對 A 的任何一個子集a ，定義其全排列集合為 D(a) 。比如對集合a 1, 3, 6，則 D(a) 1, 3, 6,1, 6, 3,3,1, 6,3, 6,1,6,1, 3,6, 3,1對給定的 A 的子集a ，設(shè)d d , d , d D(a) ，定義其因空車率而減少12mi的收入的函數(shù)為mi 11 d jL0,d (kj1g(d ) 2 kd0Ld ,d ) kdj j1mmL，式（1.9）d ,0ii 65 Wdk其中k為空車率， L 表示支局i 到支局 j 的最短路徑。dki, j65mikk d j d jd jkWd I(I O )

22、表示郵車從支局d 出發(fā)時所攜帶的郵件袋數(shù)。j 1j 1定義其因空車率而減少的收入的函數(shù)為 f (a) min g(d ) 。最對集合a ，dD(a) 終建立的數(shù)學(xué)模型如下：mi 133min f (Ai ) min(1 dj ,dj1 d ,dL0,d (k) kLmin2 k0,d1L)d ,0 d,0( A1,A2 ,A3 ) i1( A1,A2 ,A3 ) i1 dd1,d2 ,dmi D(Ai )j1mmjiij110郵車 3X1615.55小時Z1659Z1562Z1257Z1162Z1456mi 10,d d ,dLLLd ,020 5m1jj1mij1s.t. t 6idv60m

23、ikk d j d jd jWd I(I O ) 65j 1j 1式（1.10）分析及求解步驟如下：因為寄達郵件總量Q 為 176，而任一分區(qū)內(nèi)的 Ri 的和值最大為 130，所以任一分區(qū)的 Ri 的和值最小為 170-13046。即有：46 I 65類似40 Oi 65由此可以推出：任意分區(qū)點數(shù)在 3 到 8 之間。式（1.11）式（1.12）第 1 步、對 k3，將滿足式（1.15）和式（1.16）的點集放在S3 集合中，類似給出S4 ,., S8 的集合。第 2 步、對S3 ,., S8 中所有點集，比如S5 中的7,8, 9,10,11 ，給出所有120(=5!)種可能的郵路(如 X1

24、 7891011 X1 ),(注：給出的郵路中， X1 7表示由 X1 的最短路徑走到 7，在 7 停留 5 分鐘進行工作，而中途經(jīng)過的其它點不停留)。對 120 個郵路，分別計算以下三個分量：總路程，在任何一個停留點裝卸之后車上的最大袋數(shù)，空車損失，在計算過程中，若總路程過大使得郵車返回，或最大袋數(shù)大于 65，則令空車損失為一個很大的數(shù)（比如106 ）。不第 3 步、 對所有可能的郵路，（比如S5 中的點集，共有 120 種可能的郵路），求出最小空車損失，若最小空車損失小于105 ，將該郵路置于集合 SS5 中。最終SS3 到 SS8 的集合中的元素的個數(shù)分別為：SS3 : 11, SS4

25、: 598, SS5 : 1740, SS6 : 748, SS7 : 14, SS8 : 0，這表示了 k 個可行路線的數(shù)目。比如 5 個點的可行路線為 1740。第 4 步、 為使三個郵路完成 16 個支局的任務(wù)，這三個郵路中支局的數(shù)目可能由以下組合方式：3, 6, 7 ,4, 5, 7,4, 6, 6,5, 5, 611對任何一個組合方式，比如4, 5, 7 ，先取 1 個點的郵路ji1(對 SS7 中所有可能的郵路遍歷)，在取 5 個點的郵路ji2 (對 SS5 中所有可能的郵路遍歷)，若 ji1 與ji2 中支局沒有重復(fù)，則判斷剩下的 4 個點的集合是否能與 SS4 中的一條可行郵路

26、中的點一致。若能找到，令其為 ji3 ，這樣 ji1 ， ji2 ， ji3 就成為一個可行分區(qū)方案。第 5 步、對所有可能分區(qū)方案，找出取最小空車損失。通過編程實現(xiàn)（程序附后），得到最小空車損失費用下的郵路規(guī)劃方式，畫出最優(yōu)分區(qū)情況如圖（1.3）：圖 1.3計算得到最小空車損失費用下的郵路規(guī)劃方式及郵車安排方式，所得數(shù)據(jù)列表格得：表 1.4最優(yōu)郵車安排方式注：表花費時間”是指每條郵路郵車行駛時間，支局停留時間（每個支局 5 分鐘），以及縣局卸裝郵件耗時（一共兩個 10 分鐘）。該時間加上兩個集中處理的 1 小時時間，小于 8 小時說明該郵路滿足時間要求。根據(jù)表 1.4 的每輛車的最小損失費用

27、的函數(shù)，運用式（1.9）求得總的最小損失費用為：49.35 元(程序運行結(jié)果為 1604，將其除以 65，乘以 2 得到該損失費用)，郵政排方式。效益最大。表 1.4 三輛郵車的運行計劃為問題所求的最優(yōu)郵車安12郵車郵車運行計劃共花費時間最小損失費用X1 Z9 Z8 Z7 Z11 Z10 X15.683322.62X1 Z13 Z1 Z2 Z3 Z14 X15.380011.08X1 Z12 Z4 Z5 Z6 Z16 Z15 X15.933315.65合計49.35五、問題 2 模型建立與求解由題意所述知，全區(qū)郵政網(wǎng)絡(luò)的最優(yōu)郵路規(guī)劃是一個 VRP 問題。首先分析題目要求，已知全區(qū)共有 73 個

28、支局，5 個縣局，1 個區(qū)局，對于任意兩點之間的最短距離通過 Dijkstra 算法可以求得。表 2.1問題 2 新的符號說明分析求第k 輛郵車最大運行時間：12M M i, j i,j*kx Li1 j1 ji 12 20 -2-*, i A , xk 1 ， l Xt k式（2.1）maxMi,l6065求問題的最短郵路，分析建立數(shù)學(xué)模型如下：12N M M i, j i,jkminNx Lk 1 i1 j1j ixki2 0 , ki Ni , l Vj A（1）j ,l1221iM M i,lx 2k, k N, l X（2）111 i1xk2 0,k N ,l Y（3）i,l1211

29、N M Ms.t.xk 2M（4） k 1 i1 j1i, j式（2.2）j i M M i, jmax tl,l Xtl（5） i1j 1 j i M Mt 5k,k N（6）1i, j11 i1 j 1j i13符號說明符號說明AM所有支局、縣局、區(qū)局的集合AN經(jīng)過每個局的所有車的集合X所有縣局的集合Ui第i 個縣局所轄區(qū)域的支局的集合Y區(qū)局所轄區(qū)域的支局的集合N1經(jīng)過區(qū)局郵車的集合N i 2第i 縣局郵車的集合xki, j第k 車是否經(jīng)過第i 局到第 j 局t kmax第k 輛郵車最大運行時間t k i, j第k 車經(jīng)過第i 局到第 j 局花費時間M所有局的個數(shù)N所有車的個數(shù)令 xk 表

30、示第k 輛郵車是否經(jīng)過第i 局到第 j 局：i, j 1,第k輛車從郵局i出發(fā)到郵局j ；xk0，其它i, j 統(tǒng)計第k 輛郵車所經(jīng)過的路程，就是對所經(jīng)過相鄰兩個局的最短距離求和。由第一問，已經(jīng)知道任意兩點之間的最短距離為L i,j 。所以根據(jù)第k 輛郵車所經(jīng)郵局的選取情況，可以求出第k 輛經(jīng)過的總的郵路的長度。最后結(jié)果除以 2是因為考慮的是一個無向圖， xk xk ，每條邊被計算了兩次。設(shè)共有 Ni, jj,i 輛郵車，對所有郵車累和，最后得到總的郵路的長度，即為當(dāng)前郵路規(guī)劃的郵路長度。最后求出所有郵路規(guī)劃的郵路長度，從中找出最小的郵路長度，即為問題 2 的最優(yōu)解，對應(yīng)的郵路規(guī)劃就為所求的最

31、優(yōu)郵路規(guī)劃方式。在每求一個郵路長度時，必須滿足模型中的 6 個約束條件：約束（1）表示本縣的車只能到達本縣的支局，外縣的支局不能到達；約束（2）表示每輛區(qū)車必須至少經(jīng)過 1 個以上的縣局；約束（3）表示區(qū)級區(qū)內(nèi)的支局只能被區(qū)級的郵車遍歷；約束（4）表示所有支局都必須被遍歷；約束（5）表示縣局郵車運行時間必須在區(qū)級郵車運行時間之間，即區(qū)級郵車第一次到來之后和區(qū)級郵車第二次離開之前的這端時間；約束（6）表示區(qū)車從出去運行到運行后回來，要在 5 小根據(jù)題意及問題的假設(shè)分析得到。 約束（5）要時之內(nèi)。這些約束條件都是求當(dāng)前郵路下，保證當(dāng)前郵車運行時間小于等于第k 輛郵車的最大運行時間。式（2.1）的分

32、析是根據(jù)假設(shè) 5 得到的。在解決問題 2 的過程中，采取了先解決區(qū)級郵車的郵路規(guī)劃，然后解決縣級郵車的郵路規(guī)劃的步步推進的方法。在進行郵路規(guī)劃的過程中，由題目本身的要求及其對于圖形的認識，創(chuàng)造性的提出了如下的解決思路：1、區(qū)級郵車盡量使用環(huán)回路由，而不要原路返回（因為如果原路返回，那行駛路程中就有一半的路程是浪費的）；2、區(qū)級郵車經(jīng)過的支局盡量裝卸郵件，而不要一掠而過（因為如果區(qū)級郵車沒有裝卸郵件，必然要有縣級的郵車來到該支局裝卸郵件，那么相對的，縣級的郵車來往該支局的路程是浪費的）；3、由地區(qū)的郵政流程及時限規(guī)定決定，區(qū)級郵車經(jīng)過縣局 Xi 的路程耗費的時間TXi （包括汽車行駛時間和在各個

33、縣、支局卸裝郵件的時間）要小于 5 小時；4、區(qū)級郵車經(jīng)過縣局 Xi 的路徑，盡量在路徑附近的區(qū)內(nèi)的支局停留并裝卸郵件（因為區(qū)內(nèi)的支局必須要由區(qū)級郵車裝卸郵件，在路徑附近的區(qū)內(nèi)的支局停留并裝卸郵件帶來的路程上的耗費，一般比由專門來到該支局裝卸郵件的區(qū)級郵車帶來的路程上的耗費要?。?；5、區(qū)級郵車經(jīng)過縣局 Xi 的路程耗費的時間TXi 離 5 小時相差較大，可以在路徑附近的非區(qū)內(nèi)支局停留并裝卸郵件；6、縣級郵車盡量使用環(huán)回路由，而不要原路返回（因為如果原路返回，那行駛路程中就有一半的路程是浪費的）；147、縣級郵車經(jīng)過的支局盡量裝卸郵件，而不要一掠而過（因為如果縣級郵車沒有裝卸郵件，必然要有別的縣

34、級的郵車來到該支局裝卸郵件，那么相對的，別的縣級的郵車來往該支局的路程是浪費的）；8、Xi 縣的縣級郵車運行時間要小于 9 2 T 小時；Xi 3流程及時限規(guī)定決定，最大為 12下面的時間條總的長度由地區(qū)的郵政小時，表示區(qū)級郵車最大的工作時間，早上 6：00 第一班區(qū)級郵車出發(fā)，經(jīng)過 t1時間到達縣局，花 10 分鐘裝卸郵件，然后縣局用 1 個小時進行集中處理，之后，縣級郵車才能出發(fā)，下午，縣級郵車回到縣局后，先花 1 個小時進行集中處理，再花 10 分鐘進行區(qū)級郵車裝卸郵件，之后，區(qū)級郵車才能出發(fā)，而且必須經(jīng)過 t2 時間，在 18：00 前到達地市局。所以縣局郵車運行的最大的時間=12-區(qū)

35、級郵車最快到達縣局Xi的花費時間縣局集中處理的時間 2 區(qū)級郵車裝卸郵件的時間 2圖 2.1 縣級郵車運行時間說明圖局的最短路徑呈樹枝狀排布，在劃分縣級郵車的行駛的9、各個支局到所屬區(qū)域時，盡量把同一個“樹枝”上的支局分在一起（因為在同一“樹枝”上的支局若分在同一個行駛區(qū)域時，到達縣局所經(jīng)過的距離較短）；15圖 2.2 各個縣區(qū)距離縣局最近的連線10、縣級郵車和區(qū)級郵車經(jīng)過同一個支局時，盡量由縣級郵車卸裝這個支局的郵件（因為無論由縣級郵車或者區(qū)級郵車卸裝這個支局的郵件，帶來的卸裝時間是一樣的，但如果由縣級郵車卸裝的話，將使區(qū)級郵車花費時間變短，從而該縣內(nèi)的縣級郵車的花費時間的上限變高，有利于該

36、縣內(nèi)的郵路的安排）；關(guān)于到達各個縣城的區(qū)級郵車的數(shù)量，進行如下的分析：情況一、到達各個縣城的區(qū)級郵車的數(shù)量為 5 輛先設(shè)計一種較為普通的區(qū)級郵車的郵路規(guī)劃，即由地市局發(fā)出 5 輛區(qū)級郵車，每輛郵車到達一個不同的縣局。16圖 2.3 5 輛區(qū)級郵車運行郵路規(guī)劃圖郵路的形成步驟如下：1、從地市局 D 到縣局 X5，區(qū)局郵車按照 D-Z61-Z58-Z52-X5 的路徑到達縣局X5 并返回，共計耗時 4.23 小時，距離 5 小時的限定還有一定的距離，觀察到區(qū)內(nèi)支局 Z59，Z60，在路徑的周圍，把他們也放到路徑中，使用分枝定界法，得到區(qū)級郵車經(jīng)過縣局 X5 的路徑為 D-Z60-Z59-Z52-X

37、5-Z58-Z61-D，得到總的路程為 263km，花費的時間為 4.6295 小時。那么 X5 縣內(nèi)縣級郵車花費時間的上限為 5.0372 小時。但經(jīng)過驗證由于 X5 縣內(nèi)縣級郵車花費時間的上限的限制，導(dǎo)致縣內(nèi)郵車運行總長度的大量增大，經(jīng)過調(diào)整，區(qū)級郵車經(jīng)過縣局 X5 的路徑為 D-Z60-Z59-Z52-X5-Z58-D，得到總的路程為 263km，花費的時間為 4.5462 小時。那么 X5 縣內(nèi)縣級郵車花費時間的上限為 5.1205小時；2、從地市局 D 經(jīng)過縣局 X4， 返回 D，如果走最短的距離， 那么路徑為 D-Z72-Z41-X4，到達縣局 X4 并返回，共耗時 2.36 小時

38、，距離 5 小時的限定觀察到區(qū)內(nèi)支局 Z73，X4 縣內(nèi)支局 Z42 在路徑的周圍，還有一定的距離Z43，Z40 在縣局的周圍，把他們也放到路徑中，同時，為了使返回路徑盡可能的形成環(huán)路，又加入 X4 縣內(nèi)支局 Z39，Z38，Z37，Z36，使用分枝定界 法 ， 得 到 區(qū) 級 郵 車 經(jīng) 過 縣 局X4的 路 徑 為17D-Z72-Z73-Z42-Z43-Z41-X4-Z40-Z39-Z38-Z37-Z36-D ，得 到總的 路程為 259km，花費的時間為 4.9846 小時，那么 X4 縣內(nèi)縣級郵車花費時間的上限為 4.6821 小時；3、從地市局 D 經(jīng)過縣局 X3，返回 D，如果走最

39、短的距離，那么路徑為 D-Z66-Z65-Z28-X3，到達縣局 X3 并返回，共耗時 3.0154 小時，距離 5 小時的限定還有一定的距離，市內(nèi)支局距離 X3 縣較近的有Z71，Z702 個支局， X4 縣內(nèi)的Z34，Z35支局距離 X4 縣局距離較遠，而距離 X3 縣局較近，經(jīng)過調(diào)整，選取了Z29，Z31，Z28，Z33，Z30，Z32，Z34，Z35，Z70，Z71這幾個支局區(qū)級郵車的回路，使用分枝定界法，得到區(qū)級郵車經(jīng)過縣局 X3 的路徑為 D-Z29-Z28-X3-Z33-Z31-Z30-Z32-Z34-Z35-Z70-Z71-D，得到總的路程為 251km，花費的時間為 4.86

40、15 小時，那么 X3 縣內(nèi)縣級郵車花費時間的上限為 4.8052 小時；4、從地市局 D 經(jīng)過縣局 X2，返回 D，如果走最短的距離，那么路徑為 D-Z66-Z63-Z18-X2，到達縣局 X2 并返回，共耗時 2.7385 小時，距離 5 小時的限定還有一定的距離，為了使盡可能Z65，Z64，Z27，Z18，X2，Z68，Z69回路，經(jīng)過調(diào)整選取了Z67，路徑，使用分枝定界法，得到區(qū)級郵車經(jīng)過縣局 X3 的路徑為：D-Z69-Z68-Z65-Z27-X2-Z18-Z64-Z67-D，得到總的路程為 238km，花費時間為 4.4115 小時，那么 X2 縣內(nèi)縣級郵車花費時間的上限為 5.2

41、552 小時；5、從地市局 D 經(jīng)過縣局 X1，返回 D，如果走最短的距離，那么路徑為 D-Z62-Z9-Z10-X1，到達縣局 X1 并返回，共耗時 2.8308 小時，距離 5 小時的限定還有一定的距離，Z61 在路徑的附近，把它加入到路徑中，為了使盡可能回路，同時盡可能的使在同一個“樹枝”上的支局分在一起，經(jīng)過調(diào)整，選取了Z11，Z12，Z14，Z15，Z16，Z63，Z66放到路徑中，把Z9， Z10移出路徑，使用分枝定界法，得到區(qū)級郵車經(jīng)過縣局 X1 的路徑為： D-Z61-Z62-Z11-Z12-X1-Z14-Z15-Z16-Z63-Z66-D，得到總的路程為 228km，花費時間

42、為 4.4244 小時，那么 X1 縣內(nèi)縣級郵車花費時間的上限為 5.2423 小時；6、在 X1 縣內(nèi)，剩下的沒有郵車經(jīng)過的支局有Z1，Z2，Z3，Z13，Z4，Z5，Z6， Z7，Z8，Z9，Z10，根據(jù)圖 2 和處于一個“樹枝”上的支局盡量分在一起由一輛郵車負責(zé)寄收郵件，把 X1 縣內(nèi)的支局分成 2 部分，Z1，Z2，Z3， Z13，Z4，Z5，Z6，Z7，Z8，Z9，Z10，使用分枝定界法，得到他們各自的路徑，路徑一：X1-Z13-Z1-Z2-Z3-X1，長度為 109km，耗時 4.1167 小時，路徑二：X1-Z4-Z5-Z6-Z7-Z8-Z9-Z10-X1，長度為 106km，耗

43、時 3.5333 小時，以上兩條路徑的耗時都滿足 X1 縣內(nèi)縣級郵車花費時間的上限；7、在 X2 縣內(nèi)，剩下的沒有郵車經(jīng)過的支局有Z17，Z19，Z20，Z26，Z21，Z22， Z23，Z24，Z25，如果一輛郵車可以完成上述所有支局的寄收任務(wù)，那么需要的時間為 7.2500 小時：大于在步驟 4 中規(guī)定的 X2 縣內(nèi)縣級郵車花費時間的上限，故必然要使用 2 輛郵車完成 X2 縣內(nèi)剩下的沒有郵車經(jīng)過的支局的寄收任務(wù)，根據(jù)圖 2 和處于一個“樹枝”上的支局盡量分在一起由一輛郵車負責(zé)寄收郵件，把 X2 縣內(nèi)的支局分成 2 部分，Z17，Z19，Z20，Z26，Z21，Z22，Z23，Z24，Z2

44、5，使用分枝定界法，得到他們各自的路徑，路徑一：X2-Z17-Z19-Z20-Z26-X2，長度為 141km，耗時 5.0333 小時，路徑二： X2-Z21-Z22-Z23-Z24-Z25-X2，長度為 127km，耗時 4.6500 小時。以上兩條18路徑的耗時都滿足 X2 縣內(nèi)縣級郵車花費時間的上限； 8、在 X3 縣內(nèi)，沒有剩下支局沒有郵車經(jīng)過；9、在 X4 縣內(nèi)，沒有剩下支局沒有郵車經(jīng)過；10、在 X5 縣內(nèi)，剩下的沒有郵車經(jīng)過的支局有Z54，Z55，Z56，Z57，Z53，Z45，Z46，Z47，Z48，Z49，Z50，Z51，根據(jù)圖 2 和處于一個“樹枝”上把 X5 縣內(nèi)的支局

45、分成 2的支局盡量分在一起由一輛郵車負責(zé)寄收郵件部分，Z54，Z55，Z56，Z57，Z53，Z44，Z45，Z46，Z47，Z48，Z49，Z50，如果一輛郵車可以完成Z54，Z55，Z56，Z57，Z53的寄收任務(wù)，那么路徑一：X5-Z54-Z55-Z56-Z57-Z53-X5，長度為 140km，耗時 5.0833 小時。滿足步驟 1 規(guī)定的 X5 縣內(nèi)縣級郵車花費時間的上限，所以該路徑成立；如果一輛郵車可以完成Z44，Z45，Z46，Z47，Z48，Z49，Z50，Z51的寄收任務(wù)，那么需要花費時間為 6.1333 小時，超過 X5 縣內(nèi)縣級郵車花費時間的上限，所以分成兩個部分Z44，

46、Z46，Z51，Z50，Z49，Z48，Z47，Z45，使用分枝定界法，得到路徑二：X5-Z50-Z49-Z48-Z47-Z45-X5，長度為 133km，耗時 4.8500 小時，路徑三：X5-Z51-Z46-Z44-X5，長度為 144km，耗時 5.0500小時。以上兩條路徑的耗時都滿足 X5 縣內(nèi)縣級郵車花費時間的上限；整理上述的郵路規(guī)劃得：表 2.2郵路規(guī)劃19郵車郵車運行計劃：經(jīng)過的局號花費時間（h）單程行駛距離（km）行駛距離（km）X1 Z13 Z1 Z2 Z3 X14.1167109109X1 Z4 Z5 Z6 Z7 Z8 Z9 Z10 X14.6500127127X2 Z1

47、7 Z19 Z20 Z26 X25.03331411414X2 Z21 Z22 Z23 Z24 Z25 X24.65001271275X5 Z54 Z55 Z56 Z57 Z53 X55.08331401406X5 Z50 Z49 Z48 Z47 Z45 X54.85001331337X5 Z51 Z46 Z44 X55.05001441448DZ61Z62Z11Z12X1Z14Z15Z16Z63Z664.42442284569D Z69 Z68 Z65 Z27 X2 Z18 Z64 Z674.411523857610DZ29Z28X3Z33Z31Z30Z32Z34Z35Z70Z714.861

48、525150211DZ72Z73Z42Z43Z41X4Z40Z39Z38Z37Z364.9846259518注:單程行駛距離是指郵車由地市局或者縣局出發(fā),回到出發(fā)局所經(jīng)過的路程,因為地市局每天要發(fā) 2 班郵車,所以區(qū)級郵車每天行駛的路程是單程行駛距離的 2 倍2012D Z60 Z59 Z52 X5 Z58 Z61 D4.5462263526合計21603399情況二、到達各個縣城的區(qū)級郵車的數(shù)量為 4 輛。根據(jù) Dijkstra 算法，得到由地市局到各個縣局，及相鄰各個縣局之間的距離和經(jīng)過的支局如下表圖所示：表 2.3市局到各縣局，及相鄰各個縣局之間的距離：千米由于只使用了 4 輛區(qū)級郵車，

49、那么必然有一輛郵車在 2 個縣局裝卸郵件，經(jīng)過計算，得到郵路安排如下：表 2.4郵路規(guī)劃表注:單程行駛距離是指郵車由地市局或者縣局出發(fā),回到出發(fā)局所經(jīng)過的路程,因為地市局每天要發(fā) 2 班郵車,所以區(qū)級郵車每天行駛的路程是單程行駛距離的 2 倍21郵車經(jīng)過的局號花費時間（h）單程行駛距離（km）行駛距離（km）1X1 Z13 Z1 Z2 Z3 X13.96671091092X1 Z4 Z5 Z6 Z7 Z8 Z9 Z10 X14.11671061063X1 Z14 Z15 Z16 Z11 X13.200086864X2 Z19 Z20 Z26 X24.01671131135X2 Z21 Z22

50、Z23 Z24 Z25 X24.65001271276X3 Z31 Z30 Z32 Z33 X34.50001251257X4 Z43 Z40 Z39 Z38 X44.36671211218X5 Z46 Z45 X55.35001531539X5 Z50 Z49 Z48 Z47 Z51 X54.116711111110X5 Z54 Z55 Z56 Z57 X54.733313213211X5 Z44 X54.883314414412DZ62X1Z12 Z17 X2 Z18Z63Z66D4.679525050013DZ67Z64Z65Z27X3Z28Z29Z68Z69D4.91032655301

51、4D Z72 Z73 Z42 Z41 X4 Z36 Z37 Z34 Z35 Z70 Z71 D4.876925250415D Z61 Z58 Z53 X5 Z52 Z59 Z60 D4.7744267534合計23613395D到X1D到X2D到X3D到X4D到X5X1到X2X2到X3X3到X4X4到X5X5到X1距離928998661246254133119107情況三、到達各個縣城的區(qū)級郵車的數(shù)量為 3 輛由地區(qū)的郵政流程及時限規(guī)定中，已知區(qū)局郵車最大的外出時間為5 小時，而區(qū)局郵車必須要在每個經(jīng)過的縣郵局進行裝卸郵件，所要化的時間為10 分鐘。情況 3.1 有 2 輛區(qū)級郵車需要經(jīng)過 2

52、 個縣局，1 輛區(qū)級郵車經(jīng)過 1 個縣局 因為需要經(jīng)過 2 個縣局，所以共需要裝卸郵件的時間為 20 分鐘，又已知區(qū)局郵車的速度為 65km/h，那么當(dāng)經(jīng)過 2 個縣局最大行駛里程數(shù)為：4.667 65 303.3(km) 。情況 3.1.1 一輛區(qū)級郵車經(jīng)過 X1，X2 兩個縣局，一輛區(qū)級郵車經(jīng)過 X3， X4 兩個縣局：經(jīng)過計算， 區(qū)級郵車經(jīng)過 X1 ， X2 返回地市局總的行駛距離最小為92+62+89=243（km）區(qū)級郵車經(jīng)過 X3，X4 返回地市局總的行駛距離最小為98+133+66=297(km)。若按照 1 輛區(qū)級郵車經(jīng)過 X1，X2，1 輛郵車經(jīng)過 X3，X4，1 輛郵車經(jīng)過

53、 X5。對于經(jīng)過 X3，X4 的區(qū)級郵車，只能在經(jīng)過的任何支局停留 1 次，如果停留 2 次，花費時間為：297/65+2*10/60+10/60=5.06925 小時，假設(shè)經(jīng)過支局 Z72；對于經(jīng)過 X5 的區(qū)級郵車，在經(jīng)過的支局及其路徑周圍的支局停留裝卸郵件，共需要時間 4.9218 小時，此時，經(jīng)過 Z61,Z60,Z59,Z58,Z73;對于經(jīng)過 X1，X2 的區(qū)級郵車，在經(jīng)過支局及其路徑周圍的支局停留裝卸郵件，共需要時間 5.26415小時,而此時還有 Z68,Z69,Z70,Z71 沒有郵車經(jīng)過裝卸郵件。則導(dǎo)致地市局所轄的支局不能被經(jīng)過，所以不存在這樣的可能。情況 3.1.2 一輛

54、區(qū)級郵車經(jīng)過 X1，X5 兩個縣局，一輛區(qū)級郵車經(jīng)過 X2，X3兩個縣局：經(jīng)過計算，區(qū)級郵車經(jīng)過 X1 ， X5 返回地市局總的行駛距離最小為 124+92+107=323303.3（km）,所以這種情況不可能。情況 3.2 有 1 輛區(qū)級郵車需要跑 3 個縣局，2 輛區(qū)級郵車跑 2 個縣局：因為需要經(jīng)過 3 個縣局，所以共需要裝卸郵件的時間為 30 分鐘，又已知區(qū)局郵車的速度為 65km/h，那么最大行駛里程數(shù)為： dis 4.5 65 292.5(km) 。經(jīng)過計算，經(jīng)過 3 個縣局的總的行駛距離最小為 92+62+54+98=306292.5（當(dāng)區(qū)級郵車經(jīng)過 X1，X2，X3 回地市局）

55、所以不存在這樣的可能。綜上所述，到達各個縣城的區(qū)級郵車的數(shù)量大于 3 輛允許區(qū)級郵車上下午停留不同支局模型考慮郵政的實際情況，同一個支局，在由縣級郵車裝卸郵件時，每天需要裝卸郵件一次，而在由區(qū)級郵車裝卸郵件時，每天需要裝卸郵件兩次，這樣，各個支局之間，是不平權(quán)的。為了使各個支局都平權(quán)，假設(shè)區(qū)級郵車每天經(jīng)過支局兩次，但只裝卸郵件一次，而且裝卸郵件的時間可以（即可以選擇在第一班車裝卸郵件，也可以選擇在第二班車裝卸郵件）。這樣帶來的變化如下：1、由于區(qū)級郵車可以在支局裝卸郵件的時間，為了能使縣級郵車的運22行時間盡可能的長，所以第一班區(qū)級郵車從地市局出發(fā)后按照既定郵路直接開到縣局，不在支局停留裝卸郵

56、件，在返回的過程中經(jīng)過的支局停留并裝卸郵件，第二班區(qū)級郵車從地市局出發(fā)后按照既定的郵路經(jīng)過支局并裝卸郵件，從縣局出發(fā)后直接返回地市局，在經(jīng)過的支局不做停留，這樣可以使縣級郵車運行的時間極大化。2、區(qū)級郵車的運行時間也可以由于經(jīng)過的支局每天只要裝卸郵件一次，從而減少了每次的運行時間，最多可以減少經(jīng)過支局的個數(shù) 小時5260在如上的假設(shè)下，圖 2.4 允許區(qū)級郵車上下午停留不同支局的郵路規(guī)劃圖郵路的形成步驟：1、從地市局 D 到縣局 X5，區(qū)局郵車按照 D-Z61-Z58-Z52-X5 的路徑到達縣局X5 并返回，共計耗時 4.23 小時，距離 5 小時的限定還有一定的距離，觀察到區(qū)內(nèi)支局 59，

57、60，X5 縣內(nèi)支局 53 在路徑的周圍，把他們也放到路徑中 ， 使 用 分 枝 定 界 法 ， 得 到 區(qū) 級 郵 車 經(jīng) 過 縣 局 X5 的 路 徑 為 D Z61 Z58 Z53 X5 Z52 Z59 Z60 D ， 得到總的路程為 267km，花費的時間為 4.5244 小時。區(qū)級郵車最快到達縣局 X5 的時間為23T 267 4.1077 ，那么 X5 縣內(nèi)縣級郵車花費時間的上限為 5.5590 小時；X 5652、從地市局 D 經(jīng)過縣局 X4， 返回 D，如果走最短的距離，那么路徑為D Z72 Z41 X4 ，到達縣局 X4 并返回，共耗時 2.36 小時，距離 5 小時的限定還

58、有一定的距離，觀察到區(qū)內(nèi)支局 Z73，X4 縣內(nèi)支局 Z42 在路徑的周圍，Z43，Z40 在縣局的周圍，把他們也放到路徑中，同時，X5 縣內(nèi)的Z44 距離 X4 較近，而離 X5 較遠，把他也放到路徑中，使返回路徑盡可能的形成環(huán)路，又加入 X4 縣內(nèi)支局 Z39，Z38，Z37，Z36，使用分枝定界法，得到區(qū)級郵車經(jīng)過縣局 X4 的路徑為：D Z73 Z42 Z43 Z44 Z41 X4 Z40 Z39 Z38 Z37 Z36 D3、總的路程為 284km，花費的時間為 4.9525 小時；區(qū)級郵車最快到達縣局 X4的時間為T 284 4.3692 ，那么 X4 縣內(nèi)縣級郵車花費時間的上限為

59、X 4655.2975 小時；4、從地市局 D 經(jīng)過縣局 X3，返回 D，如果走最短的距離，那么路徑為 D-Z66-Z65-Z28-X3，到達縣局 X3 并返回，共耗時 3.0154 小時，距離 5 小時的限定還有一定的距離，市內(nèi)支局距離 X3 縣較近的有Z68，Z69，Z70，Z714個支局，X4 縣內(nèi)的Z34，Z35支局距離 X4 縣局距離較遠，而距離 X3 縣局較近，經(jīng)過調(diào)整，選取了Z69，Z68，Z29，Z31，Z28，Z33，Z30，Z32，Z34，Z35，Z70，Z71，Z72這幾個支局區(qū)級郵車的回路，使用分枝定界法 ， 得 到 區(qū) 級 郵 車 經(jīng) 過 縣 局X3的 路 徑 為D-

60、Z69-Z68-Z29-Z31-Z28-X3-Z33-Z30-Z32-Z34-Z35-Z70-Z71-Z72-D，得到總的路程為 275km，花費的時間為 4.9809 小時；區(qū)級郵車最快到達縣局 X3 的時間為T 275 4.2308 ，那 X3 縣內(nèi)縣級郵車花費時間的上限為 5.4359 小時；X 3655、從地市局 D 經(jīng)過縣局 X2，返回 D，如果走最短的距離，那么路徑為 D-Z66-Z63-Z18-X2，到達縣局 X2 并返回，共耗時 2.7385 小時，距離 5 小時回路，選取了Z67，Z65，的限定還有一定的距離，為了使盡可能Z64，Z27放到路徑中，使用分枝定界法，得到區(qū)級郵車