艾志景-中國郵遞員問題的應(yīng)用研究

1、分類號 論文選題類型 U D C 編號 本科畢業(yè)論文（設(shè)計(jì)）題 目 中國郵遞員問題的應(yīng)用研究 學(xué) 院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院 專 業(yè) 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 年 級 2009級 學(xué)生姓名 艾志景 學(xué) 號 2009211953 指導(dǎo)教師 李相文 二一三 年 五 月 1華中師范大學(xué)學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下獨(dú)立進(jìn)行研究工作所取得的研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。本人完全意識到本聲明的法律后果由本人承擔(dān)。學(xué)位論文作者簽名： 日期： 年 月 日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保障、使用學(xué)位

2、論文的規(guī)定，同意學(xué)校保留并向有關(guān)學(xué)位論文管理部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)省級優(yōu)秀學(xué)士學(xué)位論文評選機(jī)構(gòu)將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。本學(xué)位論文屬于1、保密 ，在_年解密后適用本授權(quán)書。2、不保密 。（請?jiān)谝陨舷鄳?yīng)方框內(nèi)打“”）學(xué)位論文作者簽名： 日期： 年 月 日導(dǎo)師簽名： 日期： 年 月 日目 錄內(nèi)容摘要1關(guān)鍵詞1Abstract1Key words11 中國郵遞員問題21.1無向圖上的中國郵遞員問題21.1.1 算法21.2有向圖上的中國郵遞員問題61.3 小結(jié)62 災(zāi)害地區(qū)的

3、中國郵遞員問題72.1 災(zāi)郵問題解存在的充分必要條件82.2 災(zāi)郵問題的多項(xiàng)式算法103 時(shí)間限制下的中國郵遞員問題123.1 時(shí)間限制下的DCPP模型123.2 值的分析143.3 DCPP模型的一個(gè)例子153.4 改進(jìn)的時(shí)間限制下的DCPP模型163.5解的存在性16參考文獻(xiàn)18內(nèi)容摘要：中國郵遞員問題（Chinese Postman Problem，簡記CPP）是首先由中國數(shù)學(xué)家管梅谷（1962）研究的，具體指：郵遞員在郵局里選出郵件，遞送郵件，然后再返回郵局，自然，他必須走過他投遞范圍內(nèi)的每一條街道至少一次，在這個(gè)前提下，希望選擇一條盡可能短的線路1。很多問題在進(jìn)行抽象出模型后都可以轉(zhuǎn)

4、化為中國郵遞員問題，在本文中，選取兩個(gè)代表：無向圖上的CPP選取災(zāi)郵問題，也即在圖上加上郵遞員在某些邊上只能通過一次的限制條件；有向圖選取時(shí)間限制下的CPP，也即在圖上加上郵遞員在過點(diǎn)過邊需要滿足某些時(shí)間限制條件。 關(guān)鍵詞：中國郵遞員問題 應(yīng)用 災(zāi)郵問題 時(shí)間限制Abstract: The Chinese Postman Problem(CPP) was first proposed by the Chinese mathematician MeiguGuan(1962). It says that a postman picks up mails at the post office, de

5、livers it along a set of streets, and returns to the post office. So he must cover over every street at least once, With that premise, the CPP is referring to investigate a tour under the least cost. Many question can be translated into Chinese Postman Problem during the model abstracting, In this p

6、aper, we select two representatives: To the undirected CPP, we get disaster-mail, that is plus the postman can travel some only once; To the CPP, we get time-constrained CPP, that is the postman should satisfied some condition when he passed some vertices or edges.Key words: Chinese Postman Problem

7、adhibtion disaster-mail promblem time-constrained161 中國郵遞員問題中國郵遞員問題（Chinese Postman Problem，簡記CPP）是首先由中國數(shù)學(xué)家管梅谷（1962）研究的，具體指：郵遞員在郵局里選出郵件，遞送郵件，然后在返回郵局，自然，他必須走過他投遞范圍內(nèi)的每一條街道至少一次，在這個(gè)前提下，希望選擇一條盡可能短的線路1。主要包括無向圖上的中國郵遞員問題、有向圖上的中國郵遞員問題、混合圖上的中國郵遞員問題、鄉(xiāng)村投遞員問題和帶風(fēng)向的中國郵遞員問題。后面兩個(gè)主要為中國郵遞員問題的推廣，在本章中主要介紹前兩種。1.1 無向圖上的中國

8、郵遞員問題設(shè)無向圖是一個(gè)賦權(quán)圖，環(huán)游的權(quán)定義為，無向圖上的中國郵遞員問題就是在具有非負(fù)權(quán)的賦權(quán)連通圖中找到一條最小的環(huán)游，這種環(huán)游稱為最優(yōu)環(huán)游。若是圖，則的任何環(huán)游都是最優(yōu)環(huán)游，因?yàn)榄h(huán)游是一條通過的每一條邊恰好一次的環(huán)游，在這種情形下，中國郵遞員問題是很容易解決的，因?yàn)樵趫D中，存在著確定環(huán)游的好算法。由提出的算法2，用依次描畫一條跡的方法來構(gòu)做環(huán)游，而這種描畫服從一個(gè)條件：在每一部中，未描畫的子圖的割邊僅當(dāng)沒有別的邊可以選擇時(shí)才被描畫。1.1.1 算法1.任意選取一個(gè)頂點(diǎn)，置。2.假設(shè)跡已經(jīng)選定，那么按下述方法從中選取邊：(i) 和相關(guān)聯(lián)；(ii) 除非沒有別的邊可以選擇，否則不是的割邊3.當(dāng)

9、第2步不能再執(zhí)行時(shí)，算法停止。 根據(jù)這個(gè)定義，算法作出中的一條跡。 定理1.1 若是圖，則中任一用算法作出的跡都是的環(huán)游。 證 設(shè)是圖，是中用算法做出的跡，顯然，終點(diǎn)在中的度必然為0，由此推知，；換言之，是閉跡。 現(xiàn)假設(shè)不是的環(huán)游，并且設(shè)是中度為正的頂點(diǎn)集，那么是非空的，且，這里。設(shè)是使得以及的最大整數(shù)。由于終止與，所以是的僅有的一條邊，因此也就是的一條割邊（如圖1.1）。設(shè)是中和關(guān)聯(lián)的另外一條邊，可以退推得：必然也是的一條割邊，因而是的割邊，但是由于，所以中的每一個(gè)頂點(diǎn)都是偶點(diǎn)，可是由此推出沒有割邊，導(dǎo)致矛盾。vm圖1.1 若不是圖，則的任何環(huán)游，特別是的最優(yōu)環(huán)游，通過某些邊將超過一次。文3

10、中提供了一種算法, 其大意如下。設(shè)是圖的一個(gè)邊集, 若把中的邊加人中（作為重復(fù)邊）, 得到的圖就沒有奇次頂點(diǎn)了, 就稱為一組可行解，總權(quán)數(shù)最短的可行解叫做最優(yōu)解，不難看出, 可行解一般可以看成是一些把的奇次頂點(diǎn)一對一對地連接起來的路。由于沒有奇次頂點(diǎn), 即是歐拉圖, 因此有回路。這樣問題就轉(zhuǎn)化為在圖上求環(huán)游，可以用算法求解。那么關(guān)鍵的部分就是如何找到使得最小的，J.Edmonds在4中提出了解決算法。上述找最優(yōu)解的辦法是以下述定理1.25為基礎(chǔ)的。定理1.2 一個(gè)可行解為最優(yōu)解的充要條件是下述兩個(gè)條件都成立:(1) 中沒有重復(fù)出現(xiàn)的邊。(2) 在的每個(gè)圈上, 屬于的邊的長度不超過圈長的一半。證

11、明 必要性：對于（1），為可行解，則對于原圖中的某條邊，添的重復(fù)邊數(shù)為奇數(shù)，當(dāng)出現(xiàn)重復(fù)邊時(shí)，只需去掉多余的邊，剩下一條添加邊，則余下的仍為可行解，但總長度減小，與為最優(yōu)解矛盾。 對于（2），假設(shè)存在一個(gè)圈，屬于的邊的長度不超過圈長的一半，這時(shí)圈上不屬于的邊的長度小于屬于的邊的長度，此時(shí)去掉中屬于圈上的邊得，而在上添加圈上不屬于的邊得，則仍為可行解，但總長度減小，為最優(yōu)解矛盾。 充分性：先證明下面的引理。引理1.1 設(shè)有兩組解都滿足定理1.2的(1)和(2)，則兩組解得總長度相等。證明 設(shè)和為兩組解都滿足定理1.2的(1)和(2)，若和在同一條邊上都有加邊，設(shè)邊的兩端點(diǎn)為和。 現(xiàn)在考慮另外一個(gè)問

12、題，它由原問題將點(diǎn)和的奇偶性對換得來的（如果和之間有邊則去掉一條邊，若無則添加一條邊），另外考慮新問題的兩組可行解和（和由和去掉和之間共有的邊而來的），顯然，和為新問題的可行解，且仍滿足(1)和(2)，這樣，問題歸結(jié)于證明和的加邊總長度相等。如果和仍在同樣的加邊，則重復(fù)上面的過程，這樣，我們可以不妨假設(shè)和原本就不存在相同的加邊。若和為空集，則它們的總長度相等，現(xiàn)設(shè)和不為空集，而可行解可以看做是一些把奇點(diǎn)一對一對的連起來的路的集合，從中選取這樣的一條路，設(shè)端點(diǎn)為和，由為奇點(diǎn)，則在中也存在一條路，端點(diǎn)為和，在取中的一條以為端點(diǎn)的路，另一端點(diǎn)為，由于奇點(diǎn)有限，因此這樣取下去，一定會得到一條路，它的端

13、點(diǎn)為和，但，這時(shí)，很明顯，路組必組成一個(gè)圈，在上述圈中，的加邊長加的加邊長等于圈長，而由(2)，可得的加邊長和的加邊長都等于圈長的一半。現(xiàn)在有考慮一個(gè)新的問題，它是將上述圈上的路的端點(diǎn)的奇偶性交換而得，若一個(gè)點(diǎn)為兩個(gè)路的端點(diǎn)，則交換兩次。然后考慮新問題的兩組可行解和，他們是由和中去掉上述圈上所有加邊而得來的，易得和為新問題的可行解，且滿足(1)和(2)，則問題可以歸結(jié)為證明和的加邊總長度相等。若和不為空集，則可以在歸結(jié)為另一個(gè)問題，由于每次由于每次由一對可行解歸結(jié)為另一對可行解，加邊的數(shù)目減小，故最后會得到一對可行解都是空集，而這就證明了和的加邊總長度相等。引理1.2 最優(yōu)解存在證明 對于任意

14、一組不滿足于(1)的可行解而言，一定可以通過去掉重復(fù)邊后得到一個(gè)總長度比他小的滿足(1)的可行解。而顯然的，滿足(1)的可行解為有限的，因此，有限個(gè)滿足(1)的可行解中最小的為最優(yōu)解?，F(xiàn)在我們來證明充分性，由于最優(yōu)解存在，且滿足(1)和(2)，而滿足(1)和(2)的可行解的總長度都一樣，因此滿足(1)和(2)的可行解都是最優(yōu)解。這樣就可以得出一種求最優(yōu)解的迭代法：先求任意一個(gè)可行解，然后用定理的(1)和(2)，判斷是否為最優(yōu)解，如果否，則進(jìn)行調(diào)整。不過這只對于圈數(shù)很少的圖適用。1.2 有向圖上的中國郵遞員問題J.Edmonds在4，Koh和Teh在6中提出了有向圖上的中國郵遞員問題:“假設(shè)是一

15、個(gè)連通有向圖 ,每一條邊有正的權(quán)， 要求找一條包含的每一條邊至少一次的回路（投遞路線）, 且使總長度為最小。”在街道只允許單向行駛時(shí)，郵遞員就面臨上述問題。對于有向圖而言，單單連通不足以保證投遞路線是存在的，可以證明，存在投遞路線的充要條件是是強(qiáng)連通的。有向圖上的投遞員問題解起來并不比無向圖上的難。解法的基本思想與無向圖的情況是一樣的，即在圖上增加邊集合來得到一個(gè)圖使得是有向歐拉圖, 即每一個(gè)頂點(diǎn)的人度數(shù)與出度數(shù)都相等的圖，于是圖的歐拉回路就是的投遞路線。為了求得的最短投遞路線, 必須使中各弧的總長度為最短。 1.3 小結(jié) 本章中初略的介紹了中國郵遞員問題的情況與研究成果，包括無向圖上的CPP

16、的各種解法，有向圖上的CPP的基本解題思路。接下來的兩章中，我們主要介紹中國郵遞員問題的具體解法和應(yīng)用，第二章為無向圖上的中國郵遞員問題（UCPP）的應(yīng)用，但在此我們添加了一個(gè)條件：某些邊上最多只能通過一次，第三章為有向圖上的中國郵遞員問題（DCPP）的應(yīng)用，添加了時(shí)間限制條件，我們應(yīng)用運(yùn)籌學(xué)的方法來解決。2 災(zāi)害地區(qū)的中國郵遞員問題近些年來，我國頻發(fā)各種自然災(zāi)害：2007年5月下旬以來，云南暴雨肆虐，163人死亡； 2008年1月以來，我國南方大部分地區(qū)遭遇罕見的冰雪災(zāi)害，交通、電力、通訊等遭受嚴(yán)峻挑戰(zhàn)，百姓生活受到嚴(yán)重影響；2008年5月12日四川汶川縣映秀鎮(zhèn)發(fā)生了里氏8.0級的地震。在遭

17、受災(zāi)害的地區(qū)，由于道路破壞嚴(yán)重使得救災(zāi)部隊(duì)的通訊員只能安全的通過一次，這就要求通訊員從指揮部出發(fā)后，必須不重復(fù)的通過這些道路，且遍歷該地區(qū)的其他道路一次，最后以最短的路程完成投遞任務(wù)返回指揮部。假設(shè)該道路可以沿任何方向通過，則用圖論術(shù)語可描述為：在無向圖中，設(shè)邊集，要求在中找到一條閉途徑滿足：(i) 經(jīng)過中的每條邊恰好一次；(ii) 經(jīng)過中的每條邊至少一次。我們稱這樣的閉途徑為中一條災(zāi)郵路線7；的所有關(guān)于的災(zāi)郵路線中總權(quán)最小的稱為的最優(yōu)災(zāi)郵路線（最優(yōu)環(huán)游）。當(dāng)為圖時(shí)，則必然存在環(huán)游，而且經(jīng)過（包括和）的每條邊恰好一次，所以為中一條災(zāi)郵路線，且為最優(yōu)災(zāi)郵路線。利用算法，就能很快的求出解。當(dāng)為非圖

18、時(shí)，則利用添加重復(fù)邊的方法使得變?yōu)閳D，于是可利用前面的方法求出解，但在這里，添加的邊集滿足，稱這樣的邊集為關(guān)于的可行方案；如果中存在關(guān)于的可行方案，則稱其中總權(quán)最小的為關(guān)于的最優(yōu)方案。但存在的問題是，中很可能不存在任何一種關(guān)于的可行方案，因此我們首先要確定的是，當(dāng)邊集滿足什么條件時(shí)，中才可能存在關(guān)于的可行方案，這個(gè)問題的答案，為后面的解關(guān)于的災(zāi)郵問題的算法提供可靠的依據(jù)。2.1 災(zāi)郵問題解存在的充分必要條件首先給出一個(gè)中存在關(guān)于的可行方案的充分條件。定理2.1 設(shè)連通非圖，若不是的邊割，則中存在關(guān)于的可行方案。證明 由不是的邊割，則仍然連通，將原中的偶數(shù)個(gè)奇點(diǎn)，在中兩兩配對，由于連通，則配對的

19、兩個(gè)奇點(diǎn)必存在一條途徑，將此途徑所經(jīng)過的邊集加到原圖中，則奇點(diǎn)變?yōu)榕键c(diǎn)，而偶點(diǎn)仍為偶點(diǎn)。所以得到的圖不含奇點(diǎn)為圖，而，則為關(guān)于可行方案。下面我們給出三個(gè)中存在關(guān)于的可行方案的必要條件。定理2.2 設(shè)連通非圖存在關(guān)于的可行方案，則必不包含中任何奇點(diǎn)的關(guān)聯(lián)邊集。證明 假設(shè)包含中奇點(diǎn)的關(guān)聯(lián)邊集，則中必為孤立點(diǎn)，不存在任何一種途徑經(jīng)過，則不能通過添加的邊集使得變?yōu)閳D，與存在關(guān)于的可行方案矛盾，則必不包含中任何奇點(diǎn)的關(guān)聯(lián)邊集。引理 2.1 設(shè)是連通非圖的一條割邊，則的兩個(gè)連通分支分別含有的奇數(shù)個(gè)奇點(diǎn)。證明 設(shè)與相關(guān)聯(lián)的兩個(gè)點(diǎn)為，由是連通非圖的一條割邊，則的兩個(gè)連通分支和，其中為的頂點(diǎn)集，點(diǎn)，連通分支和分

20、別有偶數(shù)個(gè)奇點(diǎn)，若在和上添加邊，則的奇偶性改變，而的其他點(diǎn)奇偶性不變，所以的兩個(gè)連通分支分別含有的奇數(shù)個(gè)奇點(diǎn)。定理2.3 設(shè)連通非圖存在關(guān)于的可行方案，則的任何邊都不是的割邊。證明 若不包含割邊，則顯然成立。若包含割邊，且設(shè)包含一條割邊，則分為兩個(gè)連通分支和，由引理2.1可知，其分別含有的奇數(shù)個(gè)奇點(diǎn)，再在中去掉的邊，得圖，相當(dāng)于在中去掉中的邊，則圖含有的奇數(shù)個(gè)奇點(diǎn)，若要在中將偶數(shù)個(gè)奇點(diǎn)兩兩配對，只能先在中奇數(shù)個(gè)奇點(diǎn)兩兩配對，則會剩下一個(gè)奇點(diǎn)未配對，中也剩下了一個(gè)。但由于和未連通，則中的奇點(diǎn)和中的奇點(diǎn)不可能相連。所以無論怎樣添加邊都不可能消除中的奇點(diǎn)，與存在關(guān)于的可行方案矛盾，則的任何邊都不是的

21、割邊。如果對定理2.3進(jìn)行推廣，將割邊推廣為邊割，則仿照定理2.3的證明，可以得到：定理2.4 設(shè)連通非圖中，邊集為的一個(gè)邊割，若中存在關(guān)于的可行方案，則中包含中偶數(shù)個(gè)奇點(diǎn)。引理2.2 在圖中，若為圖的一個(gè)鍵，記作為，則由和導(dǎo)出的子圖和連通。證明 不妨假設(shè)不連通，則至少包含2個(gè)連通分支，任選其中2個(gè)，記作和，則選取，易知為圖的一個(gè)邊割，而，與為圖的一個(gè)鍵矛盾，則由和導(dǎo)出的子圖和連通下面給出一個(gè)連通非圖存在關(guān)于的可行方案的充要條件：當(dāng)不是圖的邊割時(shí)，由定理2.1知，圖必包含關(guān)于的可行方案，當(dāng)是圖的極小邊割（鍵）時(shí)，圖存在關(guān)于的可行方案的充要條件由下面定理給出：定理2.5 在圖中，若為圖的一個(gè)鍵，

22、記作為，則存在關(guān)于的可行方案當(dāng)且僅當(dāng)中含有的偶數(shù)個(gè)奇點(diǎn)證明 必要性：定理2.4已給出；圖3.1 充分性：由為圖的一個(gè)鍵，記作為，生成的子圖為，由引理2.2，則分為兩個(gè)連通分支，記作和，如圖2.1。 由中含有的偶數(shù)個(gè)奇點(diǎn)，則中也含有的偶數(shù)個(gè)奇點(diǎn)。所以中的偶數(shù)個(gè)奇點(diǎn)可以兩兩配對，配對的兩個(gè)奇點(diǎn)中可以找到一條途徑且不經(jīng)過的任何一條邊，則這些途徑所經(jīng)過的邊組成的邊集構(gòu)成了關(guān)于的可行方案。2.2 災(zāi)郵問題的多項(xiàng)式算法下面給出一個(gè)求賦權(quán)非圖上災(zāi)郵問題的最優(yōu)解的一個(gè)多項(xiàng)式算法：給定賦權(quán)非圖，(1) 若，轉(zhuǎn)步驟2，否則轉(zhuǎn)步驟5。(2) 若中存在某個(gè)奇點(diǎn)使，則算法終止，上關(guān)于的災(zāi)郵問題無解，否則轉(zhuǎn)步驟3。(3)

23、 若的任何邊都屬于的某個(gè)圈，則轉(zhuǎn)步驟4，否則，找出中所有不在任何圈上的邊，記為，且若含有其中某條邊，則算法終止，無解，否則轉(zhuǎn)步驟4。(4) 若不是的邊割，則轉(zhuǎn)步驟5，否則記且若中含有的偶數(shù)個(gè)奇點(diǎn)，轉(zhuǎn)步驟5，否則算法終止，無解。(5) 把中每條邊用一對方向相反的弧代替，弧上的權(quán)值等于邊上的權(quán)值，用算法求出中任意頂點(diǎn)對之間的最短路即路長，得距離矩陣（等于中從到的最短路長）和路徑矩陣（元素代表中從到的最短路上與相鄰的頂點(diǎn)的下標(biāo)），當(dāng)頂點(diǎn)與之間不存在任何途徑時(shí)，令上寫上。(6) 取出中所有奇點(diǎn)，以這些奇點(diǎn)為頂點(diǎn)構(gòu)成一個(gè)賦權(quán)完全圖，其中各邊上權(quán)值等于數(shù)減去相應(yīng)奇點(diǎn)對在中的最短路長（對于任意），這里為一個(gè)

24、足夠大的數(shù)。(7) 應(yīng)用最大權(quán)匹配算法求出中一個(gè)最大權(quán)匹配。(8) 若的權(quán)值，則算法終止，無解；否則，轉(zhuǎn)步驟9.(9) 對于中任何一條匹配邊，根據(jù)圖的路徑矩陣找出中從頂點(diǎn)到的最短路，這些最短路徑經(jīng)過的所有邊即構(gòu)成了中一條關(guān)于的最優(yōu)方案。(10) 把中各邊添加到原圖上去，得一賦權(quán)圖，按照算法找出中一條環(huán)游，即為上關(guān)于的災(zāi)郵問題的最優(yōu)解。讓我們分析一下上述算法的復(fù)雜性，設(shè)網(wǎng)絡(luò)中含個(gè)頂點(diǎn)，條邊：第一步中計(jì)算圖的分支數(shù)的計(jì)算量為；步驟2-4的計(jì)算量為；步驟5-10的總計(jì)算量約為。故上述算法的總計(jì)算量為為多項(xiàng)式算法。3 時(shí)間限制下的中國郵遞員問題 上一章中我們討論了無向圖上的中國郵遞員問題，這一章中，主

25、要來探究有向圖上的中國郵遞員問題（DCPP），而且在當(dāng)前時(shí)間就是金錢的觀念下，考慮時(shí)間約束是必要的。我們將構(gòu)建一個(gè)包含時(shí)間限制的DCPP模型。定義3.1 對于有向圖的每個(gè)頂點(diǎn)都有入度數(shù)等于出度數(shù)，則稱為對稱的。定義3.2 對于集合，的特征函數(shù)為一個(gè)從到的映射：記作。如果有向圖上的中國郵遞員問題（DCPP）有解當(dāng)且僅當(dāng)圖為強(qiáng)連通。換句話說，任何一對頂點(diǎn)間一定有一個(gè)有向路。一旦圖為強(qiáng)連通的，DCPP可以表示如下：因此，基于一個(gè)強(qiáng)連通圖，DCPP的數(shù)學(xué)公式可以寫成UCPP，其中可以用。在解決有向圖上的中國郵遞員問題之前，我們首先要把圖轉(zhuǎn)化為圖，現(xiàn)有的DCPP算法包含兩步，第一，構(gòu)造一個(gè)花費(fèi)最小的圖，

26、就是添加最少的弧使得圖變成圖。這一步可以通過求解最小費(fèi)用流問題來實(shí)現(xiàn)，流過每條弧至少1次，這種方法可以應(yīng)用于城市垃圾收集問題8。第二，找到環(huán)游，M. Dorigo和Optimization在文9中已實(shí)現(xiàn)。3.1 時(shí)間限制下的DCPP模型 前面只提供了網(wǎng)絡(luò)結(jié)構(gòu)但并未顯示怎樣旅行來獲得最短的旅行時(shí)間，為了結(jié)合時(shí)間限制，我們需要跟蹤這樣的旅游和制定它顯式地進(jìn)入DCPP模型，因此我們需要重新構(gòu)造一個(gè)DCPP模型，然后考慮時(shí)間限制。假設(shè)有向圖有個(gè)頂點(diǎn)， 為點(diǎn)集，為弧集，郵遞員從點(diǎn)1出發(fā)送完信后回到點(diǎn)1。設(shè)為郵遞員第次重復(fù)的訪問點(diǎn)的時(shí)間，那么意味著郵遞員的在點(diǎn)1處出發(fā)，當(dāng)足夠大時(shí)，為旅行結(jié)束時(shí)間。為點(diǎn)到點(diǎn)

27、的距離，為郵遞員是否第次重復(fù)的從點(diǎn)旅行到點(diǎn)的特征函數(shù)：因此，必須滿足。根據(jù)以上的符號記法，目標(biāo)函數(shù)可以寫成： (1)這意味著郵遞員完成旅行的總時(shí)間必須最小化，因此在第次重復(fù)時(shí)，郵遞員從點(diǎn)到另一個(gè)點(diǎn)必須滿足下列不等式： (2)第次重復(fù)的從任何一點(diǎn)到點(diǎn)1的旅行時(shí)間必須滿足： (3)對于除點(diǎn)1以外的點(diǎn)，下面的不等式保證了時(shí)間的連續(xù)性： (4)此外，仍有兩個(gè)條件需要滿足：第一，所有的頂點(diǎn)必須是對稱的，如（5）；第二，每條弧必須至少通過一次。 (5) (6)因此，DCPP的數(shù)學(xué)模型為： 模型上述模型為一個(gè)包含個(gè)約束條件和個(gè)變量的混合線性規(guī)劃問題（MLP），為給定的用于指示穿越網(wǎng)絡(luò)圖中弧之間的最大時(shí)間。實(shí)

28、際上我們之前并不知道為何值，因此就必須在計(jì)算前給定一個(gè)足夠大的數(shù)。接下來，我們將構(gòu)造一個(gè)模型來發(fā)現(xiàn)的最佳值。 3.2 值的分析從前面的分析可知，在解決模型之前，我們必須構(gòu)造一個(gè)足夠大的數(shù)，然而，如果的值太大，會出現(xiàn)多余的迭代。因此，過大的值不影響模型的結(jié)果單會造成額外的計(jì)算時(shí)間。設(shè)變量為添加的從點(diǎn)到點(diǎn)的偽?。ㄌ砑拥幕。瑢τ诿總€(gè)點(diǎn)入度數(shù)必須等于出度數(shù)。因此，每個(gè)點(diǎn)必須滿足： （7）由于添加的偽弧的數(shù)量應(yīng)該最小化，我們有一個(gè)目標(biāo)函數(shù)： （8）因此我們可以通過下面的模型和條件找到最小的值：模型3.3 DCPP模型的一個(gè)例子假設(shè)網(wǎng)絡(luò)圖有5個(gè)點(diǎn)和7條弧，每條弧通過的時(shí)間已標(biāo)，如圖3.1。圖3.1 在模

29、型中共有個(gè)限制條件和個(gè)變量，為了確定最經(jīng)濟(jì)的，我們應(yīng)用模型來獲得解如，因此數(shù)等于，從圖3.1中可得，得到的答案為：總共的旅行時(shí)間為45，具體的路線如圖3.2。圖3.23.4 改進(jìn)的時(shí)間限制下的DCPP模型 基于模型，我們假定：第一，如果一個(gè)郵遞員必須過某條弧至少2次，那么郵遞員會在他第一次過此弧時(shí)將信送到，其余的只是通過此弧。因此，對于對于包含時(shí)間限制的DCPP，郵遞員必須在時(shí)間之間送信。因此，我們有時(shí)間限制，第二，郵遞員開始送信時(shí)就沒有空閑時(shí)間。則時(shí)間限制下的DCPP模型為：模型：模型仍然是一個(gè)混合的線性規(guī)劃問題，共有個(gè)限制條件和個(gè)變量，其中可以從模型中獲得。3.5解的存在性在模型中，如果上界足夠大下界足夠小，那么模型就和模型一樣的了，模型的解存在。然而當(dāng)時(shí)間限制是有效的，模