畢業(yè)設(shè)計(jì)快遞公司送貨策略數(shù)學(xué)建模

1、2009年大學(xué)生數(shù)學(xué)建模競賽論文題目：參賽人1：參賽人2：參賽人3：快遞公司送貨策略（b題）姓名學(xué)院班級姓名學(xué)院班級姓名學(xué)院班級論文編號:學(xué)校統(tǒng)一編號,個人不得填寫本文是關(guān)丁運(yùn)輸問題的優(yōu)化設(shè)計(jì)問題。該題我們的主要解題思路分三個階段：第一階段：我們先根據(jù)題設(shè)條件和基本假設(shè)畫出該題的圖。第二階段，我們根據(jù)圖和點(diǎn)的位置關(guān)系結(jié)合題設(shè)，歸納出一些最基木的確定路 線的原則：在仔細(xì)分析該題后，我們認(rèn)為，該題為一個單目標(biāo)規(guī)劃題。我們先拋開不攜帶 快件時費(fèi)用，若要把所有的郵件送到客戶手中，只耍我們能夠保證不攜帶快件路 線最小，則所花費(fèi)的時間和費(fèi)用都是最小，因此解題的關(guān)鍵在于找出一個調(diào)度方 案，使不攜帶快件的路線

2、最少。笫三階段則是編制程序階段，我們結(jié)合下山法住店搜索，并引進(jìn)隨機(jī)生成器， 在出現(xiàn)后繼點(diǎn)權(quán)值相等難以判斷以那點(diǎn)繼續(xù)搜索時，由隨機(jī)生成器確定。為了讓 算法更接近人的思維，我們讓更靠近都父點(diǎn)的了點(diǎn)有更高的幾率被作為卜一個將 去的垃圾點(diǎn)，這也與我們的算法原則對應(yīng)。問題的解答如下：求得需要六個業(yè)務(wù)員；求的所需的總費(fèi)用為1404. 86元；所需時間為2& 12小時。路線分配圖見正一文?？爝f公司送貨問題的解決一、問題的重述目前，快遞行業(yè)正蓬勃發(fā)展，為我們的生活帶來更多方便。一般地，所有快 件到達(dá)某地后，集中存放在總部，然后由業(yè)務(wù)員分別進(jìn)行派送；對于快遞公司， 為了保證快件能夠在指定的時間內(nèi)送達(dá)口的

3、地，必須有足夠的業(yè)務(wù)員進(jìn)行送貨， 但是，太多的業(yè)務(wù)員意味著更多的派送費(fèi)用。假定所冇快件在早上7點(diǎn)鐘到達(dá)，早上9點(diǎn)鐘開始派送，要求與當(dāng)天17點(diǎn)z 前必須派送完畢，每個業(yè)務(wù)員每天平均工作時間不超過6小時，在每個送貨點(diǎn)停 留的時間為10分鐘，途中速度為25km/h,每次出發(fā)最多能帶25千克的重量。為 了計(jì)算方便，我們將快件一律用重量來衡量，平均每天收到總重量為184.5千克, 公司總部位于坐標(biāo)原點(diǎn)，每個送貨點(diǎn)的位置和快件重量如下表所示，并且假設(shè)街 道平行丁坐標(biāo)軸方向。1. 請你運(yùn)用有關(guān)數(shù)學(xué)建模的知識，給該公司提供一個合理的送貨策略(需 要多少業(yè)務(wù)員，每個業(yè)務(wù)員的運(yùn)行線路，以及總的運(yùn)行公里數(shù))。2.

4、如果業(yè)務(wù)員負(fù)重時的速度是20km/h,獲得酬金是3元/kmkg；而不攜帶 快件時的速度是30km/h,酬金是2元/km,請為公司設(shè)計(jì)一個費(fèi)用最省 的策略。送貨點(diǎn)快件量t坐標(biāo)(km)送貨點(diǎn)快件量t坐標(biāo)(km)xyxy1832163.521628.215175.86183654187.5111745.547197.815126308153.419954.5311326.222577.279226.821082.396232.427991.4102247.61519106.5140259.61514114. 1173261020171212.714627122113135.8129286.02420

5、143.8101229& 12516204.6714304.22818點(diǎn)的分布如下圖、基本假設(shè)1. 送貨人員路上的拐彎時間，意外事故耽擱的時間忽略2. 所有的貨物必須在當(dāng)天及吋送完，不允許滯留。3. 工作時間內(nèi)不堵車4. 在每個送貨點(diǎn)停留的時間都為10分三、基本變量，符號和用語|a|表示a點(diǎn)到原點(diǎn)的距離，恒正|b| 表示b點(diǎn)到原點(diǎn)的距離，恒正|a-b|表示a, b兩點(diǎn)之間的距離，恒正ta表示a點(diǎn)所在地的快件量spend花費(fèi)錢的數(shù)量time花費(fèi)的時間序數(shù)號所在點(diǎn)的編號父點(diǎn)本點(diǎn)的上一點(diǎn)了點(diǎn)木點(diǎn)的卜一點(diǎn)四、問題分析和數(shù)學(xué)模型的建立送貨問題最終可以歸結(jié)為最優(yōu)路徑

6、搜索問題，但注意到此圖為森林而不是 樹，不能直接套用krusal, prim等現(xiàn)成算法，于是根據(jù)具體問題設(shè)計(jì)出隨機(jī)下 山法，用計(jì)算模擬搜索，可以搜尋到令人滿意的可行解。先注意到兩點(diǎn)的情況,設(shè)兩點(diǎn)分別為a（xl, yl）,b（x2, y2）。主要有以下兩種情況：4. 1 a> b明顯有先后次序。-遞減狀態(tài)（如圖1）不妨設(shè)xl>x2, yl>y2,不難看出a在b的后方，即a比b遠(yuǎn)。對于前方參考 點(diǎn)0,要將a, b對應(yīng)垃圾點(diǎn)的垃圾全部取回再返回0, 一共有三種方式：4. 2 oaaao, oabao單獨(dú)運(yùn)輸。這種情況下，總的路程消費(fèi)等于不攜帶快件吋（2元/km）與負(fù)

7、重吋 的費(fèi)用（3元/kmkg）的總和。所需的總時問等于業(yè)務(wù)員所走過的總路程與速丿支（負(fù) 重時的速度是20km/h,不攜帶快件時的速度是30kn）/h）的比值再加上在a, b兩點(diǎn) 停留的時間（每個送貨點(diǎn)點(diǎn)上停留了 10分鐘，1/6小時），于是有：spend 二 2*|a| + 3*|a|*ta + 2*|b| + 3*|b|*tbtime 二(|a| +|b|)/20+ (|a| +|b|)/30+l/6*24. 3 oaaabao先遠(yuǎn)點(diǎn)再近點(diǎn)，即先負(fù)載至最遠(yuǎn)處，送完a點(diǎn)后再返冋至b,再冋0點(diǎn)，有：spend 二2*|a| + 2*|a-b|*ta +3*|b|*(ta+tb)+2*|b|tim

8、e = |a+b|/20 + |b1/30+1/6*24. 5 oabaaao先近點(diǎn)在遠(yuǎn)點(diǎn)，即先送b點(diǎn)快件，然后載著a點(diǎn)的快件奔至a點(diǎn)，再冋0點(diǎn), 有：spend = 2*|b| + 2*|a-b|*tb + 3*|a|*(ta+tb)+ 2*|atime = |a|/20 + 1/6*2+|a|/30比較以上三種情況，遠(yuǎn)近點(diǎn)的遍歷順序，可以看出，“先近后遠(yuǎn)”絕對比“先 遠(yuǎn)后近”在花費(fèi)錢的數(shù)量上要少的多，省出部分的錢主要是車載著b點(diǎn)的快件奔 到a點(diǎn)再返冋b點(diǎn)。而乂注意到兩者的時間花費(fèi)是和等的。所以在其余同等的情 況下選擇“先近后遠(yuǎn)”，這也符合人的做法?？紤]到時間上單獨(dú)運(yùn)輸比其余的兩 種運(yùn)輸要大

9、的多，而且花費(fèi)的錢仍不比“先近后遠(yuǎn)”省，所以一般情況卜，不采 用單獨(dú)運(yùn)輸。4.6 a, b兩點(diǎn)沒有明顯先后順序。并鄰狀態(tài)(如圖2)還是一共有二種情況：1 oaaao, oabao單獨(dú)運(yùn)輸。這種情況下，跟a,b兩點(diǎn)冇先后順序屮的情況完全相同，即冇: spend 二 2*|a| + 3*|a|*ta + 2*|b| +3*|b|*tbtime 二(|a| + |b|)/20 +(|a| + |b|)/30+l/6*22. oaaabaospend = 2*|a| + 3*|ab|*ta + 3*|b|*(ta+tb)1time 二(|a| + |ab| + |b|)/20 +(|a| + |a-b

10、|+|b|)/30+ 1/6*23. oabaaaospend = 2*|b| + 3*|ab|*tb +3*|a|*(ta+tb) 2time = (|a| + |a-b| + |b|)/20+|ab|+|b|)/30+ 1/6*2相比zi清晰可見并鄰狀態(tài)卜的單獨(dú)運(yùn)輸所花的費(fèi)用最少，所以在不耍求時間 的情況下對于并鄰兩點(diǎn)，采用單獨(dú)運(yùn)輸?shù)姆绞阶罟?jié)約錢。用式與 &lt ;2>式相減除以1. 8,得到如下判斷式：|a-b|(ta-tb) + (ta+tb)*(|b|-|a|)上式 < 0 時，選 oaaabao;上式 > 0 時, 選 oabaaa

11、o;上式二0時，任意選上述兩路線。4. 7兩點(diǎn)選擇趨勢的討論。(如圖3)由圖屮看到b,c兩點(diǎn)沒冇明顯的先后順序，屈于并鄰點(diǎn)。因?yàn)楫?dāng)業(yè)務(wù)員負(fù)重 時費(fèi)用會成倍的增長，比其不攜帶快件時所花費(fèi)用要大的多，所以排除aabac或 aacab這樣的一次經(jīng)過3點(diǎn)的往返路線，僅選擇b, c中的某一點(diǎn)與a完成此次運(yùn)輸, 將另一點(diǎn)留到下次。那么a點(diǎn)選擇b還是c呢？不妨假設(shè)|b|>|c|,即b點(diǎn)離原點(diǎn)的距離比c點(diǎn)的更遠(yuǎn)，因?yàn)閍在b,c之后，所 以也就是b點(diǎn)離a點(diǎn)更近。這樣，此次的運(yùn)輸我們更趨向于選擇adb,因?yàn)榫瓦@三 點(diǎn)而論，a無論是選b還是c,三點(diǎn)的快件總要送完，所以花費(fèi)的錢是一樣的。但 選擇mb后，

12、下次業(yè)務(wù)員送c點(diǎn)快件時就無需跑的更遠(yuǎn)。五、基于人的心理問題的討論業(yè)務(wù)員在送快件時會選擇先送近點(diǎn)再送遠(yuǎn)點(diǎn)，這與我們算出的一致的。綜上所述，得出搜索的基木原則:1. 在兩點(diǎn)遞減的情況下，不采用單獨(dú)送貨；2. 在其余同等的情況下選擇“先近后遠(yuǎn)”;3. 不要求時間的情況下對于并鄰兩點(diǎn)，采用單獨(dú)送貨的方式最節(jié)約錢；一般 情況下用式<3）作判斷；4o每一次布局和每條線路的搜索不妨由剩下未搜點(diǎn)中的最大值開始。六、計(jì)算機(jī)隨機(jī)搜索算法的編制和實(shí)現(xiàn)根據(jù)上面確立的幾個搜索原則做出相應(yīng)的隨機(jī)算法應(yīng)用計(jì)算機(jī)搜索出最優(yōu)可行 解。七、算法中點(diǎn)的數(shù)據(jù)結(jié)構(gòu)簡述1用數(shù)組表示鏈表結(jié)構(gòu)根據(jù)30個點(diǎn)狀態(tài)做出一個36*5的

13、大數(shù)組,如下表序數(shù)號父占八、子占快件量（kg）權(quán)值19-11. 5820-11. 58.2313-10.66o o ooo oo o ooo oo o oo o ooo oo o ooo oo o o291871. 5& 1300231.34.2規(guī)定，搜索方向曲近到遠(yuǎn)（曲上到下），其中序數(shù)號表示的是當(dāng)前點(diǎn)的位置， 父點(diǎn)即當(dāng)前環(huán)中當(dāng)前點(diǎn)的上點(diǎn)，子點(diǎn)即當(dāng)前環(huán)屮當(dāng)前點(diǎn)的下一點(diǎn)，快件量即表示 該點(diǎn)中要送的快件數(shù)，權(quán)值表示該點(diǎn)被修改過的次數(shù)。一個表與一個固定的布局 （即一個搜索結(jié)果）一一對應(yīng)，稱這樣的表為布局表。算法的最終目的就是要找 到最好的布局表，使得花費(fèi)的錢和時間最少，達(dá)到我們的目的。布局

14、表表示了一 個布局中各點(diǎn)的狀態(tài)，它們的父點(diǎn)和子點(diǎn)以及權(quán)值，這樣就能確定具體的連接路 線。這樣的敘述方式跟鏈表一致，這里是借助數(shù)組來建立鏈表關(guān)系，在搜索數(shù)口 較少的情況下還是可行的。2. 基本信息的數(shù)組存放為了搜索方便，此處將題目給的地理坐標(biāo)數(shù)據(jù)表中各點(diǎn)的具體位置信息用數(shù) 組的形式儲存。用map來表示，map是一個30*20的大矩陣，如map(3, 2)二1就 表示表示點(diǎn)1的x處標(biāo)為3, y坐標(biāo)為2,又如map(27, 9)二23就表示點(diǎn)23的x 坐標(biāo)為27, y坐標(biāo)為9；特別的在沒有的點(diǎn)的地方一律用31來表示，即除了原點(diǎn) map(0, 0)=31,夕卜，在(4, 8)這里也沒冇點(diǎn)，則冇map

15、(4, 8)=31o八、隨機(jī)搜索算法具體敘述1. 基本思想。問題要求搜索出一條最短路線，但又與業(yè)務(wù)員員等問題有所區(qū)別，木問題搜 索的不完全是最優(yōu)回路問題，而更像是單支路覆蓋問題，也是np難問題，沒冇現(xiàn)成的 多項(xiàng)式次數(shù)的算法，所以口行設(shè)計(jì)了一種隨機(jī)搜索算法。基木思想是結(jié)合卜山法 逐點(diǎn)搜索，并嘗試引入隨機(jī)生成器剪枝提高搜索速度，整個算法利用鏈表結(jié)構(gòu)實(shí) 現(xiàn)。2. 算法流程一次布局開始d確定搜索點(diǎn)總集p ,判斷集p非空：若空，則一次布局結(jié) 束；非空，貝ijm=max(|p|),即m為p集中距離原點(diǎn)(0,0)的最遠(yuǎn)點(diǎn)。l二m,。(具體見下面的流程圖，圖4)給定p口:kp僅中iax點(diǎn)n殳不是【l 11*

16、-xm；v父子為o為-1 父子為o o為為o ox ll 0f ii 0v枕佰ill過佑.l尢子巨. m阪 l有子點(diǎn). 粕子點(diǎn)11 立：wrr軻此點(diǎn)縱立.轉(zhuǎn) iitfw point 父點(diǎn)設(shè)亦l(xiāng)匕轉(zhuǎn) new point 子點(diǎn)迂為0片中末點(diǎn)此點(diǎn)録立 若不丑.別的壞中末 點(diǎn)楓.川轉(zhuǎn)此點(diǎn)辻 «h不變.ui 3 找 next loop白己片中點(diǎn) 保持.即 nfv jx»innext new plmflt別的環(huán)中 點(diǎn).苦變 則辻按； 不密址憶 苻.對 lm也為圖4九、問題的搜索結(jié)果1. 在不考慮其他因素的情況下-問題的解答。業(yè)務(wù)員的最優(yōu)路線如卜 （見 圖5）y2. 路徑第一組最短路徑為

17、：06161724第二組最短路徑為：0t18t26t28第三組最短路徑為：0t5t20t25第四組最短路徑為：0t2t4t7t14第五組最短路徑為：0t3t8t13 t19第六組最短路徑為：0152729第七組最短路徑為：012212330第八組最短路徑為：0t5t9t11第九組最短路徑為：0t15t223. 最終送貨路徑經(jīng)計(jì)算需要五個業(yè)務(wù)員即可，其各自的送貨路徑是第一個業(yè)務(wù)員路徑為：0t6t16t17t240t5t20t25 （即走第一、三路徑）第二個業(yè)務(wù)員路徑為：0t12t21923t30 t0t15t22 （即走第七、九路徑）第三個業(yè)務(wù)員路徑為：0t2t4t7t14t0t3t8t13 t19 （即走第四、五路徑）第四個業(yè)務(wù)員路徑為：0t15t27t29t0t5t9t11 （即走第六、八路徑） 第五個業(yè)務(wù)員路徑為：01826-28 （即走第二路徑）4. 結(jié)果總時間2& 12小時，總費(fèi)用1404. 86元十、模型的優(yōu)缺點(diǎn)該模型優(yōu)點(diǎn)是算法簡單，容易實(shí)現(xiàn)，精度特別是后兩個模型的精度不是很高， 十一、模型的改進(jìn)方向1.隨機(jī)生成器的設(shè)計(jì)； 2可以引入專家系統(tǒng)，增強(qiáng)算法的靈活性，更人性化；3. 若用模擬退火法或遺傳算法，能更快地搜到較