蘭州交通大學2009年大學生數學建摸競賽論文題目： 快遞公司送貨策略（B題）參賽人1： 姓名 趙 杰學院 數理與軟件工程學院班級 軟件工程071班參賽人2： 姓名 張書呈學院 數理與軟件工程學院班級 軟件工程071班參賽人3： 姓名 國艷松學院 數理與軟件工程學院班級 軟件工程071班學校統(tǒng)一編號，個人不得填寫論文編號： 快遞公司送貨策略(B題)摘 要本文是關于快遞公司在已經收到確定數量的快件的情況下，在需要派送費用最省的情況下，如何確定多少業(yè)務員去派送這些快件的問題。本文建立了一個從兩個方面去解決這個問題的模型，第一: 利用四叉樹柵格索引的方法將客戶所在地劃分成若干個滿足派送快件時間最省的分區(qū)；第二:在每一個小派送區(qū)中選擇一條最佳路徑，使得走這條路徑所花的時間最短。首先我們采用了四叉樹柵格索引的方法對所確定的客戶區(qū)進行分區(qū)，每個區(qū)滿足該區(qū)的所有客戶的快件重量之和小于或等于25kg。區(qū)分好后，再用所求的的目標函數對每一個區(qū)進行優(yōu)化，優(yōu)化的目的就是要讓該區(qū)客戶的快件重量之和盡量接近25kg并且盡量靠近公司所在地。分區(qū)確定好后，必須找出從公司出發(fā)到達某一個區(qū)并把該區(qū)的快件送完再回到公司的最短路徑（即巡回路線最短）。這個問題可以轉化為經典的旅行商問題（TSP）來解決，解決旅行商問題的算法很多，在此我們采用了經典的遺傳算法來確定每一個區(qū)的最佳路徑，具體的實現是利用計算機編程來解決這個問題，路徑確定好后，我們按照行走路徑就可以算出送完所有快件的總時間 24.30小時，即24小時18分鐘。如果按照每一個業(yè)務員的平均工作時間為6個小時來確定工業(yè)務員人數的話，在實際情況下4個業(yè)務員就應該能夠送完所有快件。按照所確定的最短路徑進行總路程長度的計算，得到總的行里路程為482 km。快遞公司送貨策略1 問題的提出 快遞公司一般將收到的快件集中放到總部，然后由業(yè)務員進行派送，派送地點已經明確。每個業(yè)務員工作的平均時間不超過6小時，并且一個業(yè)務員每次出發(fā)所攜帶快件的重量不能超過25kg。公司為了節(jié)約成本，必須要用最少的人在規(guī)定的時間內把所有的快遞送到客戶家中，因此選擇什么樣的派送路線和派遣多少業(yè)務員得尤為重要。本論文試圖從最優(yōu)化的角度，建立起滿足快遞公司選擇恰當數量業(yè)務員的數學模型，借助計算機的高速運算能力和邏輯判斷能力，求出公司派遣的業(yè)務員數量和業(yè)務員的送貨路線。2 問題的分析為了分析問題方便，首先建立坐標系。以快遞公司的總部作為原點O，過原點的水平線OX作為X軸的正方向，過原點垂直于X軸指向正前方的水平線OY作為Y軸建立高斯平面直角坐標系。每個客戶所在地用一個點表示（如圖1），( 圖1)點的橫縱坐標之和表示公司和客戶所在地之間的距離。現在在客戶的坐標值中求出距離原點O的最遠的橫縱坐標值Xk和Yk。以Xk和Yk作為邊長，以原點作為矩形的第一個對角點在XY軸正方向所確定的區(qū)域畫出一個長為20km寬為28km的矩形，采用四叉樹對該地區(qū)進行四等分，形成2m2m的網格 。具體是這樣的：把這個矩形首先分成4個區(qū)，所有的客戶都被分到某一個區(qū)內。檢查每一個區(qū)所要送的快件的重量之和是否達到25kg，如果有一個區(qū)的總重量超過25kg，則繼續(xù)在每一個小區(qū)再進行分區(qū)，直到所有區(qū)的總重量都不超過25kg為止。分完之后，確定了16個區(qū)，(如圖2) 在這里m=2。在這16個區(qū)中，(圖2)有些區(qū)的送貨重量是遠遠達不到25kg的，因此必須對每一個區(qū)進行拆分和組合。也就是確定候選區(qū)，選擇距離公司送貨點最遠的四叉樹網格，沿逆時針方向進行網格中需求點的擴充，擴充的條件是：如果本網格中的快件總數量小于25kg，則進行擴充，否則不擴充。重復操作這一步，直到每一個送貨點都被分到某一個區(qū)里面，通過改進方法，對配送分區(qū)進行優(yōu)化，優(yōu)化的方法必須滿足一定的條件。區(qū)位確定好后，再來確定對該區(qū)進行送貨路線，送貨路線的確定必須滿足業(yè)務員花的時間最少，也就是走的路程最短。這就是運輸巡回路線問題的求解，我們采用的是典型的旅行商問題求解法來求解，通過計算機的高速運算能力和邏輯判斷能力來確定所走到路線。根據送貨路線求出每一個區(qū)送貨的時間，根據時間的長短來安排業(yè)務員的數量以及每個業(yè)務員所要走的區(qū)。這樣就可以求出該快遞公司所需要的業(yè)務員的數量和成本。3模型假設每次業(yè)務員從一個區(qū)送貨回來，再配貨的時間為0，即不花時間。業(yè)務員不會發(fā)生意外，即不會意外的花一些時間。業(yè)務員中途不休息。與業(yè)務員走的路都為橫縱坐標。街道平行于坐標軸。業(yè)務員在中途除了送貨之外沒有別的時間耽擱。4符號說明 ai ：第i分區(qū)，距離公司最近的客戶點。其值為1，否則問0 。bij ：客戶j屬于第i分區(qū)。其值為1，否則為0；lij ：客戶j到距離公司最近客戶點i之間的距離。wj ：客戶j的快件重量。di ：第i分取中距離公司最近的客戶點到公司的距離 z ：每一個業(yè)務員所能承載的最大快件量。xij ：=1（弧（i，j）在線路上），或0（弧（i，j）不在線路上）。dij : 任意兩個客戶之間的距離dij=|xi-xj|+|yi-yj|。5模型的建立及求解快遞公司分區(qū)配送貨物的數學模型主要分為兩個相對獨立的部分：配送分區(qū)模型和運行線路模型。在運行線路模型中將每一個區(qū)都使用一次運行線路的計算，則構造出了相應的幾條合適的路線。配送分區(qū)的數學模型如下所示： mincost=inaidi+injnbijlij (5-1) in-1bij=1 (5-2) in-1bijwjz (5-3) bijai (5-4) ai = 1，0 (55) bi j = 1，0 (56)式（11）為目標函數，使得走過的路徑最短；式（12）表示每一個客戶點都被選中；式（13） 表示每一分區(qū)的總快件的重量的限制，均小于每一個業(yè)務員的負重量。式（14）表示分區(qū)i和客戶j之間的關系。式（15）和（16）限制 ai和bij 的取值范圍。運行線路模型： 運行線路模型采用經典的旅行商問題的數學模型來求解 如下：mincost=injndijxij (5-7) i=0nxij=1 j=0,1,n (5-8) j=0nxij=1,i=0,1,n (5-9) xij=0,1 (5-10)51 配送分區(qū)的劃分(1) 高斯平面直角坐標系的建立。建立以公司為原點(0,0)的高斯平面直角坐標系，需求點采用相對坐標的方式進行記錄，vk=(xk, yk,) (1k30)。(2) 四叉樹的生成 。 檢索需求點中xk 和yk最大的絕對值作為建立四叉樹的最大網格邊長 Lx = max(|x1|，|x2|，|x3|，|x4|，|x5| , |x30|)，Ly= max(|y1|，|y2|，|y3|，|y4|，|y5| , |y30|)。以四叉樹中網格包含的客戶點快件總重量小于或等于業(yè)務員一次能夠帶走的最大的快件重量(25kg)為基準進行四叉樹的生成，當四叉樹網格包含的客戶的快件總重量小于或等于每個業(yè)務員所能夠帶走的重量時，停止該四叉樹網格的劃分，則該四叉樹網格中的每一格就為就為一個候選配送區(qū)。剔除不包含客戶點的四叉樹網格(3) 確定后選分區(qū)，選擇距離公司最遠的四叉樹網格，沿逆時針方向進行網格中客戶點的擴充。如果與之臨近網格中由方向度小于3的網格，則以臨近網格中最小方向度的網格為中心進行擴充，原網格作為次選網格。擴充的條件是：如果本網格的總需求量等于每個業(yè)務員一次所帶的重量(25kg)則不進行擴充，如果本網格的需求量不到25kg則沿逆時針方向以最近原則選擇相鄰一定等級的網格內的客戶點，使配送區(qū)位的快件總重量等于或接近25kg。所選擇的客戶點從原來的配送分區(qū)中刪除，將無需求點的網格刪除。(4) 重復操作(3) 直到使每一個客戶點僅一次被選擇如一個配送區(qū)。(5) 將以上操作確定的配送區(qū)位任作為候選區(qū)，通過改進算法的方式帶入分區(qū)算法中的目標函數，進行目標函數求解，如果求解值小于目標函數求解值則該配送區(qū)位作為新的配送區(qū)位，循環(huán)上述操作，進過有限次的計算，進行配送區(qū)位的優(yōu)化，優(yōu)化的結果如圖3。(圖3)52 運行路線的確定采用旅行商問題的解法。改解法采用計算機輔助計算來解決。程序的偽代碼和步驟如下：(1) 選取公司作為線路起點i；(2) 構造點擊的凸集和，取得一條初始路線；(3) 選擇一條不屬于初始路線上的點k以線路上的弧(i ,j)，使由弧(i,k)于弧(k,j)構成的角度最大。(4) 將點k插入到i和j之間。(5) 重復上述步驟知道得到一條哈密爾頓回路為止得到了8個區(qū)域圖，如圖4所示(6) 計算機輔助計算的結果(如圖4)。(7) 業(yè)務員應該走的路線就是下圖所示的路線(其中“入口”表示某個業(yè)務員從公司(原點)到該分配區(qū)位的第一個點。“出口”表示業(yè)務員已經走完該區(qū)到達的最后一個客戶點 )(圖4)53 時間和路程長度的確定 將每一個區(qū)都進行運行線路的確定的計算，最后得到了幾條合適的運行線路。 (如表1)。表1.業(yè)務員載重量25kg,總需求量184.5kg,分為8區(qū)區(qū)位需求點分區(qū)總量(單位kg）巡回路線(原點O為始點和終點)127,29,3024.3O273029O224,26,2823.6O262824O318,19,2524.9O192518O45,6,16,17,2021.4O61617205O54,7,8,13,1424.6O8131474O61,2,322.2O132O79,10,11,2218.8O1022119O812,15,23,3224.7O12152332O 再根據所走的路線來確定總共的行程和總共需要的時間以及每一條路線所需要的時間(如表2) 表2區(qū)位每分區(qū)總路程單位km每分區(qū)路途所時間 單位小時h每分區(qū)貨點所需時間 單位小時h每分區(qū)所需總時間 單位小時h19292/25=3.68310/60=0.54.1828888/25=3.52310/60=0.54.0236464/25=2.56310/60=0.53.0645050/25=2510/600.842.8454848/25=1.92510/600.842.7662020/25=0.8310/60=0.51.374848/25=1.92410/600.672.5987272/25=2.88410/600.673.55總的運行路程482 km總的運行時間24.3 hours 根據時間表，找出可以互補的幾條路線，互補的條件就是兩條路線所需時間相加之后時間之和在6小時附近。這樣確定下來的時間和總共要的人數是24.30hours和4.050個人現在確定每個人要走的路線。假如有4個業(yè)務員，他們所走的分區(qū)和所花的時間(如表3)：表3業(yè)務員的編號所走的分區(qū)所花時間 (單位 小時h)1號1區(qū)，6區(qū)5.482號2區(qū)，7區(qū)6.613號3區(qū)，4區(qū)5.904號5區(qū)，8區(qū)6.316 設計規(guī)范的合理性討論6.1 合理的方面 快遞公司每天要運送的快件在早上出發(fā)時間之前已經全到了，沒有到的當天就不運送，這是許多公司現在的經營模式，這種模型現在已經很成熟，因此采用這種解法應該能夠達到公司的節(jié)約成本要求。6.2 不和理的方面 由于城市快件的傳遞是一個比較復雜的問題設計到眾多的變量，上述模型尚有許多因素沒有考慮在內。比如每一次業(yè)務員送完快件，回來再準備第二趟運送快件這個過程也要花時間，這個時間沒有考慮到時間范圍內。還有像城市交通不平衡等問題，貨物分類等問題。7 結果和誤差分析理論上總時間算下來是24.30小時，每個業(yè)務員平均工作6個小時，因此人數算下來平均是4.050個人，在實際情況中4個人就能送完所有的快件。8 模型推廣該模型可用于很多領域，比如說城市物流分配問題，城市網絡布線等問題。9 模型的優(yōu)缺點 該模型實用性很強，從計算機運算結果來看，走過的路徑還算是比較優(yōu)的。但是這里面忽略了很多因素，這些因素在實際中不可忽略。因此實際中應該多分配一些時間或業(yè)務員。10 參考文獻1 霍亮 空間物