中南大學數模培訓-交通運輸問題

1、運輸問題 摘要本文針對某運輸公司送貨路線的問題進行了深入的研究設計。首先，針對第一問中臨時為客戶10配送貨物的要求，我們用Dijkstra算法對其進行了求解，得出了最短85公里的運輸路徑。但是由于Dijkstra算法遍歷計算的節(jié)點很多，所以效率低，我們又應用更為簡單有效的Floyd算法進行求解，最后得出與之前相同的結果，并確定路線為v2-v3-v8-v9-v10。其次，第二問類似于旅行商問題，目前還沒有求解這樣問題的有效算法，所以我們希望建立一個方法以獲得相當好（但不一定最優(yōu)）的解。我們采用了求最短H-圈改良圈的算法。首先求一個Hamilton圈 ，然后適當修改以得到具有較小權的另一個Hami

2、lton圈?；谶@種算法，應用matlab7.0我們計算出最短行駛路線距離為230公里，路徑為v1-v7 -v5 -v2 -v3 -v6 -v4- v8 - v9 - v10-v1，并且路線并不唯一，權為230的路徑有很多條。另外，我們還用近似算法鄰近點法進行計算，最后得出最短距離225公里，同時也得出了相應的路線。最后我們還對上述算法進行了評價及推廣。再次，針對第三問中改用兩輛小型貨車的路線設計問題。我們首先建立分步篩選模型對10個客戶進行分組，使得每一組的路徑最短。再應用第二問的模型分別求解為兩組客戶送貨的最優(yōu)路線。我們求得最后的分組情況為第一組 以及第二組 。所走最短路程305公里。再次

3、，我們分析求解了第四個問題。第四個問題中決定方案優(yōu)劣的因素有兩個，一個是車輛數，一個是行車路程。所以，我們首先建立的優(yōu)先考慮最短路徑的模型對這個問題進行求解，求得了用5輛車總費用745元的方案。但結果中第一個客戶的運送費用過高，基于貨物可分的假設，我們對求得的結果進行調整，得到了4輛車總費用645元的更優(yōu)方案。但這種方案受到應用范圍的限制。優(yōu)先考慮最短路徑模型偏重路徑最短，確定路徑后貨車輛不易調節(jié)，因此隨后，我們又建立優(yōu)先考慮送貨車輛數模型對該問題進行求解。由于該問題數據較少，第二個模型收到的良好的效果，我們得出了用4輛車總費用680的近似最優(yōu)路徑。最后，我們對模型進行了評價和推廣。一、問題的

4、重述運輸公司配送貨物的行駛路線直接影響到運輸費用，運輸公司往往希望通過合理的路線設計最大限度地提高人員、物資、金錢、時間等物流資源的效率(降低成本)，取得最大效益(提高服務)。同時，還可以去除多余的交錯運輸，并取得緩解交通、保護環(huán)境等社會效益。因此，設計合理的運輸行駛路線具有很大的意義?，F某運輸公司有10個客戶的配送任務，現針對該公司的配送路線提出如下問題：1、為已在第2個客戶處的配送員設計臨時為第10個客戶送貨的最短行駛路線；（給客戶10的貨已在車上）2、設計用一輛大型卡車一次為10個客戶送貨并回到提貨點的最優(yōu)行駛路線；（卡車可裝下所有用戶所需的貨物）3、如果因資源緊張只能用兩輛小型貨車（車

5、容量為50個單位）運貨，設計兩輛貨車的最短行駛路線；（已知每個客戶所需貨物量）4、用車容量25個單位的貨車運貨，在出車費、運費、行駛路程的約束條件下設計最優(yōu)行駛路線。 二、問題的假設各段路況都是一樣的，車子在各條路上行駛狀況相同。貨車在運貨過程中不會發(fā)生意外。 三、符號說明 G 將客戶作為頂點的賦權圖Kn 賦權完全圖 第i個客戶 第i個客戶到第j個客戶的最短距離D 行車總距離C 車輛數 S 運貨總費用 四、模型的建立及求解4.1問題一4.1.1用Dijkstra算法計算本題主要是求解最短路徑問題，求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法。Dijkstra算法以起始點為中心向外

6、層層擴展，直到擴展到終點為止，其基本思想是按距 從近到遠為順序，依次求得到G 的各頂點的最短路和距離直至（或直至G 的所有頂點），算法結束。由問題中可得配貨員從第二個客戶處出發(fā)，以為起點，對原矩陣修改得 用matlab7.0對上述矩陣應用用迪克斯特拉（Dijkstra）算法計算得配送員從到的最短距離d=85。4.1.2 用Floyd算法計算Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低。而Floyd算法簡單有效，由于三重循環(huán)結構緊湊，對于稠密圖，效率要高于執(zhí)行Dijkstra算法。可以算出任意兩個節(jié)點之間的最短距離，并且代碼編寫簡單；在matlab7.0中建

7、立如下函數對a矩陣進行處理即可得出配送員從到的最短距離d=85，路線為2-3-8-9-10。function D,R=floyd(a)n=size(a,1);D=afor i=1:nfor j=1:nR(i,j)=j;endendRfor k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j) v7 - v5 - v2 - v3 - v6 - v4 - v8 - v9 - v10 - v1然后我們又剛才算出來的Hamilton圈c2=1 7 5 2 3 6 4 8 9 10 1為初使圈用同樣的算法計算得最短路徑仍為230公里并得出新的路徑。4.2.2近似算法鄰近點法根據

8、題意，本題就是給定了賦權圖G，然后求G 的一個權最小的Hamilton 圈的問題。首先我們要判斷G是否有Hamilton 圈，在已知G 是Hamilton 圖的情況下，求出一個權最小的Hamilton 圈來。給G 添加權為 的邊，化為賦權完全圖Kn。在Kn 中，共有(n-1)!/2個不同的Hamilton 圈。如果一一計算各Hamilton 圈的長度，再逐個比較出權最小的一個，則計算量很大，當n 較大時無法實現。對這樣的問題，一般解決方法是設計較好的近似算法，求其近似最優(yōu)解。用鄰近法求解的一般步驟如下：Step1. 任選一點v1 V ，令 P1 = v 1, i=1.Step2. 設已得到Pi

9、= v1v2 vi, 選取Vi+1V v1,v2, vi 使得權w(vi,vi+1)最小。Step3. 若i = n ，則停止，C=Pn+VnV1= v1v2 vi v1 是一條近似的最小Hamilton 圈；否則i = i + 1 ，轉step2。用鄰近點法當n=10時，從v1出發(fā)，根據鄰近法，可得兩個近似解：v1-v5-v7-v6-v3-v4-v8-v9-v10-v2-v1，權為225；v1-v5-v7-v6-v4-v3-v8-v9-v10-v2-v1,，權為230。 所以最優(yōu)解是：v1-v5-v7-v6-v3-v4-v8-v9-v10-v2-v1，權為225。但是對于鄰近點法求近似解的精

10、度，有如下定理：設賦權完全圖Kn 各邊的權均為正數，且權滿足三角不等式：對于任意的vi，vj，vkV，w (vivj )+w (vjvk ) w( vi kv) ，則c0/c*( log2n+1)2其中c 是Kn 的最小Hamilton 圈的權，而c0是用鄰近點法求得的Hamilton 圈的權?？梢?，鄰近點法求近似解的精度也不高，且與初始點有關。4.2.3模型的評價求最短送貨路線時，即是求最優(yōu)圈的問題，目前還沒有求解這樣問題的有效算法。所以希望有一個方法以獲得相當好（但不一定最優(yōu)）的解。我們采用了求最短H-圈改良圈的算法。這種算法是不可能求得最優(yōu)解的，但可以我們隨機選取了不同的初始圈，比較不同

11、圈的權取其中的最小值已得到最優(yōu)的路徑，雖然該路徑與實際中的最優(yōu)路徑的近似程度不易衡量，但足可以滿足實際應用的要求了。另外在尋找權最小Hamilton 圈,模型中給G添加了權為，就把圖G轉化成了賦權完全圖，這樣就省略了判定G 是否有Hamilton 圈的問題，使問題得到了簡化。另外從鄰近點法的精確度來看，由于N比較小，所以精確度相對來說還是很高的。從幾種不同算法解出的結果也可以看出其精確性。4.3 問題三如果用兩輛小型貨車送貨，勢必要找出兩個Hamilton 圈，我們考慮將10個客戶分成兩組，每輛貨車負責一組客戶的貨物。將分好組的兩組分別求出其最小權Hamilton 圈，將兩個權相加即為最短路徑

12、。但是，由于有一些客戶間不能直達，以及車容量的限制（每輛車所載貨物量50個單位），客戶的分組并不能是完全嚴格的，一組中的點可以通過另一組中的點過度，達到最佳效果。也就是說，廣義上我們將10個客戶分為2組，但他們也可相交。4.3.1 分步篩選法求解進行近似計算我們可以以單程路程最短為衡量指標，貨車從每一點出發(fā)都駛向離它最近的，那么最后總路程也應最短。因為問題中客戶數僅為10個，所以以這種方法分組方便簡單。具體做法如下：1、以為起點，那么離其最近的兩點和則作為第二站分別分在兩組中。2、分別以和為起點尋找到他們最近的下兩個點。其中離最近的是和，已經分好組了，所以與分為一組。同理，將和分在一組。3、依

13、此類推，分組情況為：第一組 第二組 。按照我們的算法，應分在第二組，但是這樣會導致第二輛貨車超載，所以必須考慮將分給一組，但到不能直達，用Floyd算法計算得到最短路程30公里，經過。比將分到第而組多出10公里，權衡下為最佳選擇。所以最后的分組情況為第一組 以及第二組 。分好組以后對每一組中的點利用前兩個問題的算法求其最小權Hamilton 圈得到最短路徑。將分組后的各點用matlab7.0處理得到兩輛車的最短路徑分別為c1=1 5 2 3 8 910 1 和 c2=1 7 6 4 9 1。計算得d1=160公里，d2=145公里。最后兩輛車所走過的總距離為D=d1+d2=305公里。通過以上

14、算法我們得出的最后結果是：兩輛車分別給客戶1 5 2 8 10和客戶 7 6 4 9 送貨，所走的最短路程為305公里。4.4問題四這一問中約束條件更多，分析10個客戶的需貨量，車容量減少為25個單位使得每輛車最多不可能給超過4個的客戶送貨，另外每增加一輛車就會增加k（100元/輛）元的出車費，1元/公里的運費同時也給設計路線增加了約束條件?；诘诙柕那蠼?，我們還是希望先對10個客戶進行分組。顯然，運貨總費用S=kC+D。4.4.1優(yōu)先考慮最短路徑模型所有貨車在裝好貨物以后均要從v1出發(fā)，要得到最短路徑，我們不妨先算出v1到各點的最短距離及路徑。采用Dijkstra算法應用matlab7.0

15、進行求解得到如下結果：其中第一行為客戶序號，第二行為各個客戶的需貨量，第三行為最短距離，第四行為得到最短距離的路徑。每輛車所裝貨物不能超過車容量，分析客戶需求量可得到每輛車最多能夠送貨的客戶數M。設每條路徑的路徑度為完成路徑所經歷的節(jié)點個數，路徑距離為完成路徑所走過的路程。取Max（）最接近M的路徑為第一主路徑，檢索其他路徑，將重復點多的路徑淘汰。留下路徑單點，尋找含第一路徑以外節(jié)點的高路徑度路徑以相同的方法處理，單點以路徑最短為原則插入到已選的路徑中去，依此類推，最后得到了以v1為頂點，遍游所有節(jié)點的路徑束，且路徑總路程最短。由于不考慮空車返回的費用，路徑不必形成圈。最后以車容量為標準調整各

16、個路徑?；谝陨纤惴ń鉀Q題目中的問題如下：分析客戶需求量得到此題中M=4。v1到各點的最短路徑前面我們已經用Dijkstra算法求得。第一步選出與M相近的路徑有：1-5-2、1-4-3、1-7-6、1-9-10，留下的單點為v8。用Floyd算法計算v8到各個路徑末點的最短距離分別為：55、25、50、35 。顯然單點v8應放在第三條路徑中。最后得到的四條路徑分別為：1-5-2、 1-4-3-8、 1-7-6 和 1-9-10 。車輛數C=4 。v1存在與每一條路徑中，但無論將v1的貨物放在哪一輛車上都會使該車超載。以算法中優(yōu)先考慮最短路徑為原則，應再派一輛車，以最短的路徑0公里為v1送貨。這

17、樣求得的送貨方案為：車輛號路徑送貨點費用11-5-25、2100+40=140元21-4-3-84、3、8100+80=180元31-7-67、6100+55=155元41-9-109、10100+70=170元511100元費用合計：S=745元。 C=5此方案中v1最近但是送貨費用卻最高。結果不盡如人意。在貨物可分的情況下，我們考慮可以將v1的貨物分裝在1、2號車中，這樣便節(jié)省了一輛車的出車費100元，大大的優(yōu)化了方案。這樣處理后的送貨方案為：車輛號路徑送貨點費用11-5-21、5、2100+40=140元21-4-3-81、4、3、8100+80=180元31-7-67、6100+55=

18、155元41-9-109、10100+70=170元費用合計：S=645元。 C=4 以上模型優(yōu)先考慮最短路徑，對車輛數相對較難控制，分組方法相對粗糙。但是最短距離則比較控制，一個點的位置都可能在整體上很大程度的優(yōu)化結果，而這個題目中數據很少，我們很容易得出最少車輛數為4輛，因此我們又建立的新的優(yōu)先考慮車輛數的模型。 4.4.2優(yōu)先考慮車輛數模型由題意可知,，貨物總量為94，而每輛車的最大裝載量為25，故可以很容易的得到至少需要4輛車完成送貨。所以我們優(yōu)先考慮用四輛車的情況。即將共計10個客戶分成四組，再在組內求其最小路徑。更方便的是題目要求不考慮空車返回的費用，我們只需求解單程路徑最短。由于

19、本題的規(guī)模不是很大(包括提貨點共10個點),所以我們仍可用鄰近點法解決這個問題。算法思路是找出距離提貨點v1最近的四個點，將它們分別分在四組中，再分別找離這四個點最近的點，依此類推，知道所有點都被分組?；谝陨纤惴ǎ覀儜肈ijkstra算法求出各點到v1 的距離，找到v4, v5, v7, v9(v2)離v1最近。再分別找出距離v4, v5, v7, v9(v2)距離最近的點,依此類推,直到把點全部找完為止. 由于v9和v2到v1的距離相等，所以我們分成兩種情況討論：第一種情況（第一次分組選v9）經過兩次分組后計算結果如下v1-v4-v3 v1-v5-v8 v1-v7-v6 v1-v2-v

20、9現在還有v10沒有考慮進去，而1-2-9和1-7-6已經滿載，所以只有可能將v10添加到路線1-4-3和1-5-8中,前面已經算出v3和v8到v10的最短路徑分別為60公里和30公里，而且它們都能滿足容量的要求。路徑距離越短越好，自然將v10分給v8 。于是，第一條合理的路徑為:v1-v4-v3, v1-v5-v8-v9-v10, v1-v7-v6, v1-v2-v9.這四輛車分別給1 4 3, 5 8 10, 7 6, 2 9客戶送貨。最小費用為295+400=695。得到最終結果如下:車輛號路徑送貨點費用11-4-31、4、3100+55=155元21-5-8-9-105、8、10100

21、+80=185元31-7-67、6100+55=155元41-2-92、9100+100=200元費用合計：S=695元 C=4第二種情況可以得到 ：v1-v4-v3 v1-v5-v2 v1-v7-v6 v1-v9-v10,最后剩下v8再討論。在上面找出的任一條路線中,都無法直接去v8，因為這樣總會有車超載.，類似于深探法的思想，將v8分別換到v4或v5，v7，v9的后面,再分別討論。 又1-7-6恰好滿載，而且是最短路線，因此先不考慮。 如果將v8排v10后，雖然v8到v10的最短距離只有30公里，但是只要v9和v10到一起，就不能再給其它客戶送貨，如果放到v3后面，v3到v8的最短距離只有

22、25，但是會使小貨車超載，因為如果按這條路線，第四輛車就只能給v1 v5 v2 送貨，不滿足容量的要求。所以只能將v8排在v2后面。得出結果如下：車輛號路徑送貨點費用11-4-31、4、3100+55=155元21-5-2-85、2、8100+100=200元31-7-67、6100+55=155元41-9-109、10100+70=170元費用合計：S=680元 C=4另外還可以考慮用如下算法求解：此題數據較少，由于貨物總量為94，而每輛車的最大裝載量為25，故可以很容易的得到至少需要4輛車完成送貨。要使送貨所需費用最小，則盡可能的使每輛車都走最短的路線。首先，仍然是應用Dijkstra算法

23、算出v1到各個節(jié)點的最短距離及路徑： 40 55 40 25 55 30 55 50 70各個點所需貨物數量如下8 13 6 9 7 15 10 5 12 9我們發(fā)現路線剛好使一輛車滿載，而且所走的距離也最短，故我們先確定了這一條路線。剩下的三輛車總有一輛要去離最遠的點，從上面所求的數據我們不難看出，從到最短的路線為，而我們又發(fā)現距離最近的點為，距離才為10，所以選擇路線。由到點的距離也為10，所以可以選擇路線，剩下的可通過路線連起來，最后通過計算，第一條路線裝載和的貨物，第二條路線裝載點、和的貨物，第三條路線裝載點、和的貨物，最后一條路線裝載和的貨物，每一輛車都沒超載且運載量也大致相當，也盡

24、可能的沿著最短的路線走，因而所走的距離也很短，所需費用就很接近最優(yōu)解。最后得到的結果為：車輛號路徑送貨點費用11-7-67、6100+55=155元21-9-10-31、10、3100+80=180元31-5-8-95、8、9100+65=165元41-4-3-24、3、2100+85=185元費用合計：S=680元 C=4綜合以上算法的計算結果，多個小型貨車送貨問題的最優(yōu)解為S=680，C=4路徑為1 7 6、1-9-10-3、1-5-8-9、1-4-3-2和1-4-3、1-5-2-8、1-7-6、1-9-10。若假設第一個客戶的貨物可分則得到最優(yōu)解S=645，C=4路徑為1-5-2、1-4

25、-3-8、1-7-6、1-9-10。 五、模型的推廣我們建立的模型解決了一系列運送貨物最小路徑的問題。如果我們把距離該做兩點之間的直達時間則可運用我們建立的模型求解最短時間完成任務的最優(yōu)路徑等外圍類似問題。而在現實生活中類似于運輸路徑的問題有很多，比如說保安在住宅區(qū)用最短的時間巡邏、郵遞員走最短的距離送信、環(huán)形旅游花費最少等等。針對這些問題都可以通過我們的模型進行求解。本題所建立的模型,都是根據現有的數據資料設置變量,各變量之間關系明確,且各個參數可比較方便地得到. 參考文獻1 戴一奇等 編著，圖論與代數結構，北京，清華大學出版社，1995年2 徐金明 主編， MATLAB實用教程，北京 ，清

26、華大學出版社*北京交通大學出版社，2005年7月3 姜啟源等 編，大學數學實驗，北京，清華大學出版社，2005年2月4 殷劍宏，吳開亞，圖論及其算法，中國科技大學出版社，20035 徐俊明，圖論及其應用，中國科技大學出版社，19986 王樹禾，圖論及其算法，中國科技大學出版社，1994。 附錄clear; %求一點到其他各點的距離及路徑clc;M=10000;a=0 50 M 40 25 M 30 M 50 M;50 0 30 M 35 50 M 60 M M;M 30 0 15 M 30 50 25 M 60;40 M 15 0 45 30 55 20 40 65;25 15 M 45 0

27、60 10 30 M 55;M 50 30 30 60 0 25 55 35 M;30 M 50 M 10 25 0 30 45 60;M 60 25 20 30 55 30 0 10 M;20 M M 40 M 15 25 45 0 20;35 20 10 45 20 M 60 M 30 0;pb(1:length(a)=0;pb(1)=1;index1=1;index2=ones(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;while sum(pb)=2 index=index(1); end index2(temp)=index;endd, index1, index2function d,path=floyd(a,sp,ep) %求任意亮點間的距離和路徑n=size(a,1);D=a;path=zeros(n,n);for i=1:n for j=1