基于單純形法和Dijkstra算法下快遞配送終端優(yōu)化分析

孫 輝，王向前

（安徽理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院，安徽 淮南 232001）

基于單純形法和Dijkstra算法下快遞配送終端優(yōu)化分析

孫 輝，王向前

（安徽理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院，安徽 淮南 232001）

以菜鳥驛站配送終端為例，分析其存在的配送問題，建立整數(shù)規(guī)劃模型，選擇運(yùn)籌學(xué)中的單純形法為基礎(chǔ)，利用MATLAB軟件對(duì)配送終端企業(yè)在人員安排上進(jìn)行優(yōu)化.采用最短路徑Dijkstra算法對(duì)配送人員的路徑進(jìn)行研究，確定最優(yōu)配送路徑配送方案.

最后一公里；單純形法；Dijkstra算法；配送優(yōu)化

0 引言

在2016年11月11日全網(wǎng)購(gòu)物狂歡節(jié)中，據(jù)星圖大數(shù)據(jù)監(jiān)測(cè)數(shù)據(jù)平臺(tái)顯示，截止12日凌晨全網(wǎng)總的銷售額超過1 700億元，郵寄包裹突破10億個(gè)，其中東道主天貓以62.8%的網(wǎng)銷份額約1 207億元的銷售額占據(jù)銷售榜單第一名的位置［1］.但是龐大的經(jīng)濟(jì)效益現(xiàn)象下傳統(tǒng)快遞配送模式卻面臨著配送時(shí)效性差、貨件破損率高、配送脫節(jié)甚至爆倉(cāng)等一系列問題［2］.這些問題都在時(shí)刻考驗(yàn)著配送終端企業(yè)的市場(chǎng)生存能力.當(dāng)前以B2B（Business to Business）以及B2G（Business to Government）的終端配送模式中，由于存在特定配送渠道和方法能夠確保貨物快速、安全以及高效的送達(dá)［3］.然而以B2C（Business to Consumer）和C2C（Consumer to Consumer）為絕大多數(shù)的終端配送模式，卻因?yàn)橥藫Q貨繁瑣、配送不到位、配送人員素質(zhì)不高和配送等待時(shí)間較長(zhǎng)等一系列因素制約著其快速發(fā)展.根據(jù)有關(guān)權(quán)威統(tǒng)計(jì)機(jī)構(gòu)數(shù)據(jù)披露，傳統(tǒng)的終端商業(yè)配送中約30%運(yùn)輸成本在“最后一公里”配送中產(chǎn)生，而最終有80%終端配送效率發(fā)生在該環(huán)節(jié)中.對(duì)于傳統(tǒng)配送企業(yè)來說配送時(shí)間、成本以及效率無疑已經(jīng)成為配送終端和配送人員的稀缺資源，如何進(jìn)行配送終端的優(yōu)化已經(jīng)迫在眉睫［4］.文獻(xiàn)［5］運(yùn)用禁忌搜索算法和貪婪插入算法建立車輛最小行駛費(fèi)用和訂單懲罰費(fèi)用數(shù)學(xué)模型，研究電子商務(wù)中訂單的配送優(yōu)化問題，提高了車輛的使用效率問題和降低了訂單的配送時(shí)間問題.在基于啟發(fā)式算法的幾何分析中，文獻(xiàn)［6］利用二次搜索對(duì)區(qū)域終端配送問題建立VRP策略模型，解決配送時(shí)多次補(bǔ)貨的路徑優(yōu)化問題.文獻(xiàn)［7］使用動(dòng)態(tài)規(guī)劃以及貝爾曼最優(yōu)原理將配送終端分解為多個(gè)階段，使用矩陣運(yùn)算的方式確定配送路線最優(yōu)化方法.本文運(yùn)用單純形法和Dijkstra最短路徑法對(duì)配送終端在人員的配送安排以及配送路徑選擇進(jìn)行優(yōu)化，對(duì)配送終端所存在的問題進(jìn)行具體的優(yōu)化處理，從而使得快遞企業(yè)在配送時(shí)間問題上得到了有效控制以及降低了配送成本，從而提高了快遞企業(yè)運(yùn)作效率.

1 實(shí)際問題的引入及數(shù)學(xué)模型的建立

在電子商務(wù)的快速推動(dòng)下，快遞配送企業(yè)在配送效率面前的短板越來越引起人們的重視.本文通過實(shí)地調(diào)研的方式以菜鳥驛站快遞配送企業(yè)為研究對(duì)象，分析快遞包裹配送時(shí)人員配置和路徑選擇所存在的問題，進(jìn)而從企業(yè)層面和配送人員角度兩個(gè)層次分別進(jìn)行配送優(yōu)化，繼而通過合理安排限制資源使配送效益達(dá)到最優(yōu)化的狀態(tài).為了使模型盡量簡(jiǎn)化，去除一些非必要影響因素把配送終端企業(yè)人員的配送問題進(jìn)行了如下描述：菜鳥驛站快遞配送企業(yè)每天的配送人員需求量如表1所示，由于快遞行業(yè)的特殊性，為了確?？爝f配送人員的充分休息，該公司規(guī)定快遞配送人員每周有連續(xù)兩天的調(diào)休制度.

表1 快遞配送終端人員需求

其中，部分快遞配送人員的配送路線圖如圖1所示.

圖1 配送人員路徑圖

圖1 為部分配送人員的配送路線圖，起始點(diǎn)a為菜鳥驛站終端配送原點(diǎn)，g點(diǎn)為配送終點(diǎn).圖1上標(biāo)注具體距離的實(shí)線部分是配送員可能選擇的配送路徑，虛線部分為該類配送員未選擇過的路徑，圖1中并未標(biāo)注這部分路徑的實(shí)際距離.

1.1 基于單純形法配送終端人員調(diào)度安排

1947年Dantzing在研究前人在線性規(guī)劃問題方面的方法，創(chuàng)建了處理線性規(guī)劃問題的單純形法，其理論依據(jù)為在可行域是n維向量空間的Rn多面凸集中，若線性規(guī)劃問題存在最優(yōu)解的情況其必在Rn多面凸集的某頂點(diǎn)處，線性規(guī)劃問題對(duì)應(yīng)的基本可行解一定在頂點(diǎn)處達(dá)到.

設(shè)線性規(guī)劃問題的標(biāo)準(zhǔn)形式為：minf(X)=minCX，其中

同時(shí)，令

將標(biāo)準(zhǔn)式進(jìn)行向量變換：

即

將公式（1）（2）變換可得：

將線性規(guī)劃中的基本可行解X0所對(duì)應(yīng)的分量…,σm≤0時(shí)，則基B所對(duì)應(yīng)的基本可行解X0及充要條件為：

當(dāng)?σm+1,σm+2,…,σm≥0，則原方程沒有最優(yōu)解，需要找到另一個(gè)基本可行解X1，使得f(x1)≤f(x0)存在.其基本思想是：先對(duì)其中一個(gè)基本可行解進(jìn)行判斷，發(fā)現(xiàn)該基本可行解是否是線性規(guī)劃問題中的最優(yōu)解.若不是則按照線性規(guī)劃轉(zhuǎn)換方法，找到另一個(gè)改進(jìn)后的基本可行解進(jìn)行判別.以此往復(fù)不斷進(jìn)行，直到在有限個(gè)基本可行解中找出線性規(guī)劃問題的最優(yōu)解.

將表1中的問題轉(zhuǎn)化形成整數(shù)規(guī)劃模型并進(jìn)行求解為：

將約束方程加入松弛變量si,i=1,2,…,7變成標(biāo)準(zhǔn)形式，則上述整數(shù)規(guī)劃問題的系數(shù)矩陣A，約束右端向量b，目標(biāo)函數(shù)系數(shù)向量C分別為：

調(diào)用MATLAB中的SimpleMthd函數(shù)，調(diào)用格式為：

其中A，C，b，baseVector分別為方程的約束矩陣、目標(biāo)函數(shù)系數(shù)向量、約束右端向量及初始基向量.可以得到X1=12,X2=0,X3=11,X4=5,X5=0,X6=8,X7=0，目標(biāo)函數(shù)的最小值為36，即配送終端可以安排36個(gè)快遞配送人員，其中有12個(gè)人在星期一和星期二調(diào)休，11個(gè)人在星期三和星期四休息，5個(gè)人在星期四和星期五休息，8個(gè)人在周六和周日休息.這樣的調(diào)休制度不僅能夠滿足日常的配送要求，還使得配送人員總數(shù)達(dá)到最小化，降低了配送終端的人力資本耗費(fèi).

1.2 基于Dijkstra最短路徑法下的配送人員路徑優(yōu)化

1959年計(jì)算機(jī)科學(xué)家狄克斯特拉在研究路徑優(yōu)化時(shí)提出了最短路徑的算法，又稱雙標(biāo)號(hào)法.即對(duì)圖中的點(diǎn)Qj賦予兩個(gè)標(biāo)號(hào)(lj,kj)，第一個(gè)標(biāo)號(hào)lj為起點(diǎn)Qs到點(diǎn)Qj的最短距離，第二個(gè)標(biāo)號(hào)kj表示點(diǎn)Qs到點(diǎn)Qj的最短距離上Qj前面一個(gè)鄰點(diǎn)的下標(biāo)，發(fā)現(xiàn)點(diǎn)Qs到點(diǎn)Qj最短距離，其基本步驟［8］：

（a）給起點(diǎn)Q1以標(biāo)號(hào)(0,s)，表示點(diǎn)Q1為起點(diǎn)，起始距離為0；

（b）列出所有以標(biāo)號(hào)的點(diǎn)集合I和未標(biāo)號(hào)集合J以及弧集合T={(Qi,Qj)|Qi∈I,Qj∈J}；

（c）若弧的集合T=?則計(jì)算結(jié)束，若點(diǎn)Qt標(biāo)號(hào)(lt,kt)，則點(diǎn)Qs到點(diǎn)Qt的最短距離為lt，如果點(diǎn)Qt未標(biāo)號(hào)，則不存在這樣的有向路，若T=?，則計(jì)算T中的每一條弧sij=li+cij.在所有的sij中找出最小的弧(Qc,Qd)并令其標(biāo)號(hào)(scd,c).

Dijkstra算法在求網(wǎng)絡(luò)中的其中某個(gè)源節(jié)點(diǎn)到其余節(jié)點(diǎn)時(shí)，核心就是從未標(biāo)記的點(diǎn)中選擇一個(gè)權(quán)值最小的?。?］.

將圖1配送人員路徑進(jìn)行優(yōu)化，其步驟為：

1）給予起始點(diǎn)a標(biāo)號(hào)(0,s)，I={a},J={b,c,d,e,f,h,g}邊的集合{[Qi,Qj]|Qi,Qj其中一點(diǎn)屬于I，另一個(gè)屬于J}={[a,b],[a,c]}，并有：s12=l1+c12，即s12=0+16=16，s13=l1+c13=11，min(s12,s13+s13)=11.給邊[a,c]中的未標(biāo)號(hào)的點(diǎn)c標(biāo)以（11，1）表示從a到c的距離為11，且在a到c的最短路徑上c前面的點(diǎn)為a點(diǎn).

2）I={a,c},J={b,d,e,f,g}，邊集合 {[a,b],[c,b],[c,e]}，則s32=l3+c32=15，s35=l3+c35=16，min(s13,s32,s35)=15，將b以標(biāo)號(hào)（15，3）.

3）同理可得c（11，1），d（20，5），e（16，3），（f18，5）標(biāo)號(hào).

4）此時(shí)I={a,b,c,d,e,f},J={g}，邊集合 {[Qi,Qj]|Qi,Qj其中一點(diǎn)屬于I，另一個(gè)屬于J}={[b,g],[d,g],[f,g]}，則s47=l4+c47=25，min(s27,s47,s67)=24，g點(diǎn)標(biāo)號(hào)（24，6）.

5）最后I={a,b,c,d,e,f},J=?，邊集合{[Qi,Qj]|Qi,Qj其中一點(diǎn)屬于I，另一個(gè)屬于J}=?計(jì)算結(jié)束，得出最短配送路徑依次為a→c→e→f→g，最短配送距離為22 km.

在通過對(duì)配送人員路徑優(yōu)化后可以幫助配送人員在路徑選擇中提供參考，克服以往配送時(shí)以經(jīng)驗(yàn)為主導(dǎo)的配送模式，節(jié)約了配送成本以及調(diào)高了配送效率，對(duì)于配送人員來說時(shí)間日益成為配送中的稀缺資源，通過路徑優(yōu)化降低了時(shí)間和距離成本對(duì)配送人員的影響.

2 總結(jié)

隨著我國(guó)快遞行業(yè)的不斷發(fā)展，傳統(tǒng)式的配送模式終將會(huì)被行業(yè)淘汰.終端配送企業(yè)會(huì)運(yùn)用更為先進(jìn)的管理理念和方法不斷地對(duì)配送效率進(jìn)行優(yōu)化［10］.如何將電子商務(wù)的“最后一公里”配送成本與效率達(dá)到最優(yōu)化是配送企業(yè)一直關(guān)注的問題.通過利用運(yùn)籌學(xué)中的單純形法以及Dijkstra最短路徑法對(duì)配送終端的具體問題建立數(shù)學(xué)模型，以對(duì)配送企業(yè)和配送人員兩個(gè)方面進(jìn)行優(yōu)化.對(duì)于配送企業(yè)可以進(jìn)一步規(guī)范配送模式，降低人力資源的浪費(fèi)以及做到配送成本的最優(yōu)，對(duì)于終端配送人員則可以通過優(yōu)化配送路徑達(dá)到配送效率最大化，提高作業(yè)效率.

［1］李芳.2016年11月12日全網(wǎng)銷售總額統(tǒng)計(jì)［N］.重慶商報(bào)，2016-11-12（4）.

［2］譚述芳.我國(guó)快遞配送最后一公里問題研究［J］.商業(yè)時(shí)代化，2015（3）：62-64.

［3］AIZED Tauseef.Hierarchical modelling of last mile logistic distribution system［J］.The International Journal of Advanced Manufacturing Technology，2014，70（5）：1053-1061.

［4］薛開源，蔣惠西，顧傳進(jìn)，等.快遞配送終端優(yōu)化研究［J］.物流技術(shù)，2016（2）：42-44.

［5］李琳，劉士新，唐家福.電子商務(wù)中訂單配送優(yōu)化模型及兩階算法［J］.系統(tǒng)工程學(xué)報(bào)，2011（2）：237-243.

［6］劉向，李延暉.電子商務(wù)配送的跨區(qū)域VRP模型及其啟發(fā)式算法［J］.清華大學(xué)學(xué)報(bào)（自然科學(xué)版），2006（S1）：1014-1018.

［7］楊茂盛，李琦.基于動(dòng)態(tài)規(guī)劃的物流配送優(yōu)化研究［J］.商場(chǎng)現(xiàn)代化，2007（11）：128.

［8］韓伯棠.管理運(yùn)籌學(xué)［M］.北京：高等教育出版社，2009：85-115.

［9］王志和，凌云.Dijkstra最短路徑算法優(yōu)化及其實(shí)現(xiàn)［J］.微計(jì)算機(jī)信息，2007（33）：275-277.

［10］唐倚智.B2C電子商務(wù)物流的挑戰(zhàn)和趨勢(shì)［J］.物流技術(shù)與應(yīng)用，2012（9）：66-68.

Optimization Analysis of Express Delivery Terminal Based on Simplex and Dijkstra Algorithm

SUN Hui，WANG Xiangqian
（School of Economics and Management，Anhui University of Science&Technology，232001，Huainan，Anhui，China）

Taking the rookie terminal distribution as an example，the paper analyzes the existence of the distri?bution problems.The linear integer programming model is established.Based on the simplex method in the research，the software of the distribution terminal is optimized by the MATLAB software.Finally，the shortest path Dijkstra algorithm is used to study the routing of the distribution personnel to determine the optimal dis?tribution route distribution scheme.

last mile；simplex method；Dijkstra algorithm；distribution optimization

C 936

A

2095-0691（2017）03-0049-04

2017-04-26

孫 輝（1993- ），男，安徽壽縣人，碩士生，主要研究方向：物流與供應(yīng)鏈.