賀冰倩, 李昆鵬, 成幸幸

(華中科技大學 管理學院,湖北 武漢 430074)

0 引言

網(wǎng)絡購物的迅猛發(fā)展給我國快遞業(yè)帶來了前所未有的發(fā)展契機，而日益激烈的行業(yè)競爭，不斷上升的客戶要求，促使快遞企業(yè)在提高服務水平的同時關注運作效率與成本。從理論和實踐角度看，實現(xiàn)收派路徑的智能選擇，提高收派效率，提高服務水平，降低運營成本，對于企業(yè)提高競爭力具有十分重要的意義。

本文以A快遞公司為例，研究公司日?？旒张芍新窂絻?yōu)化問題。面對日益增長的快件服務需求，快遞公司的作業(yè)活動是一個復雜的、充滿隨機性的動態(tài)調(diào)度過程，簡化如圖1所示，收件請求隨機到達，配送快件固定到達，每個批次開始時，收派員執(zhí)行已知的收派任務，收派過程中靈活處理臨時到達的收件請求，如圖2所示，任務完成后返回網(wǎng)點，整個批次受時長與運輸工具荷載限制。A快遞公司在派送處理方面主要以客戶為中心，盡可能最大化客戶滿意程度，但目前業(yè)務水平已到達瓶頸階段，希望尋求進一步提升，主要突破口在于以下兩個方面：首先是需要提升路線行走效率，經(jīng)驗決定路線、業(yè)務生疏、訂單的隨機性，都導致了現(xiàn)階段配送耗時增加；其次是時間反饋精確性需要加強。目前實際派送過程與進展程度反饋存在偏差，客戶無法準確獲知收派員上門服務時間，公司無法根據(jù)目前的派送效率設計人員安排規(guī)則及批次周期時長。本文以此為背景，深入研究快件“最后一公里”收派流程，綜合考慮收派混合、動態(tài)性、時間窗和容量約束四個最主要的因素，找尋適用于實際問題的流程優(yōu)化及高效的路線設計。

圖1 快遞公司快件實際收派流程

圖2 靈活處理收件請求

關于快遞公司收派問題的研究，除了從流程角度[1,2]、配送量[3]、客戶群體劃分[4]等方面展開，在路徑設計方面，丁浩等[5]針對目前快遞車輛運輸成本問題，采用Dijkstra快速找出快遞配送派件過程中的最短路；劉欣萌等[6]研究了單個配送中心帶時間窗的車輛路徑問題；饒衛(wèi)振等[7]研究了大規(guī)模具有能力約束的車輛路徑問題；賀政綱等[8]提出了物流配送系統(tǒng)中存在的車輛負載不均衡問題；張如云等[9]提出了低碳、節(jié)能和成本節(jié)約最小化的城市車輛配送問題模型；熊浩等[10]研究需求可拆分車輛路徑問題，提出三階段禁忌算法用于計算雙層規(guī)劃模型。

側重這四類約束的VRP問題，一直是國內(nèi)外研究的重點。在建模優(yōu)化方面，Ninikas等[11]針對動態(tài)裝卸混合VRP問題，提出再優(yōu)化模型；Chabrier等[12]對基礎最短路徑的生成提出了若干優(yōu)化方法；Feillet等[13]針對基礎最短路徑問題，放松約束條件實現(xiàn)路徑生成；Gendreau等[14]將原來用于計算靜態(tài)問題的模型，改進成為計算動態(tài)問題的模型。在算法設計方面，Clarke等[15]針對不同容量的一組車輛服務若干客戶的問題，設計了一種迭代算法；針對帶時間窗問題，Desrochers等[16]運用動態(tài)規(guī)劃、LP松弛、列生成來逐步求解；Taillard等[17]用禁忌搜索迭代求解；Athanasopoulos等[18]研究分支定界框架下的帶時間窗的多周期車輛路徑問題的有效方法。在策略選擇方面，Gelinas等[19]提出策略并評估了分支節(jié)點選擇的標準；Bent等[20]研究有隨機客戶的帶時間窗的車輛路徑問題，提出多情景法預測未來的客戶；Yang等[21]考慮空載成本，任務延遲，任務未完成等成本，研究實時多車裝卸混合問題，提出了一種再優(yōu)化策略；Angelelli等[22]針對動態(tài)多周期路徑問題，提出了幾種短期路徑策略。

國內(nèi)外關于快遞企業(yè)收派研究偏重于問題分析與流程質量評估。路徑設計方面，由于VRP問題非常靈活，針對不同情況背景，有不同的側重點?？爝f收派屬于偏實際應用且特點鮮明的一類問題，以往文獻只是在部分方面與本文研究的情況類似。所以針對快遞公司實際派送情況，如何將收派混合、動態(tài)性、時間窗和容量約束四個要求結合起來，并采用改進的禁忌搜索算法，靈活處理動態(tài)需求，得出適用于實際情況的結果，將是本文研究的重點。

1 問題模型構建與分析

1.1 數(shù)學模型

模型目標函數(shù)：

(1)

約束條件：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

ai≤wi≤bi;?i∈A,?k∈K

(13)

(14)

其中(1)為模型的目標函數(shù)，即總路線行走時間最短；(2)～(3)表示必須完成所有已安排的收派任務；(4)～(5)表示收派員必須從服務網(wǎng)點出發(fā)并返回；(6)為線路平衡約束，表示任一收派任務完成后，收派員必須前往下一個客戶點；(7)為單次收派時間約束；(8)～(9)為載重約束，(8)表示車輛裝載快件總重量的變化，(9)表示在收派過程中任何時候車輛都不超重；(10)～(11)為體積約束，(10)表示車輛裝載的快件總體積的變化，(11)表示收派過程中車輛不能超過最大裝載體積；(12)表示車輛到達相鄰兩個客戶點的時間關系；(13)為時間窗約束，表示收派員必須在客戶所要求的時間范圍內(nèi)到達地點；(14)表示0-1變量，若收派員k在服務完客戶i后服務客戶j，值為1，否則為0。

1.2 區(qū)域熱點劃分

實際收派過程中快件數(shù)量多，若以每件為單位輸入算法進行運算，會使算法運算時間及運算難度呈指數(shù)型上升。因此，本文引入“熱點”的概念，以有效合并相近點，達到優(yōu)化運算效率的目的。

所謂熱點，具體指一個地址，以這個地址為中心的一定范圍內(nèi)覆蓋了若干快件的收貨地址，在運算中，本文統(tǒng)一默認將屬于覆蓋范圍內(nèi)的快遞送往對應的熱點地址，這樣可大大降低運算中點的數(shù)量，對結果的質量也不會產(chǎn)生很大影響。熱點的具體劃分規(guī)則如下：①收集某服務區(qū)域一段時間內(nèi)的收派件數(shù)據(jù)；②將快件地址信息根據(jù)距離進行聚類，每個類別的中心為熱點，覆蓋周圍直徑為20米的區(qū)域；③找出不重復的熱點地址，利用電子地圖建立熱點間的距離矩陣；④快件和熱點匹配，根據(jù)快件地址信息將其分配到距離最近的熱點。

通過以上四個步驟就能對派件問題的數(shù)據(jù)進行初步處理，合并距離相近的點，減少點的數(shù)量，從而提升運算效率。

2 “最后一公里”收派優(yōu)化方案算法說明

本節(jié)對區(qū)域收派流程進行優(yōu)化設計，設計內(nèi)容包括數(shù)據(jù)處理和計算機編程實現(xiàn)路徑智能化計算。方案的整體框架圖如圖3所示。

圖3 收派流程優(yōu)化方案框架圖

當一批快件到達配送網(wǎng)點，先在數(shù)據(jù)庫中找到當前批次快件信息。根據(jù)快件地址信息，動態(tài)劃分熱點。每個熱點，依次與快件匹配后，計算熱點總的快件重量、體積，作為該熱點的需求信息。然后計算各熱點之間的距離矩陣，作為距離信息，輸入算法。同時根據(jù)實際情況，輸入當前可用的人員車輛信息、歷史單票快件的服務時間，從而保證輸出結果的可用性與準確性。在收派件過程中，當新的動態(tài)需求到達，利用優(yōu)化算法再次優(yōu)化收派路徑。最后根據(jù)算法得到路徑結果，合理安排人員及對應行走路徑。

2.1 收派路徑問題求解基本框架

本算法主要通過時間片的分割，轉動態(tài)需求為靜態(tài)需求，實時計算收派員當前點及以后的可行路徑，最小化時間消耗，并將生成的行走路線結果實時反饋到收派員，將快件到達時間實時反饋給客戶，保證收派工作順利展開。

算法首先讀入相應的快件信息和人員信息，初始解的生成采用貪婪算法。雖然貪婪算法可能獲得較好的可行解，但隨機性較強，所以需要做進一步優(yōu)化。

本文之所以采用禁忌搜索算法作為后續(xù)優(yōu)化算法，主要是基于研究問題本身的特點，問題本身的限制條件不多，不易產(chǎn)生沖突，禁忌搜索算法搜索范圍廣泛，產(chǎn)生可行解的空間廣，能最大可能性的找到最優(yōu)解，適用性相對較好。

圖4 區(qū)域收派優(yōu)化路線生成算法整體工作流程圖

針對動態(tài)到達的收件需求，由于已經(jīng)分配給收派員的任務無法再分給別的收派員，只能在每條路徑已有的任務上，加入新的任務，采取基于臨近原則處理動態(tài)需求的TSP問題求解即可滿足。

基于此，區(qū)域派送優(yōu)化路線的生成算法整體工作流程如圖4所示。

2.2 基于時間窗要求的貪婪算法求解初始解

在算法求解的第一階段，本文首要目標是產(chǎn)生一個可行解，在此基礎上盡可能獲得較優(yōu)的解。產(chǎn)生可行解的方法為基于時間要求的貪婪算法，對于時間要求高的客戶，先進行裝車安排，依次搜索與它距離近的客戶訂單，裝入同一輛車，直到達到容量約束上限，然后安排下一輛車。需注意，派件和收件對車容量的影響，不僅要保證出發(fā)時的車裝載量不超過車容量，還要保證途中的車裝載量不超過車容量。具體的操作流程如圖5所示。

在使用基于時間窗要求的貪婪算法獲得初始解的方法外，考慮到希望在后續(xù)優(yōu)化迭代中，獲得更大的搜索廣度，本文還用隨機的方法生成了一組初始解。上述方法生成的初始解，通過實例測試，可行度高且質量較好(尤其是第一種)，為隨后的迭代優(yōu)化提供了好的基礎。

2.3 改進的禁忌搜索算法

由于優(yōu)化的目的是找到總行駛時間最短的方案，所以改進的禁忌搜索算法的搜索空間在一個較大范圍內(nèi)進行，以跳出局部最優(yōu)來尋找全局最優(yōu)，并舍棄不可行解。算法在當前搜索區(qū)域內(nèi)進行了一定次數(shù)的搜索后，若不能發(fā)現(xiàn)更好的解，就執(zhí)行分散搜索策略，將禁忌表清空，從一個新的初始解開始搜索。如果最好解的記錄被更新，就執(zhí)行集中搜索策略，且清空禁忌表，可以在當前區(qū)域更自由的搜索。

關于鄰域解的獲得。鄰域解生成方法對于搜索效率有很大的影響。考慮到問題規(guī)模，每批次收派工作量不會很大，即服務點個數(shù)有限，所以本文盡可能在鄰域搜索時，全面計算各個鄰域。為了節(jié)省運行時間，在生成鄰域解前設定一個評判標準，例如時間和容量等硬性約束，若不能滿足約束，則舍棄。具體實現(xiàn)方法為：①移動點選擇。從當前解第一條路徑的第一位客戶開始，將其抽出；②移動位置選擇。遍歷其他有容量剩余的路徑，將之前抽出的點依次插入這條路徑每兩個客戶之間以及最后一個客戶之后；③可行性判斷。若滿足約束則計算當前解的目標值；④記錄與調(diào)整。遍歷所有的情況后，保留結果最好的兩個解，若該解為明顯劣解，則將其舍去，隨機生成一個可行解代替。⑤鄰域解優(yōu)化。生成的鄰域解不一定達到了最優(yōu)狀態(tài)，對其中的每條路徑分別進行調(diào)整能進一步提升鄰域解的質量，在此本文采取Gendreau等[23]提到的路徑調(diào)整US算法進一步優(yōu)化鄰域解。

關于終止條件。在改進的禁忌搜索算法中采用總分散搜索次數(shù)和連續(xù)沒有找到更好解次數(shù)來控制，分別記作N和M，每當連續(xù)未提升次數(shù)達到M時執(zhí)行分散搜索，當分散搜索次數(shù)達到N時，搜索停止。詳細步驟如圖6所示。

圖6 改進的禁忌搜索算法

2.4 基于臨近原則處理動態(tài)需求

當收派員在派件途中，會隨機到達若干收貨請求。請求反饋到系統(tǒng)，系統(tǒng)中有各個收派員的實時位置和容量信息，管理人員需要讓收派員在完成原來任務的基礎上，靈活加入新收件任務， 具體的安排方式如下：

(1)當每個動態(tài)請求到來時，系統(tǒng)自動獲取收貨位置和各個收派員當前未完成任務點的集合，算出其間距離，并按升序排列；(2)選定第一個未完成任務點；(3)將該動態(tài)收貨請求加入該任務點之后，更新路徑長度、時間，以及各個節(jié)點車的裝載量；(4)判斷路徑是否可行，考慮容量約束、時間(距離)要求。若可行，將該收派員的新路徑信息發(fā)送到本人，處理結束；若不可行，選定下一個未完成任務點，轉至步驟(3)。

3 A快遞公司快件收派案例分析

3.1 案例背景

為了驗證所提出的優(yōu)化方案在實際問題中的有效性，本文結合A快遞公司實際案例進行模擬。A快遞公司是一家著名快遞企業(yè)，經(jīng)營國內(nèi)外快遞業(yè)務，于九十年代初成立。隨著客戶配送需求的增加，A快遞公司的服務網(wǎng)絡延伸開來。目前A快遞公司希望進一步提升競爭力，在“最后一公里”快件收派上提升效率，并且完善對收派員作業(yè)的管理。A公司現(xiàn)存的問題簡要概括為：收派路線行走效率低下，時間反饋精確性不高。

將本文提出的優(yōu)化方案用于A快遞公司，首先是考慮到與其他快遞企業(yè)相比較，A快遞公司管理模式較規(guī)范，信息傳遞系統(tǒng)較先進，有更好的實施性和比較性。其次是通過優(yōu)化方案結果和實際派送情景比較，找出本研究的意義及提升空間，為后續(xù)研究做鋪墊。

圖7 深圳市南頭區(qū)

本文利用A快遞公司2015年10月份位于深圳市南頭區(qū)的實際收派件數(shù)據(jù)，來說明收派路徑優(yōu)化的處理流程及實施效果。深圳市南頭區(qū)位于深圳市西南部，如圖7，是深圳經(jīng)濟特區(qū)，覆蓋面積約182平方公里。這一整個月的快件收派歷史數(shù)據(jù)包含了3621個收件任務和2793個派件任務，一共安排了三位收派員，都使用同樣的交通工具二輪電動車進行收派活動，每個批次開始時，從派送網(wǎng)點出發(fā)，結束任務后，返回派送網(wǎng)點。該企業(yè)中有一個“收1派2”的規(guī)則，即客戶下單后1小時完成收件，快件出倉后2小時完成派件，作為衡量結果的一個標準。

3.2 小規(guī)模路線優(yōu)化方案實施效果

本組數(shù)據(jù)選取部分小規(guī)模的批次，客戶數(shù)量在5～10之間，包含收件和派件，由最多三名收派員完成。收派員的交通工具均為二輪電動車，標準載重為60kg，速度為24km/h，本文假設這三個收派員的操作水平、行走速度、服務速度一定，即看作相同的員工來完成這次工作。

為衡量模型的有效性及改進禁忌搜索算法的高效性，采用CPLEX軟件求解本數(shù)據(jù)中的六組小規(guī)模算例，并與改進禁忌搜索算法得到的解作比較，結果如表1所示。

表1 CPLEX與改進禁忌搜索對小規(guī)模算例測試結果

測試結果顯示，所有客戶均能在時間窗要求內(nèi)被服務。由表1可以看出，對于客戶數(shù)目為5～9的算例，改進的禁忌搜索算法和CPLEX得到相同的最優(yōu)解；對于客戶數(shù)目為10的算例，改進的禁忌搜索算法得到近似于CPLEX的最優(yōu)值。在計算時間上，改進的禁忌搜索算法較CPLEX快很多。由此可見，對于小規(guī)模算例，改進的禁忌搜索算法可以在短時間內(nèi)獲取最優(yōu)解或近似最優(yōu)解。

3.3 大規(guī)模路線優(yōu)化方案實施效果

隨著客戶數(shù)目的增加，CPLEX的運行時間會急劇增加，無法在可行時間內(nèi)獲得最優(yōu)解。故對于大規(guī)模算例，本文采用實際收派數(shù)據(jù)與算法得到的解作比較，以體現(xiàn)算法的高效性。

本文從10月份的數(shù)據(jù)中，挑選了50組情景各異的批次，它們的數(shù)據(jù)量不同、時間點不同、動態(tài)請求到來的規(guī)律不同。本文仍然把他們放在相同外在條件下，即三名能力相似的收派員，交通工具均為二輪電動車。

首先將每組數(shù)據(jù)提取出來進行整理，設定派件開始時間，對應開始派件時已知的收派任務，以及需求到達時間，對應后續(xù)派件過程中接收到收件任務。然后對地址進行熱點劃分，將同一熱點的多個數(shù)據(jù)合并到一個點，并計算該點的快件重量和快件數(shù)量。在得到所有熱點信息后，計算熱點距離矩陣。然后帶入程序運算，得到初始路徑規(guī)劃。在收派員派送過程中隨時更新收件請求，添加進行走路徑中，從而得到最終的收派任務完成結果。

測試結果分為兩個方面：任務完成時間和任務完成情況。通過這兩個指標來比較實際操作與算法計算的結果，可全面反映優(yōu)化方案的提升效果。任務完成時間與歷史數(shù)據(jù)時間比較可以展現(xiàn)時間上的優(yōu)化性能，任務完成比例可以展示方案的實用性，滿足時間窗任務比例可以展示方案的柔性。

表2展示了優(yōu)化方案結果，其中靜點和動點分別表示路徑生成前的熱點數(shù)和派件過程中接到的總收件請求數(shù)，完成率為最終服務客戶的比例，時間窗比率為完成的任務中，滿足“收1派2”的客戶比例，用時為所有參與派件的人員用時總和，比率為程序結果用時與實際用時之差比上實際用時，為負值表示實際用時更短，為正值表示程序結果用時更短。結果表明，隨著點數(shù)的增加，用時增加，算法在絕大多數(shù)批次的結果優(yōu)于歷史數(shù)據(jù)的結果，在點數(shù)較小的時候(例如批次2、4、13、32)，算法得到的結果劣于現(xiàn)實操作的概率較大，這可能由于人工對于較簡單的路徑依靠經(jīng)驗判斷可以完成的更好，而算法存在波動性與隨機性，隨著點數(shù)的增多，人工無法進行規(guī)劃，算法的優(yōu)勢性可明顯體現(xiàn)。雖然每批數(shù)據(jù)的特點不同，優(yōu)化的程度也不同，但是平均保持在百分之十，有了一定的提升。另外結果還說明，動態(tài)點的比例越高，對總用時的影響越大，因為在相同總點數(shù)的情況下，動態(tài)點越多，優(yōu)化空間越少，導致了用時的增加。

任務完成率與滿足時間窗的任務比例，如表3所示。上述50個批次一共包含1739個點，其中完成了收派任務的點數(shù)是1626，任務完成率是93.5%，有113個動態(tài)請求沒有在當批次完成，占總的動態(tài)需求的28.83%。導致這些請求沒有完成的原因是，收件任務到達時間太晚，或者位置相距太遠，完成時間超出了當批次收派員的時間約束。在完成的任有務里，131個快件未在“收1派2”的建議規(guī)定時間內(nèi)完成，其中大多數(shù)為收件請求，來源于總點數(shù)較多的批次，因為收件請求的時間要求較高，且受靜態(tài)路徑狀況的影響較大，容易造成延遲。滿足時間窗的任務比例占總任務的85.97%，這一比例雖然沒有非常高，但是相對于歷史數(shù)據(jù)里的派送情況，還是有一定的提升效果。

表2 多情境下優(yōu)化方案實施效果

表3 任務完成情況

3.4 優(yōu)化方案實施效果總結

關于程序運行方面，程序采用C++編碼，使用2GB內(nèi)存、2.8GHz英特爾雙核處理器運行。所有的算例運行表明：對于靜態(tài)路徑的計算，最長用時不超過3min；對于實時訂單插入的計算，最長用時不超過2s。故可以滿足實際操作中的時間要求。

優(yōu)化方案的結果表明該方案能夠滿足大部分收派任務，并且保證“收1 派2”的要求，在路徑方面，明顯降低了路徑行走的長度，保證了收派任務進行的效率。

方案的不足之處有以下幾點：(1)沒有考慮人員負載的均衡性，下一步可以將最小化路徑最長的線路作為一個指標，來滿足這一要求；(2)新需求的處理。算法中新需求的處理，是與未完成任務點相聯(lián)系，若新需求到來太晚，或者收派員效率太高導致任務點已處理完，新需求很容易被擱置，等到下一周期處理。

4 結論

本文深入研究了快遞企業(yè) “最后一公里”收派環(huán)節(jié)的實際收派現(xiàn)狀，對其區(qū)域收派路線規(guī)劃問題進行研究，優(yōu)化了收派流程及路徑生成算法，并結合A快遞公司實際操作中具體案例進行分析，給出了適合快遞業(yè)派送中路徑規(guī)劃的熱點劃分法，并綜合考慮裝卸混合、動態(tài)性、時間窗和容量約束這四個最主要的因素，建立數(shù)學模型，通過改進的禁忌搜索算法在短時間內(nèi)得到最優(yōu)路徑結果，設計了一套基于算法的派送流程優(yōu)化方案，并運用到實際情境中，數(shù)據(jù)表明，通過提出的相應流程和算法能比實際操作獲得更好的解，保證收派工作的有效進行。但是也發(fā)現(xiàn)了一些不足之處，人員負載的均衡性和新需求的處理有待提升。

本文研究考慮的四個最基本因素，對動態(tài)性的處理稍顯薄弱，有一定局限性，后期可以進一步研究，提升對動態(tài)請求處理的靈活性。除此之外，在實際中會遇到一系列不確定因素：客戶需求的變化、交通狀況、車輛故障等。所以在未來的研究中，整體的優(yōu)化可以在本文的基礎上建立動態(tài)模型，將不確定因素加入模型以預防突發(fā)情況，使生成的解的適用性及抗干擾性更強。