快遞企業(yè)“最后一公里”快件收派優(yōu)化方案研究

賀冰倩, 李昆鵬, 成幸幸

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

0 引言

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

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

圖1 快遞公司快件實(shí)際收派流程

圖2 靈活處理收件請(qǐng)求

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

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

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

1 問(wèn)題模型構(gòu)建與分析

1.1 數(shù)學(xué)模型

模型目標(biāo)函數(shù)：

(1)

約束條件：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

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

(13)

(14)

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

1.2 區(qū)域熱點(diǎn)劃分

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

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

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

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

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

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

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

2.1 收派路徑問(wèn)題求解基本框架

本算法主要通過(guò)時(shí)間片的分割，轉(zhuǎn)動(dòng)態(tài)需求為靜態(tài)需求，實(shí)時(shí)計(jì)算收派員當(dāng)前點(diǎn)及以后的可行路徑，最小化時(shí)間消耗，并將生成的行走路線(xiàn)結(jié)果實(shí)時(shí)反饋到收派員，將快件到達(dá)時(shí)間實(shí)時(shí)反饋給客戶(hù)，保證收派工作順利展開(kāi)。

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

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

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

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

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

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

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

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

2.3 改進(jìn)的禁忌搜索算法

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

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

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

圖6 改進(jìn)的禁忌搜索算法

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

當(dāng)收派員在派件途中，會(huì)隨機(jī)到達(dá)若干收貨請(qǐng)求。請(qǐng)求反饋到系統(tǒng)，系統(tǒng)中有各個(gè)收派員的實(shí)時(shí)位置和容量信息，管理人員需要讓收派員在完成原來(lái)任務(wù)的基礎(chǔ)上，靈活加入新收件任務(wù)， 具體的安排方式如下：

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

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

3.1 案例背景

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

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

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

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

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

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

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

表1 CPLEX與改進(jìn)禁忌搜索對(duì)小規(guī)模算例測(cè)試結(jié)果

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

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

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

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

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

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

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

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

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

表3 任務(wù)完成情況

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

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

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

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

4 結(jié)論

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

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