數(shù)學(xué)建模——郵件送遞問題

1、郵件送遞問題【摘要】本文的主要思想，是將郵件送遞問題轉(zhuǎn)化為圖論中的旅行商問題，求最佳哈密爾頓回路，在此基礎(chǔ)上，結(jié)合重量、體積、時(shí)間這三個(gè)約束條件，對送遞路線進(jìn)行調(diào)整，找到最佳的送遞路線。問題一，用Floyd算法計(jì)算51個(gè)地點(diǎn)任意兩點(diǎn)之間的最短距離，然后采用二邊逐次修正法求21個(gè)送達(dá)地點(diǎn)構(gòu)成的最佳H圈。為減小二次逐邊修正法對初始圈的敏感，每次隨機(jī)搜索1000個(gè)初始圈。為提高計(jì)算速度；我們采用在MATLAB環(huán)境中，用矩陣翻轉(zhuǎn)的方法來實(shí)現(xiàn)二邊逐次修正的過程。最終我們求得序號分別為3和150的兩條總路程最短的送遞路徑。兩條路徑的總長度均為54.708km，總時(shí)間3.149小時(shí)。問題二，在第一問的基礎(chǔ)上

2、，我們對1000條近似最短路徑進(jìn)行時(shí)間檢驗(yàn)，計(jì)算每條路徑上每一點(diǎn)郵件送達(dá)的時(shí)間是否早于要求的時(shí)間，從而判斷該路徑是否符合時(shí)間要求。我們從1000條近似最短路徑中篩選出48條符合時(shí)間要求的路徑，再從中找出總長度最短的路徑，得到序號為150的路徑為本問題的最佳方案。問題三，本問題相比第一問，增加了分組的問題。由于郵件重量和體積的約束，100個(gè)郵件需分批次送遞，我們制定了衡量分組優(yōu)劣的標(biāo)準(zhǔn)均衡度，以此為準(zhǔn)則，我們對Prim算法求出的50點(diǎn)最小生成樹做適當(dāng)調(diào)整，并結(jié)合重量、體積兩個(gè)約束條件，確定分組。完成分組后，求解每一組地點(diǎn)的送遞路徑，與第一問相同。最終我們得到均衡度為0.026的分組方案及各組的送

3、遞路徑，并求出送完所有郵件的最短時(shí)間為6.728h。問題四針對第一小問，在第一問基礎(chǔ)上增加檢驗(yàn)郵遞員到達(dá)每一地點(diǎn)的重量和體積，我們求出分2組的送遞路徑。針對第二小問，在第一小問基礎(chǔ)上增加檢驗(yàn)郵遞員到達(dá)每一地點(diǎn)的實(shí)際時(shí)間，提出以準(zhǔn)點(diǎn)率為標(biāo)準(zhǔn)衡量路徑優(yōu)劣，求出準(zhǔn)點(diǎn)率為76.2%的最佳路徑。針對第三小問，由于郵件增多帶來的重量、體積的上升，分組數(shù)目相應(yīng)增加，最終我們求出分6組，準(zhǔn)點(diǎn)率為72.0%的送遞路徑。 【關(guān)鍵詞】 最優(yōu)圈，二邊逐次修正法，矩陣翻轉(zhuǎn)，最小生成樹，均衡度一、問題的提出現(xiàn)有一郵局在圖1中的O點(diǎn)，一郵遞員需將郵件送至城市內(nèi)多處。該地形圖的示意圖，各點(diǎn)連通信息，各件貨物的相關(guān)信息，50個(gè)

4、位置點(diǎn)的坐標(biāo)已在附錄中給出。郵遞員要將100件郵件送到50個(gè)地點(diǎn)。假設(shè)郵遞員的最大載重是50公斤，所帶貨物的最大體積為1立方米，郵遞員的路上平均速度為30公里/小時(shí)，每件貨物交接花費(fèi)2.5分鐘。在不同的情況和要求下，郵遞員需要以最快的速度及時(shí)將郵件送達(dá)指定地點(diǎn)。我們的任務(wù)是，在以下幾個(gè)問題的特定要求下，給出具體的郵遞員送郵件的具體路線，使其消耗的時(shí)間最少。問題一： 將130號郵件送到指定地點(diǎn)并返回。我們將設(shè)計(jì)出最快完成路線與方式，給出結(jié)果，標(biāo)出送貨線路。問題二：該郵遞員從早上8點(diǎn)上班開始送郵件，要將130號郵件的送達(dá)時(shí)間不能超過指定時(shí)間。我們將設(shè)計(jì)出最快完成路線與方式并標(biāo)出送貨線路。問題三：

5、不考慮所有郵件送達(dá)時(shí)間限制(包括前30件貨物)，現(xiàn)在要將100件郵件全部送到指定地點(diǎn)并返回。我們將設(shè)計(jì)出最快完成路線與方式，標(biāo)出送貨線路，給出送完所有郵件的時(shí)間。由于受重量和體積限制，郵遞員可中途返回取貨?？刹豢紤]中午休息時(shí)間。問題四：如果郵遞員送郵件的同時(shí)，還負(fù)責(zé)將各地需要寄送的郵件帶回郵局，各地點(diǎn)需要帶回郵局寄送的郵件的信息如表3，按照此條件重新解答以上三個(gè)問題。二、符號說明：賦權(quán)圖；：賦權(quán)圖的權(quán)矩陣；D ： 兩點(diǎn)最短路徑距離矩陣；: 兩點(diǎn)最短路徑的走法參考舉證； ： 某條路徑上第i個(gè)送達(dá)地點(diǎn)，收到郵件的實(shí)際時(shí)間； ： 某條路徑上第i個(gè)送達(dá)地點(diǎn)，要求的送達(dá)時(shí)間；： 某條路徑上第i-1個(gè)送達(dá)

6、地點(diǎn)，到第i個(gè)送達(dá)地點(diǎn)的距離；： 某條路徑上第i-1個(gè)送達(dá)地點(diǎn)，到第i個(gè)送達(dá)地點(diǎn)的路上花費(fèi)的時(shí)間；v ： 郵遞員在路上的平均速度；： 表示每件貨物的交接時(shí)間。： 表示最短距離矩陣： 表示要求第i個(gè)送達(dá)地點(diǎn)對應(yīng)的地點(diǎn)序號三、模型的假設(shè) 1、假設(shè)送貨員的最大載重是50公斤，所帶貨物的最大體積為1立方米； 2、假設(shè)送貨員的路上平均速度為30公里/小時(shí)，不會出現(xiàn)意外現(xiàn)象； 3、每件貨物交接花費(fèi)2.5分鐘，同一地點(diǎn)有多件貨物也簡單按照每件2.5分鐘交接計(jì)算，不會出現(xiàn)特殊情況而延誤時(shí)間；4、送貨員只沿示意圖連線路徑行走；5、假設(shè)快遞公司地點(diǎn)O為第51個(gè)位置點(diǎn)；6、假設(shè)送貨員回到出發(fā)點(diǎn)O后取貨時(shí)間不計(jì)。四、

7、模型的建立與求解4.1 數(shù)據(jù)的預(yù)處理在給出的50個(gè)點(diǎn)中，我們已經(jīng)知道了各點(diǎn)的坐標(biāo)，通過代入兩點(diǎn)間距離公式，我們可以得到50個(gè)點(diǎn)中可以兩兩直接到達(dá)的點(diǎn)之間的距離，即相鄰的點(diǎn)的距離，如表1所示，詳見附錄。表 1序號位置點(diǎn)1位置點(diǎn)2位置點(diǎn)1坐標(biāo)位置點(diǎn)2坐標(biāo)兩點(diǎn)間距離L113（9185，500）（7270，570）1916.3218（9185，500）（7160，2525）2863.83220（1445，560）（780，8355）7823.3424（1445，560）（3735，670）2292.6538（7270，570）（7160，2525）1958.1634（7270，570）（3735，67

8、0）3536.4742（3735，670）（1445，560）2292.6794942（11575，15160）（13265，14145）1971.4805040（8010，15325）（8345，12300）3043.5815118（11000，8250）（8825，8075）2182825121（11000，8250）（12770，8560）1796.9835126（11000，8250）（10860，9635）1392.14.2 任兩點(diǎn)之間的最短路徑下面我們采用Floyd法來計(jì)算50個(gè)點(diǎn)中任意兩點(diǎn)之間的距離。設(shè)， 是一個(gè)有51個(gè)頂點(diǎn)和83條邊的圖。若將圖G的每一條邊e都對應(yīng)一個(gè)實(shí)數(shù)， 則

9、稱為該邊的權(quán)，并稱圖G為賦權(quán)圖(網(wǎng)絡(luò))，記為。設(shè)為賦權(quán)圖的權(quán)矩陣，表示從到點(diǎn)的距離，表示從到點(diǎn)的最短路中前一個(gè)點(diǎn)的編號。算法步驟： 步驟一：賦初值。對所有， 轉(zhuǎn)向步驟二。 步驟二： 更新。 對所有， 若，則令 , 轉(zhuǎn)向步驟三; 步驟三：終止判斷。 若k = n終止；否則令k = k + 1, 轉(zhuǎn)向步驟二。 于是，最短路線可由得到。算法流程圖：圖 1由表1各地點(diǎn)的距離可構(gòu)造示意圖的帶權(quán)鄰接矩陣。由已知可知共有83條邊，表示相鄰點(diǎn)到的距離，不相鄰的點(diǎn)之間的距離為無窮大。用Matlab編程得D(51)=（Dij）51×51，其中D(i,j)即為兩點(diǎn)最短路徑距離。表 2dij12345678

10、910111213145110774519165453899812941968286459734028603846216077865410068 2774505829229312539040971477871371811773109629544110011640016296 319165829035367082321138851958788959445133371551721057110467 4545322933536035466747742154951142694808669725187081410714004 589981253708235460102931096790401497113

11、026112289810112671765316563 612949040321167471029303263415872675322733359157372994911363 71968971438857421109673263048324005205980066589804666868100 82864778719585495904041584832088376891317417573214115188509 9597313718788911426149717267400588370194612011105941096926817775 10402811773594494801302653

12、222059689119460100668648902346278092 1160381096251338669112287333800631741201110066014181670101256965 124621954437157251981059156589175710594864814180145799126752 13607711001517287081126773728046321410969902316701457084565295 5110068 16296 10467 14004 16563 11363 8100 8509 7775 8092 6965 6752 5295 5

13、094 0同時(shí)，根據(jù)得到的R矩陣（見附錄）求出插入點(diǎn)矩陣以便得到兩點(diǎn)間的最短路徑。例如，我們通過查詢R矩陣來找到121的最短路徑。首先，找到路徑的第一個(gè)點(diǎn)，即為點(diǎn)7；再次尋找721最短路徑的第一個(gè)點(diǎn)；再次找到1021最短路徑的第一個(gè)點(diǎn)；最后找到5121最短路徑的第一個(gè)點(diǎn)。于是121的最短路徑為：。同理，可得的最短路徑為：；的最短路徑為：。圖 24.3 過固定幾個(gè)點(diǎn)的最短回路（問題一）對于問題一，需要送達(dá)的1-30號郵件的坐標(biāo)共有21個(gè)，這21個(gè)點(diǎn)組成的集合為V，V=（13,14,16,17,18,21,23,24,26,27,31,32,34,36,38,39,40,42,43,45,49），

14、我們的任務(wù)是設(shè)計(jì)一條路線，從O（51）點(diǎn)出發(fā)，經(jīng)過以上21點(diǎn)，并返回至O點(diǎn)的最短路徑。4.3.1模型的建立設(shè)G=(V,E)是連通無向圖，經(jīng)過G的每個(gè)頂點(diǎn)正好一次的圈，稱為G的一條哈密爾頓圈，簡稱H圈；含H圈的圖成為哈密爾頓圖或H圖。那么我們要做的是找到最小哈密頓回路。在加權(quán)圖G=(V，E，F(xiàn))中，權(quán)最小的哈密爾頓圈稱為最佳H圈；判定一個(gè)加權(quán)圖G=(V，E)是否存在哈密爾頓圈是一個(gè)NP問題，而它的完備加權(quán)圖（中的每條邊（x,y）的權(quán)等于頂點(diǎn)x與y在圖G中最短路徑的權(quán)）中一定存在哈密爾頓圈，所以在完備圖G'=(V,E')中尋找最佳H圈。該過程可采用二邊逐次修正法并利用矩陣翻轉(zhuǎn)實(shí)現(xiàn)。

15、二邊逐次修正法的算法過程： 1任取初始H圈: 2. 對所有的，若,則在C0中刪去邊和而加入邊和，形成新的H圈C，即3. 對C重復(fù)步驟（），直到條件不滿足為止，最終得到的C即為所求。矩陣翻轉(zhuǎn) 在一個(gè)矩陣中，對它的第i行（列）到第j行（列）翻轉(zhuǎn)是以第i行（列）和j行（列的）中心位置為轉(zhuǎn)軸，旋轉(zhuǎn)180度，這樣：第i行（列）和第j行（列）的位置互換，第i+1行（列）和第j-1行（列）位置互換，4.3.2 模型的應(yīng)用：根據(jù)51個(gè)點(diǎn)間的最短距離矩陣D，可以得到起始點(diǎn)O（51）和V中21點(diǎn)，共22點(diǎn)的完備加權(quán)圖，這22個(gè)點(diǎn)即為：51，13,14,16,17,18,21,23,24,26,27,31,32,3

16、4,36,38,39,40,42,43,45,49的。將完備加權(quán)圖用距離矩陣表示，假設(shè)這初始圈為。使所選的初始圈為矩陣的主對角線的上方元素對應(yīng)的頂點(diǎn)，于是權(quán)鄰接矩陣為初始圈所走距離為主對角線的上方元素之和，其經(jīng)過的權(quán)為=11958。如果所選初始H圈不是c0，可通過交換距離矩陣H的行和列，使矩陣的主對角線的上方元素對應(yīng)的頂點(diǎn)為所選的初始H圈。為了能看到翻轉(zhuǎn)效果和更直觀確定優(yōu)化后H圈所走的路線，在第一行和最后一行給距離矩陣加上了一個(gè)點(diǎn)的排列順序的框，與此同時(shí)為了使矩陣仍然保持為方陣，在第一列和最后一列加上2個(gè)0列(或者在距離矩陣第一行、列和最后一行、列同時(shí)加上一個(gè)點(diǎn)的排列順序的框)： 調(diào)用求最佳H

17、圈的函數(shù)，把得出的結(jié)果矩陣再次調(diào)用這個(gè)函數(shù)，即為近似最佳H圈。此過程即是模型中的二邊逐次修正法的算法過程的第2和第3步，以及矩陣翻轉(zhuǎn)的過程。得到最后的距離矩陣： 的第一行的第二列到倒數(shù)第二列即為最佳H圈的路徑。起點(diǎn)的確定：，對應(yīng)于集合V中的，即出發(fā)點(diǎn)O（51）；第一步點(diǎn)的確定：，對應(yīng)于集合V中的，即點(diǎn)21；第二步點(diǎn)的確定：，對應(yīng)于集合V中的，即點(diǎn)14；第三步點(diǎn)的確定：，對應(yīng)于集合V中的，即點(diǎn)26；如此下去，根據(jù)最優(yōu)H矩陣找到對應(yīng)點(diǎn)第二十二步點(diǎn)的確定：，對應(yīng)于集合V中的，即點(diǎn)27；最后回到O點(diǎn)。則此近似最佳H圈的總權(quán)為=56980，郵遞員30公里每小時(shí)，那么，郵遞員花在路途中的時(shí)間為：；共交接了

18、30分郵件，每件郵件的交接時(shí)間為2.5分鐘，則郵遞員用于交接郵件的時(shí)間為：；總時(shí)間即為3.149小時(shí)。由于用矩陣翻轉(zhuǎn)方法來實(shí)現(xiàn)二邊逐次修正法的結(jié)果與初始圈有關(guān)，故為了的到得到較優(yōu)的計(jì)算結(jié)果，我們用MATLAB編程時(shí)，隨機(jī)搜索出1000個(gè)初始H圈，每個(gè)初始H圈都可以通過上面類似的步驟找到所對應(yīng)的近似最佳H圈。在這1000個(gè)近似最佳H圈中，我們再找出權(quán)最小的一個(gè)，即郵遞員走的路程最短。1000近似最佳H圈的路徑和所走距離見附錄，下面我們給出了這1000條近似最佳H圈中權(quán)重最小的5條：表 3路線序號消耗總時(shí)間S所 走 路 線133.0736547085126211714162332383643424

19、9454034312739241318511503.07365470851181324312739344045424943363832231614172126511323.10685570551211714162332383643494245403439273124131826518273.109155772512639273124131834404542494336383223161417215143.11645599151131831242739344045494243363832231614172126511003.118056041512621171416233238434249454

20、0343127363924131851可見，路線13和路線150是路程相等，方向相反的兩條路，它們的權(quán)值相同。其具體走法如圖：圖 34.4 問題二在第一問中，我們已經(jīng)得到了1000條近似最佳路徑，這一千條路徑，總長度接近最短。但是第一問中并沒有考慮每份郵件送達(dá)目的地的時(shí)間要求，在本問題中，我們試圖從以上1000條近似最佳路徑中，搜尋出符合時(shí)間要求，并且總長度最短的路徑。因此，我們需考慮的兩個(gè)約束條件分別是：1.時(shí)間要求；2.總長度最短4.4.1 判斷路徑是否符合時(shí)間要求判斷一條路徑是否符合時(shí)間要求，需要判斷該路徑上每一站郵件送到的時(shí)間均符合要求的時(shí)間，即 表示某一路徑上，第i個(gè)送達(dá)地點(diǎn)收到郵件

21、的時(shí)間，表示第i個(gè)送達(dá)地點(diǎn)要求不超過的時(shí)間，i表示某一路徑上第i個(gè)送達(dá)地點(diǎn)，而非原來的送達(dá)地點(diǎn)序號。例如，某一送遞路徑為O5121141716233236273924313440454249433813182651O，序號21的送達(dá)地點(diǎn)i=1，序號14的送達(dá)地點(diǎn)i=2，以此類推，序號26的送達(dá)地點(diǎn)i=21。所有的值題目已經(jīng)給出，接下來我們需要計(jì)算值，第i個(gè)送達(dá)地點(diǎn)的收件時(shí)間，由上一個(gè)點(diǎn)（即第i-1個(gè)送達(dá)地點(diǎn)）的收件時(shí)間、路上花費(fèi)的時(shí)間、貨物交接時(shí)間三部分組成，即指郵件送至第i個(gè)送達(dá)地點(diǎn)時(shí)的時(shí)間點(diǎn)；指郵件送達(dá)第i-1個(gè)地點(diǎn)（即前一個(gè)地點(diǎn)）時(shí)的時(shí)間點(diǎn)；值表示從第i-1個(gè)地點(diǎn)到第i個(gè)地點(diǎn)，在路上花費(fèi)

22、的時(shí)間；表示每件貨物交接的時(shí)間。由題目知，郵遞員8點(diǎn)從郵局出發(fā)，因此=8.00。為方便運(yùn)算，下文在涉及時(shí)間時(shí)，均用小數(shù)表示，例如8時(shí)表示為8.00，9：30表示為9.50。值由第i-1個(gè)送達(dá)地點(diǎn)和第i個(gè)送達(dá)之間的距離、郵遞員路上的平均速度決定，即值表示從第i-1個(gè)地點(diǎn)到第i個(gè)地點(diǎn)，在路上花費(fèi)的時(shí)間；表示第i-1個(gè)送達(dá)地點(diǎn)與第i個(gè)送達(dá)地點(diǎn)之間的最短距離；郵遞員路上的平均速度題目已經(jīng)給出。第i-1個(gè)送達(dá)地點(diǎn)與第i個(gè)送達(dá)地點(diǎn)之間的最短距離，可從最短距離矩陣得到，即表示第i個(gè)送達(dá)地點(diǎn)，其對應(yīng)的送達(dá)地點(diǎn)序號，以路線O/5121141716233236273924313440454249433813182

23、651/O為例，若i=3，i-1=2，。分別將對應(yīng)的送達(dá)地點(diǎn)序號、作為最短距離矩陣的行、列，找到對應(yīng)的兩地間最短距離。例如，綜合以上所述，我們可以得出，某一路徑上，每一個(gè)送達(dá)地點(diǎn)收到郵件時(shí)間的計(jì)算公式：需要說明的是，我們認(rèn)為，只有當(dāng)郵件交付客戶手中并完成交接手續(xù)之后，郵件才是真正意義上的送達(dá)，因此，在計(jì)算第一個(gè)送達(dá)地點(diǎn)的收件時(shí)間時(shí)，仍然需要加上交接時(shí)間項(xiàng)。通過i=1:n的迭代，可以計(jì)算出某一路徑上，所有的送達(dá)地點(diǎn)收到郵件的時(shí)間，當(dāng)路徑上所有的送達(dá)地點(diǎn)收到郵件的時(shí)間均滿足時(shí)，說明該路徑符合時(shí)間要求。按此方法可批量檢驗(yàn)路徑是否符合時(shí)間要求。4.4.2 計(jì)算實(shí)現(xiàn)我們在MATLAB7.6環(huán)境中，將上述

24、的檢驗(yàn)過程實(shí)現(xiàn)，具體的算法示意圖如下：第一步：初始化，載入待檢驗(yàn)的路徑矩陣,該矩陣的的每一列表示一條路徑，送達(dá)地點(diǎn)為21個(gè)，起點(diǎn)和終點(diǎn)均為O/51點(diǎn)，因此，矩陣行數(shù)為23，共有1000條待檢驗(yàn)的路徑，因此矩陣列數(shù)為1000。第二步：賦初值，令k=1,i=1執(zhí)行k=1:1000,i=1:23的循環(huán)。小循環(huán)檢驗(yàn)一條路徑內(nèi)23個(gè)送達(dá)地點(diǎn)時(shí)候據(jù)滿足時(shí)間要求，大循環(huán)用于檢驗(yàn)1000條路徑中有多少條路徑符合時(shí)間要求。第三步：輸出結(jié)果，Total值代表符合時(shí)間要求的路徑數(shù)目，矩陣SL1×total 表示符合時(shí)間要求的路徑序號。4.4.3 計(jì)算結(jié)果程序執(zhí)行結(jié)果，從1000條路徑中得到48條符合時(shí)間要

25、求的路徑，表1為部分符合路線舉例。表 4路線S所 走 路 線455990.6151131831242739344045494243363832231614172126512755771.5451263927312413183440454249433638322316141721517456689.95511813243134403927364542494338322316141721265111056979.97511813243134404542494327393638322316141721265114556075.8451181324312739344049424345363832231

26、6141721265115054707.645118132431273934404542494336383223161417212651表 5路徑13路徑150路徑132路徑132反路徑送達(dá)點(diǎn)到達(dá)時(shí)刻要求時(shí)刻送達(dá)點(diǎn)到達(dá)時(shí)刻要求時(shí)刻送達(dá)點(diǎn)到達(dá)時(shí)刻要求時(shí)刻送達(dá)點(diǎn)到達(dá)時(shí)刻要求時(shí)刻tiTitiTitiTitiTi518518518518268.09 12:00188.11 9:00218.10 12:00268.09 12:00218.20 12:00138.26 9:00178.20 12:00188.25 9:00178.31 12:00248.49 9:00148.32 12:00138.39

27、9:00148.42 12:00318.59 9:30168.45 12:00248.63 9:00168.55 12:00278.67 12:00238.56 12:00318.73 9:30238.66 12:00398.77 12:00328.64 12:00278.80 12:00328.75 12:00348.99 9:30388.77 10:15398.91 12:00388.87 10:15409.08 9:30368.86 12:00349.12 9:30368.96 12:00459.23 9:30439.04 10:15409.22 9:30439.14 10:15429.

28、35 10:15499.18 10:15459.36 9:30429.22 10:15499.46 10:15429.29 10:15429.48 10:15499.32 10:15439.60 10:15459.41 9:30499.59 10:15459.51 9:30369.78 12:00409.56 9:30439.73 10:15409.66 9:30389.87 10:15349.65 9:30369.91 12:00349.75 9:30329.99 12:00399.87 12:003810.00 10:15319.87 12:002310.08 12:00279.97 12

29、:003210.13 12:00279.95 12:001610.19 12:003110.05 9:302310.21 12:003910.05 9:301410.32 12:002410.15 9:001610.33 12:002410.25 9:001710.43 12:001310.38 9:001410.45 12:001310.48 9:002110.54 12:001810.52 9:001710.57 12:001810.63 9:002610.65 12:002610.69 12:002110.67 12:005110.74 5110.74 5110.77 5110.73 在

30、表5 中，路徑13、路徑132中有部分送達(dá)地點(diǎn)（以斜體加粗表示）的收件時(shí)間晚于要求時(shí)間，因此這類路徑不符合時(shí)間要求；而在路徑150和路徑132的反路徑中，所有送達(dá)地點(diǎn)的收件時(shí)間均早于要求的時(shí)間，因此這類路徑符合時(shí)間要求。符合時(shí)間要求的路徑共有48條，我們再從中找出總長度最小的路徑，為路徑150，得到符合時(shí)間要求的最快完成路徑。表 6路徑序號消耗總時(shí)間S所 走 路 線1503.0736547085118132431273934404542494336383223161417212651在第一問的求解中，我們得到總長度最短的兩條路徑，路徑13和路徑150，這兩條路徑所遍歷點(diǎn)的順序恰好相反，總長度相

31、等。在第一問中，兩條路徑均滿足要求，但是在第二問中，路徑13不符合時(shí)間要求，路徑150滿足。因此，路徑150為本問題的理想方案。4.5 問題三對于單環(huán)路徑的最短路徑已經(jīng)在問題一中解決，我們在此問中要解決的問題是對圖中50個(gè)點(diǎn)的分組情況。一旦分組問題解決，每一組的路徑可以根據(jù)問題一的模型求解最優(yōu)H圈，進(jìn)而解決。由于郵遞員的最大載重是50公斤，所帶貨物的最大體積為1立方米，因此分組要滿足這兩個(gè)條件。經(jīng)過數(shù)據(jù)統(tǒng)計(jì)，郵件的總重量為148公斤，總體積為2.8立方米?？梢娻]遞員至少分3次運(yùn)送郵件。分組的形成:我們考慮將所有郵件分為組。此問題是多個(gè)售貨員的最佳旅行售貨員問題，即在加權(quán)圖G中求定點(diǎn)集的劃分，將

32、G分成k個(gè)子圈，使得：（1） 定點(diǎn)（2）（3） ，其中為的導(dǎo)出子圖中的最佳郵遞員回路，為的權(quán)，。其中為該分組的實(shí)際均衡度，為最大容許均衡度。越小說明分組的均衡度越好。（4） 為所有分組中的最小值圖中的節(jié)點(diǎn)數(shù)較多，有51個(gè)，我們只能去尋求一種較為合理的劃分準(zhǔn)則，對節(jié)點(diǎn)進(jìn)行粗步劃分后，利用問題一中的模型求出每個(gè)劃分最佳H圈，再根據(jù)郵遞員的實(shí)際情況進(jìn)一步進(jìn)行調(diào)整。我們首先用prim法生成最小生成樹，觀察干支和分支的情況：圖 4從起始點(diǎn)51出發(fā)，共有兩條干支，分成兩組顯然超過了郵遞員的每次的送郵件限度。最小生成樹的總權(quán)值可以通過將各支的權(quán)值相加，得到權(quán)值為91287。由圖可見，點(diǎn)17和點(diǎn)31為兩條干支

33、上的明顯分支點(diǎn)，且各分支上的點(diǎn)較多。各分叉支的最遠(yuǎn)點(diǎn)主要有點(diǎn)5，點(diǎn)13，點(diǎn)15，點(diǎn)16，點(diǎn)33，點(diǎn)48，點(diǎn)39，點(diǎn)50，點(diǎn)45。若將所有點(diǎn)分成三組，盡量是值小，均衡度就越高。首先，我們將最遠(yuǎn)的幾個(gè)叉點(diǎn)分為三組，將距離較近的點(diǎn)分在一起。為方便計(jì)算，我們將同一地點(diǎn)需要送達(dá)的幾封郵件看為同一封郵件，即把它們合并起來。在這個(gè)假設(shè)條件下我們來計(jì)算各組的總質(zhì)量和總體積。當(dāng)最遠(yuǎn)叉點(diǎn)組合為，時(shí)表 7分法1地點(diǎn)序號路徑走法總時(shí)間t總質(zhì)量M總體積Va組1 2 3 4 5 6 78 9 10 11 1213 14 17 18 215121171491071642538121113185145237.532.2236

34、.230.7579b組15 19 20 22 24 2528 29 30 33 37 4041 44 46 4851403741444846332830152220292519245145616.552.1943.280.7828c組16 23 26 27 31 3234 35 36 38 39 4243 45 47 49 505126392731344750494243453638353216235148159.292.3168.491.2593此法雖然=已經(jīng)很小，說明該分法的平衡度非常好。郵遞員走的總路程為139012m，總花時(shí)6.72h。但是c組郵遞員所送的郵件M=69.49>50

35、,V=1.2593>1，超過了郵遞員的送件能力。調(diào)整最遠(yuǎn)叉點(diǎn)組合為，并調(diào)整a，b，c組的組成地點(diǎn)序號。表 8分法2地點(diǎn)序號路徑走法總時(shí)間t總質(zhì)量M總體積Va組1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 21 2351211723161491071632548121113185149521.642.4447.730.9575b組15 19 20 22 24 25 27 28 29 30 33 37 39 40 41 44 46 48512739241925292022153028334648444137405151311.92.4652.030.95

36、5c組26 31 32 34 35 36 38 42 43 45 47 49 5051263134474550494243383235365138205.131.8248.240.8875郵遞員走的總路程為139037m，總花時(shí)間為6.728h。=。此法雖然b組總質(zhì)量超過了最大質(zhì)量的4.06%，但相對于分法1，已經(jīng)較符合要求。4.6 問題四4.6.1 有寄回郵件情況下問題一的解答對于1-30號郵件，郵遞員除了送件以外，還要將各地需要寄送的郵件帶回郵局。我們首先對1-30號郵件的送往點(diǎn)集合V中地點(diǎn)需要帶回的郵件進(jìn)行統(tǒng)計(jì)，V=13,14,16,17,18,21,23,24,26,27,31,32,

37、34,36,38,39,40,42,43,45,49表 9郵件號地點(diǎn)V送件質(zhì)量送件體積回件質(zhì)量回件體積1132.50.0316006141.720.015.280.4330161.20.04292.70.07827171.380.01090.150.042180.50.03544.420.2865212.150.0305008,29234.310.09131.620.01920242.930.0421.80.034,23263.130.0560.60.0219,22274.70.0463003,21311.980.03482.20.259,17,28321.470.09130.50.15243

38、42.80.01032.50.0718361.790.01840.450.0610381.330.02191.520.40613392.560.05950025401.140.01553.270.3515422.850.0191.080.04912,16432.650.1010.80.0211,14,26454.060.0970.450.1227491.350.014400總計(jì)48.50.8829.342.3782在第一問中，我們已經(jīng)求得這21個(gè)點(diǎn)與起點(diǎn)構(gòu)成的近似最佳H圈為：5126211714162332383643424945403431273924131851或：511813243127

39、3934404542494336383223161417212651 現(xiàn)在在需要帶回待發(fā)郵件的要求下，我們對上面兩條路徑進(jìn)行檢驗(yàn)。過程5126，郵遞員所載的郵件質(zhì)量為48.5公斤，體積為0.88立方米； 過程2621，郵遞員所載的郵件質(zhì)量為45.97公斤，體積為0.844立方米；過程2117，郵遞員所載的郵件質(zhì)量為43.82公斤，體積為0.8135立方米； 過程1714，郵遞員所載的郵件質(zhì)量為42.4509公斤，體積為0.8488立方米； 過程1416，郵遞員所載的郵件質(zhì)量為46.0109公斤，體積為1.2688立方米；體積過大。對于另外一條近似最佳H圈，過程5118，郵遞員所載的郵件質(zhì)量為4

40、8.5公斤，體積為0.88立方米；18點(diǎn)后郵遞員載重為52.42，超過最大載重量。因此我們對這段路的進(jìn)行調(diào)整，即稍微多走點(diǎn)路，將另郵件送到另一點(diǎn)減負(fù)，路線可以調(diào)整為 5113過程中郵遞員于18點(diǎn)處將郵件送出，其所帶的郵件質(zhì)量變?yōu)?8公斤，體積變?yōu)?.8495立方米；達(dá)到點(diǎn)13后郵遞員又將郵件送出，且此點(diǎn)無須帶回的郵件，于是郵遞員在1318過程中郵件質(zhì)量變?yōu)?5.5公斤，體積為0.5335立方米。回到點(diǎn)18將須帶回的郵件帶上，于是郵遞員在1831途中的郵件質(zhì)量為49.92公斤，體積為0.8195立方米。312739，郵遞員第一次到點(diǎn)27時(shí)也同樣從先送郵件，回來過程中再取，這樣郵件體積不會超過最大

41、體積限制。由于須帶回的郵件總體積為2.3782，若分三組則太浪費(fèi)時(shí)間。我們考慮將郵件分為兩組，雖然體積超過了限制，但超得不多，約為0.37/2=0.19立方米左右,但是可以大大的減少時(shí)間。我們根據(jù)第一問的路線和最小生成樹的分支情況，將這21點(diǎn)分為2組；第一組分支的得出已如上陳述。第一組：51131831344024273936212651，此過程中郵件質(zhì)量沒有超過最大負(fù)重，所載最大體積為1.066立方米，僅僅超過了最大體積的6.6%。第二組中郵遞員須送郵件號為6，7，8，9，11，12，14，16，17， 25， 26，28，27，29，30的郵件，出發(fā)時(shí)郵遞員負(fù)重23.46公斤，須帶回的郵件

42、質(zhì)量為17.37公斤，因此路途中郵遞員絕對不會出現(xiàn)所載郵件超重的現(xiàn)象。那么只要考慮郵件體積的情況，出發(fā)時(shí)郵件體積為0.9013立方米，須帶回郵件體積為1.3122，超過標(biāo)準(zhǔn)0.3122立方米，但比起再次分組送件，大大減少了所花的時(shí)間。將這10個(gè)點(diǎn)與原點(diǎn)利用第一問中的近似最優(yōu)H圈解法，可以給出路徑為：51261714162332384342494551。這兩組路線的走法如圖5：圖 5 4.6.2 有寄回郵件情況下問題二的解答問題二中加入了時(shí)間的要求，郵件須盡量按時(shí)送到且按時(shí)帶回。個(gè)別點(diǎn)既有須送到的郵件時(shí)間的要求又有須帶回的郵件的要求，我們將這樣的點(diǎn)取其最早的時(shí)間要求點(diǎn)。例如點(diǎn)16須送到的郵件的最

43、晚時(shí)間要求為12：00，須帶回的郵件的最早時(shí)間為13：00。集合V的21個(gè)點(diǎn)中既有須送到的郵件時(shí)間的要求又有須帶回的郵件的點(diǎn)有15個(gè)，記作，圖中即用圓圈出。圖 6在用二次逐邊修正法確定了兩組的近似最佳H圈后，我們可以計(jì)算到達(dá)各點(diǎn)的時(shí)刻。郵遞員無論先走第一組路線，還是先走第二組路線，走的總路徑距離相同，花的總時(shí)間按也都相同，為3.12小時(shí)。但是由于個(gè)地點(diǎn)對郵件寄到的時(shí)間按要求不同，先走第一組和先走第二組對客戶的滿足度不同。在下表中分別給出了兩種走法和達(dá)到各點(diǎn)的時(shí)間情況。表 10走法1到達(dá)時(shí)間要求時(shí)間超時(shí)時(shí)間走法2到達(dá)時(shí)間要求時(shí)間超時(shí)時(shí)間第二組178.16 12準(zhǔn)時(shí)第一組138.22 9準(zhǔn)時(shí)148

44、.28 12準(zhǔn)時(shí)188.36 9準(zhǔn)時(shí)168.41 12準(zhǔn)時(shí)318.48 9.5準(zhǔn)時(shí)238.52 12準(zhǔn)時(shí)348.59 9.5準(zhǔn)時(shí)328.60 12準(zhǔn)時(shí)408.69 9.5準(zhǔn)時(shí)388.73 10.25準(zhǔn)時(shí)248.92 9準(zhǔn)時(shí)438.86 10.25準(zhǔn)時(shí)279.06 12準(zhǔn)時(shí)428.93 10.25準(zhǔn)時(shí)399.16 12準(zhǔn)時(shí)499.04 10.25準(zhǔn)時(shí)369.34 12準(zhǔn)時(shí)459.22 9.5準(zhǔn)時(shí)219.47 12準(zhǔn)時(shí)519.48 /準(zhǔn)時(shí)269.59 12準(zhǔn)時(shí)第一組139.70 90.70 519.63 /準(zhǔn)時(shí)189.85 90.85 第二組179.80 12準(zhǔn)時(shí)319.96 9.50.46 14

45、9.91 12準(zhǔn)時(shí)3410.08 9.50.58 1610.04 12準(zhǔn)時(shí)4010.18 9.50.68 2310.15 12準(zhǔn)時(shí)2410.41 91.41 3210.24 12準(zhǔn)時(shí)2710.54 12準(zhǔn)時(shí)3810.36 10.250.11 3910.65 12準(zhǔn)時(shí)4310.49 10.250.24 3610.82 12準(zhǔn)時(shí)4210.56 10.250.31 2110.96 12準(zhǔn)時(shí)4910.67 10.250.42 2611.07 12準(zhǔn)時(shí)4510.86 9.51.36 5111.12 /5111.12 /先走第二組，再走第一組4.68 先走第一組，再走第二組2.45 對于走法1，21個(gè)點(diǎn)中

46、有6個(gè)點(diǎn)超過了時(shí)間的要求，準(zhǔn)點(diǎn)率為71.4%，總超時(shí)為4.68小時(shí)。對于走法2，21個(gè)點(diǎn)中有5各點(diǎn)超過了時(shí)間的要求，準(zhǔn)點(diǎn)率為76.2%，總超時(shí)為2.45小時(shí)。相對于走法1，走法二更為合理。4.6.3 有寄回郵件情況下問題三的解答對于100號郵件，郵遞員除了送件以外，還要將各地需要寄送的郵件帶回郵局。我們首先對51個(gè)地點(diǎn)需要帶回的郵件進(jìn)行統(tǒng)計(jì)。需要帶回郵局的郵件的總重量為75.52公斤，總體積為6.1192立方米。郵遞員所帶貨物的最大體積為1立方米，但若郵遞員至少分7次送郵件則浪費(fèi)了大量的人力和物力。我們將送件分為6次，體積總超限度量最多為0.1192立方米，平均每次超出的體積僅僅約為0.019立方米，基本可以接受。分組應(yīng)符合問題三中（1）（2）（3）的條件，且郵件送遞過程中郵遞員所帶的郵件量不超過郵遞員的能力限制。類似問題三的分組方法，找到最小生成樹叉支上較遠(yuǎn)的幾個(gè)點(diǎn)，對其