考慮臨時(shí)配送的動(dòng)態(tài)車(chē)輛路徑規(guī)劃研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

結(jié)

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