帶有時間窗的電商物流終端配送研究

袁雨果，高華峰

(1.集美大學(xué) 誠毅學(xué)院，福建 廈門 361021；2.湖北民族學(xué)院 經(jīng)濟(jì)與管理學(xué)院，湖北 恩施 445000)

帶有時間窗的電商物流終端配送研究

袁雨果1，高華峰2,*

(1.集美大學(xué) 誠毅學(xué)院，福建 廈門 361021；2.湖北民族學(xué)院 經(jīng)濟(jì)與管理學(xué)院，湖北 恩施 445000)

物流配送是支撐電子商務(wù)發(fā)展的關(guān)鍵環(huán)節(jié)和重要基礎(chǔ)，而電商物流終端配送更是制約配送效率、影響服務(wù)質(zhì)量的關(guān)鍵.以電商物流終端配送為對象，研究時間約束下的帶有時間窗的多快遞員任務(wù)分配和線路優(yōu)化.將其抽象為一個具有時間窗的團(tuán)體定向問題，并設(shè)計一個四步驟啟發(fā)式算法進(jìn)行求解.為驗(yàn)證算法性能，通過構(gòu)建算例對比該算法和標(biāo)準(zhǔn)遺傳算法、粒子群算法的效果差異.方差分析結(jié)果表明，該四步驟啟發(fā)式算法能夠獲得更好效果.

終端配送；時間窗；團(tuán)體定向問題；啟發(fā)式算法

近年來，互聯(lián)網(wǎng)技術(shù)的發(fā)展促進(jìn)了電子商務(wù)的迅速發(fā)展,而電子商務(wù)也成為物流配送業(yè)持續(xù)發(fā)展的重要推動力量[1]；物流配送是支撐電子商務(wù)發(fā)展的關(guān)鍵環(huán)節(jié)和重要基礎(chǔ)[2-3]，物流配送質(zhì)量的高低直接影響客戶對電商企業(yè)的滿意程度[4-5].因此，很多業(yè)界人士指出，電子商務(wù)未來發(fā)展的關(guān)鍵癥結(jié)在于物流配送.正因?yàn)槿绱?，近年來國?nèi)最具代表性的電商巨頭“亞馬遜、阿里巴巴和京東”都在物流配送領(lǐng)域動作頻繁：如2012年初，亞馬遜提出了“云倉儲”服務(wù)并給出明確操作方案；阿里巴巴不遺余力的推動阿里“菜鳥網(wǎng)絡(luò)”；京東花費(fèi)巨資所打造的自有物流體系，其核心價值在于遍及全國各主要城市的“分布式倉儲體系”.不管采取哪種方式，他們的目標(biāo)都是實(shí)現(xiàn)“成本低、時效快、服務(wù)好”的物流配送目標(biāo)，而物流終端配送顯然是實(shí)現(xiàn)這個目標(biāo)的重點(diǎn)，它是制約配送效率、影響服務(wù)質(zhì)量的關(guān)鍵[6-7].

與一般物流配送不同，電商物流終端配送具有對配送方式要求苛刻、對配送時效要求很高、訂單數(shù)量大、規(guī)模小等特點(diǎn)[8].近年來，為了提升電商物流配送的效率和滿意度，電子商務(wù)物流終端配送的模式不斷豐富[9-12].此外，隨著消費(fèi)觀念的轉(zhuǎn)變，有些客戶會對配送時間的個性化提出更高的要求：他們愿意支付額外的費(fèi)用使得物流公司能夠根據(jù)自己的預(yù)約時間進(jìn)行配送(如以小時為單位).通常而言，對配送時間窗口期的要求越精確(即窗口時間跨度越小)，對物流公司配送的要求就越高，需要支付的配送費(fèi)用也會越高.對于這種服務(wù)，一旦無法在客戶預(yù)約的時間內(nèi)完成配送，則物流公司需要承擔(dān)約定的賠償責(zé)任.面對這種新型和傳統(tǒng)配送方式共存的情況，物流公司由于資源的約束(主要是快遞員人數(shù)以及工作時間的限制)，它們往往需要評估各個配送任務(wù)的特征，如配送地址、時間窗口和收益等情況，進(jìn)而規(guī)劃出相應(yīng)的配送線路，從而使總收益最大，該問題可以抽象為帶有時間窗的團(tuán)隊定向問題.

定向問題(orienteering problem,OP)最早是由Golden等人提出來的[13]，它起源于定向運(yùn)動比賽.在該比賽中，每個關(guān)卡都有一定的分值，每名參與者都希望在有限的時間內(nèi)從不同關(guān)卡中獲得盡可能多的分值[14].在此之后，定向問題被廣泛應(yīng)用在交通規(guī)劃、物流配送和旅游線路設(shè)計等眾多領(lǐng)域[15-16].而團(tuán)隊定向問題(team orienteering problem,TOP)則對應(yīng)于以多名成員為小組所進(jìn)行的定向運(yùn)動比賽，在該比賽中，需要為團(tuán)隊中每個成員設(shè)計一條線路，目標(biāo)是使團(tuán)隊所有成員所獲得的分值之和最大[17].團(tuán)隊定向問題也被應(yīng)用在越來越多的領(lǐng)域中[18-19]，而且各種解決該問題的精確算法[20-21]和啟發(fā)式算法[17-18，22-24]被不斷設(shè)計出來.近年來，帶有時間窗的團(tuán)隊定向問題(TOP with time windows,TOPTW)受到了更多的關(guān)注[21，25-27]，主要原因是解決TOPTW的方法與一般TOP有很大的不同.Montemanni和Gambardella設(shè)計了蟻群優(yōu)化[25]、Tricoire等提出變鄰域搜索算法(VNS)并嵌入了一個精確算法以解決路徑可行性的子問題[28]；Vansteenwegen等設(shè)計了一個快速迭代局部搜索算法[26]；Labadie等設(shè)計了基于LP的細(xì)粒度變鄰域搜索算法[27].

以電子商務(wù)物流終端配送為研究對象，研究時間約束下的帶有時間窗的多快遞員任務(wù)分配和線路優(yōu)化.該問題可以分為兩個階段：第一階段是任務(wù)選擇與分配，即選擇需要當(dāng)天配送的任務(wù)，并將所選任務(wù)分配給相應(yīng)的快遞員；第二，根據(jù)配送任務(wù)的特征(如時間窗、獎懲系數(shù)等)，為每個快遞員規(guī)劃配送線路.團(tuán)體定向問題已經(jīng)被證明是一個NP難問題，很難通過精確算法對大規(guī)模問題進(jìn)行精確求解.為此，本文設(shè)計了一個四步驟的啟發(fā)式算法對其進(jìn)行求解.為驗(yàn)證該算法的性能，構(gòu)建了一個算例進(jìn)行實(shí)驗(yàn).

1 數(shù)學(xué)模型構(gòu)建

本文所研究的問題可以抽象為帶有時間窗的團(tuán)體定向運(yùn)動問題(TOPTW).在該問題中，每個快遞員都是從同一個倉儲中心出發(fā)，在完成所有配送任務(wù)后，又返回相同的倉儲中心.由于快遞員都有一定的工作時間限制，因此有可能不能完成所有任務(wù)的配送.因此該問題的目標(biāo)是使得所有快遞員在有限的工作時間內(nèi)取得的效益值之和最大.

設(shè)快遞員人數(shù)為P，物流倉儲中心為v0，每個任務(wù)的配送地址標(biāo)記為v1,v2,…,vN，每個任務(wù)的配送時間窗口期為[Oi,Ei]，如果快遞員早于窗口期開始時間Oi到達(dá)任務(wù)i的配送地址vi，則需要等待；如果他晚于窗口期的結(jié)束時間Ei到達(dá)，則會產(chǎn)生一定的懲罰，該懲罰為ci.假定延遲的時間越長，懲罰值越高，則該懲罰值如式(1)所示，它與vi的時間窗口[Oi,Ei]、到達(dá)vi的時間sip、以及懲罰系數(shù)δi有關(guān).如果快遞員完成配送任務(wù)，則他將得到一個收益值ri.顯然，快遞員在vi是否有凈效益值，取決于ri與pi之差，則該問題的目標(biāo)函數(shù)如式(2)所示，其中yip為0-1變量，若任務(wù)vi分配給快遞員p，則yip=1，否則yip=0.

cip=δ·max[sip-Ei,0]

(1)

(2)

(3)

(4)

(5)

(6)

(7)

sip≥Oi,?i=1,2,…,N

(8)

sip≥Ci,?i=1,2,…,N

(9)

(10)

2 四步驟啟發(fā)式算法

團(tuán)隊定向問題是一個NP難問題，很難在可接受的時間內(nèi)通過多項(xiàng)式算法求解其精確值[13].為此，本文設(shè)計了一個四步驟啟發(fā)式算法，包括解編碼、初始解集合構(gòu)造、解集合進(jìn)化和解集合評估，算法流程如圖1.

圖1 四步驟啟發(fā)式算法流程圖Fig.1 Framework of the four-stepheuristic algorithm

2.1解編碼

2.2初始解集合構(gòu)造

2)從任務(wù)集合中隨機(jī)抽取若干任務(wù)，構(gòu)建任務(wù)序列；

4)拆分任務(wù)以確定每名快遞員的配送任務(wù)及任務(wù)配送線路；

5)計算每名快遞員完成所有配送任務(wù)需要的時長，如果每名快遞員的配送時長滿足式(3)～(10)的約束條件，則該任務(wù)序列為可行解，將其插入到初始解集合中，否則重新返回步驟2)；

6)如果初始解集合IS所包括的可行解數(shù)量達(dá)到種群規(guī)模Q，則結(jié)束初始解集合構(gòu)造過程，否則返回步驟2).

2.3解集合進(jìn)化

在解的進(jìn)化過程中，本文采用局部搜索的方式來進(jìn)行，包括插入、調(diào)整和調(diào)換等三個算子：

1)插入算子：對于某一可行解，隨機(jī)地選擇一個插入點(diǎn)，并從未選擇的任務(wù)中隨機(jī)的選擇一個插入該可行解中，若得到的解仍是可行解，且收益大于插入前，則新形成的解替代原來的解.

2)調(diào)整算子：對于某一可行解，隨機(jī)地選擇該可行解中的兩個任務(wù)，并交換所選擇的任務(wù).根據(jù)原可行解和新產(chǎn)生的解的收益值，采用輪盤賭的方式選擇一個替代原可行解.

3)調(diào)換算子：對于某一可行解，隨機(jī)地選擇其中一個任務(wù)vi，并從未在該解中的任務(wù)中隨機(jī)選擇一個收益大于任務(wù)vi的任務(wù)vj，替代任務(wù)vi；若得到的解仍是可行解，則根據(jù)原可行解和新產(chǎn)生的解的收益值，采用輪盤賭的方式選擇一個替代原可行解.

2.4解集合評估

將進(jìn)化后的所有解進(jìn)行評估，首先還是刪除掉不可行解，包括具有重復(fù)配送解，超過時間約束的解.之后根據(jù)目標(biāo)函數(shù)式(2)進(jìn)行評價.得到最好的Q個解再進(jìn)入新的一次迭代，直至達(dá)到最大迭代次數(shù).在最后一次迭代所得到的解集合中，選擇目標(biāo)函數(shù)值最好的任務(wù)序列，該序列即為最滿意解，作為算法的輸出.

3 算例分析及結(jié)果

為了驗(yàn)證四步驟啟發(fā)式算法的性能，通過構(gòu)建一個算例，并與標(biāo)準(zhǔn)遺傳算法(standard Genetic Algorithm,sGA)和粒子群算法(particle swarm optimization,PSO))進(jìn)行對比.為了減少誤差的干擾，分別用每種方法測試30次，得到的結(jié)果如圖2所示，而圖3為啟發(fā)式算法其中一次實(shí)驗(yàn)的結(jié)果，不同顏色表示不同的快遞員.

為進(jìn)一步分析這3種方法的性能是否有差異，采用方差分析(ANOVA)的方法進(jìn)行驗(yàn)證.3種方法得到的效益值的描述性統(tǒng)計如表1所示.而表2顯示了方差分析的結(jié)果，由于F=7.364，Plt;0.05，表示這3種方法所取得的效益值存在顯著性差異.

表1 描述性統(tǒng)計

表2 方差分析

表3 多重比較(Scheffe)

注：*：均值差的顯著性水平為 0.05

為了進(jìn)一步確定哪種方法存在差異，本文采用了Sheffe方法進(jìn)行多重分析(如表 3所示)：對于HA和sGA的比較，二者平均效益差為6.201 7，Plt;0.05，說明HA獲得的效益值要顯著高于sGA；同樣地，對于HA和PSO的比較，二者平均效益差為7.017 33，Plt;0.05，也說明HA獲得的效益值要顯著高于PSO.因此，方差分析的結(jié)果表明本文所提的啟發(fā)式算法明顯優(yōu)于另外兩種算法的性能.

4 展望

近年來，電子商務(wù)的發(fā)展成為推動物流配送業(yè)持續(xù)發(fā)展的重要推動力量，而物流配送也是支撐電子商務(wù)發(fā)展的關(guān)鍵環(huán)節(jié)和重要基礎(chǔ)，物流終端配送更是制約配送效率、影響服務(wù)質(zhì)量的關(guān)鍵.相比一般物流配送，電商物流終端配送具有訂單數(shù)量大規(guī)模小、用戶對物流的配送方式和配送時效要求高且不斷呈現(xiàn)個性化和差異化等特點(diǎn).這些特點(diǎn)使得電商物流終端配送面臨眾多挑戰(zhàn)和機(jī)遇.

本文所提出的啟發(fā)式算法盡管能夠較好地解決考慮帶有時間窗、具有時間約束的多快遞員配送問題.但是隨著任務(wù)規(guī)模的增加，算法的效率還有待提升.此外，在電子商務(wù)物流終端配送中，會出現(xiàn)等待客戶、運(yùn)輸時間不確定等隨機(jī)問題.因此，在今后的研究中需要考慮將這些隨機(jī)性因素.

[1] 符瑛,彭銀香.電子商務(wù)環(huán)境下物流配送模式選擇[J].中國管理信息化,2009,12(19):115-117.

[2] 楊朋玨,胡昊,王俊嘉,等.電子商務(wù)環(huán)境下城市配送末端網(wǎng)點(diǎn)選址模型研究[J].工業(yè)工程與管理,2014,19(1):35-40.

[3] 張成志,趙亮.電子商務(wù)下的物流配送模式選擇研究[J].物流技術(shù),2012,31(19):66-68.

[4] 崔珊珊,陳宏,俆加勝.電商促銷井噴需求下的應(yīng)急商品配送研究[J].中國管理科學(xué),2013(s1):141-147.

[5] HOLDORF S,HAASIS H-D.Last mile delivery concepts in E-Commerce an empirical approach[C]∥2014 8th International Conference on Software,Knowledge,Information Management and Applications(SKIMA),IEEE,2014:1-6.

[6] 詹斌,谷孜琪,李陽.“互聯(lián)網(wǎng)+”背景下電商物流“最后一公里”配送模式優(yōu)化研究[J].物流技術(shù),2016,35(1):1-4.

[7] 張錦,陳義友.物流“最后一公里”問題研究綜述[J].中國流通經(jīng)濟(jì),2015(4):23-32.

[8] 楊聚平.以客戶為中心“最后一公里”配送模式研究[D].北京:對外經(jīng)濟(jì)貿(mào)易大學(xué),2014.

[9] 詹林敏.電子商務(wù)物流最后一公里配送模式研究[D].大連:大連理工大學(xué),2015.

[10] 陳義友,張錦,曾倩,等.最后一公里配送服務(wù)選擇均衡問題[J].計算機(jī)集成制造系統(tǒng),2016,22(8):2035-2045.

[11] 楊聚平,楊長春,姚宣霞.電商物流中“最后一公里”問題研究[J].商業(yè)經(jīng)濟(jì)與管理,2014(4):16-22.

[12] 方璽,耿艷.我國快遞“最后一公里”收派模式創(chuàng)新探討[C]∥中國論壇論文集,2012:5-5.

[13] GOLDEN B L,LEVY L,VOHRA R.The orienteering problem[J].Naval Research Logistics,1987,34(3):307-318.

[14] CHYAO I M,GOLDEN B L,WASIL E A.A fast and effective heuristic for the orienteering problem[J].European Journal of Operational Research,1996,88(3):475-489.

[15] GUNAWAN A,LAU H C,VANSTEENWEGEN P.Orienteering problem:A survey of recent variants,solution approaches and applications[J].European Journal of Operational Research,2016,255(2):315-332.

[16] VANSTEENWEGEN P,SOUFFRIAU W,VAN OUDHEUSDEN D.The orienteering problem:A survey[J].European Journal of Operational Research,2011,209(1):1-10.

[17] CHAO I-M,GOLDEN B L,WASIL E A.The team orienteering problem[J].European journal of operational research,1996,88(3):464-474.

[18] TANG H,MILLER-HOOKS E.Algorithms for a stochastic selective travelling salesperson problem[J].Journal of the Operational Research Society,2005,56(4):439-452.

[19] BUTT S E,CAVALIER T M.A heuristic for the multiple tour maximum collection problem[J].Computers amp; Operations Research,1994,21(1):101-111.

[20] BUTT S E,RYAN D M.An optimal solution procedure for the multiple tour maximum collection problem using column generation[J].Computers amp; Operations Research,1999,26(4):427-441.

[21] BOUSSIER S,FEILLET D,GENDREAU M.An exact algorithm for team orienteering problems[J].4OR:A Quarterly Journal of Operations Research,2007,5(3):211-230.

[22] ARCHETTI C,HERTZ A,Speranza M G.Metaheuristics for the team orienteering problem[J].Journal of Heuristics,2007,13(1):49-76.

[23] KE L,ARCHETTI C,FENG Z.Ants can solve the team orienteering problem[J].Computers amp; Industrial Engineering,2008,54(3):648-665.

[24] VANSTEENWEGENAABBA P.A guided local search metaheuristic for the team orienteering problem[J].European Journal of Operational Research,2009,196(1):118-127.

[25] MONTEMANNI R,GAMBARDELLA L M.Ant colony system for team orienteering problems with time windows[J].Foundations of Computing amp; Decision Sciences,2009,34(4):287-306.

[26] VANSTEENWEGEN P.Iterated local search for the team orienteering problem with time windows[J].Computers amp; Operations Research,2009,36(12):3281-3290.

[27] LABADIE N,MANSINI R,MELECHOVSKY J,et al.The team orienteering problem with time windows:An LP-based granular variable neighborhood search[J].European Journal of Operational Research,2012,220(1):15-27.

[28] TRICOIER F,ROMAUCH M,DOERNER K F,et al.Heuristics for the multi-period orienteering problem with multiple time windows[J].Computers amp; Operations Research,2013,40(5):1516-1519.

責(zé)任編輯：高山

StudyonTerminalDistributionofE-commerceLogisticswithTimeWindows

YUAN Yuguo1,GAO Huafeng2,*

(1.Chengyi University College,Jimei University,Xiamen 361021,China; 2.School of Economics and Management,Hubei University for Nationalities,Enshi 445000,China)

The logistics distribution is the important back-up and basis for the development of e-commerce,while the terminal distribution of e-commerce logistics is the key to determining the distribution efficiency and affecting the quality of service.Focusing on the terminal distribution of e-commerce logistics,this paper studies the task assignment and route optimization for the multiple couriers with time windows.This issue can be abstracted as a team orienteering problem with time windows(TOPTW).A four-step heuristic algorithm is proposed to solve the TOPTW.In order to evaluate the performance of the proposed algorithm,an example is given to compare the effect of the proposed algorithm with that of the standard genetic algorithm and the particle swarm optimization.The results of an analysis of variance(ANOVA)indicate that the proposed method performs significantly better than the existing algorithms.

terminal distribution;time windows;team orienteering problem;heuristic algorithm

2017-08-23.

福建省中青年教師教育科研項(xiàng)目(JAS160017)

袁雨果(1989-)，女，主要從事物流管理、旅游供應(yīng)鏈管理的研究.*

：高華峰( 1972-)，男，博士，副教授，主要從事企業(yè)管理的研究.

1008-8423(2017)04-0394-05

10.13501/j.cnki.42-1569/n.2017.12.009

C931

A