1、快遞公司送貨策略優化模型摘要本文討論了快遞公司送貨路線的優化設計問題，即在給定送貨地點和給定設計規范的條件下，綜合考慮最大載重范圍、以及各快遞員工作時限，建立了人員分配和路徑優化的數學模型。在這個題目中兩點之間的路線權值賦為這兩點橫縱坐標之和，如此便可以用MATLAB求出任意兩配送點間的距離。針對問題一，我們以路程最短為目標 ，使公司獲得最大效益并且快遞員工作時間和每次出發的快件量越接近臨界值越好，使其利用率最高。我們用以下方法：即每一個行程的第一個送貨點是距離總部最近的未服務的送貨點，可得到一組運行路線，總的運行公里數，以及總費用。通過用TSP模型對每條路線的最短路處理，在之前的路線上進行修

2、正，得到優化模型結果為：最短時間為28.2699h，最短行程為506km，需要6個業務員。針對問題二，在問題一的條件下，以給業務員的酬金最少為目標，結合業務員的安排和路線的選擇，結果顯示最優：共安排了8業務員，跑9路線，其中1號業務員跑的路線為0-1-3-8-13-0和0-2-4-7-14-0，2號業務員跑的路線為0-6-5-20-18-30-0，3號業務員的路線為0-9-12-19-0，4號業務員的路線為0-10-11-32-23-0，5號業務員的路線為0-16-17-24-28-0，6號業務員的路線為0-22-29-0，7號業務員的路線為0-15-27-0，8號業務員的路線為0-25-26

3、-0，時間為30.7668h，用為13830.7元 針對問題三，因為所需的總時間不變，而每個業務員的工作時間增加為8小時，所以對其工作量重新安排，可將業務員減少到4人。關鍵字：快遞公司送貨 歐拉回路模型 0-1規劃 TSP模型 1、 問題重述目前，快遞行業正蓬勃發展，為我們的生活帶來更多方便。一般地，所有快件到達某地后，先集中存放在總部，然后由業務員分別進行派送；對于快遞公司，為了保證快件能夠在指定的時間內送達目的地，必須有足夠的業務員進行送貨，但是，太多的業務員意味著更多的派送費用。假定所有快件在早上7點鐘到達，早上9點鐘開始派送，要求于當天17點之前必須派送完畢，每個業務員每天平均工作時間

4、不超過6小時，在每個送貨點停留的時間為10分鐘，途中速度為25km/h，每次出發最多能帶25千克的重量。為了計算方便，我們將快件一律用重量來衡量，平均每天收到總重量為184.5千克，公司總部位于坐標原點處（如圖2），每個送貨點的位置和快件重量見下表，并且假設送貨運行路線均為平行于坐標軸的折線。（1）請你運用有關數學建模的知識，給該公司提供一個合理的送貨策略（即需要多少業務員，每個業務員的運行線路，以及總的運行公里數）；（2）如果業務員攜帶快件時的速度是20km/h，獲得酬金3元/km×kg；而不攜帶快件時的速度是30km/h，酬金2元/km，請為公司設計一個費用最省的策略；（3）如果

5、可以延長業務員的工作時間到8小時，公司的送貨策略將有何變化？送貨點快件量T坐標(km)送貨點快件量T坐標(km)xyxy1832163.521628.215175.86183654187.5111745.547197.815126308153.419954.5311326.222577.279226.821082.396232.427991.4102247.61519106.5140259.61514114.1173261020171212.714627122113135.8129286.02420143.81012298.12516204.6714304.22818點的分布如下圖：根據題意，

6、得到運輸情況及業務員工作信息如表1所示表1 運輸情況及業務員工作信息運輸車載重量25kg平均每天收到總重量184.5kg運輸車途中平均速度25km/h每個業務員每天平均工作時間<=6h每個送貨點停留的時間10min攜帶快件時速度20km/h攜帶快件時酬金3元/km.kg不攜帶快件速度30km/h不攜帶快件酬金2元/km.kg備注1.公司總部位于坐標原點處 2.送貨運行路線均為平行于坐標軸的折線處于實際情況的考慮,本研究中對人的最大行程不加限制.本論文試圖從最優化的角度，建立起滿足設計要求的送貨的數學模型，求出滿足題意要求的結果。2 模型的假設1.無塞車現象,且車輛技術良好2.車輛使用無限

7、制3.業務員到某送貨點后必須把該送貨點的快件送完4每次業務員從一個區送貨回來，再配貨的時間為0，即不花時間。5業務員中途不休息。6街道平行于坐標軸，且在保證該前提下，車輛可任意選擇路徑7業務員在中途除了送貨之外沒有別的時間耽擱。8每個送貨點每天的快件量基本相同。9在業務員出發后到達快遞公司的快件量均算入第二天的快件量10業務員送完貨后必須到公司報到。11.每個業務員只在自己送貨的點有等待時間，路過送貨點但不送貨的沒有等待時間。三、符號說明Ti：序號為i的送貨點的快件重量（xi ，yi）序號為i的送貨點的坐標dij:兩點之間的距離W1：業務員送貨總重載費用W2：業務員送貨總空載費用W：業務員送貨

8、總費用N：業務員送貨的總次數 第i線送完貨的終點；四、模型的分析、建立和求解問題一：運用有關數學建模的知識，給該公司提供一個合理的送貨策略（即需要多少業務員，每個業務員的運行線路，以及總的運行公里數）（一） 模型分析 在問題一中，只要求給出一個合理的送貨策略，并沒有涉及到業務員的工資問題，故只要滿足要求每個業務員每天平均工作時間不超過6小時且必須從早上9點鐘開始派送，到當天17點之前（即在8小時之內）派送完畢；以及每次出發最多能帶25千克的重量。由于，故最少需要8條路線。如果將兩點之間的路線權值賦為這兩點橫縱坐標之和，比如，兩點，則權值為。那么便可以用MATLAB求出任意兩配送點間的距離，即權

9、重（如表1，求解程序見附件一）。得到距離矩陣因為距離是對稱的，即從送貨點i到送貨點j的距離等于從j到i的距離。記作：（二） 模型的建立和求解可以通過以下方法實現：每一個行程的第一個送貨點是距離總部最近的未服務的送貨點。 本模型中以滿足需求的路程最短的人員行駛路徑,且使用盡量少的人數，即不走冤枉路原則（即只能向上或者向右走）。一方面，離原點（快遞公司）較遠的送貨點坐標應分別大于離原點較近送貨點的 坐標，在各個坐標上均不走回頭路。 用這種方法，即可得到一組運行路線，總的運行公里數。 且 約束條件為： 時間約束： 載重量約束：方法如下：尋找每一個行程的第一個送貨點是距離總部最近的未服務的送貨點。用該

10、算法得到的各路線為：第一條路線：快遞公司1（3，2）3（5，4）4（4，7）5（3，11）出發線返回線第二條路線：快遞公司2（1，5）6（0，8）7（7，9）13（12,9）出發線返回線第三條路線：快遞公司9（10，2）8（9，6）12（14，6）出發線返回線10（14，0）第四條路線：快遞公司16（2，,16）17（6,18）20（7,14）14（10,12）15（19,9）23（27,9）出發線返回線第五條路線：快遞公司11（17，3）22（21，0）21（22，5）19（15，12）出發線返回線第六條路線：快遞公司27（21，13）26（20，17）出發線返回線第七條路線：快遞公司18（

11、11，17）24（15，19）25（15，14）出發線返回線第八條路線：快遞公司29（25，16）28（24，20）30（28，18）出發線返回線得到的路線圖如下：圖1注釋：用線連接起來的幾個點表示一次送貨可以服務的點，代表送貨的先后和走的路線，但走的首尾順序可以任意。每條線路的所用時間和載重量如下：表一以上8條路線，我們分別對每條回路利用TSP模型求得該回路的最短路，使得路程和時間得到改善，提高工作效率。我們把快遞員送貨問題轉化為0-1規劃，然后用LINGO來求解。引入0-1整數變量 (且ij):=1表示路線從i到j，即邊i-j在旅行路線中，而0則表示不走i-j路線。目標函數：首先必須滿足約

12、束條件：對每個送貨點訪問一次且僅一次。從送貨點i出發一次(到其它送貨點去),表示為從某個送貨點到達j一次且僅一次，表示為以上建立的模型類似于指派問題的模型，對快遞員送貨問題只是必要條件，并不充分。例如，用圖示路線連接六個點，滿足以上兩個約束條件，但這樣的路線出現了兩個子回路，兩者之間不通，不構成整體巡回路線312654為此需要考慮增加充分的約束條件以避免產生子巡回增加變量,i=2,3,n，（它的大小可以取整數：例如從起點出發所達到的投遞點u=2,依此類推）。綜上所述，該約束條件只限止子巡回，不影響其它，于是快遞員送貨問題轉化成了一個混合整數線性規劃問題。快遞員送貨問題可以表示為規劃：利用LIN

13、GO求解，依次可求得每天回路的最短路線：修改后得到總的送貨路線為：第一條路線：快遞公司1（3，2）3（5，4）4（4，7）5（3，11）出發線返回線第二條路線：快遞公司2（1，5）6（0，8）7（7，9）13（12，9）出發線返回線第三條路線：快遞公司10（14，0）8）12(14,6)8（9，6）9（10，2）出發線返回線第四條路線：快遞公司16（2，,16）17（6,18）20（7,14）14（10,12）15（19,9）23（27,9）出發線返回線第五條路線：快遞公司19（15，12）11（17，3）21（22，5）22（21，0）出發線返回線第六條路線：快遞公司18（11，17）24（

14、15，19）出發線返回線25（15,14）第七條路線：快遞公司27（21，13）26（20，17）出發線返回線第八條路線：快遞公司29（25，16）30（28，18）出發線返回線28（11,17）修改后得到的路線圖如下：注釋：用線連接起來的幾個點表示一次送貨可以服務的點，代表送貨的先后和走的路線，但走的首尾順序可以任意。修改后每條線路的所用時間和載重量如下：表二運輸員序號所經站數最近點所用時間(小時)總載重（kg）總路程（km）141（3，2）1.94672432242（1，5）2.506724.246349（10，2）1.866422.9304616（2，16）4.600023.590541

15、1（17，3）4.213424.9726318（11，17）3.750024.7687227（21，13）3.706722768329（25，16）4.840018.396合計3028.2699184.5506改進前和改進后的路程，時間比較如下：根據所經歷的時間進行劃分，確定運送人數。在工作時間小于6小時的前提下，最終只需要六名運輸員，第一條線路和第二條線路有一人完成，第三條和第七條線路由一人完成，則各運輸員到達各站點時間的情況如下：路線站點編號到各站點時間出發時間路線站點編號到各站點時間出發時間119：129：0051910：059：0039：321110：4149：523211：08510

16、：142211：322212：0211：5861810：079：001312：482410：31713：102510：53613：3972713：4512：233109：349：002614：07129：5882910：389：00810：203011：00910：442811：244169：439：00問題二：如果業務員攜帶快件時的速度是20km/h，獲得酬金3元/km×kg；而不攜帶快件時的速度是30km/h，酬金2元/km，請為公司設計一個費用最省的策略。（一） 模型的分析問題二中由于業務員所得的費用是最主要的，業務員安排、路線選擇都是為了總費用的最小化提供條件，所以應首先考慮

17、路費，之后再考慮業務員的安排。為了使總能夠費用最少，總的思路是先送貨給離快遞公司最近切塊間最重的送貨點，以此類推，在保證時間、載重量有限的前提下，沿途把快遞送完，最終讓業務員最遠點空載返回。（二） 模型的建立和求解總費用為重載與空載費用之和，所以總費用的確定就可以轉化為滿足一定條件下的各路線的最遠點的選擇問題。某路線業務員經過的路徑選擇應遵循以下原則：一是，近者優先原則。某業務員最近起始送貨點的選擇直接關系到費用的多少，所以該業務員在沿途往送貨終點站中應盡量把較近點的快件送完，不讓下一條路線再把較近點作為起始送貨站。二是，不走冤枉路原則（即只能向上或者向右走）。一方面，離原點（快遞公司）較遠的

18、送貨點坐標應分別大于離原點較近送貨點的 坐標，在各個坐標上均不走回頭路。 另一方面，由于在路途相等的條件下，重載費用要比空載費用大得多，因此，盡量讓業務員空載行走。 根據上述分析及基本假設，業務員送貨的費用可以表示如下：業務員負載費用： 業務員空載費用： 總費用:因此，目標函數建立為應滿足以下約束條件:1時間約束:2載重量約束25 據路線約束條件以及問題一中的表二知：送貨點1（3，2）、2（1，5）首先必須作為某路線的最近起始送貨點，再結合時間約束條件、載重量約束條件以及上述分析的有關內容，依次選出各路線的次近點，并做統籌兼顧，一直到滿足約束條件的最大值為止。隨后又選出6（0，8）、9（10，

19、2）、10（14，0）、16（2，16）、22（21，0）、15（19，9）、25（15，14）為某條路線的最近點，分別確定次近點等，最后確定各路線如下所示：第一條路線：快遞公司1（3，2）3（5，4）8（9，6）13（12，9）出發線返回線第二條路線：快遞公司2（1，5）4（4，7）7（7，9）14（10，12）出發線返回線第三條路線：快遞公司6（0，8）5（3，11）20（7，14）18（11，17）出發線返回線30（28，18）第四條路線：快遞公司9（10，2）12（14，6）19（15，12）出發線返回線第五條路線：快遞公司10（14，0）11（17，3）32（22，5）23（27，9

20、）出發線返回線第六條路線：快遞公司16（2，16）17（6，18）24（15，19）28（24，20）出發線返回線第七條路線：快遞公司22（21，0）29（25，16）出發線返回線第八條路線：快遞公司15（19，9）27（21，13）出發線返回線第九條路線：快遞公司25（15，14）26（20，17）出發線返回線根據上面確定的路線，把個業務員所經過的送貨點數、最近點、所用時間、總載重量進行歸納，求出各業務員送貨所得費用以及總費用，如下表：路線號所經送貨點數最近送貨點所用時間（小時）總載重量（kg）費用（元）141（3，2）2.4166722.1792.9242（1，5）2.524.7969.5

21、356（0，8）4.6666723.81852.4439（10，2）2.7521.91498.25410（14，0）3.6666719.21352.46416（2，16）4.3333322.92261.87222（21，0）3.7514.91506.78215（19，9）3.1666715.41577.69225（15，14）3.4266719.62019.2合計3030.7668184.513830.7根據時間約束，最少要8個業務員送快件，其中把路線1和2合并，讓業務員A執行任務，其余的分別由其他7個業務員送貨。同時，為了便于統籌業務員，可以得出各業務員到各送貨點的時間（各業務員的出發時間為

22、0）以及各路線從快遞公司出發的參考時間（從9：00開始工作）。第一個人：0-1-3-8-13-0和0-2-4-7-14-0第二個人：0-6-5-20-18-30-0第三個人：0-9-12-19-0第四個人：0-10-11-32-23-0第五個人：0-16-17-24-28-0第六個人：0-22-29-0第七個人：0-15-27-0第八個人：0-25-26-0問題三：如果可以延長業務員的工作時間到8小時，公司的送貨策略將有何變化？（一）模型分析問題三是建立在問題一的基礎上的，因為每個業務員可以攜帶的郵件量是一定的，即不超過25kg，當工作時間調至八小時時，無論對總公里數還是總酬金都沒有影響，只需

23、對業務員的多少進行改進即可。（2） 模型的建立和求解在問題一中已算得，修改前的方案所需的總時間最少為27.69h，當業務員時間調至8小時時，所需的業務員至少為個,所以業務員至少為4個。于是我們就對修改前的方案的表一的八個路線重新分配，分配給4個送貨員，盡量給業務員分配同樣的工作時間，即，即每個業務員工作時間在6.07左右。重新分配后得到如表15所示的方案業務員送貨路線線路耗時線路路程10-16-17-20-14-15-23-06.551220-1-3-4-5-020-29-28-30-06.931440-2-6-7-13-030-11-22-21-19-06.761190-9-8-12-10-

24、040-27-26-07.461440-18-24-25-0表15綜上所述，當時間變成8小時時，業務員減為4個，具體安排為：1號業務員跑的路線為0-16-17-20-14-15-23-0和0-1-3-4-5-0，2號業務員跑的路線為0-29-28-30-0和0-2-6-7-13-0，3號業務員的路線為0-11-22-21-19-0和0-9-8-12-10-0，4號業務員的路線為0-27-26-0和0-18-24-25-0。五模型的評價1.模型的優點：(1）模型系統的給出了業務員的調配方案，便于指導工作實踐。(2）模型簡明明了，容易理解與靈活應用。(3)本論文模型的建立從實際問題出發,對于解決其

25、它問題也具有一定的實用性, 具 有較強的推廣價值。(4)成功運用matlab和LINGO等軟件，減少計算量（5）充分利用0-1規劃、歐拉回路模型和TSP模型，使方案更具有可行性2 模型的缺點：(1) 本模型求解復雜程度太大，當送貨點個數增加一個，求解復雜度就會成級數增加，由于受各種條件的限制，送貨員的送貨線路只能逐條去求，增加了勞動量。3 模型給出的約束條件有些不太現實，忽略了很多因素，比如快遞員休息時間等，這些因素在實際中不可忽略。(3）對街道的方向，客戶的快件量的假設有待進一步改進。六模型的推廣（1）本模型不但適合于快遞公司送貨問題，還是用于一般的送貨以及運輸問題， 只需要稍微改動模型即可

26、。（2）模型方便、直觀，可以實現計算機模擬。（3）建模的方法和思想可以推廣到其他類型，如車輛調度問題等。七、 結果分析通過以上模型我們解決了快遞公司在實際中所面臨的送貨員聘用問題，我們幫他們找出了聘用的最少送貨員人數，以及每個送貨員運送路線的安排，線路的產生是我們通過對實際問題中可能遇到的結果進行比較，從中選擇出了最優結果。 對于問題一和問題二的分析，我們可以將問題二看成是問題一約束條件的增加，問題一的結果適用于問題二，只是因需要滿足時間要求而進行調整。本問題的求解具有一般性，對實際問題的解決具有一定的指導意義。八、參考文獻1姜啟源 謝金星 葉俊 編著，數學模型，北京：高等教育出版社，2003

27、年第三版；2鄧微，MATLAB函數速查手冊：人民郵電出版社，2008.3吳建國 編著，數學建模案例精編，北京：中國水利水電出版社，2005年5月第一版.4數學建模案例精編（超星閱覽器）5中國郵遞員模型案例九、附錄附件一：求矩陣：求任意兩配送點間的距離clearclcx=0 3 1 5 4 3 0 7 9 10 14 17 14 12 10 19 2 6 11 15 7 22 21 27 15 15 20 21 24 25 28;y=0 2 5 4 7 11 8 9 6 2 0 3 6 9 12 9 16 18 17 12 14 5 0 9 19 14 17 13 20 16 18;for i=

28、1:31 for j=1:31d(i,j)=abs(x(i)-x(j)+abs(y(i)-y(j); end end運行結果:Columns 1 through 10 0 5 4 6 9 9 11 10 7 13 5 0 5 5 4 8 10 9 12 18 4 5 0 4 9 9 7 6 7 13 6 5 4 0 5 5 5 6 11 17 9 4 9 5 0 6 8 11 16 22 9 8 9 5 6 0 6 11 16 2211 10 7 5 8 6 0 5 10 1610 9 6 6 11 11 5 0 5 11 7 12 7 11 16 16 10 5 0 613 18 13 17

29、 22 22 16 11 6 0 15 18 13 17 22 22 16 11 8 6 15 14 11 11 16 16 10 5 8 616 15 12 10 13 11 5 6 9 1117 16 13 11 14 8 6 7 10 1616 15 12 10 13 7 5 10 15 21 15 12 15 11 10 6 12 17 22 2819 18 15 13 16 10 10 15 20 26 23 22 19 17 20 14 12 13 16 20 22 21 18 16 19 13 11 12 15 13 23 22 19 17 20 18 12 13 16 14 2

30、2 21 18 20 25 25 19 14 15 13 20 25 20 24 29 29 23 18 13 7 31 30 27 25 28 26 20 21 24 22 29 28 25 23 26 20 18 19 22 20 24 23 20 18 21 15 13 14 17 15 32 31 28 26 29 23 21 22 25 23 29 28 25 23 26 20 18 19 22 20 39 38 35 33 36 30 28 29 32 30 36 35 32 30 33 27 25 26 29 27 41 40 37 35 38 32 30 31 34 32 Co

31、lumns 11 through 20 15 15 16 17 16 15 19 23 22 23 18 14 15 16 15 12 18 22 21 22 13 11 12 13 12 15 15 19 18 19 17 11 10 11 10 11 13 17 16 17 22 16 13 14 13 10 16 20 19 20 22 16 11 8 7 6 10 14 13 18 16 10 5 6 5 12 10 12 11 12 11 5 6 7 10 17 15 13 12 13 8 8 9 10 15 22 20 16 15 16 6 6 11 16 21 28 26 20

32、13 14 0 6 11 16 21 28 26 20 11 8 6 0 5 10 15 22 20 14 7 8 11 5 0 5 10 17 15 9 6 7 16 10 5 0 5 12 10 6 5 12 21 15 10 5 0 7 5 7 10 17 28 22 17 12 7 0 6 10 17 24 26 20 15 10 5 6 0 6 15 22 20 14 9 6 7 10 6 0 9 16 11 7 6 5 10 17 15 9 0 7 8 8 7 12 17 24 22 16 7 0 7 9 14 19 24 31 29 23 14 7 7 13 18 23 28 3

33、5 33 27 18 11 16 16 15 20 25 32 30 24 15 8 18 14 13 12 13 16 10 6 7 14 13 9 8 7 8 15 13 7 2 9 17 17 16 15 16 19 15 9 10 9 14 14 13 12 15 22 20 14 7 6 24 24 23 22 23 26 20 16 17 16 21 21 20 19 20 23 21 15 14 13 26 26 25 24 25 28 22 18 19 18 Columns 21 through 30 22 20 31 29 24 32 29 39 36 41 21 25 30

34、 28 23 31 28 38 35 40 18 20 27 25 20 28 25 35 32 37 20 24 25 23 18 26 23 33 30 35 25 29 28 26 21 29 26 36 33 38 25 29 26 20 15 23 20 30 27 32 19 23 20 18 13 21 18 28 25 30 14 18 21 19 14 22 19 29 26 31 15 13 24 22 17 25 22 32 29 34 13 7 22 20 15 23 20 30 27 32 7 7 16 18 13 17 14 24 21 26 9 13 16 14

35、9 17 14 24 21 26 14 18 15 13 8 16 13 23 20 25 19 23 20 12 7 15 12 22 19 24 24 28 25 13 8 16 15 23 20 25 31 35 32 16 15 19 22 26 23 28 29 33 30 10 13 15 20 20 21 22 23 27 24 6 7 9 14 16 15 18 14 18 15 7 2 10 7 17 14 19 7 11 8 14 9 9 6 16 13 18 0 6 9 21 16 14 9 17 14 19 6 0 15 25 20 18 13 23 20 25 9 1

36、5 0 22 17 15 10 14 9 10 21 25 22 0 5 7 12 10 13 14 16 20 17 5 0 8 7 15 12 17 14 18 15 7 8 0 5 7 6 9 9 13 10 12 7 5 0 10 7 12 17 23 14 10 15 7 10 0 5 6 14 20 9 13 12 6 7 5 0 5 19 25 10 14 17 9 12 6 5 00 5 4 6 9 9 11 10 7 135 0 5 5 4 8 10 9 12 184 5 0 4 9 9 7 6 7 136 5 4 0 5 5 5 6 11 179 4 9 5 0 6 8 1

37、1 16 229 8 9 5 6 0 6 11 16 2211 10 7 5 8 6 0 5 10 1610 9 6 6 11 11 5 0 5 117 12 7 11 16 16 10 5 0 613 18 13 17 22 22 16 11 6 0 15 18 13 17 22 22 16 11 8 6 15 14 11 11 16 16 10 5 8 6 16 15 12 10 13 11 5 6 9 11 17 16 13 11 14 8 6 7 10 16 16 15 12 10 13 7 5 10 15 21 15 12 15 11 10 6 12 17 22 28 19 18 1

38、5 13 16 10 10 15 20 26 23 22 19 17 20 14 12 13 16 20 22 21 18 16 19 13 11 12 15 13 23 22 19 17 20 18 12 13 16 14 22 21 18 20 25 25 19 14 15 13 20 25 20 24 29 29 23 18 13 7 31 30 27 25 28 26 20 21 24 22 29 28 25 23 26 20 18 19 22 20 24 23 20 18 21 15 13 14 17 15 32 31 28 26 29 23 21 22 25 23 29 28 25 23 26 20 18 19 22 20 39 38 35 33 36 30 28 29 32 30 36 35 32