數(shù)學建模送貨線路設計問題 答案僅供參考

1、裝訂線第九屆西安電子科技學數(shù)學建模競賽暨全國大學生數(shù)學建模賽選拔賽題目A 年 5 4 日 年 5 4 日 學院員 員 3送貨路線設計問題1、 現(xiàn)今社會網(wǎng)絡越來越普及，網(wǎng)購已成為一種常見的消費方式，隨之物流行業(yè) 也漸漸興盛個送貨員需要以最快的速度及時將貨物送達且他們往往一人 送多個地方，請設計方案使其耗時最少?，F(xiàn)有一快遞公司圖 1 中的 O 點員需將貨物送至城市內(nèi)多處， 請設計送貨方案，使所用時間最少。該地形圖的示意圖見 1，各點連通信息見 表 3，假定送貨員只能沿這些連通線路行走，而不能走其它任何路線。各件貨物 的相關信息見表 1，50 個位置點的坐標見表 。假定送貨員最大載重 斤，所帶貨物最

2、大體積 方米。送貨員的平均 速度為 24 公里/小時定每件貨物交接花費 3 分鐘簡化起見一地點有 多件貨物也簡單按照每件 3 分鐘交接計算。現(xiàn)在送貨員要將 100 件貨物送到 50 個地點。請完成以下問題。若將 130 號貨物送到指定地點并返回。設計最快完成路線與方式。給出 結(jié)果。要求標出送貨線路。假定該送貨員從早上 8 點上班開始送貨將 130 號貨物的送達時間不 能超過指定時間，請設計最快完成路線與方式。要求標出送貨線路。若不需要考慮所有貨物送達時間限制(包括前 貨物)，現(xiàn)在要將 件貨物全部送到指定地點并返回完成路線與方式送貨線路， 給出送完所有快件的時間于受重量和體積限制貨員可中途返回取

3、貨 不考慮中午休息時間。2、 送貨路線問題可以理解為知起點和終點的圖的遍歷問題的合理優(yōu)化的路 線設計。圖的遍歷問題的指標：路程和到達的時間，貨物的質(zhì)量和體積，以及最大可 以負載的質(zhì)量和體積路線的安排問題中慮所走的路程的最短即為最合理 的優(yōu)化指標。對于問題二要考慮到所到的點的時間的要求是否滿足題意即采用多次分區(qū) 域的假設模型從而找出最優(yōu)的解對于問題三則要考慮到體積和質(zhì)量的雙重影響次到達后找到達到最大的體積和質(zhì)量的點然后返回分析各個步驟中可能存在的不合理因素達到模 型的進一步合理優(yōu)化得到最合理的解。3、 設的（1地點的貨物要一次拿上，即不考慮再以后又經(jīng)過時再帶些貨物 （2到不超過的時間不包括此次在

4、該點交易的時間。所用的距離數(shù)據(jù)都精確到米而時間則精確到同一地點有多件貨物也簡單按照每件 3 分鐘交接計算。說其中 i，j=1、2、350 并且 M=50kg V=14、 立模型一模型二模型三模型四最 徑模型圖 的 遍歷模型多 域最短路多 最短路 始 路 域 起 段 起 模型一模型的立我們?yōu)榱饲蟪龈鱾€點的之間的最短的路徑，使用 算法求解。 Dijkstra 算法是圖論中非常有名的一個算法。圖采用鄰接矩陣的形式描述，（i,j）表示結(jié)點 i 到結(jié)點 j 間的最短距離， 如果沒有直接連通，則為無窮大，計算機中可以用一個很大的數(shù)據(jù)代替（如 matlab 中的 inf但 dijkstra 算法只能求出從結(jié)

5、點 到其它各結(jié)點的最短路徑入這樣 兩個集合 s 和 t，s 是那些已經(jīng)確定了到 i 結(jié)點的最短路徑的結(jié)點，t 為全集 u 和 s 的差集，即那些還未確定最短路徑的結(jié)點。而且 的初值是i 的初值 是 u-i外再引入一個標記數(shù)組 dn中在某一步 dk表示當前從 到 k 的較短路徑，dk的初值為 w（i，k整個算法過程如下：在 t 中選擇一個 最小的結(jié)點 k， k 并入 s，并 t 中去掉，如果 t 為則轉(zhuǎn)到；用 k 結(jié)點和 t 中其余結(jié)點進行一遍比較，如 didk+mki，則 用 dk+mki取代原來的 di，重復；算法結(jié)束，此時 中保存的就是從 i 到 k 結(jié)點的最短路徑。算法就以這樣非常簡單的

6、形式完成了求解，時間復雜度 O(n2)確定了從 i 到其余各結(jié)點的最短路徑。模型的解根據(jù)算法和相鄰的點的距離可以用 求出任意兩點的最短路徑。 使用循環(huán)的結(jié)構求出 各個點之間的最短距離。程序 1 見附錄可以求出 w 和 aa 為最短路徑是的所過的的地點如從 O 開始到其余 個點的 a(0)= 7 4 8 3 15 1 18 12 14 18 13 13 18 21 12 23 21 0 24 22 0 29 17 31 19 0 31 30 25 22 26 23 28 31 38 21 40 36 27 34 37 43 38 41 36 41 40 46 42 40要從 O 點到 16 點則

7、要先到 23 即 0-23-16 要從 O 點到 23 點則要先到 17 即 0-17-23-16 要從 o 點到 17 點則要先到 21 即 O 可以直接到 21 所以從 0 到 16 的最優(yōu)路徑是 0-21-17-23-16 短的距離是 w（0,16）=7493m模型二模型的立由前 30 件貨物可以到達的地點可以知道 i，j= 、14、16、17、21、 23、24、26、27、31、32、34、36、38、39、42、43、45、49。 到點其中共經(jīng)過 21 個點，運送 30 件貨物該 30 件貨物 =50kg = ,所以可以一次把貨物攜帶進行運送。由 T 與 W 關系可知要使所用的時間

8、最小即所走的距離最短。即：T=WV+必須部遍歷回到 點即求出從 O 出發(fā)遍歷這圖的 個點的并回到 o 的最短的距離要距離最短則每一步也要最短 開始找最短的點到達后繼續(xù)找未遍歷的最 短的點則可求出最短的距離。本題要求出回 O 則可以看到兩個開始最短遍歷的點在某點重合即可完成 最短的遍歷。模型的解由圖可以明顯得出距離 O 最近的點是 21 點和 26 點于 32 點到 點的距 離小 點 點的距離為使 點出來的線遍歷右下的點完后再 點出 來的匯合則安排 32 點到 35 點斷開。有程序 2（附錄）可得：0 1 31 1213 2 32 1314 3 34 1416 4 36 1517 5 38 16

9、18 6 39 1721 7 40 1823 8 42 1924 9 43 2026 10 45 2127 11 49 22遍歷節(jié)點路線是：0-2-4-40-45-49-42-43-38-36-39-27-31-26-0最優(yōu)的路線是： 0-2-3-0-45-42-49-42-43-38-36-27-39-27-31-26-0 總路程是：W=53787m 最優(yōu)時間是：T=模型的立由第一個模型建立的可以求出到 24 時所用的時間是:可知到 24 點的時間是：t(24)=由表可知必須在 之前把貨物送到 24 即 模型一不適用于問題二 的求解.由下圖 3 可知： 點由于右邊的點的地點需要的時間要比左邊

10、的早以先分兩個階段先走左邊 后走右邊即先走圈內(nèi)的元素由程序 3（附錄）可得： 45 點 9 = T 到個點的間最大 模型的求解段對四個階段分別求出到達的時間，由程序 4附錄）可知 分 4 個階段1. 從 0 出發(fā)經(jīng)過 、18 到 24。 滿足 t1 的條件故路線為：3241813242. 從 24 出發(fā)經(jīng)過 、34、40 到 45。 滿足 t故路線為：24-31-34-40-453. 從 45 出發(fā)經(jīng)過 、42、43 到 49。 滿足 t所以路線為：45-42-49-43-382 313 344 405 454. 從 38 出發(fā)經(jīng)過 、16、17、21、23、26、27、32、36、39 到

11、O。 10 368 2711 397 265 214 176 239 32 3 423 16 5 492 14 4 43滿足 t4 2 38故路線為：38-36-27-39-27-3-32-16-14-21-0所以總的遍歷點順序是：0-4-40-45-42-49-43-38-36-27-39-26-2-14-0總時間是 T=總距離是 W=57912m最優(yōu)路線是：0-49-42-43-38-36-27-39-27-3-32-23-16-14-21-0到每個點的時間見附錄模型建立本題中要遍歷所有的 個點但由于=147kg 而M50kg,V1 M50kg 和 V50)|(V1);% 順 ) 總 ) 所： ) 第 ) (M50)|(V1);% 順 ) 總 ) 所： ) 第 ) (M50)|(V1)