考慮臨時配送的動態(tài)車輛路徑規(guī)劃研究

摘要：文章研究了客戶請求的配送車輛呈動態(tài)化的車輛路徑規(guī)劃問題，在該問題中，客戶請求的動態(tài)化可能在配送計劃制定時已知，也可能在任一配送時間節(jié)點更新；配送車輛的動態(tài)化體現(xiàn)在管理配送的公司配備固定的車隊進行配送，也有臨時的司機通過接單形式提供服務(wù)，且臨時配送與對應(yīng)時間窗相關(guān)聯(lián)。文章的研究目的是確定分配成本最小化的分配計劃，分配成本由常規(guī)車輛成本、支付給接單司機補償款項和罰款成本共同構(gòu)成。該問題研究基于大鄰域搜索算法和遺傳算法設(shè)計優(yōu)化算子，探索處理動態(tài)請求并實時調(diào)整路徑規(guī)劃的分配計劃。通過計算研究與靈敏度分析評估算法性能，確定其解決動態(tài)問題的可行性與優(yōu)勢。關(guān)鍵詞：動態(tài)車輛路徑規(guī)劃；大鄰域搜索算法；遺傳算法；優(yōu)化算法電子商務(wù)在過去幾年經(jīng)歷了指數(shù)級增長，對多個行業(yè)而言，無疑是一個巨大的商機，但其對管理與滿足客戶訂單相關(guān)的運營方面也提出了巨大挑戰(zhàn)[1]，尤其聚焦供應(yīng)鏈的最后一站。電商的爆發(fā)式增長讓“最后一公里”交付成為焦點。事實上，客戶對送貨速度的要求越來越高。一方面，提供“當天送達”或“次日送達”等的服務(wù)是增加收入和獲取客戶忠誠度的絕佳機會[2]。另一方面，送貨速度加快意味著減少合并機會和縮短交付計劃時間。而在這一過程中，主要風險表現(xiàn)在提供質(zhì)量差的服務(wù)或產(chǎn)生高昂的交付成本?；诖?，為“最后一公里”交付尋找創(chuàng)新和高效的解決方案成為了所有電子市場參與者成功的關(guān)鍵手段。亞馬遜公司便是該領(lǐng)域的領(lǐng)先創(chuàng)新者之一。它推出的“amazonFlex”，使私人司機可以為亞馬遜運送包裹并獲得服務(wù)補償。司機提交可用時間和實時位置，亞馬遜要求他們必須從亞馬遜配送中心取貨并交付給最終客戶。該服務(wù)于2015年在美國開始運營，目前已覆蓋100多個城市。針對物流行業(yè)存在的相關(guān)問題，王緝憲[3]的研究以多層次的社會技術(shù)轉(zhuǎn)型理論為基礎(chǔ)，建立了促進“最后一公里”城市物流轉(zhuǎn)型的概念框架，確定了該配送形式在改善電子商務(wù)時代“最后一公里”配送方面的巨大潛力；韓慧瑜等[4]提出了使用眾包工人的“最后一公里”交付選擇模型，用于優(yōu)化成本、時間和工人表現(xiàn)間的權(quán)衡。但其更多側(cè)重于從定價策略上進行規(guī)劃，而沒有將其與司機路線聯(lián)系起來；周林等[5]研究了在旅行時間隨時間變化的情況下，使用眾包車輛順路捎帶進行城市包裹在線眾包配送的問題，側(cè)重于從司機個人角度進行協(xié)同配送規(guī)劃；趙建有等[6]引入了在線眾包卡車交付（OCTD）問題，并將其重新表述為“在線雙點超匹配”的問題。雖然其從企業(yè)的角度進行了算法模擬，但缺少容量、時間窗及解決相關(guān)問題路徑的研究?？梢?，現(xiàn)有研究對于眾包與傳統(tǒng)配送相結(jié)合的物流系統(tǒng)的相關(guān)研究較少，尤其在涵蓋多種現(xiàn)實因素的算法研究較為空缺。因此，本文以此為研究切入點展開了研究探討。本文從薛桂琴等[7]的兩階段動態(tài)車輛調(diào)度問題出發(fā)，創(chuàng)新引入了臨時車輛的規(guī)劃算法。在徐倩等[8]研究的配送車輛路徑規(guī)劃問題的基礎(chǔ)上，探究了一項配送服務(wù)方式，即公司需要將包裹送到城市地區(qū)的客戶手中。該公司配備有一支能力較高的“正式司機”（即由公司雇用并在配送服務(wù)中全職工作的司機）車隊，該車隊在夏小云等[9]研究的帶容量限制的車隊問題的基礎(chǔ)上增加了使用“臨時車輛”提供服務(wù)，該臨時車隊由可在特定時間窗口內(nèi)進行配送服務(wù)的臨時工作人員構(gòu)成。在臨時車輛執(zhí)行完一次送貨任務(wù)時，就會得到相應(yīng)的報酬。此外，如果一個臨時車輛不得不消耗比其自行規(guī)定時間更長的時間來交付指定的包裹，則會收到額外的補償。當開始配送包裹后，出現(xiàn)的新請求將會被作為臨時的顧客需求點。因此，公司需要不斷調(diào)整配送計劃以處理新的訂單?？蛻粲唵闻c特定時間窗口相關(guān)聯(lián)，便成為該客戶選擇接收包裹的首選時間。任何違反這個時間窗口的行為都會產(chǎn)生懲罰性費用。如果公司不能為在線客戶訂單提供服務(wù)，且不安排交貨，則會被認為訂單配送可能會被推遲到后一天。這便會產(chǎn)生罰款成本。而公司的目標是實現(xiàn)總配送成本的最小化。該成本由常規(guī)的司機成本、對臨時車輛的補償款項以及對客戶延遲或推遲交貨的懲罰款項共同構(gòu)成?；诖?，我們將研究臨時配送的動態(tài)車輛路徑規(guī)劃問題。本研究假設(shè)沒有關(guān)于臨時客戶的信息，且這種設(shè)定與最近在某一地區(qū)開始的相關(guān)服務(wù)情況是一致的。因此，本文不存在關(guān)于請求出現(xiàn)的可靠信息。1

動態(tài)VRP模型動態(tài)VRP作為一種企業(yè)實際問題，從公司設(shè)計的角度來看，公司必須將貨物交付給一組地理上分散的客戶?？蛻舻男枨罂赡茉谂渌陀媱潓嵤┣疤崆矮@知，也可能在配送過程中在線獲得。公司擁有一支固定的常規(guī)車輛車隊，用于向客戶提供配送服務(wù)，同時，也配備有臨時車輛可用于靈活執(zhí)行服務(wù)。具體而言，每個臨時車輛可自行設(shè)計服務(wù)的時間窗口，且其獲得的收益與行進距離成正比。此外，如果未滿足客戶時間窗口或服務(wù)時間超過預(yù)先設(shè)計的時間窗口，系統(tǒng)將自動生成相應(yīng)的懲罰。此外，如果因司機原因未能滿足客戶要求，公司將需要支付未滿足需求的成本費用。公司的目標是實現(xiàn)分配成本最小化，而分配成本由支付給臨時車輛的補償款項、與使用常規(guī)車輛相關(guān)的路線成本和贏得時間的懲罰成本的總和而得。每個客戶i都與一個需求di和一個時間窗[ei，li]相關(guān)聯(lián)，確定了為客戶提供服務(wù)的時間段。在站點（倉庫）有一個容量為Q的固定車輛車隊F，并由企業(yè)司機駕駛。每條常規(guī)車輛路線都從倉庫s開始，最終又回倉庫t。此外，一組臨時車輛K可用于執(zhí)行該服務(wù)。每個臨時車輛K與時間窗[ek，lk]相關(guān)聯(lián)，用于確定司機可用時間并設(shè)置相應(yīng)懲罰，以及可用的最大容量Qk。此外，每個臨時車輛均可指定其在整體范圍內(nèi)的終止節(jié)點Vk。A是弧的集合。每個圓?。╥，j）∈A表示從i到j(luò)的最短路徑。還有兩個相關(guān)參數(shù)與?。╥，j）相關(guān)聯(lián)，分別為成本cij和時間tij。它們都滿足三角不等式。本研究假設(shè)成本cij代表使用普通車輛從i到j(luò)的成本。因此，它包括與車輛使用相關(guān)的所有成本（燃料、通行費，以及車輛使用費用）和司機工資；同時，本研究還假設(shè)成本與穿過弧線的時間成正比。這意味著最短路徑對應(yīng)于最快路徑。每個臨時車輛都在與普通車輛相同的原點倉庫s出發(fā)。研究假設(shè)，當臨時車輛在倉庫S中取貨時，會被分配一個“路徑計劃”，即應(yīng)該執(zhí)行交付的順序。因此，除了常規(guī)司機的路線之外，公司還定義了臨時車輛的行程路徑。每個臨時車輛根據(jù)可以從站點出發(fā)的最早時間和想要到達目的地的最晚時間來定義時間可用性并完成交貨。給予每個臨時車輛的補償計算為遞送分配給的包裹而遍歷的弧的成本cij（從倉庫S到最后一個訪問的客戶遍歷的弧乘以補償參數(shù)q），且對所有臨時車輛都是統(tǒng)一的。懲罰成本與客戶時間窗口違規(guī)、臨時車輛時間窗口違規(guī)和未滿足請求相關(guān)。特別是，懲罰成本Cs與客戶時間窗口違規(guī)相關(guān)，并且與違規(guī)延長時間成正比。因此，把客戶時間窗違反情況計算值設(shè)置如下。類似地，我們將對臨時車輛時間窗口違規(guī)的懲罰定義為Ch。設(shè)置臨時車輛的時間窗口違反情況的計算值如下。最后，Cr是為每個未滿足請求支付的罰款。我們假設(shè)必須為Cs中的客戶提供服務(wù)，而原始路徑中客戶的請求可能會被推遲。這反映了客戶在Cs中提前下訂單并保證在給定期限內(nèi)得到服務(wù)的情況。此外，我們假設(shè)未滿足請求支付的罰款與未滿足的客戶需求成正比。在這種情況下，每個未滿足的請求都會支付罰款。設(shè)置ri為二進制變量，在客戶i的請求未得到滿足的情況下，相應(yīng)值的計算如下。通過這種方式，我們近似于請求根據(jù)其“重要性”具有不同優(yōu)先級的情況。這可能與請求的價值或承運人與客戶簽訂的合同有關(guān)。需要注意的是，該模型和解決方法很容易被修改，以考慮不同的懲罰成本設(shè)置。研究設(shè)置目標為定義總成本最小化的分配計劃?？偝杀居沙Ｒ?guī)司機的路由成本、臨時車輛補償支出、違反客戶和臨時車輛時間窗口的懲罰成本以及未滿足請求的懲罰成本的總和得出。目標函數(shù)設(shè)置如下。式中，第一項是與車輛相關(guān)的運輸成本；第二項是臨時車輛的補償成本；后三個多項式分別是客戶時間窗口違反成本、臨時車輛時間窗口違規(guī)成本和未滿足請求的懲罰成本。另外，與本文創(chuàng)新設(shè)置的臨時車輛問題的相關(guān)約束條件陳述如表1所示。約束（1）（2）對可用的臨時車輛數(shù)量和離開車輛的數(shù)量進行限制；（3）為計算節(jié)點j的到達時間；（4）為臨時車輛在ek之后開始行程；（5）為保證每個在線客戶最多被訪問一次，無論是固定車輛還是臨時車輛；（6）為強制要求訪問所有靜態(tài)客戶節(jié)點。1.1

客戶問題的描述靜態(tài)顧客需求點是指在進行路徑規(guī)劃時已知時間配送距離的點；而臨時顧客需求點則是在配送過程中提出的。這種情況在原始路徑規(guī)劃中無法得知足夠信息，進而無法進行規(guī)劃安排，只能由本文研究的動態(tài)優(yōu)化算法實現(xiàn)。針對本文提出的動態(tài)客戶問題，創(chuàng)建模型。具體模型如圖1所示。本文以確定倉庫為基礎(chǔ)，對圖1中時間t為9時出現(xiàn)的臨時顧客需求點的相關(guān)路線進行了詳細探討。臨時顧客需求點4出現(xiàn)時，車輛已從倉庫出發(fā)向顧客點1行進，且直接執(zhí)行插入算子形成的路徑規(guī)劃（2）顯然不滿足成本最小化原則，故需要對此路徑進行進一步優(yōu)化，得到最終可滿足目標函數(shù)路徑（3）。1.2

車輛問題的描述設(shè)K為臨時車輛總集。司機的行程公告k∈K，指定其目的地。司機k∈K有最早出發(fā)時間ek和最晚到達時間lk。駕駛員還指定了最大行程時間Tk，其中tok，dk≤Tk≤lk-ek，出發(fā)時間靈活性表示為Fk=lk-ek-tok，dk。除了繞行和出發(fā)時間的靈活性，還要考慮到司機可能愿意額外停靠的最大次數(shù)。令Qk∈Z+表示駕駛員k的停車意愿。在同一地點多次上車或下車算作一次?？俊Ｒ虼?，停車意愿限制了司機訪問不同位置的數(shù)量，反映了臨時車輛愿意接受的不便程度。一項服務(wù)配送任務(wù)最多與兩個站點相關(guān)聯(lián)：一個在上車地點，一個在下車地點。當司機的出發(fā)地與任務(wù)的取件地點重合時，便只需多停一站即可完成送貨（見圖2中的a）。這符合沃爾瑪公司配送服務(wù)的想法，即讓實體店顧客沿著從實體店到家的路線將包裹遞送給在線買家。圖2中的b顯示了一個示例，表示其中駕駛員的來源與任務(wù)的上車位置不同。在這種情況下，司機需要額外?？績纱?，即一次上車和一次下車。圖2中的c中描繪了另一個需要兩次額外?？康氖纠硎酒渲兴緳C在他的起點處拿起兩個包裹，然后進行兩次下客。為了簡化符號，研究假設(shè)時間和停止限制比容量限制更嚴格。理論上，這是一個合理的假設(shè)，因為大多數(shù)消費品都小到可以輕松放入汽車后備箱（亞馬遜86%的包裹重量不到5磅，小到甚至可以用無人機運送）。為了適應(yīng)運輸較大物體（例如家具或白色家電）的環(huán)境，我們針對貨物體積引入額外的限制。研究將作業(yè)p定義為一組任務(wù)，且作業(yè)可以由單個任務(wù)或多個任務(wù)組成。集合P為至少在一個可行匹配中的所有作業(yè)的集合。假設(shè)存在一條可行路線r，使得司機k和工作p之間的匹配（k，p）是可行的。其中，司機從他的起點ok開始，涵蓋p中的所有任務(wù)，并在他的目的地dk結(jié)束。如果滿足以上約束條件，則表示路徑r是可行的。2

動態(tài)優(yōu)化算法在本節(jié)中，研究首先介紹了一種基于簡單插入方案的動態(tài)車輛路徑問題的解決算法。該算法允許處理在線決策和實時調(diào)整分配計劃。在傳統(tǒng)解法（即對計劃進行局部調(diào)整以適應(yīng)新的請求）的基礎(chǔ)上，提出重新優(yōu)化策略。其出發(fā)點是在給定的連續(xù)時間點上反復(fù)重新優(yōu)化路線，且每次重新優(yōu)化都會重建整個分配計劃。尤其值得注意的是，我們假設(shè)，每次有一定數(shù)量的在線請求被放置，就有一個程序被應(yīng)用，并試圖將擱置請求插入到現(xiàn)有路線的最佳可行位置。然后，我們在每條路線上應(yīng)用一個重新優(yōu)化的程序，只考慮仍需執(zhí)行的那部分路線，即在最后一個請求時段內(nèi)到達后并執(zhí)行的那部分。我們之所以提出這個策略，是為了顯示重新優(yōu)化比簡單插入算法更占優(yōu)勢，即強調(diào)了LNS算法的優(yōu)勢。同時，基于此研究，評估了遺傳算法對插入帶來的效益，以實現(xiàn)再插入。針對以上兩種算法的基礎(chǔ)思路，引入多種不同類別的移除與插入算子進行權(quán)重改變的重優(yōu)化，增加系統(tǒng)的動態(tài)性與復(fù)雜性，使整體程序?qū)崿F(xiàn)局部最優(yōu)。2.1

大鄰域搜索算法在下文中，基于李珍萍等[10]（2021）提出的改進LNS算法，作進一步優(yōu)化改進記作DynamicVRP問題。Dynamic代表“動態(tài)問題”，該算法是基于上文描述的從客戶以及車輛兩方面的動態(tài)車輛路徑規(guī)劃問題提出的。本研究提供LNS-VRP的一般方案，并參考徐倩[8]等外賣路徑規(guī)劃研究中考慮時間窗及懲罰情況的更多細節(jié)，重點討論DynamicVRP問題，以建立一個可行的解決方案，在不違反時間窗口的情況下訪問CS中的所有客戶。具體來說，該算法由三個主要階段組成，分別為初始化、移除和再插入。初始化階段是通過一個貪婪的插入啟發(fā)式建立一個初始可行的解決方案（不考慮任何成本及距離問題）；然后在解決方案初步可行的情況下，重新優(yōu)化并更新融合程序。解決方案被傳遞到第2和第3階段進行迭代，直到達到最大迭代次數(shù)。特別需要提及的是，要先找出滿足時間窗約束和容量約束的所有插入點，再計算上述插入點的距離增量；接著找出上述插入點距離增量最小的那個插入點，并記錄其距離增量。通過重新優(yōu)化階段得到的解決方案將被傳遞給LNS。不同的鄰域已被明確定義，再由LNS按順序逐一探索。一個鄰域的解決方案只有在改善當前解決方案的情況下才會被接受。當所有鄰域都被探索后，LNS就會停止執(zhí)行。然后，除非達到最大的迭代次數(shù)，否則便會對當前的解決方案進行持續(xù)更新。具體如表2所示。2.2

優(yōu)化移除算子本研究從夏小云等[9]解決帶容量約束的車輛路徑問題（CVRP）時設(shè)計的５個移除算子和２個插入算子出發(fā)，用相同的思路深入挖掘更符合本研究問題的算子。移除算子設(shè)置如下。2.2.1

隨機移除算子不考慮任意約束直接進行移除，雖然會給系統(tǒng)迭代次數(shù)帶來壓力，但其跳出局部最優(yōu)能力較強。2.2.2

節(jié)約值最大移除算子僅考慮個體節(jié)約值進行移除，較易陷入局部最優(yōu)，且其僅考慮線路中單一節(jié)點數(shù)值問題，可將節(jié)約值作為移除因子納入算式進行整體計算移除。2.2.3

獨立個體移除算子考慮到無上限車輛問題中，較容易出現(xiàn)一條路線上涉及節(jié)點較少的問題，將獨立個體納入移除，可以設(shè)計節(jié)點節(jié)約值與路線總節(jié)約值在某程度上相近則移除。2.2.4

鄰域問題移除算子針對每個節(jié)點進行鄰域搜索，鄰域內(nèi)出現(xiàn)節(jié)點個數(shù)超過設(shè)置值則觸發(fā)移除算子。2.2.5

需求值過大移除算子將任一路線中節(jié)點的需求量與總路線需求量進行比較，當設(shè)置范圍相近時，則考慮該節(jié)點是需求過大節(jié)點，將其執(zhí)行移除。2.3

優(yōu)化插入算子插入算子除了涉及遺傳算法的相關(guān)求解問題，還關(guān)系到多種本研究中單獨引入的插入算子因素，具體如下。2.3.1

貪婪法插入算子使用貪婪法得到節(jié)點的最優(yōu)插入位置，其對應(yīng)插入后增加路程最小的插入點，即將對應(yīng)的待插入節(jié)點亂序排列后使用貪婪法依次插入。該運算符重復(fù)地將請求插入整體最佳位置，并被稱為最小成本位置。2.3.2

二分法插入算子對于所有的插入節(jié)點進行隨機排序獲得數(shù)組，利用二分查找法查找出插入位置，并將有序數(shù)組中插入位置后的數(shù)據(jù)后移一位，空出插入位置依次插入數(shù)組中的數(shù)據(jù)。2.4

基于LNS的GA優(yōu)化（GA-LNS）求解動態(tài)VRP考慮到遺傳算法對該問題解決效率的正向影響，以黃新林等[11]相關(guān)改進遺傳算法研究的理解以及呂東許等[12]相關(guān)大領(lǐng)域搜索算法在任務(wù)規(guī)劃方面的研究作為基礎(chǔ)，將遺傳算法納入到研究中進行詳細討論?；谝陨蟽煞N優(yōu)化方向的研究思路，從最后一個角度，即插入時涉及到的數(shù)學(xué)問題求最優(yōu)解出發(fā)，引入較容易跳出局部最優(yōu)且適合處理大數(shù)據(jù)集問題的遺傳算法。出于本研究的特殊性對其作優(yōu)化改進獲得如圖3所示算法流程圖，依據(jù)該流程運行遺傳算法得出最優(yōu)，將該最優(yōu)值插入上述操作優(yōu)化后的LNS算式中。3

實驗分析為了驗證該算法比現(xiàn)有的傳統(tǒng)算法或優(yōu)化前算法更有效，對其得到的性能數(shù)據(jù)進行比較與分析。從實驗結(jié)果來看，該算法能在在大迭代次數(shù)內(nèi)形成最優(yōu)配送方案，同時滿足已有的時間窗及多種約束。將本算法與已知信息不考慮動態(tài)問題的離線算法作比較，可發(fā)現(xiàn)路徑最優(yōu)性存在波動，但在該水平上近似有效，具體如圖4所示。針對算法的懲罰問題進行初步的計算研究，以評估懲罰成本成分對問題解決方案的影響。特別是對小尺寸實例上的懲罰效果有較好展示。通過測試了Cs不同數(shù)值對結(jié)果的影響，對10個客戶、三個普通車輛和三個臨時車輛的實例進行深入演算研究。最終得出違反時間窗口約束如何通過改變Cs和Ch的值來影響目標函數(shù)。不考慮Cr上限的影響，將其值設(shè)置為1000，以便為所有客戶提供服務(wù)。對于q的每個值，給予相對應(yīng)的不同Cs和Ch值，最終得出解決方案成本以及常規(guī)車輛和臨時車輛路線的數(shù)量。研究結(jié)果顯示，時間窗違規(guī)不會影響解決方案的配置，因為對于不同的Cs和Ch值，常規(guī)車輛和臨時車輛的數(shù)量幾乎保持不變。相反，臨時車輛的補償對解決方案有更大的影響，臨時車輛路徑的數(shù)量隨著q的減小而增加。我們通過以下統(tǒng)計數(shù)據(jù)來評估各種實驗中的解決方案?？偝杀緸槠ヅ渌緳C的補償和后備行程的成本之和。任務(wù)匹配為由臨時車輛提供服務(wù)的任務(wù)比例；完成度代表由后備服務(wù)提供的任務(wù)比例。司機匹配為分配給任務(wù)的臨時車輛數(shù)量；一些提供服務(wù)的臨時車輛將不會被使用。后備車輛為所有任務(wù)提供服務(wù)所需的后備車輛的數(shù)量。4

結(jié)

論本文研究了臨時配送的動態(tài)路徑優(yōu)化問題，在該問題中，一家公司利用眾包運輸來分發(fā)其部分客戶訂單。對于面臨“最后一公里”交付帶來的復(fù)雜問題而言，眾包運輸被認為是一