數(shù)學建模：快遞公司送貨策略

1、-PAGE . z.2012年第九屆北數(shù)學建模聯(lián)賽承 諾 書我們仔細閱讀了第九屆北數(shù)學建模聯(lián)賽的競賽規(guī)則。我們完全明白，在競賽開場后參賽隊員不能以任何方式包括、電子、網上咨詢等與本隊以外的任何人包括指導教師研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其它公開的資料包括網上查到的資料，必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們愿意承當由此引起的一切后果。我們的參賽報名號為： 2394參賽組別研究生或本科或?？疲罕究平M參賽隊員 (簽名) ：隊員

2、1：鞠珊隊員2：夏逸凡隊員3：胡思想獲獎證書郵寄地址：工程學院數(shù)理學院教2-5132012年第九屆北數(shù)學建模聯(lián)賽編 號 專 用 頁參賽隊伍的參賽：請各個參賽隊提前填寫好：競賽統(tǒng)一編號由競賽組委會送至評委團前編號：競賽評閱編號由競賽評委團評閱前進展編號：題目 快遞公司送貨策略摘要本文針對快遞公司送貨策略的優(yōu)化問題進展研究，重點放在給該快遞公司提供一個合理的送貨策略；在一些特殊條件的限制下，給該公司提供一個費用最省的送貨策略。對于問題一，我們通過運送總距離最短目標函數(shù)首先建立了模型0-1整數(shù)線性規(guī)劃模型。在給定送貨地點和給定送貨量和送貨時間的約束條件下，結合最近插入法和最正確匹配的原理，將送貨點抽

3、象為一個點頂點，由于街道和坐標軸平行，即任意兩頂點之間都有路，且任意兩點間的距離為這兩點橫縱坐標差的絕對值之和。如兩點，則權值為。在此根底上,運用矩形，將整個區(qū)域分成5個區(qū)域，以選擇的點的送貨質量之和小于25kg且距離盡可能小的點的集合作為一個區(qū)域。依次來分配業(yè)務員的送貨地點。通過我們的計算，在不考慮時間的情況下，我們求得一個人完成任務的運送路線為8條，由于工作時間的限制，求出了完成任務所需的最少業(yè)務員為5人，最短總路程為。對于問題二，我們借助于問題一求解出來的路線，運用圖論中最小生成樹的原理，以費用最省為目標函數(shù)建立數(shù)學模型。通過TSP模型在滿足約束條件的前提下求出最短距離，再對所求解方案進

4、展優(yōu)化修改，從而我們求得問題二的最省費用為。關鍵詞 0-1整體線性規(guī)劃 最近插入法 最小生成樹TSP模型 e*cel一、問題重述1.1背景分析目前，快遞行業(yè)正蓬勃開展，為我們的生活帶來更多方便。一般地，所有快件到達*地后，先集中存放在總部，然后由業(yè)務員分別進展派送；對于快遞公司，為了保證快件能夠在指定的時間送達目的地，必須有足夠的業(yè)務員進展送貨，但是，太多的業(yè)務員意味著更多的派送費用。1.2問題重述假定所有快件在早上7點鐘到達，早上9點鐘開場派送，要求于當天17點之前必須派送完畢，每個業(yè)務員每天平均工作時間不超過6小時，在每個送貨點停留的時間為10分鐘，途中速度為25km/h，每次出發(fā)最多能帶

5、25千克的重量。為了計算方便，我們將快件一律用重量來衡量，平均每天收到總重量為184.5千克，公司總部位于坐標原點處如圖2，每個送貨點的位置和快件重量見下表，并且假設送貨運行路線均為平行于坐標軸的折線。問題1：請你運用有關數(shù)學建模的知識，給該公司提供一個合理的送貨策略即需要多少業(yè)務員，每個業(yè)務員的運行線路，以及總的運行公里數(shù)；問題2：如果業(yè)務員攜帶快件時的速度是20km/h，獲得酬金3元/kmkg；而不攜帶快件時的速度是30km/h，酬金2元/km，請為公司設計一個費用最省的策略。送貨點快件量T(kg)坐標(km)送貨點快件量T(kg)坐標(km)*y*y1832163.521628.2151

6、75.86183654187.5111745.547197.815126308153.419954.5311216.222577.279226.821082.396232.427991.4102247.61519106.5140259.61514114.1173261020171212.714627122113135.8129286.02420143.81012298.12516204.6714304.22818點的分布如下列圖：二、問題分析2.1對于問題一的分析問題一，我們以運送總距離最短為目標函數(shù)建立01規(guī)劃數(shù)學模型。對于本問題，有時間和重量兩個約束條件，我們優(yōu)先考慮重量。，所以至少要有8

7、個區(qū)域。表中數(shù)據的分析最大載重量重駛時速地中的平均速度重駛酬金業(yè)務員工作時間上限空駛時速每個送貨點停留時間空駛酬金備注1.快件一律用重量來衡量2.假定街道方向平行于坐標軸然而，從題目中我們很明顯的能夠得知一個業(yè)務員要運送很屢次，而運送每次的路線即是我們所要確立的對于完成該任務運送路線。由于每個業(yè)務員的工作量有時間限制，于是我們又將時間考慮在，此時就需要增加業(yè)務員去完成任務，在此條件下所需的業(yè)務員就是完成該任務所需的最少業(yè)務員。對于運送路線確實定，我們主要分兩步進展，一是每條路線上的目的地，二是經過這些目的地的先后順序。對于每條路線上的目的地確實定，我們根據實際情況的需要，定義了最近插入法在滿足

8、約束條件的前提下，在一次運送過程中，下一目標點確實定要離上一目標點最近。經過我們的分析，我們分別考慮了從最近點和最遠點出發(fā)的送貨路線，經過我們的求解比擬可知，從最近點出發(fā)的送貨路線較優(yōu)，于是我們選擇了從最近點出發(fā)的送貨路線。在此方法下我們通過MATLAB編程，找出了每條路線所經過的目的地。對于經過每條路線中目的地的先后順序，我們采用了TSP算法，借助于計算機輔助計算，通過MATLAB編程找出了經過它們的最短路，也就是經過他們的先后順序，使業(yè)務員用最少的時間完成一次運送，為下一次的運送節(jié)約了時間，可是業(yè)務員的工作時間最大化，從而只需較少的業(yè)務員即可完成任務。2.2問題二的分析問題二，業(yè)務員的速度

9、改變，分成攜帶快件和不攜帶兩種情況下的具有不同的速度，分別為20km/h,30km/h,且業(yè)務員的薪酬與其工作過程中的行走的總路程有關。我們借助于第一問求解出送貨路線的根底上，以運費最省為目標函數(shù)建立數(shù)學模型。由于問題一我們運送路線的安排都是最短的，而問題二只是對于速度這一約束條件進展了改變，運行的路線是沒有變化的，所以我們根據時間要求，在問題一的根底上，對業(yè)務員的送貨路線進展了調整。經過我們的分析，以費用最省建立目標函數(shù)，建立動態(tài)規(guī)劃數(shù)學模型，每人工作時間不超過6小時且每次出發(fā)最多只帶25千克的重量，列出目標函數(shù)和約束條件，來找出每條路線的送貨點。三、模型假設結合此題的實際，為了確保模型求解

10、的準確性和合理性，我們排除了一些位置因素的干擾，提出以下幾點假設：1、每個業(yè)務員每天的工作時間不超過6個小時，且送完貨后必須再回公司報到。2、假設以送貨運行路線均為平行于坐標軸的折線而不是直線。3、運貨途中快件沒有任何損壞，并且業(yè)務員的運送過程也十分平安，沒有堵車、天氣等問題，即送貨過程非常順利。4、如果離*一點最近的點不止一個，這時我們要從快件的量出發(fā)，選取加上此快件量最接近25千克而不能超過25千克的目的地。5、各個業(yè)務員之間的快件運送過程是相互獨立的，互不影響。6、假設每個人的路線一旦確定，再不更改。四、符號說明為了便于問題的求解，我們給出以下符號說明：符號說明兩質點的橫縱坐標一個區(qū)域經

11、過的地方數(shù)一個區(qū)域所用的時間min總的所用的工作時間min兩質點之間的距離總的路程km業(yè)務員每天送貨的平均速度v=km/min1 在第i條路線上業(yè)務員向第j個送貨點送快件0 在第i條路線上業(yè)務員不向第j個送貨點送快件1 第i條路線上選擇第j個送貨點是最遠點0 第i條路線上選擇第j個送貨點不是最遠點第j個送貨點坐標第j個送貨點所需快件重量五、模型的建立與求解經過以上的分析和準備，我們將逐步建立以下數(shù)學模型，進一步闡述模型的實際建立過程。5.1問題一的模型建立與求解問題一我們分兩步來完成，首先將30個點進展分組，使每組總的數(shù)之和盡量接近25kg，即一個郵遞員的最大載重量。分組時我們采用先找兩個可行

12、解，然后將兩可行解比擬擬合得到最優(yōu)解的方法。其次，確立組數(shù)之后求每組最優(yōu)路線，通過計算時間，將郵遞員分到相應的組。模型一的建立與求解兩質點的橫縱坐標，各自的差的絕對值的和等價于兩質點之間的距離，即兩點間距離： d都是使用用e*cel得到的距離,即a矩陣見附錄一個區(qū)域所用時間為：所用總時間：根據各個送貨點的分布，以矩形把整個區(qū)域分成5個區(qū)域，在區(qū)域或區(qū)域周圍找出送貨質量和小于25KG且距離盡可能小的點的集合，為一個送貨區(qū)域，由一位業(yè)務員負責送貨。由此，畫出送貨區(qū)域成折線距離的如下列圖：將質量大的進展分組，在不超過25KG的同時將前面質量小的分攤給后面質量大的，將其缺乏25KG的局部補足。形成8條

13、路線。行進次序送貨路線12345678業(yè)務員的送貨路線、送貨區(qū)域、送貨的路程及時間通過e*cel可得行進次序送貨路線問題一路程km時間min170168258139.234198.4456134.453379.262867.273788.8842100.8總計365876模型二的建立與求解考慮一個目標：總運行公里數(shù)最短?？梢杂靡韵路椒ǎ合燃僭O每條線路由不同的業(yè)務員來完成，即需要8名業(yè)務員來完成運送快遞；然后在人數(shù)不變的情況下，此題先從最遠點開場出發(fā)，依次查找臨近點，并考慮總重量小于25kg，以此來劃分區(qū)域，最后利用最近插入法來尋求最優(yōu)解，最后根據表中的時間的約束，對業(yè)務員人數(shù)安排進展重新調整。

14、根據題意每個業(yè)務員工作時間不超過6小時，又因為184.5/25=7.38；即派送這些快件至少需要8個業(yè)務員。因此問題一只需滿足兩個條件即可：業(yè)務員工作時間不超過6小時；每條線路上最大載重不超過25kg。由于快遞員從公司出發(fā)最多只能載25kg，因此: 1 在每一條線路上，每一個送貨點只能選擇一次，因此： 2在每條線路上只有一個最遠點，即： 3一條線路上至少有一個貨點， 4業(yè)務員在每個貨點停留10min，而業(yè)務員每天工作不超過6小時，因此： 6因此，此模型滿足路程最短目標函數(shù)，建立如下模型：約束條件為：因為30這個點距原點最遠，因此假設先從30出發(fā)，29是距離30最近的送貨點，而且兩點的快件重量和

15、為12.3kg小于每個人的最大負重，可以繼續(xù)指配。接著28是距離29最近的點，此時三點的快件重量和為18.3kg仍小于25還可以繼續(xù)指配，剩余送貨點中23距離28最近其實距離28最近的點有23,24,26,27四個點，但是結合快遞重量，將其從小到大依次排列，快遞重量大者先選，但需滿足總重量要求，綜合考慮選擇23，同理確定下一個點選擇15，再繼續(xù)擴大，會超出最大限載重，故返回原點，該路線總送貨重量為24.1，所以第一條路線為。用該算法得到的所有路線一?，F(xiàn)在這五個送貨點之間的最優(yōu)訪問路徑的是一個典型單回路問題。可以根據單回路運輸模型TSP求解。一般而言，用比擬法求解TSP模型求解有最鄰近法和最近插

16、入法兩種。由最近插入法比最近鄰點法得到的結果更好，由于已經構成一個子回路，但現(xiàn)在要將28插入，但是28送貨點有3個位子可以插入：1、插入到0和30之間2、插入到30和29之間3、插入到29和0之間。分析比擬，得出插入到0和30之間，增量最小。同理將23和15用最近插入法，可以得出最優(yōu)化路線為。用這種方法可以依次對剩下的七條路線進展優(yōu)化，進而得出所有的優(yōu)化送貨路二。優(yōu)化后優(yōu)化前每個業(yè)務員每天工作不超過6小時的最正確匹配方案，又考慮每個業(yè)務員所經過工作站之間的距離，即：業(yè)務員3和業(yè)務員8的工作可以合并為一個人來做；業(yè)務員4和業(yè)務員7的工作可以合并為一個人來做。業(yè)務員5和業(yè)務員6的工作可以合并為一個

17、人來做。由此得出每位快遞員的送貨路線為：所得列表如下：業(yè)務員編號過站數(shù)所用時間小時總載重量千克總路程千米154.8324.1100233.5424.37634+33.39+1.6322.4+20.768+2845+33.15+2.1824.4+24.258+4254+32.83+2.6623.6+20.854+54合計3024.211845480下列圖為各條路線優(yōu)化前與優(yōu)化后所用時間比擬下列圖為各條路線優(yōu)化前與優(yōu)化后經過路程比擬5.2問題二的模型建立與求解問題一是以路程作為劃分的界限，而問題二就是考慮以費用為主，費用最主要的因素就是重量和路程，根據題意，每個送貨點的送貨的質量是確定的，在確定送

18、貨路線的時候，需要考慮每個業(yè)務員每次的載重量不得超過25Kg，且每個業(yè)務員每天工作量少于6小時即滿足上面論述中需要注意的一些限制條件。要使得快遞公司支出費用最少，則在安排業(yè)務員的路線的時候，需要盡可能使路線短，且載重量在離原點近的時候可以卸載快件。根據問題一的模型一的求解方法，首先把快件的重量按從大到小的順序排列，將排序的前八個送貨點記為重貨點，其次八個為中等點，其余的記為輕貨點。顯然每個送貨點的信件量的大小的分布是隨機分布的。在此，我們考慮到它的總酬金越少則總費用越省，在考慮到重量的根底上，我們建立了以下的模型，來進展改良。因此我們轉向討論它是滿載還是空載的情況。所以*業(yè)務員路線的選擇應遵循

19、：近者優(yōu)先，即應使盡量多的路線的最遠點靠近原點，則必須同時考慮貨物的重量和路程，先把貨物重且近的送貨點送完，依次篩選，最后送貨物輕及遠的，因此我們得到優(yōu)化方案，即以貨物的輕重做參考由近到遠依次篩選。因此，所有業(yè)務員每天的總酬金：可建立動態(tài)規(guī)劃模型如下：我們接下來用問題一的模型進展求解可以求得以下的的路線，同時我們對路線進展進一步的優(yōu)化, 從而可以進展一次優(yōu)化前后比照。從比照分析中我們對詞的前后變動進展分析，通過簡單的軟件進展推斷，再參加限制條件。1、近者優(yōu)先原則。*業(yè)務員最近起始送貨點的選擇直接關系到費用的多少，所以該業(yè)務員在沿途往送貨終點站中應盡量把較近點的快件送完，不讓下一條路線再把較近點

20、作為起始送貨站。2、少走重復路原則。由于在路途相等的條件下，重載費用要比空載費用大得多，因此，盡量讓業(yè)務員空載行走。3、坐標貼近原則。在同一條路線中，離原點較近送貨點的坐標僅次于較遠點的坐標。4、路線較少原則。路線多，一方面，相對最遠點的選擇多，跑的空路多，費用就多；另一方面，過分地強調短暫效益，出動路線多，會引起業(yè)務員的反感，不利于以后的人員控制。根據這一思路，全部路線業(yè)務員的重載費用可表示為：根據上述分析及根本假設，業(yè)務員送貨的費用可以表示如下：重載費用：空載費用：根據題意可知，業(yè)務員在第i條線路運送與不運送貨物，所需時間：所以總約束條件為：時間約束：載重量約束:路線約束：；優(yōu)化前優(yōu)化后路

21、線編號經過站點所用時間小時總負載載重量千克負重路程空載路程總路程千米費用142.566724.8301242687.6253.324.8401454937333.066724.63820581659.8444.266724.65624801761.6543.133314.944852817.6634.424.45436902665.273523.74644902711.5844.922.76628942326.4合計30 = sum(C2:C9) * MERGEFORMAT 30.6334 = sum(D2:D9) * MERGEFORMAT 184.5 = sum(E2:E9) * MERG

22、EFORMAT 374 = sum(F2:F9) * MERGEFORMAT 186560 = sum(H2:H9) * MERGEFORMAT 13586.7由以上分析知，第一條路線和第二條路線可以由一名業(yè)務員來完成，其余每條路線分別由一名業(yè)務員運送，所以總共需要7名業(yè)務員。在以上方案中，公司每天付給業(yè)務員的總薪金為：13586.7。六、模型的評價與改良6.1模型的優(yōu)點1、模型一給出了業(yè)務員的調配方案，便于指導工作。2、兩個問題中所建的模型將多目標規(guī)劃問題轉化為單目標0-1規(guī)劃問題求解，減少了運算量。3、此模型在業(yè)務員的調配中利用了最有匹配原理，減少了問題的時間復雜度。4、此模型的方法和思想

23、對其他類型也適，便于推廣到其他領域。5、問題中的模型都通過最近插入法，來進展優(yōu)化，以改變其條件，從而到達最優(yōu)解。6、問題一中所建兩個模型，來進展比照，從而找出更加簡單且更好的結果。6.2模型的缺點1、本模型問題二沒有充分利用問題一的結論進展相關的靈敏度分析，而是重新建立相對穩(wěn)定的模型求解，因此增加了問題的繁瑣程度。2、模型給出的約束條件也有不太現(xiàn)實的地方，對街道的方向和客戶的快件量的假設也有待進一步改良。3、各個業(yè)務員的工作時間安排不甚合理，這需要進一步改良。七、模型的推廣1、本模型不但適合于快遞公司送貨問題，還是用于一般的送貨以及運輸問題只需要稍微改動模型即可。 2、建模的方法和思想可以推廣

24、到其他類型。3、模型方便直觀，可以在很多中實現(xiàn)運用。八、參考文獻1啟源 金星 葉俊，數(shù)學建模第三版，：高等教育，2006年2 基于matlab 動態(tài)規(guī)劃中最短路線的實現(xiàn)程序J電腦學習施益昌、賢斌、自立。3 Lingowenku.baidu./view/3bef9888d0d233d4b14e697e.html4 袁新生、邵大宏、郁時煉編，LINGO和E*cel在數(shù)學建模中的應用，科學，2007.1九、附錄附錄問題一中TSP算法求解路線即經過目的地的先后順序：%運用tsp算法求的任一回路中各點的先后順序，是總和最小；function y=tsp(hl)an=*lsread(3.*ls);m=si

25、ze(hl,2); n=hl;for i=1:m-2for j=i+1:m-1 i0=hl(i);j0=hl(j);i1=hl(i+1);j1=hl(j+1); an1=an(i0,j0)+an(i1,j1); an2=an(i0,i1)+an(j0,j1);if an1an2 n(i+1)=hl(j); n(j)=hl(i+1);n(j+1)=hl(j);endendendy=n;附錄問題二中最省費用的計算：%此程序根據用TSP算法求出的各條回路中的最短回路共八條；%在第二問的條件下求出各條的路走完所需的時間及費用；%s_t(i)用來表示走完第i條回路所需的時間；%cost(i)用來表示走完

26、第i條回路的費用；w=cell(8,1);w1,1=1 2 4 5 6 1;k(1)=24;w2,1=1 3 14 8 7 1;k(2)=24.2;w3,1=1 11 13 9 10 1 ;k(3)=22.9;w4,1=1 17 18 21 15 1;k(4)=17.7;w5,1=1 23 22 24 16 12 1;k(5)=22.9;w6,1=1 20 26 25 1;k(6)=25;w7,1=1 19 27 29 1;k(7)=23.5;w8,1=1 28 30 31 1;k(8)=24.3;T=*lsread(1.*ls,j3:j33);V=*lsread(3.*ls);for i=1

27、:8 m=size(wi,1,2);an1=0;an2=0;an3=0;an=k(i);for j=1:m-2 s=wi,1(j);t=wi,1(j+1); an1=an1+V(s,t); an2=V(wi,1(1,(m-1),1); t1=1/6*(m-2); t2=an1/20;t3=an2/30; s_t(i,1)=t1+t2+t3; %求得每條的時間； an=an-T(wi,1(1,j); an3=an3+(an)*3*V(wi,1(1,j),wi,1(1,j+1); s_s(i,1)=an1+an2;end cost(i,1)=an3+an2*2; %求得每條的花費；endfor i=1:8 disp (第,num2str(i),條回路為：,num2str(wi,1), 時間為：,num2str(s_t(i,1), 花費為：,num2str(cost(i,1); disp(.);endss_t=sum(s_t);s_c=sum(cost);ss_s=sum(s_s);disp (這八條路線的總時間為：,num2str(ss_t), 總費用為：,num2str(s_c), 總路程為：,num2str(ss_s);送貨點快件量T坐標(km)*Y91.4102*82.396*19.8232.4279*6308*153.4199163.5216143.81012