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

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

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

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

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

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

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

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

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

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

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

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

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

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