快遞員的送貨策略問題

1、 2015高教社杯全國大學生數學建模競賽承 諾 書我們仔細閱讀了全國大學生數學建模競賽章程和全國大學生數學建模競賽參賽規(guī)則（以下簡稱為“競賽章程和參賽規(guī)則”，可從全國大學生數學建模競賽網站下載）我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關的問題我們知道，抄襲別人的成果是違反競賽章程和參賽規(guī)則的，如果引用別人的成果或其他公開的資料（包括網上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出我們鄭重承諾，嚴格遵守競賽章程和參賽規(guī)則，以保證競賽的公正、公平性如有違反競賽章程和參賽規(guī)則的

2、行為，我們將受到嚴肅處理我們授權全國大學生數學建模競賽組委會，可將我們的論文以任何形式進行公開展示（包括進行網上公示，在書籍、期刊和其他媒體進行正式或非正式發(fā)表等）我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）： A 我們的參賽報名號為（如果賽區(qū)設置報名號的話）： A06007001 所屬學校（請?zhí)顚懲暾娜?北華大學 參賽隊員 (打印并簽名) ：1. 2. 3. 指導教師或指導教師組負責人 (打印并簽名)： （論文紙質版與電子版中的以上信息必須一致，只是電子版中無需簽名以上內容請仔細核對，提交后將不再允許做任何修改如填寫錯誤，論文可能被取消評獎資格） 日期： 2015 年 9

3、月 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：2015高教社杯全國大學生數學建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）：快遞員的送貨策略問題摘要 在貨物運輸的過程中，合理的選擇貨物路線很重要，他不僅可以加快配送速度，提高服務質量，還可以降低配送成本，增加經濟效益本文構建貨物路線的規(guī)劃模型，運用圖論思想，Dijkstra算法，經典Floyd算法，利用lingo與MATLAB進行編程求解，給出了最佳的送貨路線，另外將貨物的分配問題轉

4、化成旅行商推銷問題，進行編程求解；根據運輸路線策略中的成組法，用射線旋轉法進行區(qū)域劃分，以送貨員最大承受力為50公斤，貨物體積不大于1立方米為依據，利用整體規(guī)劃進行區(qū)域規(guī)劃，從而得到最優(yōu)化模型問題一以最快完成送貨任務并返回倉庫的路線與方式，分析題知盡可能地縮短路徑可以達到盡快完成任務的目標在題目所給的各個點的坐標基礎上，為確定最短路徑，先應用Dijkstra算法求解出任意兩點的直線距離，運用Floyd算法，借用MATLAB求出任意兩點之間的最短距離，應用lingo軟件進行優(yōu)化求解，求得遍歷路程結果為125499.5m，時間為493.7min問題二在問題一的前提下進行了對送貨時重量和體積的約束，

5、經過分析，快遞員需要在送貨途中返回一次倉庫，進行補貨根據問題一中最小生成樹，根據聚集原則，將區(qū)域分成兩部分，進行分次求解，第一部分路程為67554.8m,時間為261.9min ，第二部分路程為66624.56m，時間為246.8min 關鍵字：Dijkstra算法；經典Floyd算法；0-1規(guī)劃法；最小距離一、問題重述小張是某快遞公司送貨員，其負責送貨的區(qū)域如圖，該區(qū)域包含50個送貨地點，倉庫在圖中O點處送貨時，小張只能沿圖中的道路行進，沒有其他道路可選送貨時，小張的平均行進速度為24公里/小時，每件貨物交接時間3分鐘（如同一地點有多件貨物，交接時間也按每件3分鐘計算）根據某天小張的送貨清單

6、，請你們幫助他解決下列問題：1. 設計最快完成送貨任務并返回倉庫的路線與方式，給出結果并注明送貨路線2. 實際上小張每次送貨時，只能裝載重量不超過50公斤，體積不超過1立方米的貨物這樣，小張不能將全天的貨物一次取走，只能中途返回倉庫取貨在這種情況下，設計最快完成送貨任務并返回倉庫的路線與方式，給出結果并注明送貨路線以上兩種情況都不考慮中午休息時間 圖1 送貨地點示意圖表1：送貨地點坐標編號X坐標（米）Y坐標（米）07750500011245581502154308730314565592041120151155155006815679257175776451522087440323098955

7、635108615183511840442512134758840136235154351461351342015636551401664751156517176550851849358720195635116520694512352194012970225900660523675799024150051338025133202155267165138002760451443528137205975295500561530154401455531667082103210800837033370076553417851820351295040653615330122653743902085387

8、83510145392350110704011815941541510014750421855273543106752595444490959045395064904645853610471450826548462569549150013670501002513875二、 問題分析 在日常生活中購物送貨問題，如何在有效的時間內送到貨物且能最大限度的節(jié)約成本，合理規(guī)劃過程中的最短路線我們需要在考慮題的過程中重點分析各個點的路徑問題，送貨員能承受的重量體積等因素條件下，規(guī)劃處最優(yōu)路線首先我們利用excel處理數據，求出總重量，總體積等數據，在求出每條路的總距離，對于送貨員能承受的重量等情況，我們利

9、用射線旋轉法進行劃分，0-1型規(guī)劃法對問題進行巧妙的轉化，從而求解 對于問題一：不考慮裝載重量和物體體積，最佳運送方案就為找出一條走遍所有送貨點然后返回出發(fā)點的最短路線根據表1和表2所給出的送貨點位置信息即可計算出所有直通點的距離根據以上數據即可利用Floyd算法算出任意兩點間的距離矩陣然后運用lingo軟件就可以得到最優(yōu)路線 對于問題二：由于質量和體積的約束，綜合總的質量與體積得出送貨員將貨物的分配問題轉化成旅行商推銷問題，進行編程求解，根據運輸路線策略中的成組法，用射線旋轉法進行區(qū)域劃分，以送貨員最大承受力為50公斤，貨物體積不大于1立方米為依據，利用整體規(guī)劃進行區(qū)域規(guī)劃，從而得到最優(yōu)化模

10、型三、問題假設1. 假設送貨員只能沿如圖路線圖行駛，不能走其他的任何路線2. 在聯通線路中，送貨員可自由選擇路口3. 交接貨物只需要3分鐘，行進速度總是24公里/小時，路上行進暢通無意外阻礙4. 如果要從任意一點出發(fā)前往另一點，送貨員必然選擇最短路徑5. 送貨員路程中都是勻速行走6. 不考慮送貨員中午休息及中途休息四、符號說明表示送貨點i到送貨點j之間的距離表示最短距離和表示矩陣中任意的位置，0-1決策變量 ,表示送貨的路線表示經過路程所花費的總時間表示路程表示從 個點到 點運送貨物的質量表示從 個點到 點運送貨物的體積五、模型建立與求解5.1模型分析 不考慮裝載重量和物體體積，所以最佳運送方

11、案就為找出一條走遍所有送貨點然后返回出發(fā)點的最短路線根據表1和表2所給出的送貨點位置信息即可計算出所有直通點的距離（程序見附錄3）根據以上所得數據，即可采用0-1規(guī)劃模型尋找送貨點間的最短路徑 圖2坐標點之間的關系5.2模型的建立 利用圖論思想，將已連接的送貨點一一標明，送貨點抽象為下列圖的頂點任意兩頂點間都有通路講兩點之間的路線權值賦為，兩坐標間的距離這樣送貨點的分布圖就構成了加權網絡圖見圖（2）問題就轉化為在給定加權網絡圖中尋找從原點0出發(fā)滿足做給約束條件下，行遍所有頂點，并再回到0點，使得總權最小 設假最佳送貨路線問題由送貨點1，2，3,n組成，W表示送貨點i到送貨點j之間的 距離決策變

12、量定義為： 1，選擇從送貨點i到送貨點j, X= 0, 否則，其線性（整數）規(guī)劃模型為： 引入0-1決策變量xij=0，最短路經過?。╥,j），xij=1，最短路不經過弧（i,j）考慮最短路徑唯一和，必須從O點出發(fā)并反回O作為約束條件目標函數是路徑上所有弧長度之和最小，我們建立0-1規(guī)劃模型： 1.上式目標函數（1）給出了送貨路線的總長度2.約束（2）保證由送貨點i到送貨點j，3.約束（3）保證i只能到一個送貨點 4.（4）式保證了經過全部送貨點在以上約束下用MATLAB和lingo軟件求解最佳路線5.3模型的求解（1）求任意兩點之間的直線距離： 根據Dijkstra算法，并運用MATLAB，

13、可求出任意兩點間的直線距離（程序見附錄3，結果見附錄4） 從中選出可行解：序號地點1地點2距離1062182.022081796.9430151392.0641401417.6852121958.0962363536.417351294.3184212152.549521916.28105122863.78116222103.69127261948.93138101823.91148152191.74158464775.74169202197.641710201774.511811233568.811911421971.382012401756.772113411325.68221426109

14、7.862316141885.92416381966.222516394154.592617233102.762717422351.722818331630.782919201311.8730194811143120101774.51322142152.543321234987.053422151537.033522182324.753623333043.493724301252.943824505004.543925351945.514025432681.354126271287.494227131017.894327394997.62442851968.25452865917.944629

15、221067.76473077823.324830362292.64493122178056513263113.465232383455.75333173217.015433181630.785534372618.44563565909.555735282059.375836302292.645937461537.426038312258.646139212366.036239442601.926339492735.426440165756.576540321456.796640504805.786741131325.696841493758.516942111971

16、.38704234917.6771436534273734392607.687443102195.727544332090.057645291779.927746173182.467846292203.927947332331.228048371409.73814941494.138250164235.48350262860.98（2）求任意兩點間的最短距離： 運用經典Floyd算法，并借助MATLAB，可解出任意兩點間的最短距離（程序見附錄5，結果見附錄6）（3）求快遞員遍歷的最短距離： lingo是一種用來解規(guī)劃的常用軟件，故本問采用lingo進行求解（程序見附錄

17、7）由lingo計算出的結果可以給出送貨路線如下：015810209194837461734421123334744182229453138161472641131750243036253123214021449394325352860總路程為125499.5m,時間為493.7min5.4問題二模型的建立與求解1 模型建立： ; ; ; ； ； ； ；2 模型的求解：送貨員將60個包裹最快送到50個指定地點，經過計算60個包裹的總質量為87.73公斤，總體積為1.7588立方米，送貨員每次攜帶貨物質量不能超過50公斤，體積不能超過1立方米，可以將路線分成兩個片區(qū)根據最小生成樹，和聚集原則還有

18、根據分組，我們在每一個最短區(qū)域根據分動態(tài)線性規(guī)劃尋找最短最佳路線，根據運籌學中滿載率的規(guī)定為80%-90%，為使用時時間最短，兩個子區(qū)域區(qū)域區(qū)分如下：區(qū)域10，4，8，9，10，11，15，17，18，19，20，21，22，23，29，31，33，34，37，39，42，43，44，45，46，47，48，49區(qū)域20，1，2，3，5，6，7，12，13，14，16，24，25，26，27，28，30，32，35，36，38，40，41，50根據遍歷程序，解得區(qū)域一的最短遍歷路徑，即路徑1為：01581043920194837461742344211232144939443347331822

19、294529223122150；第一區(qū)域路程為67554.8m，用時261.9min解得區(qū)域二的最短路徑，即路徑2為：0635253528535236302450267262713411327261416383240124013260 第二區(qū)域路程為66624.56m，時間為243.8 min 六、模型的優(yōu)缺及評價6.1模型的評價在現實的物流配送中，人們多數是按照經驗去制定送貨路線而此模型在運用滿載率原理對送貨區(qū)域進行合理化而科學劃分的基礎上，用0-1整數規(guī)劃的方法對路線進行優(yōu)化，得到最優(yōu)的送貨路線和最優(yōu)的分配方案，非常貼近生活實際對現實的物流派送有較強的指導意義以此，物流公司或其他機構可以根

20、據這個采用劃分區(qū)域，進行線性規(guī)劃的方法提高自己的送貨情況的路徑優(yōu)化，可以提高自己的效率，降低成本，提高企業(yè)競爭率有利于降低社會交易話的成本6.2模型優(yōu)點1、模型是從簡單到復雜一步一步的進行的，使得更加貼近實際2、本文模型簡單，算法直觀，容易編程3、本文注重數據的處理和儲存方式，大大提高了規(guī)劃效率6.3模型缺點在建模和編程過程中，使用數據只是現實數據的一種近似值因而得出的可能與現實有一定差距，不過差強人意，理論要求強計算比較復雜，這個模型在現實中運用可能還有一些其他因素影響，所以實際運用中需進一步考慮七、參考文獻1楊丹,趙海濱. MATLAB從入門到精通M.北京:中國鐵道出版社,2013.2.

21、謝金星,薛毅編.優(yōu)化建模與lingoM.北京:清華大學出版社,20053. 薛毅.數學建模M.北京:北京工業(yè)大學出版,20044. 張杰.運籌學模型與實驗M.北京:中國電力出版社,20075. 趙靜.數學建模與數學實驗M.北京:高等教育出版社,20036. 龔劬.圖論與網絡最優(yōu)化算法M.重慶: 重慶大學出版,2009附錄附錄1：表2：道路連通信息序號地點1地點21062083015414052126236735842195210512116221272613810148151584616920171020181123191142201240211341221426231614241638251

22、639261723271742281833291920301948312010322143321233422153522183623333724303824503925354025434126274227134327394428545286462922473074830364931225032151326523238533317543318553437563565735285836305937466038316139216239446339496440166540326640506741136841496942117042347143672438734397443107544337645297

23、7461778462979473380483781494825016835026附錄2表3：送貨清單序號送貨地點重量（公斤）體積（立方米）113.090.0145221.900.0332320.460.0133421.960.0406531.340.0043640.900.0339751.420.0462861.670.0559971.280.05571081.730.03481191.340.043112101.730.011413110.580.029914110.990.024015121.450.020616132.790.030317141.220.034418151.230.039

24、919161.420.005120171.820.034821181.200.059022191.190.025023200.900.030024211.590.005525221.650.025226231.450.008027240.940.031228251.620.049229262.130.037930271.110.026631271.030.049732281.550.020933291.770.029034291.990.002935301.710.004236311.120.019137321.180.028638331.400.045739341.520.011840352

25、.330.015641351.300.042042360.480.048643361.370.027144371.140.002445381.360.018346390.870.004147401.700.049148411.710.014449421.170.016050430.060.050751442.370.030352451.180.013353460.900.034554461.310.024855472.050.059156482.510.025757491.110.042958491.550.058659501.770.056660502.120.0093附錄3： x=7750

26、,12455,15430,14565,1120,15500,7925,7645,7440,8955,8615,840,13475,6235,6135,6365,6475,1765,4935,5635,6945,940,5900,675,15005,13320,7165,6045,13720,5500,15440,6670,10800,3700,1785,12950,15330,4390,7835,2350,11815,5100,1855,10675,4490,3950,4585,1450,4625,1500,10025;y=5000,8150,8730,5920,15115,6815,7175

27、,15220,3230,635,1835,4425,8840,15435,13420,5140,11565,5085,8720,1165,1235,12970,6605,7990,13380,2155,13800,14435,5975,5615,14555,8210,8370,7655,1820,4065,12265,2085,10145,11070,9415,14750,2735,2595,9590,6490,3610,8265,695,13670,13875;distance=zeros(length(x);for i=1:length(x)distance(i,:)=sqrt(x-x(i

28、).2+(y-y(i).2);end附錄405662.1138537.8746876.81812094.2210687.919161.9465662.11303031.0113070.01613303.8912267.136219.3678537.8743031.01102940.12315669.85147807462.2426876.8183070.0162940.123016288.5315190.689159.34612094.2213303.8915669.8516288.5301494.138990.9197959.6943324.7931916.2791294.31416603.

29、4515588.178934.1612182.0294633.7387664.4016757.56110457.139135.9547021.39610220.548551.08210135.411592.086525.8456337.472733.7571796.9427025.4279700.0057615.88613460.8912011.5410954.374528.2728290.06810366.037707.35516463.8315016.2713283.173281.0757390.8619694.5997217.32115249.0513809.0712122.286933

30、.88212197.715211.8713806.1810693.679268.52913178.276893.5641231.4631958.0923116.80913857.1912912.386103.58310544.49579.12411380.0312646.1151255053.2614098.58573.4848228.93110411.211283.395293.6994641.7373916.521392.0586793.2479749.9918237.01411269.99819.8339470.7886687.6646886.4099393.0439864.792642

31、4.8375402.0044235.3985985.60411120.7214142.7812827.2110050.728589.08912061.994665.0437541.5711049510028.87446.4926025.0917244.4554379.5499762.30612376.2410117.0614662.4613170.9213446.793850.0978841.79411321.238945.03415052.7413574.8813009.8410483.1812483.0915097.6115340.92152.539896.43749129.9642449

32、.1896734.6169764.0428692.0349760.5588323.1148358.7397680.86711781.0914773.5414043.47138.8835739.60111047.8811084.25818.5394669.3827472.96513992.9813508.115004.546254.5126057.0836905.2683965.50817798.9216501.7512174.388819.4237739.9359696.1410809.926186.3765666.4912860.9839587.8188977.15610982.951204

33、5.564971.7234608.9324019.2046049.0932516.1183242.549846.78815565.9814440.968721.4122332.5367402.58410407.129070.1310461.098993.4999418.23912265.167066.4175825.0098679.21914330.9513968.065457.5293386.8135785.3118775.428220.4098858.987519.3426583.9394545.2611669.5584643.9754491.96211798.210704.25559.2

34、854842.6778768.98211779.1611002.667893.5426404.7038870.9656759.70612406.3615294.9113421.5613311.6211853.4314602.085283.3914114.8825283.242459.5221618814945.1810236.7810499.365019.8463536.4146390.95114492.9813901.185543.9274448.23810091.0112885.5610873.7213434.0511940.0313067.415145.7025032.3387725.6

35、887946.298354.1687249.6794325.398124.3410518.4313287.6613256.274227.8752735.4168171.5156001.3711417.6833679.3274447.19312119.1211158.154805.79910103.719882.10611956.1412944.313996.7023758.515002.1256315.1611903.0314839.8313102.9912401.810940.7613814.793786.7735833.2177761.9755117.39415749.5514381.81

36、1298.715629.8938094.12310973.7510722.626471.6715058.316999.8184081.6798665.48511696.510630.299077.4187586.4959562.6283456.789085.62111992.8510243.8512015.4610522.411617.397095.78911005.613987.73133236857.9445405.23110247.085319.64810811.3813465.1111229.6114839.8613346.0214243.3310687.9112267.1314780

37、15190.681494.1308527.4649161.9466219.3677462.2429159.3468990.9198527.4640附錄5：a=long; %調用附錄3的建立的long表格n=size(a,1);d=a;for k=1:n for i=:n for j=1:n if d(i,k)+d(k,j)<d(i,j) d(i,j)=d(i,k)+d(k,j); end end endenddisp(d);附錄6：012093.115595.217795.212647.911153.813169.412093.105132.67332.65936.27430.36223

38、.515595.25132.603210.68233.49727.58520.717795.27332.63210.6010433.411927.510720.712647.95936.28233.410433.401494.19324.316500.96038.31916.31294.39139.110633.29426.4218211267.714769.816969.812173.610679.51234413416.710403.412700.614900.610382.68888.54179.91796.912892.716394.818594.8108519356.91396974

39、92.915375.317672.519872.59439.1794513599.63620.814716.617260.519460.59027.1753313187.61172212339.514636.716836.710708.312202.415727.613637.13174.51958.14158.16275.37769.46562.614223.211209.913507.115707.16578.35084.24986.410819.98977.411357.413557.49981.68487.53778.91392.11070114203.116403.113042.71

40、1548.611777.389347091.59471.511671.58384.168904235.47859.611873.514170.716370.710242.311736.415261.65253.811488.714990.817190.811813.813307.9125656707.216496.819998.922198.912113.510619.4162745395.316491.1190352123510801.69307.514962.114246.33783.76080.98280.92152.53646.67171.82929.1916412666.114866

41、.113469.712783.210240.39928.18770.711067.913267.97139.58633.612158.818173.9112287081.910292.514328.815075.15004.58497.815448.917746.119946.19512.78018.613673.211917.88904.511201.713401.78883.77389.6268113205.31019212489.214689.27596.26102.13968.58099.917185.620687.722887.713517.612023.517678.13996.9

42、10231.813733.915933.914537.51385111308.119426.810961.658299039.614062.415556.56257.44709.27383.9108861308611689.611114.88460.210423.51669.65171.77371.75975.37469.46262.66884.611814.214111.416311.41018311677.114195.88832.915142.917440.119640.113511.715005.817667.88091.517177.219691.621891.611458.29964.115618.719131.686693536.4674711769.813263.985506214.513973.117475.219675.214637.213143.115049.46967.85125.38627.410827.494318856.26201.68418.410165.712462.91