多快遞員的電商物流“最后一公里”配送研究

袁雨果

多快遞員的電商物流“最后一公里”配送研究

袁雨果

（集美大學 誠毅學院 商船系， 福建 廈門 361021）

物流配送是支撐電子商務發(fā)展的關(guān)鍵環(huán)節(jié)和重要基礎(chǔ)。作為電商物流的最后環(huán)節(jié)——“最后一公里”配送，更是直接影響客戶對電商的滿意度。以電商物流“最后一公里”配送為對象，研究多快遞員任務分配和線路優(yōu)化。將其抽象為一個考慮任務均衡的多旅行商問題，并設(shè)計改進遺傳算法進行求解。為驗證算法性能，通過構(gòu)建算例對比改進遺傳算法和一般遺傳算法的效果差異。獨立樣本t檢驗結(jié)果表明，改進遺傳算法能夠獲得更好效果。

“最后一公里”配送；任務均衡；多旅行商；遺傳算法

一、引言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展和普及，近年來我國電子商務得到了迅猛發(fā)展，特別是B2C和C2C型電子商務更是呈現(xiàn)井噴式發(fā)展，占據(jù)了電子商務交易的主要份額，涌現(xiàn)了一批如淘寶網(wǎng)、京東商城等一批代表性企業(yè)。電子商務的發(fā)展也帶動了物流配送需求的快速增長[1]。根據(jù)《2015年度快遞市場監(jiān)管報告》，全國快遞服務企業(yè)業(yè)務量累積完成206.7億件，其中6成來自于電子商務業(yè)務，電子商務已經(jīng)成為我國快遞業(yè)持續(xù)快速發(fā)展的重要推動力量。另一方面，物流配送也是支撐電子商務發(fā)展的關(guān)鍵環(huán)節(jié)和重要基礎(chǔ)[2，3]，物流配送質(zhì)量的高低直接影響客戶對電商企業(yè)的滿意程度[4，5]。

物流配送的基本流程包括倉儲階段、主干網(wǎng)運輸階段和“最后一公里”配送階段。與一般物流配送不同，電子商務物流“最后一公里”配送具有對配送方式要求苛刻、對配送時效要求很高、個性化差異化配送需求多、訂單數(shù)量大規(guī)模小等特點，因此面臨眾多問題或挑戰(zhàn)[6]?！?015年度快遞市場監(jiān)管報告》指出，2015年我國快遞服務滿意度僅為74分，72小時準時率僅為73.85%，有效申訴率為13.3件/百萬件（27.56萬），其中因投遞服務和延誤導致的申訴分別有10.37萬件和8.62萬件，分別占比37.6%和31.3%。因此，作為物流配送終端環(huán)節(jié)的“最后一公里”成為制約配送效率、影響服務質(zhì)量的關(guān)鍵[7，8]。

本文正是在這樣的背景下，以物流配送“最后一公里”為研究對象，研究多快遞員任務分配和線路優(yōu)化問題。在該問題中可以分為兩個階段：第一個階段是將快遞配送任務分配給不同快遞員；第二階段是根據(jù)任務配送的位置，為快遞員規(guī)劃線路。這個問題可以抽象為一個多旅行商問題（Multiple TravelingSalesman Problem）。過去有很多研究對這個問題展開研究，然而卻往往忽略了任務分配均衡性的問題，從而會導致有些快遞員超負荷運行，而有些快遞員卻處于空閑狀態(tài)。因此，在優(yōu)化多快遞員任務分配和線路優(yōu)化時需要將快遞員間的任務均衡性納入考慮范疇。多旅行商問題已經(jīng)被證明是一個NP難問題，很難通過精確算法對大規(guī)模多旅行商問題進行精確求解。因此本文提出了一個改進遺傳算法，包括了染色體編碼等4個步驟。為了驗證該算法的性能，本文構(gòu)建了一個算例，并引入一般遺傳算法為對比。通過獨立樣本t檢驗的結(jié)果表明，把問題提出的改進遺傳算法比一般遺傳算法具有更好的優(yōu)化效果。

二、文獻綜述

（一）“最后一公里”配送

電子商務物流是指電子商務物流服務提供者采用網(wǎng)絡(luò)化的計算機技術(shù)和現(xiàn)代化的硬件設(shè)備、軟件系統(tǒng)以及先進的管理手段，針對客戶的需求、根據(jù)客戶的訂貨要求，進行一系列的分類、編碼、整理配貨等理貨工作，按照約定的時間和地點將指定數(shù)量和規(guī)格要求的商品傳遞到用戶的活動和過程。它的基本流程包括倉儲、主干網(wǎng)運輸和“最后一公里”配送等3個階段[6]。其中，“最后一公里”配送是電子商務物品從物流倉儲中心發(fā)送至目的地的過程，它是完成電子商務交易的最后一個環(huán)節(jié)[9]。與一般物流配送不同，電子商務物流“最后一公里”配送具有對配送方式要求苛刻、對配送時效要求很高、個性化差異化配送需求多、訂單數(shù)量大規(guī)模小等特點，因此面臨眾多問題或挑戰(zhàn)[6]。

現(xiàn)階段電子商務物流“最后一公里”配送的模式不斷豐富，包括送貨上門、自助收發(fā)箱和顧客自提站等模式[10]。針對送貨上門的研究主要集中于優(yōu)化配送線路、降低配送成本和提升顧客滿意度等方面。而對于自助收發(fā)箱，Mikko等人等人通過仿真研究表明采用自主收發(fā)箱模式可以比標準的送貨上門的模式節(jié)約60%的成本[11]。而客戶自提站模式也是解決最后一公里配送的有效方法，選擇什么樣的機構(gòu)作為自提點的合作伙伴將對“最后一公里”配送的成本、效率產(chǎn)生很大的影響[12]。方璽和耿艷探討了我國“最后一公里”各種配送方式的優(yōu)劣，并提出了創(chuàng)新派送模式的建議[13]。

不管“最后一公里”配送采用哪種方式，都需要解決由哪個快遞員配送、按什么樣的順序配送等問題?？梢詫⒃搯栴}抽象為一個具有多個旅行商的配送問題。

（二）多旅行商問題

多旅行商問題 （Multiple Traveling Salesman Problem，MTSP）是旅行商問題的更為一般化的形式，它需要為多個旅行商規(guī)劃線路。相比旅行商問題，對于多旅行商問題的研究還相對較少，但多旅行商問題卻具有更加重要的實踐意義，很多實際的問題都常常為轉(zhuǎn)換為多旅行商問題并加以求解[14]，比如人力資源規(guī)劃[15-18]、交通規(guī)劃[19，20]、任務分配[21]、生產(chǎn)調(diào)度[22]、出版印刷調(diào)度[23，24]等。

關(guān)于MTSP問題的求解，有學者嘗試從運用精確算法進行求解，比如：Ali和Kennington提出了一個基于分支定界的方法來解決不對稱MTSP問題，但是他們研究的問題規(guī)模相對較小[25]；而Gavish and Srikanth則嘗試用該方法解決一個更大規(guī)模的對稱性MTSP問題[26]，相比過去研究，他們的算法得到明顯提升。

Gromicho等人則基于準分配算法 （quasiassignment） 的精確算法去解決不對稱的MTSP[27]。然而，Tang和Denardo指出MTSP是一個典型NP難問題[28]，很難在有限的時間內(nèi)對大規(guī)模問題進行精確求解。因此，越來越多的學者致力于設(shè)計出各種啟發(fā)式算法對多旅行商問題進行求解，比如神經(jīng)網(wǎng)絡(luò)[29，30]、遺傳算法[22，31，32]、禁忌搜索算法[33]、蟻群算法[34]、模擬退火方法[35]，Sofge等人則比較了多種解決MTSP的進化算法，包括粒子群算法、蒙特卡洛優(yōu)化算法等[36]。

通常情況下，多旅行商問題的主要目標是所有旅行商旅行距離/成本/時間的最小化，然而這往往會導致旅行商之間任務的不均衡[37]。因此，有學者指出限制單個旅行商的路程具有一定的實際意義，因此他們將目標函數(shù)定義為所有旅行商路程最大值的最小化[38，39]。本文基于這樣的背景下，在構(gòu)建多旅行問題模型時充分考慮了快遞員之間的任務均衡。

三、數(shù)學模型構(gòu)建

對于電子商務“最后一公里”配送問題，可以將其抽象為具有單個物流倉儲中心，M個快遞員和N個配送地址的多旅行商問題。配送地址可以是客戶的地址，也可以是自助收發(fā)箱或顧客自提站。本文將相同配送地址的所有快遞均視為同一任務。每個快遞員都從物流倉儲中心出發(fā)，完成所有配送任務以后又回到倉儲中心。問題的目標是使得所有快遞員的配送時間最短。在傳統(tǒng)的多旅行商問題求解中，由于過分追求最配送時間最短，會出現(xiàn)快遞員之間配送任務不均衡的情況[37]。因此，本文為了確?？爝f員的工作量相對均衡，引入了均衡系數(shù)δ。具體建模過程如下：

設(shè)物流倉儲中心為v0，每個任務的配送地址標記為v1，v2，…，vN。快遞員的個數(shù)為M。變量，當快遞員k經(jīng)過弧段（vi，vj） （即配送完任務vi后又相繼配送訂單v）j，則否則yki也為0-1變量，當位于vi的任務分配給第k個快遞員時，則有yki=1，否則yki=0。cij表示快遞員經(jīng)過對應弧段（vi，vj） 的時間距離。則目標函數(shù)如式（1）所示，表示所有快遞員配送時長之和最小。其中zk表示第k個快遞員的配送時長。式（3）-（7）表示問題的約束條件：式（3）表示從物流配送中心出發(fā)，所有訂單只有一個快遞員配送；式（4）表示任一條弧的終點位置僅有一個起點位置與之相連；式（5）表示任一條弧的起點位置僅有一個終點位置與之相連；式（6）表示任務均衡要求；式（7）表示消去構(gòu)成不完整線路的解，其中S為支路消去約束，即消去構(gòu)成不完整路線的解[40]。

四、改進遺傳算法

MTSP問題是一個NP難問題，很難在有限的時間內(nèi)通過一個多項式算法求解其精確值。因此，本文通過設(shè)計一個改進遺傳算法對上述算法進行求解，其算法流程圖如圖1所示，包括了染色體編碼、初始解集合構(gòu)造、解集合進化和解集合評估等4個主要步驟。

圖1 算法流程圖

（一）染色體編碼

沿用上面變量定義，即快遞員數(shù)量為M，需配送的任務地址數(shù)量為N。本文通過引入虛擬任務地址來進行染色體編碼，具體處理如下：引入M-1個虛擬任務地址，則該問題可以轉(zhuǎn)換為單旅行商問題，即一個快遞員從倉儲中心v0出發(fā)，完成所有任務的配送后，又回到v0。則只需要對{v1，…，vN，vN+1，…，vN+M-1}進行隨機排列，即可得到其中一條染色體。為了說明編碼的過程，以具有10個任務，3名快遞員的情況為例。需要引入2個虛擬任務，分別標記為v11和v12。則對{v1，v2，…，v10，v11，v12}這12個任務隨機排序，假定得到其中的一條染色體為0-1-5-7-9-11-10-8-2-12-3-4-6-0。將染色體中的虛擬位置替換為倉儲中心 v0，即可得到0-1-5-7-9-0-10-8-2-0-3-4-6-0。以“0”為標記將該染色體進行拆分，得到{0-1-5-7-9-0}，{0-10-8-2-0}和{0-3-4-6-0}等3條子染色體，即表示3名快遞員所分配的配送任務及任務配送線路。

（二）初始解集合構(gòu)造

根據(jù)上述方式，對{v1，…，vN，vN+1，…，vN+M-1}進行隨機排列，理論上可以有！種排列方式。但是并不是所有的解都是可行解。需要根據(jù)上述的約束條件對隨機產(chǎn)生的解進行甄別，只有滿足所有約束條件的染色體才可以視為可行解，并進入初始解集合。初始解產(chǎn)生的流程如下：

（1）引入M-1個虛擬任務，構(gòu)建任務集合{v1，…，vN，vN+1，…，vN+M-1}；

（2）根據(jù)任務集合，隨機產(chǎn)生一條染色體；

（3）拆分染色體以確定每名快遞員的配送任務及任務配送線路；

（4）計算每名快遞員完成所有配送任務需要的時長zk；

（5）如果滿足均衡度要求，即符合式（6）的任務均衡約束，則該染色體記為可行解，將其插入到初始解集合IS中，否則重新返回步驟（2）；

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

（三）解集合進化

傳統(tǒng)的遺傳算法通常會采用交叉互換、變異和復制等算子。考慮到本文染色體的特殊性，本文在進行解進化時，只采用了單點變異和雙點變異兩種算子。為了更好地說明這兩種算子，分別以圖2和圖3來說明變異的過程。

圖2 單點交叉變異

對于單點變異，首先從解集合中任意選擇一個解（如8-5-4-10-6-2-1-11-7-12-9-3），并從中任意選擇一個基因（如圖2標紅的“2”）。以該變異點為 節(jié) 點 ， 將 染 色 體 截 取 為 8-5-4-10-6和1-11-7-12-9-3兩個染色體片段，并將這兩個染色體片段互換位置，進而得到新的染色體，即：1-11-7-12-9-3-2-8-5-4-10-6。

同樣地，以圖3為例說明染色體雙點變異的過程。同樣從解集合中隨機選擇一條染色體（如1-11-7-12-9-3-2-8-5-4-10-6），并在選取的染色體中隨機選擇兩個基因（如圖3的“7”和“5”）。以兩個變異基金為節(jié)點，可以將染色體截取為1-11，12-9-3-2-8和4-10-6等3個子染色體片段。將兩個變異基因之間的染色體片段進行倒序排序，得到新的染色體，即1-11-7-8-2-3-9-12-5-4-10 -6.

圖3 兩點交叉變異

（四）解集合評估

將進化后的所有解進行評估，首先還是刪除掉不可行解，包括具有重復配送和沒有配送到的解，以及刪除掉不滿足任務均衡條件的解。之后根據(jù)目標函數(shù)Eq.（1）進行評價。得到最好的Q條染色體再進入新的一次迭代，直至達到最大迭代次數(shù)。將最后的解集合中性能最好的染色體即為最滿意解，作為算法的輸出。

五、算例分析及討論

為了說明本算法的性能，通過構(gòu)建一個算例來對比改進遺傳算法 （Improved Genetic Algorithm，IGA）的效果。綠色方塊為唯一的倉儲物流中心，并隨機產(chǎn)生50個訂單，其位置隨機分布在倉儲物流中心的四周（如圖4紅色圓圈所示），另外產(chǎn)生4名快遞員。此外，本文引入了標準遺傳算法（Standard Genetic Algorithm，SGA）作為對比。分別用IGA和SGA對該算例運行100次，并運用獨立樣本t檢驗對兩種方法運行的結(jié)果進行比較分析。在算法運行前，需要對輸入?yún)?shù)進行設(shè)定，將均衡度δ設(shè)定為0.5，種群規(guī)模為200。

圖4

圖5 SGA和IGA優(yōu)化效果對比（100次）

圖6 SGA和IGA優(yōu)化效果對比圖

表1 兩種方法優(yōu)化結(jié)果的描述統(tǒng)計

表2 兩種方法優(yōu)化結(jié)果的獨立樣本T檢驗結(jié)果

兩種方法運行的結(jié)果如圖5所示，其中藍色曲線表示SGA所優(yōu)化的結(jié)果，而紅色曲線表示IGA所優(yōu)化的結(jié)果。圖6（左）展示了運行SGA100次中效果最優(yōu)方案，在這個優(yōu)化方案中，每個快遞員的線路分別為：[15 28 1 33 10 40 32 19 21 31 47 36 18]、 [41 14 49 23 6 26 24 48 27 34 17 16 11 9]、[37 20 8 25 7 30 42 35 50 13 43 45 2]和[12 29 44 4 46 3 38 39 22 5]；而圖6（右）則展示了運行IGA100次中效果最優(yōu)的方案，在這種優(yōu)化方案中，每個快遞員的線路分別為：[18 36 23 47 31 21 19 32 40 10]、[1 33 39 38 3 46 29 5 22 28 15]、[37 2 12 44 4 45 43 13 50 35 42 30 7 25 8 20]和[41 9 11 16 24 48 27 34 17 6 26 49 14]。

為了進一步比較兩種方法的差異，本文運用獨立樣本t檢驗的方法對兩種方法得到的結(jié)果進行進一步的分析對比。兩種方法優(yōu)化的結(jié)果如表1所示，而通過獨立樣本t檢驗發(fā)現(xiàn)IGA得到的結(jié)果（均值=1371.04，標準差=131.15）顯著優(yōu)于（均值=1519. 72，標準差=165.87） （t（100）=7.031，P＜0.05），如表2所示，此外，IGA的穩(wěn)定性也要高于SGA（131.15＜165.87）。

六、研究總結(jié)與展望

近年來，我國電子商務的迅猛發(fā)展帶動了物流配送需求的快速增長。而另一方面，物流配送也是支撐電子商務發(fā)展的關(guān)鍵環(huán)節(jié)和重要基礎(chǔ)。特別是作為“最后一公里”的物流配送，更是直接影響客戶對電商的滿意度。與一般物流配送不同，電子商務物流的“最后一公里”配送具有對配送方式要求苛刻、對配送時效要求很高、個性化差異化配送需求多、訂單數(shù)量大規(guī)模小等特點，因此面臨眾多問題或挑戰(zhàn)。

本文以電子商務物流“最后一公里”配送為研究對象，研究多快遞員任務分配和線路優(yōu)化。將該問題抽象為一個考慮任務均衡的多旅行商問題，并設(shè)計了一個改進遺傳算法對其進行求解。該算法包括染色體編碼、初始解集合構(gòu)造、解集合進化和解集合評估等4個步驟。其中在染色體編碼中，本文引入了虛擬任務，從而優(yōu)化了染色體的編碼方式；在解集合進化中，與一般遺傳算法通過交叉互換、變異和復制等算子進行進化不同，本文主要采用單點和雙點變異的算子。為了驗證算法的性能，構(gòu)建了一個算例來比較改進遺傳算法和一般遺傳算法的效果。獨立樣本t檢驗的結(jié)果表明，改進遺傳算法確實能夠獲得更好的優(yōu)化方案。

本文所提出的改進遺傳算法盡管能夠較好地解決考慮任務均衡的多旅行商問題，但是隨著任務規(guī)模的增加，算法的效率還有待提升。此外，在電子商務物流“最后一公里”配送中，特別是對于送貨上門這種配送方式，經(jīng)常會出現(xiàn)客戶具有嚴格的配送時間窗口的問題，同時在配送過程中也會出現(xiàn)等待客戶、運輸時間不確定等隨機問題。因此，在今后的研究中需要考慮配送時間窗口和隨機性的問題。

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

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

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

[4]崔珊珊，陳宏，俆加勝.電商促銷井噴需求下的應急商品配送研究[J].中國管理科學，2013，（s1）：141-147.

[5]Holdorf S，Haasis H-D.Last mile delivery concepts in E-Commerce an empirical approach[A].，2014 8th IEEE International Conference on Software，Knowledge，Information Management and Applications（SKIMA）[C].2014：1-6.

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

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

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

[9]Lee HL，Whang S.Winning the last mile of e-commerce[J].MIT Sloan Management Review，2001，42（4）：54-62.

[10]詹林敏.電子商務物流最后一公里配送模式研究[D].大連：大連理工大學，2015.

[11]Punakivi M，Holmstr.m J，Yrj.l.H.Solving the last mile issue：reception box or delivery box?[J].International Journal of Physical Distribution &Logistics Management，2001，31（6）：427-439.

[12]Song L，Cherrett T，Mcleod F，等.Addressing the last mile problemthe transport impacts of collection/delivery points[J].Transportation Research Record Journal of the Transportation Research Board，2009，2097（2097）：9-18.

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

[14]Bektas T.The multiple traveling salesman problem：an overview of formulations and solution procedures[J].Omega，2006，34（3）：209-219.

[15]Svestka JA，Huckfeldt VE.Computational experience with an msalesman traveling salesman algorithm [J].ManagementScience，1973，19（7）：790-799.

[16]Gilbert KC，Hofstra RB.A new multiperiod multiple traveling salesman problem with heuristic and application to a scheduling problem[J]. Decision Sciences，1992，23（1）：250-259.

[17]Okonjo-Adigwe C.An effective method of balancing the workload amongst salesmen[J].Omega，1988，16（2）：159-163.

[18]Calvo RW，Cordone R.A heuristic approach to the overnight security service problem[J].Computers&Operations Research，2003，30（9）：1269-1287.

[19]Angel R，Caudle W，Noonan R，等.Computer-assisted school bus scheduling[J].Management Science，1972，18（6）：279-288.

[20]Kim KH，Park Y-M.A crane scheduling method for port container terminals[J].European Journal of operational research，2004，156（3）：752-768.

[21]Basu A，ElnagarA，Al-HajjR.Efficientcoordinated motion[J]. Mathematical and computer modelling，2000，31（2-3）：39-53.

[22]Tang L，Liu J，Rong A，等.A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron&Steel Complex☆ [J].European Journal of Operational Research，2000，124（2）：267-282.

[23]Gorenstein S.Printing press scheduling for multi-edition periodicals[J]. Management Science，1970，16（6）：373-383.

[24]Carter AE， Ragsdale CT.Scheduling pre-printed newspaper advertising inserts using genetic algorithms[J].Omega，2002，30（6）：415-421.

[25]Ali AI，Kennington JL.The asymmetric M-travelling salesmen problem：A duality based branch-and-bound algorithm[J].Discrete Applied Mathematics，1986，13（2-3）：259-276.

[26]Gavish B，Srikanth K.An optimal solution method for large-scale multiple traveling salesmen problems[J].Operations Research，1986，34（5）：698-717.

[27]Gromicho J，Paix.o J，Bronco I.Exact solution of multiple traveling salesman problems.Combinatorial Optimization：Springer，1992：291-292.

[28]Tang CS，Denardo EV.Models arising from a flexible manufacturing machine，part I：minimization of the number of tool switches[J]. Operations research，1988，36（5）：767-777.

[29]Somhom S，Modares A，Enkawa T.Competition-based neural network for the multiple travelling salesmen problem with minmax objective[J]. Computers&Operations Research，1999，26（4）：395-407.

[30]Torki A，Somhon S，Enkawa T.A competitive neural network algorithm for solving vehicle routing problem [J].Computers& Industrial Engineering，1997，33（3）：473-476.

[31]Carter AE，Ragsdale CT.A new approach to solving the multiple traveling salesperson problem using genetic algorithms[J].European Journal of Operational Research，2006，175（1）：246-257.

[32]Yuan S，Skinner B，Huang S，等.A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms[J]. European Journal of Operational Research，2013，228（1）：72-82.

[33]Ryan JL，Bailey TG，Moore JT，等.Reactive tabu search in unmanned aerialreconnaissance simulations [A].Proceedings ofthe 30th conference on Winter simulation[C].IEEE Computer Society Press，1998：873-880.

[34]Pan J，Wang D.An Ant Colony Optimization Algorithm for Multiple Travelling Salesman Problem [A].InternationalConference on Innovative Computing，Information and Control[C].2006：210-213.

[35]Song C-H，Lee K，Lee WD.Extended simulated annealing for augmented TSP and multi-salesmen TSP[A].2003 IEEE Proceedings of the International Joint Conference on Neural Networks[C].2003：2340-2343.

[36]Sofge D，Schultz A，De Jong K.Evolutionary computational approaches to solving the multiple traveling salesman problem using a neighborhood attractor schema [A].Workshops on Applications of Evolutionary Computation[C]：Springer，2002：153-162.

[37]Alves RM，Lopes CR.Using genetic algorithmstominimizethe distance and balance the routes for the multiple traveling salesman problem[A].2015 IEEE Congress on Evolutionary Computation（CEC）[C].2015：3171-3178.

[38]周輝仁，唐萬生，王海龍.基于差分進化算法的多旅行商問題優(yōu)化[J].系統(tǒng)工程理論與實踐，2010，30（8）：1471-1476.

[39]周輝仁，唐萬生，魏穎輝.基于GA的最小旅行時間的多旅行商問題研究[J].計算機應用研究，2009，26（7）：2526-2529.

[40]李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京：中國物資出版社，2001.

Study on Last Mile Delivery of Multi-Couriers E-logistics

YUAN Yu-guo
（Chengyi University College，Jimei University，Xiamen，F(xiàn)ujian 361021）

The logistics is the important back-up and basis for the development of E-commerce.Especially，the Last Mile Delivery，which serves as the last part of the E-logistics，is directly affect the customer satisfaction.This paper focuses on the Last Mile Delivery，and studies the task assignment and route optimization for the multiple couriers.This issue can be abstracted as a multiple travelling problem with consideration of task balancing.An improved genetic algorithm is proposed to solve the MTSP.In order to evaluate the performance of the proposed algorithm，an instance is constructed，and the basic genetic algorithm is used as baseline.The results of an independent samples t-test indicate that the proposed method indeed performs significantly better than the basic genetic algorithm.

last mile delivery；task balancing；MTSP；genetic algorithm

C931

A

1671－9743（2017）07－0039－06

2017-05-21

袁雨果，1989年生，女，陜西漢中人，助教，研究方向：物流管理、旅游供應鏈管理。