快遞公司送貨策略 路程矩陣

1、.：.；快遞公司送貨戰(zhàn)略摘要快遞是快遞公司快速搜集、運輸和遞送客戶文件、物品或貨物的一種效力.合理選擇送貨線路并制定業(yè)務(wù)員分派方案是極其重要的,它不僅可以加快配送速度,提高效力質(zhì)量,還可以有效的降低配送本錢,添加經(jīng)濟效益.本文是關(guān)于快遞公司送貨戰(zhàn)略的優(yōu)化設(shè)計問題，即在給定送貨地點和給定設(shè)計規(guī)劃的前提下，確定所需的業(yè)務(wù)員人數(shù)，每個業(yè)務(wù)員的行程道路，總的運轉(zhuǎn)公里數(shù)及費用最省的戰(zhàn)略。對此,本文重點討論的問題是快遞公司如何雇傭多少業(yè)務(wù)員送貨,如何確定每個業(yè)務(wù)員的運轉(zhuǎn)線路以到達(dá)費用最省的目的。在問題一中，由于不要思索業(yè)務(wù)員費用，所以我們以業(yè)務(wù)員所走路程最短為目的函數(shù)：先假定將送貨點劃分為N個區(qū)域，然后用

2、LINGO軟件進展求解，得出最短送貨間隔 ，然后引入途徑矩陣D，用MATLAB編程求解得出業(yè)務(wù)員的最正確行走途徑及所需求的業(yè)務(wù)員個數(shù)5人。在問題二中，主要思索業(yè)務(wù)員的費用，經(jīng)過對載貨費用與空載費用求和得到所需總費用。所以，我們以總費用最小為目的建立動態(tài)規(guī)劃模型：經(jīng)過運用LINGO和MATLAB軟件求解得出最優(yōu)送貨道路及送貨費用。在問題三中，我們沿用問題一的模型，并將其中每趟送貨不超越6個小時的約束條件改為不超越8個小時，得出最有送貨道路及業(yè)務(wù)員人數(shù)4人。關(guān)鍵字：路程矩陣 動態(tài)規(guī)劃 遺傳算法一、問題重述目前，快遞行業(yè)正蓬勃開展，為我們的生活帶來更多方便。普通地，一切快件到達(dá)某地后，先集中存放在總

3、部，然后由業(yè)務(wù)員分別進展派送；對于快遞公司，為了保證快件可以在指定的時間內(nèi)送達(dá)目的地，必需有足夠的業(yè)務(wù)員進展送貨，但是，太多的業(yè)務(wù)員意味著更多的派送費用。假定一切快件在早上7點鐘到達(dá)，早上9點鐘開場派送，要求于當(dāng)天17點之前必需派送終了，每個業(yè)務(wù)員每天平均任務(wù)時間不超越6小時，在每個送貨點停留的時間為10分鐘，途中速度為25km/h，每次出發(fā)最多能帶25千克的分量。為了計算方便，我們將快件一概用分量來衡量，平均每天收到總分量為184.5千克，公司總部位于坐標(biāo)原點處如圖2，每個送貨點的位置和快件分量見下表，并且假設(shè)送貨運轉(zhuǎn)道路均為平行于坐標(biāo)軸的折線。1請他運用有關(guān)數(shù)學(xué)建模的知識，給該公司提供一個

4、合理的送貨戰(zhàn)略即需求多少業(yè)務(wù)員，每個業(yè)務(wù)員的運轉(zhuǎn)線路，以及總的運轉(zhuǎn)公里數(shù)；2假設(shè)業(yè)務(wù)員攜帶快件時的速度是20km/h，獲得酬金3元/kmkg；而不攜帶快件時的速度是30km/h，酬金2元/km，請為公司設(shè)計一個費用最省的戰(zhàn)略；3假設(shè)可以延伸業(yè)務(wù)員的任務(wù)時間到8小時，公司的送貨戰(zhàn)略將有何變化？二、問題假設(shè)與符號闡明2.1模型的假設(shè)假設(shè)1：每天每個送貨點只由一個業(yè)務(wù)員送一次貨假設(shè)2：業(yè)務(wù)員在送貨區(qū)域內(nèi)只走最短途徑假設(shè)3：各個業(yè)務(wù)員相互獨立，互不影響假設(shè)4：送貨運轉(zhuǎn)道路均為平行于坐標(biāo)軸的折線假設(shè)5：各業(yè)務(wù)員在中途除了送貨之外沒有其它時間耽擱2.2符號闡明符號符號闡明用0、1表示第i個送貨點能否屬于第

5、j個送貨區(qū)第i個送貨點的郵件+分量D途徑矩陣三、問題分析此題是一個典型的中國郵遞員問題，要求我們根據(jù)各種約束條件為快遞公司建立出比較合理的送貨戰(zhàn)略。針對問題一：要求我們根據(jù)時間和分量等方面的約束來建立一個合理的郵件配送模型。模型以郵遞員數(shù)量最少且送貨總間隔 最小為最正確送貨戰(zhàn)略。思索到送貨時間由送貨行駛間隔 和行駛速度來決議送貨點個數(shù)和位置確定的情況下，所以當(dāng)送貨所需的總行駛間隔 為最小時，所需的送貨時間和所需的郵遞員個數(shù)都將最少。因此我們思索建立以送貨總行駛間隔 最小為目的函數(shù)的數(shù)學(xué)模型。以此為根底將送貨點分到假設(shè)干區(qū)內(nèi)，然后確定由多少郵遞員分別給哪幾個區(qū)送貨。 針對問題二：此問給出了詳細(xì)的

6、運輸費用，要求我們求解費用最省的送貨戰(zhàn)略，因此我們根據(jù)運費和送貨行程的關(guān)系建立費用最省模型，并結(jié)合各種約束條件來計算求解。針對問題三：此問即在問題一的根底上將約束條件中每個業(yè)務(wù)員平均每天的任務(wù)時間從不超越6個小時改為了不超越8個小時，因此我們可以沿用第一問的模型，改動時間約束條件來進展求解計算。四、模型的建立與求解問題一：建立一個合理的送貨模型一模型分析建立此問要求我們根據(jù)時間和分量等方面的約束來建立一個合理的郵件配送模型。當(dāng)郵遞員數(shù)量最少且送貨總間隔 最小時可得到比較合理的送貨戰(zhàn)略。當(dāng)送貨所需的總行駛間隔 為最小時，所需的送貨時間和所需的郵遞員都將最少。因此我們思索建立以送貨總行駛間隔 最小

7、為目的函數(shù)的數(shù)學(xué)模型。為了得到簡化的數(shù)學(xué)模型，我們首先假定將一切送貨點分為N個送貨區(qū)，在最優(yōu)化總體送貨總間隔 的根底上為N個送貨區(qū)分得一些送貨點，并得出此區(qū)域內(nèi)的送貨詳細(xì)線路即順序，然后再根據(jù)時間的約束為每位郵遞員分配送貨區(qū)域，以此來得到一個較優(yōu)的合理的送貨方案。先設(shè)立如下變量： ：第i個送貨點的郵件分量以總行駛間隔 最小為目的函數(shù)：約束條件：每天每個送貨點只由一個郵遞員送一次貨: 二模型求解1定義途徑矩陣由于有序解集R的難以確定性，為了方便求解我們引入一新變量途徑矩陣D：設(shè)的矩陣D是所求的一條解途徑, 它滿足每行每列有且僅有一個元素為1, 其他為0。表示途徑中存在從送貨點到送貨點的邊, 顯然

8、, 當(dāng)時必有。這是一種基于邊的途徑編碼方法, 如圖1a所示的矩陣是四個送貨點的一個解, 它表示如圖1( b) 所示的一條解途徑。 (b)圖1因此可由途徑矩陣D得到有序解集R：當(dāng)矩陣D滿足時可得到獨一的有序解集R： 其中2確定算法送貨途徑問題是物流送的中心問題,對于此類多變量，多可行性的問題，普通難以由LINGO等軟件直接求得最優(yōu)解。此題我們采用一種基于途徑問題的遺傳算法，經(jīng)過在MATLAB中編程求得了較優(yōu)解。遺傳算法( Genetic Algorithm, 簡稱為GA) 是基于“適者生存的一種高度并行、隨機和自順應(yīng)化的優(yōu)化算法, 它將問題的求解表示成“染色體的適者生存過程, 經(jīng)過“染色體群的一

9、代代不斷進化, 最終收斂到“最順應(yīng)環(huán)境的個體, 從而尋求得到問題的最優(yōu)解或稱心解。求解此題詳細(xì)算法流程如下：初始化途徑矩陣D進化代數(shù)加1交叉、變異內(nèi)部擾動此群體能進化滿足終止條件終了算法外部擾動3計算結(jié)果針對標(biāo)題中所給數(shù)據(jù)用MATLAB軟件對該模型進展編程求解得到最短送貨總間隔 為528km。由解得到每個送貨區(qū)的劃分，并根據(jù)題中所給數(shù)據(jù)信息可得其區(qū)內(nèi)一組最短道路以及送貨一趟所需總時間：送貨區(qū)序號每個送貨區(qū)包含的送貨點及其一組最短道路給每個區(qū)送貨的總時間13.0724.3532.8342.8352.1862.186774.5183.54由上圖得一切送貨總時間約為25.4967小時，題中要求每個業(yè)

10、務(wù)員每天平均任務(wù)時間不超越6小時。由5*6=3025.4967，所以只需5個業(yè)務(wù)員便可到達(dá)要求，假設(shè)出現(xiàn)某些送貨義務(wù)超越6小時而有些不到6小時的時候，只需5個業(yè)務(wù)員進展輪番換班送貨即可。據(jù)此用MATLAB軟件編程對8個送貨區(qū)進展分組，分為5個組，使每個組的送貨總時間為接近6的最優(yōu)解：組號每個組所含送貨區(qū)送貨時間小時74.5124.265 85.721 35.94 65.016據(jù)此需求的業(yè)務(wù)員數(shù)量為5個，無需輪番換班，假設(shè)思索每個業(yè)務(wù)員之間的公平性那么可讓每個業(yè)務(wù)員按天輪番給每個組送貨，總的運送公里為528km。問題二： 為公司設(shè)計一個費用最省的戰(zhàn)略4.2.1模型的分析建立在這一問中由于業(yè)務(wù)員送

11、貨行程及其郵件分量決議了主要的費用，與郵遞員的安排無關(guān)，所以我們以運費總費用最小為目的函數(shù)建立模型：式中表示第j個送貨區(qū)的第m個送貨點的郵件分量。約束條件：每天每個送貨點只由一個郵遞員送一次貨: 4.2.1模型的求解針對標(biāo)題中所給數(shù)據(jù)用MATLAB軟件采用問題一所述的遺傳算法對該模型進展編程求解得到最小費用為15742元。由解得到每個送貨區(qū)的劃分，并根據(jù)題中所給數(shù)據(jù)信息可得其區(qū)內(nèi)一組最短道路以及送貨一趟所需總時間：送貨區(qū)序號每個送貨區(qū)包含的送貨點及其一組最短道路所需費用元12.7014e+00322.7156e+00331.6413e+00341.4631e+00351.0078e+00361

12、12273.1186e+00381.9724e+003問題三：在平均每天任務(wù)時間允許延伸為8小時后建立送貨戰(zhàn)略此問要求我們假設(shè)可以延伸業(yè)務(wù)員的任務(wù)時間到8小時，求公司的送貨戰(zhàn)略。這里我們可以沿用問題一的模型，并將其中每趟送貨不超越6個小時的約束條件改為不超越8個小時，再用MATLAB軟件求得最優(yōu)送貨區(qū)的劃分：送貨區(qū)序號每個送貨區(qū)包含的送貨點及其一組最短道路給每個區(qū)送貨的總時間13.0724.3532.8342.8352.1862.186774.5183.54再在任務(wù)時間變?yōu)?小時的根底上，為每位郵遞員分配送貨區(qū)域，以此來得到一個較優(yōu)的合理的送貨方案。由上表得一切送貨總時間與問題一的結(jié)果一樣約為

13、25.4967小時，題中要求每個業(yè)務(wù)員每天平均任務(wù)時間不超越8時。由4*8=3225.4967，得只需4個業(yè)務(wù)員即可，假設(shè)出現(xiàn)某些送貨義務(wù)超越8小時而有些不到8小時的時候，只需4個業(yè)務(wù)員進展輪番換班送貨即可到達(dá)要求。據(jù)此用MATLAB軟件編程對8個送貨區(qū)進展分組，分為4個組，使每個組的送貨總時間為接近8的最優(yōu)解：組號每個組所含送貨區(qū)送貨時間小時1 273 45.665 85.726 76.6967據(jù)此需求的業(yè)務(wù)員數(shù)量為4個，業(yè)務(wù)員無需換班，如要思索每個業(yè)務(wù)員之間的公平性的話，亦可輪番換班送貨。總的運送公里為528km。五、模型評價與推行5.1模型的優(yōu)點在建立模型時我們都是將問題轉(zhuǎn)換為一個數(shù)學(xué)目的函數(shù)，模型結(jié)果一方面詳細(xì)分配出了送貨戰(zhàn)略，另一方面模型簡單明晰，便于了解和推行。在求解分析中靈敏的將有序途徑問題引入到矩陣中，以求解變量途徑矩陣的方式進展分區(qū)道路的求解；另外在求解過程中用MATLAB并結(jié)合運用遺傳算法得出了比較理想