《建模送貨策略》由會員分享，可在線閱讀，更多相關《建模送貨策略（29頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、29 快遞公司送貨策略 一 摘要： 本文是關于快遞公司送貨策略的優(yōu)化設計問題，即在給定送貨地點和給定設計規(guī)范的條件下，確定所需業(yè)務員人數(shù)，每個業(yè)務員的運行線路，總的運行公里數(shù)，以及費用最省的策略。 本文主要從最短路經(jīng)和費用最省兩個角度解決該問題，建立了兩個數(shù)據(jù)模型。模型一：利用“圖”的知識，將送貨點抽象為“圖”中是頂點，由于街道和坐標軸平行，即任意兩頂點之間都有路。在此模型中，將兩點之間的路線權值賦為這兩點橫縱坐標之和。如A（x1，y1），B（x2，y2）兩點，則權值為D=|x2-x1|+|y2-y1|。并利用計算機程序對以上結果進行了校核。模型二：根據(jù)題意，建立動態(tài)規(guī)劃的數(shù)學模型。然后

2、用動態(tài)規(guī)劃的知識求得最優(yōu)化結果。根據(jù)所建立的兩個數(shù)學模型，對滿足設計要求的送貨策略和費用最省策略進行了模擬，在有標尺的坐標系中得到了能夠反映運送最佳路線的模擬圖。最后，對設計規(guī)范的合理性進行了充分和必要的論證。 二 關鍵詞： 快遞公司送貨 最優(yōu)化 圖模型 多目標動態(tài)規(guī)劃 TSP模型 三 問題重述： 在快遞公司送貨策略中，確定業(yè)務員人數(shù)和各自的行走路線是本題的關鍵。這個問題可以描述為:一中心倉庫(或配送調度中心) 擁有最大負重為25kg的業(yè)務員m人, 負責對30個客戶進行貨物分送工作, 客戶i 的快件量為已知 , 求滿足需求的路程最短的人員行駛路徑,且使用盡量少的人數(shù),并滿足

3、以下條件: 1) 每條送快件的路徑上各個客戶的需求量之和不超過個人最大負重。 2) 每個客戶的需求必須滿足, 且只能由一個人送貨. 3）每個業(yè)務員每天平均工作時間不超過6小時，在每個送貨點停留的時間為10分鐘，途中速度為25km/h。 4）為了計算方便，我們將快件一律用重量來衡量，平均每天收到總重量為184.5千克。 表一為題中所給的數(shù)據(jù)： 表一 最大載重量 25kg 重載時速 20km/h 途中的平均速度 25km/h 重載酬金 3元/km*kg 業(yè)務員工作時間上限 6h 空載時速 30km/h

4、每個送貨點停留時間 10min 空載酬金 2元/km 備注 1、快件一律用重量來衡量 2、假定街道方向均平行于坐標軸 處于實際情況的考慮, 本研究中對人的最大行程不加限制.本論文試圖從最優(yōu)化的角度，建立起滿足設計要求的送貨的數(shù)學模型，借助于計算機的高速運算與邏輯判斷能力，求出滿足題意要求的結果。 四 問題分析： 從公司總部配出一個人，到任意未配送的送貨點，然后將這個人配到最近的未服務的送貨點范圍之內的鄰居，并使送貨時間小于6小時，各送貨點總重量不超過25kg。繼續(xù)上述指派，直到各點總重量超過25kg，或者送貨時間大于6小時。最后業(yè)務員返回總部，記錄得到的可行行程（即路線）。

5、對另一個業(yè)務員重復上述安排，直到?jīng)]有未服務的送貨點。對得到的可行的行程安排解中的每一條路徑，求解一個旅行商問題，決定訪問指派給每一條行程的業(yè)務員的順序，最小化運輸總距離。得到可行解的行程安排解后退出。 根據(jù)題意的要求，每個人的工作時間不超過6小時，且必須從早上9點鐘開始派送，到當天17點之前（即在8小時之內）派送完畢。且，故至少需要8條路線。表二列出了題中任意兩配送點間的距離。 表二：任意兩點間的距離矩陣 因為距離是對稱的，即從送貨點i到送貨點j的距離等于從j到i的距離。記作：dij. 表三給出了客戶的需求，為了完成送快遞的任務，每個人在工作時間范圍內，可以承擔兩條甚至更多的線路。

6、表中給出了送貨點序號，送貨點編號，快件量T，以及送貨點的直角坐標。 表三 序號 送貨點 快件量T 坐標（km） 序號 送貨點 快件量T 坐標（km） x y x Y 1 1 8 3 2 16 16 3.5 2 16 2 2 8.2 1 5 17 17 5.8 6 18 3 3 6 5 4 18 18 7.5 11 17 4 4 5.5 4 7 19 19 7.8 15 12 5 6 3 0 8 20 15 3.4 19

7、 9 6 5 4.5 3 11 21 32 6.2 22 5 7 7 7.2 7 9 22 22 6.8 21 0 8 8 2.3 9 6 23 23 2.4 27 9 9 9 1.4 10 2 24 24 7.6 15 19 10 10 6.5 14 0 25 25 9.6 15 14 11 11 4.1 17 3 26 26 10 20 17 12 12 12.7 14 6 27 27 12 21 13 13 13 5.8 12 9 28

8、 28 6.0 224 20 14 14 3.8 10 12 29 29 8.1 25 16 15 20 4.6 7 14 30 30 4.2 28 18 五 模型假設： （1）街道方向均平行于坐標軸，且在該前提下，業(yè)務員可以任意選擇路線。 （2）無塞車現(xiàn)象，即業(yè)務員送快遞途中不受任何外界因素影響，且業(yè)務員的休息時間不包括在最大工作時間6個小時內。 （3）業(yè)務員人數(shù)不限制。 （4）每個業(yè)務員的路線一旦確定，便不再更改。 （5）每個業(yè)務員送快遞是獨立的，每人之間互不影響。 （6）業(yè)務員到某送貨點后必須把該送貨點的快件送完。

9、 （7）每個業(yè)務員每天的工作時間不超過6個小時。 （8）業(yè)務員回到快遞公司后停留一個小時。 六 主要符號說明： Ti：序號為i的送貨點的快件重量 （xi ，yi）序號為i的送貨點的坐標 M重：業(yè)務員送貨總重載費用 M空：業(yè)務員送貨總空載費用 M總：業(yè)務員送貨總費用 N：業(yè)務員送貨的總次數(shù) m：業(yè)務員人數(shù) mj：第j個業(yè)務員送貨的次數(shù) 七 模型建立與求解： 7.1問題一模型 本模型考慮用多目標動態(tài)規(guī)劃求解。由于問題一中只要求給出一個合理的方案，且未涉及到業(yè)務員工資問題，故只要滿足條件——業(yè)務員的工作時間上限是6個小時以及每條路線的最大載重量不大于25k

10、g即可，本模型中追加兩個目標——路程最短和人員最少?？梢酝ㄟ^以下兩種方法實現(xiàn)：（1）每一個行程的第一個送貨點是距離總部最近的未服務的送貨點。用這種方法，即可得到一組運行路線，總的運行公里數(shù)，以及總費用。（2）每一個行程的第一個送貨點是距離總部最遠的未服務的送貨點。然后以該點為基準，選擇距它最近的點，加上約束條件，也可得到一組數(shù)據(jù)。然后比較兩組結果，通過函數(shù)擬合即可得到最優(yōu)化結果。 本模型中以滿足需求的路程最短的人員行駛路徑,且使用盡量少的人數(shù)，即 且 約束條件為： ① 時間約束： ② 載重量約束： 方法一：每一個行程的第一個送貨點是距離總部最近的未服務的送貨點

11、。 開始 找離原該點最近的點v，且該點的訪問標志設為被訪問，該點快遞重量為w，輸出該點。 找點v最近的點，快遞重量為w1，且w1+w<25，當其不成立時找次遠點。 N Y 找不到符合條件的點 時 找到符合條件的點，且不止一個時選擇快遞重量最重的那個點，訪問標志設為被反問，并輸出該點，賦值給v，且w=w+w1； 第一條行程中訪問了節(jié)點0-1-3-4-5-0，是因為1距離原點最近，因此由1出發(fā)，3是距離1點最近的點，而且兩處快件量之和為14kg，小于每個人最大負重量，可以繼續(xù)指配。接著，4是距離3最近的點，而且三處快件量之和為19.

12、5kg，仍小于25kg,還可以繼續(xù)指配。在剩下的未服務送貨點中，5距離4最近（其實距離4最近的點有2，5，6，7四個點，然后考慮該點需求的快件量，將其從大到小依次排列，快件量需求大者優(yōu)先，但超過25kg上限的點舍去。這里2，7被舍去，故選擇了5）總快件量之和為24kg。再繼續(xù)擴充，發(fā)現(xiàn)就會超出“25kg”這個上限，因此選擇返回，所以0-1-3-4-5就為第一條路線所含有的送貨點。 用該算法得到的各路線為： （1）0 1 3 4 5 0 （2）1 2 6 7 13 0 （3）9 8 12

13、 10 0 （4）0 16 17 20 14 15 23 0 （5）0 11 22 32 19 0 （6）0 27 26 0 （7）0 18 24 25 0 （8）0 29 28 30 0 現(xiàn)在0-1-3-4-5這四個送貨點之間的最優(yōu)訪問路徑安排就

14、是一個典型的單回路問題?？梢酝ㄟ^單回路運輸模型-TSP模型求解。一般而言，比較簡單的啟發(fā)式算法求解TSP模型求解有最鄰近法和最近插入法兩種。由RosenkrantzStearns等人在1977年提出的最近插入法，能夠比最近鄰點法，取得更滿意的解。由于0-1-3-0 已經(jīng)先構成了一個子回路，現(xiàn)在要將節(jié)點4 插入，但是客戶4有三個位置可以插入，現(xiàn)在分析將客戶4插入到哪里比較合適: 1.插入到（0，1）間，C總= 7+4+5+1+4+9=30。 2.插入到（1，3）間，C總=5+6+4+9=24。 3.插入到（3，0）間，C總=5+4+4+11=24。 比較上述三種情況的增量，插入到（3，0

15、）間和（1，3）間增量最小，考慮到下一節(jié)點插入時路程最小問題，所以應當將4插入到送貨點3和總部0之間。接下來，用同樣的方法，將5插到4和0之間，能使該條路線總路程最小，該路線總路程為32km，歷時1.9467h。結果子回路為T={0-1-3-4-5-0}.因為街道平行于坐標軸方向，所以它就是最優(yōu)化路線。 第二條行程這中，由于所剩下節(jié)點中，2距離0點最近，因此由2出發(fā)，就可以找到最近點13，接著是7，然后6.這樣，第二條優(yōu)化路線0-2-13-7-6-0就確定了。用這種方法，依次可確定以下剩余六條路線。 得到總的送貨路線為： （1）0 1 3 4 5 0 （2）0 2

16、13 7 6 0 （3）0 10 12 8 9 0 （4）0 16 17 20 14 15 23 0 （5）0 19 11 32 22 0 （6）0 18 24 25 0 （7）0 27 26 0 （8）0 29 30 28 0 運輸員序號 所經(jīng)站數(shù) 最近點 所用時間 (小時) 總載重（kg）

17、總路程（km） 1 4 1（3，2） 1.9467 24 32 2 4 2（1，5） 2.3467 24.2 42 3 4 9（10，2） 1.8664 22.9 30 4 6 16（2，16） 4.6000 23.5 90 5 4 11（17，3） 4.2134 24.9 72 6 3 18（11，17） 3.7500 24.7 68 7 2 27（21，13） 3.7067 22 76 8 3 29（25，16） 4.8400 18.3 96 合計 30 28.2699 184.5

18、 506 改進前和改進后的路程，時間比較如下： 然后，根據(jù)所經(jīng)歷的時間進行劃分，確定運送人數(shù)。在工作時間小于6小時的前提下，最終只需要六名運輸員，第一條線路和第二條線路有一人完成，第三條和第七條線路由一人完成，則各運輸員到達各站點時間的情況如下： 路線 站點 編號 到各站 點時間 出發(fā)時間 路線 站點 編號 到各站點時間 出發(fā)時間 1 1 9：12 9：00 5 19 10：05 9：00 3 9：32 11 10：41 4 9：52 32 11：08 5 10：14 22 11：32

19、2 2 12：02 11：58 6 18 10：07 9：00 13 12：48 24 10：31 7 13：10 25 10：53 6 13：39 7 27 13：45 12：23 3 10 9：34 9：00 26 14：07 12 9：58 8 29 10：38 9：00 8 10：20 30 11：00 9 10：44 28 11：24 4 16 9：43 9：00 17 10：07 20 10：29 14 10：51 15

20、11：30 23 11：59 路徑為： 方法二：每一個行程的第一個送貨點是距離總部最遠的未服務的送貨點。 分析方法如一： 得到的路徑為： （1）0 30 29 28 23 15 0 （2）0 26 27 8 0 （3）0 24 25 14 9 0 （4）0 18 17 20 16 6 0 （5）0

21、32 22 11 10 0 （6）0 19 13 7 0 （7）0 12 4 3 0 （8）0 5 2 1 0 同方法一，用最近插入法修改路徑可以得到更優(yōu)的解，改進后的路徑為： （1） 0 28 30 29 23 15 0 （2） 0 26 27 8 0 （3） 0 24 25 14 9 0

22、（4） 0 20 18 17 16 6 0 （5） 0 11 32 22 10 0 （6） 0 19 13 7 0 （7） 0 4 12 3 0 （8） 0 2 5 1 0 運輸員序號 所經(jīng)站數(shù) 最遠點 所用時間（小時） 總載重（km） 總路程（km） 1 5 30（28，18） 4.8333 24.1 100 2 3 26（20，17） 3.5400

23、 24.3 76 3 4 24（15，19） 3.3867 22.4 68 4 5 18（11，17） 3.1530 24.4 58 5 4 32（22，5） 2.8267 23.6 54 6 3 19(15, 12 ) 2.6600 20.8 54 7 3 12(14, 6 ) 2.1800 24.2 42 8 3 5 (3, 11) 1.6200 20.7 28 合計 30 24.1997 184.5 480 改進前后路程和時間的比較如下：然后，根據(jù)所經(jīng)歷的時間進行劃分，確定運送人數(shù)。在工作時

24、間小于6小時的前提下，最終只需要五名運輸員，第三條線路和第八條線路由一人完成 第四條線路和第七條線路由一人完成，第五條線路和第六條線路由一人完成，則各運輸員到達各站點時間的情況如下： 路線 站點編號 到各站點時間 出發(fā)時間 路線 站點編號 到各站點時間 出發(fā)時間 1 28 10：46 9：00 5 11 9：48 9：00 30 11：11 32 10：15 29 11：33 22 10：39 23 12：05 10 11：06 15 12：34 6 19 13：55 12：50

25、 2 26 10：29 9：00 13 14：31 27 10：51 7 14：53 8 11：47 7 4 13：36 13：10 3 24 10：22 9：00 12 14：12 25 10：44 3 14：48 14 11：11 8 2 13：48 13：34 9 11：45 5 14：07 4 20 9：50 9：00 1 14：39 18 10：17 17 10：41 16 11：07 6 11：41 路徑圖為： 由上面得圖表

26、知改進后的方法二的路線的總的距離為480km，時間為24.1997；比改進后的方法一的距離短，時間短，所以若是只考慮時間和路程，改進后的方法二為最優(yōu)解。 7.2 問題二模型 問題二中由于業(yè)務員所得的費用是最主要的，業(yè)務員安排、路線選擇都是為了總費用的最小化提供條件，所以應首先考慮路費，之后再考慮業(yè)務員的安排。為了使總能夠費用最少，總的思路是先送貨給離快遞公司最近切塊間最重的送貨點，以此類推，在保證時間、載重量有限的前提下，沿途把快遞送完，最終讓業(yè)務員最遠點空載返回。根據(jù)這一思路，全部路線業(yè)務員的重載費用可表示為： 從上式可以看出，業(yè)務員的重載費用是恒定的，又由于總費用為重載與空載費用

27、之和，所以總費用的確定就可以轉化為滿足一定條件下的各路線的最遠點的選擇問題。某路線業(yè)務員經(jīng)過的路徑選擇應遵循以下原則：一是，近者優(yōu)先原則。某業(yè)務員最近起始送貨點的選擇直接關系到費用的多少，所以該業(yè)務員在沿途往送貨終點站中應盡量把較近點的快件送完，不讓下一條路線再把較近點作為起始送貨站。二是，不走冤枉路原則。一方面，離原點（快遞公司）較遠的送貨點坐標應分別大于離原點較近送貨點的坐標，在各個坐標上均不走回頭路，即按圖（a）中的①②路線前進，而不按③路線前進： 圖（a）業(yè)務員行走路線約定 另一方面，由于在路途相等的條件下，重載費用要比空載費用大得多，因此，盡量讓業(yè)務員空載行走。三是，坐標貼近原則

28、。在同一條路線中，離原點較近送貨點的坐標僅次于較遠點的坐標。四是，路線較少原則。路線多，一方面，相對最遠點的選擇多，跑的空路多，費用就多；另一方面，過分地強調短暫效益，出動路線多，會引起業(yè)務員的反感，不利于以后的人員控制。 根據(jù)上述分析及基本假設，業(yè)務員送貨的費用可以表示如下： 重載費用： 空載費用： 總費用： 應該滿足以下要求： ① 時間約束： ② 載重量約束: ③ 路線約束： 根據(jù)路線約束條件③以及表二知：送貨點1（3，2）、2（1，5）首先必須作為某路線的最近起始送貨點，再結合時間約束條件①、載重量約束條件②以及上述分析的有關內容，依次選出各路線的次近點，并做統(tǒng)籌

29、兼顧，一直到滿足約束條件的最大值為止。隨后又選出6（0，8）、9（10，2）、10（14，0）、16（2，16）、22（21，0）、15（19，9）、25（15，14）為某條路線的最近點，分別確定次近點等，最后確定各路線如圖（b）所示： 第一條路線： 快遞公司 1（3，2） 3（5，4） 8（9，6） 13（12，9） 出發(fā)線 返回線 第二條路線： 快遞公司 2（1，5） 4（4，7） 7（7，9） 14（10，12） 出發(fā)線 返回線 第三條路線： 快遞公司 6（0，8） 5（3，11） 20（7，14） 18（11，17） 出發(fā)線

30、返回線 30（28，18） 第四條路線： 快遞公司 9（10，2） 12（14，6） 19（15，12） 出發(fā)線 返回線 第五條路線： 快遞公司 10（14，0） 11（17，3） 32（22，5） 23（27，9） 出發(fā)線 返回線 第六條路線： 快遞公司 16（2，16） 17（6，18） 24（15，19） 28（24，20） 出發(fā)線 返回線 第七條路線： 快遞公司 22（21，0） 29（25，16） 出發(fā)線 返回線 第八條路線： 快遞公司 15（19，9） 27（21，13） 出發(fā)線 返回線

31、 第九條路線： 快遞公司 25（15，14） 26（20，17） 出發(fā)線 返回線 圖（b）業(yè)務員行走路線 根據(jù)上面確定的路線，把個業(yè)務員所經(jīng)過的送貨點數(shù)、最近點、所用時間、總載重量進行歸納，并用C++編程求出各業(yè)務員送貨所得費用以及總費用，如下表： 路線號 所經(jīng)送貨點數(shù) 最近送貨點 所用時間（小時） 總載重量（kg） 費用（元） 1 4 1（3，2） 2.41667 22.1 792.9 2 4 2（1，5） 2.5 24.7 969.5 3 5 6（0，8） 4.66667 23

32、.8 1852.4 4 3 9（10，2） 2.75 21.9 1498.2 5 4 10（14，0） 3.66667 19.2 1352.4 6 4 16（2，16） 4.33333 22.9 2261.8 7 2 22（21，0） 3.75 14.9 1506.7 8 2 15（19，9） 3.16667 15.4 1577.6 9 2 25（15，14） 3.42667 19.6 2019.2 合計 30 184.5 13830.7 根據(jù)時間約束，最少要8個業(yè)務員送快件，其

33、中把路線1和2合并，讓業(yè)務員A執(zhí)行任務，其余的分別由其他7個業(yè)務員送貨。同時，為了便于統(tǒng)籌業(yè)務員，可以得出各業(yè)務員到各送貨點的時間（各業(yè)務員的出發(fā)時間為0）以及各路線從快遞公司出發(fā)的參考時間（從9：00開始工作）。 第一個人：0-1-3-8-13-0和0-2-4-7-14-0 第二個人：0-6-5-20-18-30-0 第三個人：0-9-12-19-0 第四個人：0-10-11-32-23-0 第五個人：0-16-17-24-28-0 第六個人：0-22-29-0 第七個人：0-15-27-0 第八個人：0-25-26-0 根據(jù)上述分析，得到各路線的行走路線如下圖所示

34、： 若根據(jù)問題一的求解方法，可得以下8條路線： 第一條路線： 快遞公司 1（3，2） 3（5，4） 4（4，7） 5（3，11） 出發(fā)線 返回線 第二條路線： 快遞公司 2（1，5） 13（12，9） 7（7，9） 6（0，8） 第三條路線： 快遞公司 10（14，0） 12（14，6） 8（9，6） 9（10，2） 第四條路線： 快遞公司 16（2，16） 17（6，18） 20（7，14） 14（10，12） 第五條路線： 快遞公司 22（21，0） 32（22，5） 23（27，9） 15（19

35、，9） 11（17，3） 第六條路線： 快遞公司 19（15，12） 25（15，14） 24（15，19） 第七條路線： 快遞公司 18（11，17） 26（20，17） 28（24，20） 第八條路線： 快遞公司 27（21，13） 29（25，16） 30（28，18） 圖（b）業(yè)務員行走路線 根據(jù)上面確定的路線，把個業(yè)務員所經(jīng)過的送貨點數(shù)、最近點、所用時間、總載重量進行歸納，并用C++編程求出各業(yè)務員送貨所得費用以及總費用，如下表： 路線號 所經(jīng)送貨點數(shù) 最近送貨點 所用時間（

36、小時） 總載重量（kg） 費用（元） 1 4 1（3，2） 2.03333 24 767.5 2 4 2（1，5） 2.73333 24.2 1390.6 3 4 10（14，0） 2.56667 22.9 1357.5 4 4 16（2，16） 3.1 17.7 1438.4 5 5 22（21，0） 5.2 22.9 2680.6 6 3 19（15，12） 3.33333 25 2310.2 7 3 18（11，17） 4.16667 23.5 2620 8 3 27（21，13） 4.333

37、33 24.3 2891.9 合計 30 27.46666 184.5 15456.7 合并則有以下人員分配： 第一個人：0-1-3-4-5-0和0-19-25-24-0 第二個人：0-2-13-7-6-0和0-10-12-8-9-0 第三個人：0-16-17-20-14-0 第四個人：0-22-32-23-15-11-0 第五個人：0-18-26-28-0 第六個人;0-27-29-30-0 八 模型評價 1、模型的優(yōu)點： （1）模型系統(tǒng)的給出了業(yè)務員的調配方案，便于指導工作實踐。 （2）模型簡單明了，容易理解與靈活應用。 （3）模型的方法和

38、思想對其他類型也適合，易于推廣到其他領域。 （4）本模型方便、直觀，易于在計算機上實現(xiàn)和推廣。 2、模型的缺點： （1）模型給出的約束條件可能也有不太現(xiàn)實的。 （2）對街道的方向，客戶的快件量的假設有待進一步改進。 3、 模型的推廣 （1）本模型不但適合于快遞公司送貨問題，還是用于一般的送貨以及運輸問題，只需要稍微改動模型即可。 （2）模型方便、直觀，可以實現(xiàn)計算機模擬。 （3）建模的方法和思想可以推廣到其他類型，如車輛調度問題等。 參考文獻： [1]：姜啟源、謝金星、葉俊編，數(shù)學模型-3版，北京，高等教育出版社，2003.8 [2]：吳建國、汪名杰、李虎軍、

39、劉仁云編，數(shù)學建模案例精編-1版，北京，中國水利水電出版社，2005.5 [3]：唐煥文、賀明峰編，數(shù)學模型引論-3版，北京，高等教育出版社，2005.3 注釋：C++源碼 求解路線及其相關內容： 問題一之方法一： #include #include #include #define max 1000 using namespace std; struct ver{ int x; int y; int num; float weight; }; bool visited[31]; ver v[

40、31]; int next1(){ int k,min=max,tag=0; float w; for(int i=1;i<31;i++){ if(visited[i]==false&&v[i].x+v[i].yw){ k=i; w=v[i].weight;

41、tag=1; } } if(tag)return k; else return 0; } int next2(int k,float w){ int min=max,tag=0,m,i; for(i=1;i<31;i++){ if(visited[i]==false&&fabs(v[k].x-v[i].x)+fabs(v[k].y-v[i].y)

42、; tag=1; } if(visited[i]==false&&fabs(v[k].x-v[i].x)+fabs(v[k].y-v[i].y)==min&&w+v[i].weight<=25&&v[i].weight>v[m].weight){ m=i;tag=1; } } if(tag)return m; else return 0; } void way(){ int k; float w; k=next1(); while(k!=0){ float time; int nu

43、m_of_station=0,distance,tag; visited[k]=true; w=v[k].weight; distance=v[k].x+v[k].y; time=(v[k].x+v[k].y)/25.0; cout<<'0'<<"->"<"; tag=next2(k,w); while(tag!=0){ num_of_station++; visited[tag]=true; cout<"; w=w+v[tag].weight;

44、 time=time+(fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y))/25.0; if(time+(v[tag].x+v[tag].y)/25.0+(num_of_station+1)/6.0<=6){ distance=distance+fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y); k=tag; tag=next2(tag,w); }else{ time=time-(fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y)

45、)/25.0; break; } } time=time+(v[k].x+v[k].y)/35.0+(num_of_station+1)/6.0; distance=distance+v[k].x+v[k].y; cout<<'0'<<" "<

46、xt"); cout<<"各站點的坐標及相關信息是："<>v[i].num>>v[i].x>>v[i].y>>v[i].weight; cout<

47、 way(); return 0; } 問題一之方法二： #include #include #include #define max 1000 using namespace std; struct ver{ int x; int y; int num; float weight; }; bool visited[31]; ver v[31]; int next1(){ int k,max1,tag=0; float w; for(int i=1;i<31;i++){

48、 if(visited[i]==false&&v[i].x+v[i].y>max1){ max1=v[i].x+v[i].y; k=i; w=v[i].weight; tag=1; } if(visited[i]==false&&v[i].x+v[i].y==max1&&v[i].weight

49、,float w){ int min=max,tag=0,m,i; for(i=1;i<31;i++){ if(visited[i]==false&&fabs(v[k].x-v[i].x)+fabs(v[k].y-v[i].y)

50、.y-v[i].y)==min&&w+v[i].weight<=25&&v[i].weight

51、=v[k].x+v[k].y; time=(v[k].x+v[k].y)/25.0; cout<<'0'<<"->"<"; tag=next2(k,w); while(tag!=0){ num_of_station++; visited[tag]=true; cout<"; w=w+v[tag].weight; time=time+(fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y))/25.0; if(time+(v[t

52、ag].x+v[tag].y)/25.0+(num_of_station+1)/6.0<=6){ distance=distance+fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y); k=tag; tag=next2(tag,w); }else{ time=time-(fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y))/25.0; break; } } time=time+(v[k].x+v[k].y)/25.0+(num

53、_of_station+1)/6.0; distance=distance+v[k].x+v[k].y; cout<<'0'<<" "<>

54、v[i].num>>v[i].x>>v[i].y>>v[i].weight; cout< #include #include

55、h> #define M 1000 using namespace std; struct node{ int x; int y; int num; float weight; }; node v[31]; int mindis[31]; bool vd[31]; void create(ifstream &in,int n){ int i; for(i=0;i>v[i].num>>v[i].x>>v[i].y>>v[i].weight; cout<

56、("<

57、 int k,min=M,tag=0; float w; for(int i=1;i<31;i++) { if(vd[i]==false&&d(v[0],v[i])w) { k=i; w=v[i].weight; tag=1; } } if(tag) r

58、eturn k; else return 0; } int next2(int k,float w) { int min=M,tag=0,m,i; for(i=1;i<31;i++) { if(vd[i]==false&&d(v[k],v[i])v[k].x&&v[i].y>v[k].y) { min=d(v[k],v[i]); m=i; tag=1; } if(vd[i]

59、==false&&d(v[k],v[i])==min&&w+v[i].weight<=25&&v[i].weight>v[m].weight&&v[i].x>v[k].x&&v[i].y>v[k].y) { m=i;tag=1; } } if(tag) return m; else return 0; } void way() { int k; float w; k=next1(); while(k!=0) { float time,money; int num_of_station=0,dis

60、tance,tag; vd[k]=true; w=v[k].weight; distance=v[k].x+v[k].y; money=3.0*w*distance; time=(v[k].x+v[k].y)/20.0; cout<<'0'<<"->"<"; tag=next2(k,w); while(tag!=0) { num_of_station++; vd[tag]=true; cout<"; w=w+v[tag].weight;

61、 time=time+(d(v[k],v[tag]))/20.0; if(time+(v[tag].x+v[tag].y)/20.0+(num_of_station+1)/6.0<=6){ distance=distance+d(v[k],v[tag]); money=money+3.0*distance*v[tag].weight; k=tag; tag=next2(tag,w); } else { time=time-(fabs(v[k].x-v[tag].x)+fabs(v[k].y-v[tag].y))/20.0;

62、 break;} } time=time+(v[k].x+v[k].y)/30.0+(num_of_station+1)/6.0; distance=distance+v[k].x+v[k].y; money=money+(v[k].x+v[k].y)*2.0; cout<<'0'<<" "<