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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、3Z4Z5Z6Z7Z8Z9Z10Z11Z12Z13Z14Z15Z16X1Z1031273851587167574752482141526127Z2310193327324564534761575248566336Z32749392942383829384417Z43833251533323215243011Z551272713092137262643454528293824Z658323420901332323547525235334231Z77145473321656548444044Z86764493537326134252140Z95753392526323011010204351241

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

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

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

18、完成當(dāng)天的送達(dá)郵件的任務(wù)，所以需送達(dá)的郵件總量必須小于所有郵車的最大送達(dá)能力，即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ù)就可以完成郵件寄達(dá)任務(wù)。證明：不妨將縣局 X1 的 16 個(gè)支局分成 3 個(gè)區(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ū)說明圖為每一個(gè)區(qū)域分配一輛郵車，三輛郵車分別完成三個(gè)區(qū)域的任務(wù)。如果每一輛郵車都能完成該區(qū)域的任務(wù)，則總的縣局 X1 的任務(wù)可以完成；對(duì)于每一輛郵車設(shè)定一種運(yùn)行計(jì)劃如表 1.2：表 1.2三輛郵車運(yùn)行計(jì)劃對(duì)于每輛郵車的運(yùn)行計(jì)劃可行性，如果該郵車運(yùn)行計(jì)劃可以完成，則該郵車的任務(wù)可以完成。將每輛郵車在每個(gè)到達(dá)站點(diǎn)的所裝郵件數(shù)量和一共運(yùn)行時(shí)間列表如表 1.3：表 1.3三輛郵車按計(jì)劃運(yùn)行情況9郵車到達(dá)站點(diǎn)及郵件數(shù)量Wi一共時(shí)間T郵車 1X1514.60小時(shí)Z1353Z152Z251Z350Z451郵車 2X164

20、4.87小時(shí)Z1056Z958Z863Z761Z557Z661郵車郵車運(yùn)行計(jì)劃1X1 Z13 Z1 Z2 Z3 Z4 X12X1 Z10 Z9 Z8 Z7 Z5 Z6 X13X1 Z Z Z Z Z X對(duì)每輛郵車的出行情況進(jìn)行，滿足該縣的郵件要求，即式（1.1）和式（1.2）。所以 3 輛郵車可以完成該縣的郵件寄達(dá)任務(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 。對(duì) A 的任何一個(gè)子集a ，定義其全排列集合為 D(a) 。比如對(duì)集合a 1, 3, 6，則 D(a) 1, 3, 6,1, 6, 3,3,1, 6,3, 6,1,6,1, 3,6, 3,1對(duì)給定的 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í)所攜帶的郵件袋數(shù)。j 1j 1定義其因空車率而減少的收入的函數(shù)為 f (a) min g(d ) 。最對(duì)集合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小時(shí)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）分析及求解步驟如下：因?yàn)榧倪_(dá)郵件總量Q 為 176，而任一分區(qū)內(nèi)的 Ri 的和值最大為 130，所以任一分區(qū)的 Ri 的和值最小為 170-13046。即有：46 I 65類似40 Oi 65由此可以推出：任意分區(qū)點(diǎn)數(shù)在 3 到 8 之間。式（1.11）式（1.12）第 1 步、對(duì) k3，將滿足式（1.15）和式（1.16）的點(diǎn)集放在S3 集合中，類似給出S4 ,., S8 的集合。第 2 步、對(duì)S3 ,., S8 中所有點(diǎn)集，比如S5 中的7,8, 9,10,11 ，給出所有120(=5!)種可能的郵路(如 X1

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

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

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

27、的函數(shù)，運(yùn)用式（1.9）求得總的最小損失費(fèi)用為：49.35 元(程序運(yùn)行結(jié)果為 1604，將其除以 65，乘以 2 得到該損失費(fèi)用)，郵政排方式。效益最大。表 1.4 三輛郵車的運(yùn)行計(jì)劃為問題所求的最優(yōu)郵車安12郵車郵車運(yùn)行計(jì)劃共花費(fèi)時(shí)間最小損失費(fèi)用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合計(jì)49.35五、問題 2 模型建立與求解由題意所述知，全區(qū)郵政網(wǎng)絡(luò)的最優(yōu)郵路規(guī)劃是一個(gè) VRP 問題。首先分析題目要求，已知全區(qū)共有 73 個(gè)

28、支局，5 個(gè)縣局，1 個(gè)區(qū)局，對(duì)于任意兩點(diǎn)之間的最短距離通過 Dijkstra 算法可以求得。表 2.1問題 2 新的符號(hào)說明分析求第k 輛郵車最大運(yùn)行時(shí)間：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符號(hào)說明符號(hào)說明AM所有支局、縣局、區(qū)局的集合AN經(jīng)過每個(gè)局的所有車的集合X所有縣局的集合Ui第i 個(gè)縣局所轄區(qū)域的支局的集合Y區(qū)局所轄區(qū)域的支局的集合N1經(jīng)過區(qū)局郵車的集合N i 2第i 縣局郵車的集合xki, j第k 車是否經(jīng)過第i 局到第 j 局t kmax第k 輛郵車最大運(yùn)行時(shí)間t k i, j第k 車經(jīng)過第i 局到第 j 局花費(fèi)時(shí)間M所有局的個(gè)數(shù)N所有車的個(gè)數(shù)令 xk 表

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

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

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

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

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

35、級(jí)郵車最快到達(dá)縣局Xi的花費(fèi)時(shí)間縣局集中處理的時(shí)間 2 區(qū)級(jí)郵車裝卸郵件的時(shí)間 2圖 2.1 縣級(jí)郵車運(yùn)行時(shí)間說明圖局的最短路徑呈樹枝狀排布，在劃分縣級(jí)郵車的行駛的9、各個(gè)支局到所屬區(qū)域時(shí)，盡量把同一個(gè)“樹枝”上的支局分在一起（因?yàn)樵谕弧皹渲Α鄙系闹Ь秩舴衷谕粋€(gè)行駛區(qū)域時(shí)，到達(dá)縣局所經(jīng)過的距離較短）；15圖 2.2 各個(gè)縣區(qū)距離縣局最近的連線10、縣級(jí)郵車和區(qū)級(jí)郵車經(jīng)過同一個(gè)支局時(shí)，盡量由縣級(jí)郵車卸裝這個(gè)支局的郵件（因?yàn)闊o論由縣級(jí)郵車或者區(qū)級(jí)郵車卸裝這個(gè)支局的郵件，帶來的卸裝時(shí)間是一樣的，但如果由縣級(jí)郵車卸裝的話，將使區(qū)級(jí)郵車花費(fèi)時(shí)間變短，從而該縣內(nèi)的縣級(jí)郵車的花費(fèi)時(shí)間的上限變高，有利于該

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

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

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

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

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

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

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

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

44、5，使用分枝定界法，得到他們各自的路徑，路徑一：X2-Z17-Z19-Z20-Z26-X2，長(zhǎng)度為 141km，耗時(shí) 5.0333 小時(shí)，路徑二： X2-Z21-Z22-Z23-Z24-Z25-X2，長(zhǎng)度為 127km，耗時(shí) 4.6500 小時(shí)。以上兩條18路徑的耗時(shí)都滿足 X2 縣內(nèi)縣級(jí)郵車花費(fèi)時(shí)間的上限； 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 和處于一個(gè)“樹枝”上把 X5 縣內(nèi)的支局

45、分成 2的支局盡量分在一起由一輛郵車負(fù)責(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，長(zhǎng)度為 140km，耗時(shí) 5.0833 小時(shí)。滿足步驟 1 規(guī)定的 X5 縣內(nèi)縣級(jí)郵車花費(fèi)時(shí)間的上限，所以該路徑成立；如果一輛郵車可以完成Z44，Z45，Z46，Z47，Z48，Z49，Z50，Z51的寄收任務(wù)，那么需要花費(fèi)時(shí)間為 6.1333 小時(shí)，超過 X5 縣內(nèi)縣級(jí)郵車花費(fèi)時(shí)間的上限，所以分成兩個(gè)部分Z44，

46、Z46，Z51，Z50，Z49，Z48，Z47，Z45，使用分枝定界法，得到路徑二：X5-Z50-Z49-Z48-Z47-Z45-X5，長(zhǎng)度為 133km，耗時(shí) 4.8500 小時(shí)，路徑三：X5-Z51-Z46-Z44-X5，長(zhǎng)度為 144km，耗時(shí) 5.0500小時(shí)。以上兩條路徑的耗時(shí)都滿足 X5 縣內(nèi)縣級(jí)郵車花費(fèi)時(shí)間的上限；整理上述的郵路規(guī)劃得：表 2.2郵路規(guī)劃19郵車郵車運(yùn)行計(jì)劃：經(jīng)過的局號(hào)花費(fèi)時(shí)間（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)過的路程,因?yàn)榈厥芯置刻煲l(fā) 2 班郵車,所以區(qū)級(jí)郵車每天行駛的路程是單程行駛距離的 2 倍2012D Z60 Z59 Z52 X5 Z58 Z61 D4.5462263526合計(jì)21603399情況二、到達(dá)各個(gè)縣城的區(qū)級(jí)郵車的數(shù)量為 4 輛。根據(jù) Dijkstra 算法，得到由地市局到各個(gè)縣局，及相鄰各個(gè)縣局之間的距離和經(jīng)過的支局如下表圖所示：表 2.3市局到各縣局，及相鄰各個(gè)縣局之間的距離：千米由于只使用了 4 輛區(qū)級(jí)郵車，

49、那么必然有一輛郵車在 2 個(gè)縣局裝卸郵件，經(jīng)過計(jì)算，得到郵路安排如下：表 2.4郵路規(guī)劃表注:單程行駛距離是指郵車由地市局或者縣局出發(fā),回到出發(fā)局所經(jīng)過的路程,因?yàn)榈厥芯置刻煲l(fā) 2 班郵車,所以區(qū)級(jí)郵車每天行駛的路程是單程行駛距離的 2 倍21郵車經(jīng)過的局號(hào)花費(fèi)時(shí)間（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合計(jì)23613395D到X1D到X2D到X3D到X4D到X5X1到X2X2到X3X3到X4X4到X5X5到X1距離928998661246254133119107情況三、到達(dá)各個(gè)縣城的區(qū)級(jí)郵車的數(shù)量為 3 輛由地區(qū)的郵政流程及時(shí)限規(guī)定中，已知區(qū)局郵車最大的外出時(shí)間為5 小時(shí)，而區(qū)局郵車必須要在每個(gè)經(jīng)過的縣郵局進(jìn)行裝卸郵件，所要化的時(shí)間為10 分鐘。情況 3.1 有 2 輛區(qū)級(jí)郵車需要經(jīng)過 2

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

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

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

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

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

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

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

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

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