李盛威 童澤平

摘 要：文章研究了客戶請(qǐng)求的配送車輛呈動(dòng)態(tài)化的車輛路徑規(guī)劃問(wèn)題，在該問(wèn)題中，客戶請(qǐng)求的動(dòng)態(tài)化可能在配送計(jì)劃制定時(shí)已知，也可能在任一配送時(shí)間節(jié)點(diǎn)更新；配送車輛的動(dòng)態(tài)化體現(xiàn)在管理配送的公司配備固定的車隊(duì)進(jìn)行配送，也有臨時(shí)的司機(jī)通過(guò)接單形式提供服務(wù)，且臨時(shí)配送與對(duì)應(yīng)時(shí)間窗相關(guān)聯(lián)。文章的研究目的是確定分配成本最小化的分配計(jì)劃，分配成本由常規(guī)車輛成本、支付給接單司機(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)車輛路徑規(guī)劃；大鄰域搜索算法；遺傳算法；優(yōu)化算法

中圖分類號(hào)：F252文獻(xiàn)標(biāo)志碼：ADOI：10.13714/j.cnki.1002-3100.2024.08.022

Abstract： The paper studies the dynamic vehicle path planning problem of delivery vehicles requested by customers. In this issue， the dynamism of customer requests may be known during the development of delivery plans， or may be updated at any delivery time node. The dynamism of delivery vehicles is reflected in the management of delivery companies equipped with fixed fleets for delivery， as well as temporary drivers providing services through order taking， and temporary delivery is associated with corresponding time windows. The research objective of this paper is to determine an allocation plan that minimizes allocation costs， which consist of regular vehicle costs， compensation payments to drivers who receive orders， and penalty costs. Based on the design of optimization operators using large neighborhood search algorithms and genetic algorithms， the paper explores the allocation plan for handling dynamic requests and real-time adjustment of path planning. The paper evaluates the performance of algorithms through computational research and sensitivity analysis to determine their feasibility and advantages in solving dynamic problems.

Key words： dynamic vehicle path planning; large neighborhood search algorithm; genetic algorithm; optimization algorithm

電子商務(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)新者之一。它推出的“amazon Flex”，使私人司機(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í)間變化的情況下，使用眾包車輛順路捎帶進(jìn)行城市包裹在線眾包配送的問(wèn)題，側(cè)重于從司機(jī)個(gè)人角度進(jìn)行協(xié)同配送規(guī)劃；趙建有等[6]引入了在線眾包卡車交付（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)車輛調(diào)度問(wèn)題出發(fā)，創(chuàng)新引入了臨時(shí)車輛的規(guī)劃算法。在徐倩等[8]研究的配送車輛路徑規(guī)劃問(wèn)題的基礎(chǔ)上，探究了一項(xiàng)配送服務(wù)方式，即公司需要將包裹送到城市地區(qū)的客戶手中。該公司配備有一支能力較高的“正式司機(jī)”（即由公司雇用并在配送服務(wù)中全職工作的司機(jī)）車隊(duì)，該車隊(duì)在夏小云等[9]研究的帶容量限制的車隊(duì)問(wèn)題的基礎(chǔ)上增加了使用“臨時(shí)車輛”提供服務(wù)，該臨時(shí)車隊(duì)由可在特定時(shí)間窗口內(nèi)進(jìn)行配送服務(wù)的臨時(shí)工作人員構(gòu)成。在臨時(shí)車輛執(zhí)行完一次送貨任務(wù)時(shí)，就會(huì)得到相應(yīng)的報(bào)酬。此外，如果一個(gè)臨時(shí)車輛不得不消耗比其自行規(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í)車輛的補(bǔ)償款項(xiàng)以及對(duì)客戶延遲或推遲交貨的懲罰款項(xiàng)共同構(gòu)成?；诖耍覀儗⒀芯颗R時(shí)配送的動(dòng)態(tài)車輛路徑規(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ī)車輛車隊(duì)，用于向客戶提供配送服務(wù)，同時(shí)，也配備有臨時(shí)車輛可用于靈活執(zhí)行服務(wù)。具體而言，每個(gè)臨時(shí)車輛可自行設(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í)車輛的補(bǔ)償款項(xiàng)、與使用常規(guī)車輛相關(guān)的路線成本和贏得時(shí)間的懲罰成本的總和而得。

每個(gè)客戶i都與一個(gè)需求di和一個(gè)時(shí)間窗[ei，li]相關(guān)聯(lián)，確定了為客戶提供服務(wù)的時(shí)間段。在站點(diǎn)（倉(cāng)庫(kù)）有一個(gè)容量為Q的固定車輛車隊(duì)F，并由企業(yè)司機(jī)駕駛。每條常規(guī)車輛路線都從倉(cāng)庫(kù)s開(kāi)始，最終又回倉(cāng)庫(kù)t。此外，一組臨時(shí)車輛K可用于執(zhí)行該服務(wù)。每個(gè)臨時(shí)車輛K與時(shí)間窗[ek，lk]相關(guān)聯(lián)，用于確定司機(jī)可用時(shí)間并設(shè)置相應(yīng)懲罰，以及可用的最大容量Qk。此外，每個(gè)臨時(shí)車輛均可指定其在整體范圍內(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代表使用普通車輛從i到j(luò)的成本。因此，它包括與車輛使用相關(guān)的所有成本（燃料、通行費(fèi)，以及車輛使用費(fèi)用）和司機(jī)工資；同時(shí)，本研究還假設(shè)成本與穿過(guò)弧線的時(shí)間成正比。這意味著最短路徑對(duì)應(yīng)于最快路徑。每個(gè)臨時(shí)車輛都在與普通車輛相同的原點(diǎn)倉(cāng)庫(kù)s出發(fā)。研究假設(shè)，當(dāng)臨時(shí)車輛在倉(cāng)庫(kù)S中取貨時(shí)，會(huì)被分配一個(gè)“路徑計(jì)劃”，即應(yīng)該執(zhí)行交付的順序。因此，除了常規(guī)司機(jī)的路線之外，公司還定義了臨時(shí)車輛的行程路徑。每個(gè)臨時(shí)車輛根據(jù)可以從站點(diǎn)出發(fā)的最早時(shí)間和想要到達(dá)目的地的最晚時(shí)間來(lái)定義時(shí)間可用性并完成交貨。給予每個(gè)臨時(shí)車輛的補(bǔ)償計(jì)算為遞送分配給的包裹而遍歷的弧的成本cij（從倉(cāng)庫(kù)S到最后一個(gè)訪問(wèn)的客戶遍歷的弧乘以補(bǔ)償參數(shù)q），且對(duì)所有臨時(shí)車輛都是統(tǒng)一的。

懲罰成本與客戶時(shí)間窗口違規(guī)、臨時(shí)車輛時(shí)間窗口違規(guī)和未滿足請(qǐng)求相關(guān)。特別是，懲罰成本Cs與客戶時(shí)間窗口違規(guī)相關(guān)，并且與違規(guī)延長(zhǎng)時(shí)間成正比。因此，把客戶時(shí)間窗違反情況計(jì)算值設(shè)置如下。

類似地，我們將對(duì)臨時(shí)車輛時(shí)間窗口違規(guī)的懲罰定義為Ch。設(shè)置臨時(shí)車輛的時(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í)車輛補(bǔ)償支出、違反客戶和臨時(shí)車輛時(shí)間窗口的懲罰成本以及未滿足請(qǐng)求的懲罰成本的總和得出。目標(biāo)函數(shù)設(shè)置如下。

式中，第一項(xiàng)是與車輛相關(guān)的運(yùn)輸成本；第二項(xiàng)是臨時(shí)車輛的補(bǔ)償成本；后三個(gè)多項(xiàng)式分別是客戶時(shí)間窗口違反成本、臨時(shí)車輛時(shí)間窗口違規(guī)成本和未滿足請(qǐng)求的懲罰成本。

另外，與本文創(chuàng)新設(shè)置的臨時(shí)車輛問(wèn)題的相關(guān)約束條件陳述如表1所示。

約束（1）（2）對(duì)可用的臨時(shí)車輛數(shù)量和離開(kāi)車輛的數(shù)量進(jìn)行限制；（3）為計(jì)算節(jié)點(diǎn)j的到達(dá)時(shí)間；（4）為臨時(shí)車輛在ek之后開(kāi)始行程；（5）為保證每個(gè)在線客戶最多被訪問(wèn)一次，無(wú)論是固定車輛還是臨時(shí)車輛；（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í)，車輛已從倉(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 ? ?車輛問(wèn)題的描述

設(shè)K為臨時(shí)車輛總集。司機(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的停車意愿。在同一地點(diǎn)多次上車或下車算作一次?？?。因此，停車意愿限制了司機(jī)訪問(wèn)不同位置的數(shù)量，反映了臨時(shí)車輛愿意接受的不便程度。一項(xiàng)服務(wù)配送任務(wù)最多與兩個(gè)站點(diǎn)相關(guān)聯(lián)：一個(gè)在上車地點(diǎn)，一個(gè)在下車地點(diǎn)。當(dāng)司機(jī)的出發(fā)地與任務(wù)的取件地點(diǎn)重合時(shí)，便只需多停一站即可完成送貨（見(jiàn)圖2中的a）。這符合沃爾瑪公司配送服務(wù)的想法，即讓實(shí)體店顧客沿著從實(shí)體店到家的路線將包裹遞送給在線買家。圖2中的b顯示了一個(gè)示例，表示其中駕駛員的來(lái)源與任務(wù)的上車位置不同。在這種情況下，司機(jī)需要額外?？?jī)纱?，即一次上車和一次下車。圖2中的c中描繪了另一個(gè)需要兩次額外停靠的示例，表示其中司機(jī)在他的起點(diǎn)處拿起兩個(gè)包裹，然后進(jìn)行兩次下客。

為了簡(jiǎn)化符號(hào)，研究假設(shè)時(shí)間和停止限制比容量限制更嚴(yán)格。理論上，這是一個(gè)合理的假設(shè)，因?yàn)榇蠖鄶?shù)消費(fèi)品都小到可以輕松放入汽車后備箱（亞馬遜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)車輛路徑問(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ǔ)思路，引入多種不同類別的移除與插入算子進(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)題”，該算法是基于上文描述的從客戶以及車輛兩方面的動(dòng)態(tài)車輛路徑規(guī)劃問(wèn)題提出的。本研究提供LNS-VRP的一般方案，并參考徐倩[8]等外賣路徑規(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]解決帶容量約束的車輛路徑問(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ú)上限車輛問(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)求插入整體最佳位置，并被稱為最小成本位置。

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è)普通車輛和三個(gè)臨時(shí)車輛的實(shí)例進(jìn)行深入演算研究。最終得出違反時(shí)間窗口約束如何通過(guò)改變Cs和Ch的值來(lái)影響目標(biāo)函數(shù)。不考慮Cr上限的影響，將其值設(shè)置為1 000，以便為所有客戶提供服務(wù)。對(duì)于q的每個(gè)值，給予相對(duì)應(yīng)的不同Cs和Ch值，最終得出解決方案成本以及常規(guī)車輛和臨時(shí)車輛路線的數(shù)量。研究結(jié)果顯示，時(shí)間窗違規(guī)不會(huì)影響解決方案的配置，因?yàn)閷?duì)于不同的Cs和Ch值，常規(guī)車輛和臨時(shí)車輛的數(shù)量幾乎保持不變。相反，臨時(shí)車輛的補(bǔ)償對(duì)解決方案有更大的影響，臨時(shí)車輛路徑的數(shù)量隨著q的減小而增加。

我們通過(guò)以下統(tǒng)計(jì)數(shù)據(jù)來(lái)評(píng)估各種實(shí)驗(yàn)中的解決方案。

總成本為匹配司機(jī)的補(bǔ)償和后備行程的成本之和。

任務(wù)匹配為由臨時(shí)車輛提供服務(wù)的任務(wù)比例；完成度代表由后備服務(wù)提供的任務(wù)比例。

司機(jī)匹配為分配給任務(wù)的臨時(shí)車輛數(shù)量；一些提供服務(wù)的臨時(shí)車輛將不會(huì)被使用。

后備車輛為所有任務(wù)提供服務(wù)所需的后備車輛的數(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)為是一項(xiàng)有趣且具挑戰(zhàn)性的機(jī)會(huì)。它允許靈活地組織配送服務(wù)，并能顯著降低與車輛和普通司機(jī)投資相關(guān)的固定成本。電子商務(wù)的大型運(yùn)營(yíng)商看到了該系統(tǒng)的潛力，正在積極推動(dòng)該系統(tǒng)的開(kāi)發(fā)。同時(shí)，眾包與當(dāng)日送達(dá)服務(wù)的結(jié)合，再一次增加了問(wèn)題的復(fù)雜性，也帶來(lái)了更多的研究機(jī)會(huì)。本研究便是基于眾包與在線請(qǐng)求相結(jié)合的理論基礎(chǔ)來(lái)展開(kāi)分析探討的，旨在研究問(wèn)題、提出解決方案并根據(jù)問(wèn)題特征評(píng)估配送服務(wù)行為。研究數(shù)據(jù)表明，設(shè)置的動(dòng)態(tài)性對(duì)求解方法的性能有很大影響。在合理的時(shí)間內(nèi)找到高質(zhì)量的解決方案是在動(dòng)態(tài)競(jìng)爭(zhēng)中的公司必須應(yīng)對(duì)的主要挑戰(zhàn)之一。本研究提出的方法易于實(shí)施、快速且靈活，并且適用于臨時(shí)提出請(qǐng)求且沒(méi)有關(guān)于未來(lái)請(qǐng)求信息的系統(tǒng)。在實(shí)際研究中，需關(guān)注動(dòng)態(tài)客戶請(qǐng)求和動(dòng)態(tài)司機(jī)問(wèn)題，獲得臨時(shí)車輛的可用時(shí)間和起止位置等信息。研究客戶請(qǐng)求到達(dá)和臨時(shí)司機(jī)的可用性都是動(dòng)態(tài)配置研究中一個(gè)有趣的擴(kuò)展與研究。

5 ? ?展 ? ?望

未來(lái)的研究還可以側(cè)重于為提出的問(wèn)題及其擴(kuò)展設(shè)計(jì)更智能的解決方案和更切合生活實(shí)際的可行路徑，考慮更多種類的現(xiàn)實(shí)因素。然而，需要注意的是，在沒(méi)有任何關(guān)于未來(lái)請(qǐng)求隨機(jī)信息的情況下，很難在完全動(dòng)態(tài)的環(huán)境中設(shè)計(jì)出有效的解決方案。而且，現(xiàn)有相關(guān)文獻(xiàn)仍然很少，需要對(duì)問(wèn)題的性質(zhì)和有效的求解算法進(jìn)行更多的實(shí)踐研究。特別是針對(duì)現(xiàn)有算法在該方向上的性能評(píng)估等仍有很大的發(fā)展空間，其理論框架及評(píng)價(jià)因素仍有待挖掘。

在未來(lái)，我們還可以將該問(wèn)題擴(kuò)展到更大范圍，考慮該種方法是否在唐堅(jiān)強(qiáng)等[13]的多倉(cāng)庫(kù)問(wèn)題中依舊最優(yōu)；可以將已知需求與隨機(jī)需求結(jié)合探討后續(xù)的動(dòng)態(tài)系統(tǒng)問(wèn)題，將本文方法向隨機(jī)需求擴(kuò)展，與石建力等[14]考慮隨機(jī)需求的近似動(dòng)態(tài)問(wèn)題相結(jié)合；還可以深入研究動(dòng)態(tài)訂單釋放情況，深入分析動(dòng)態(tài)問(wèn)題與時(shí)間、空間或是如石海洋等[15]研究波次訂單動(dòng)態(tài)釋放的相關(guān)問(wèn)題作為切入點(diǎn)，再與整體任務(wù)與路徑規(guī)劃乃至整體系統(tǒng)規(guī)劃相結(jié)合進(jìn)行深入研究。

參考文獻(xiàn)：

[1] 華迎，梁致浩．城市電商化建設(shè)能否促進(jìn)企業(yè)數(shù)字化轉(zhuǎn)型？——基于國(guó)家電子商務(wù)示范城市的準(zhǔn)自然實(shí)驗(yàn)[J]．中國(guó)流通經(jīng)

濟(jì)，2024，38（1）：68-79.

[2] 程兆兆．城市軌道交通開(kāi)展物流配送的可行性及運(yùn)行模式探析[J]．城市軌道交通研究，2023，26（10）：211-212.

[3] 王緝憲．城市物流設(shè)施的規(guī)劃與政策轉(zhuǎn)型[J]．國(guó)際城市規(guī)劃，2022，37（4）：1-3.

[4] 韓慧瑜，張志清．競(jìng)合視閾下眾包物流定價(jià)決策研究[J]．物流科技，2023，46（19）：14-17，35.

[5] 周林，陳燕萍，李海燕，等．基于眾包捎帶協(xié)作的協(xié)同配送優(yōu)化研究[J]．運(yùn)籌與管理，2023，32（7）：78-84.

[6] 趙建有，李玥，田浩，等．眾包配送研究現(xiàn)狀和發(fā)展趨勢(shì)[J/OL]．交通運(yùn)輸工程學(xué)報(bào)：1-32. [2024-01-27].http：//kns.cnki.net/

kcms/detail/61.1369.U.20230710.1949.002.html.

[7] 薛桂琴，葛顯龍．考慮品類前置的兩階段動(dòng)態(tài)車輛調(diào)度優(yōu)化研究[J/OL]．中國(guó)管理科學(xué)：1-10. [2024-01-27].https：//doi.org/

10.16381/j.cnki.issn1003-207x.2021.2037.

[8] 徐倩，熊俊，楊珍花，等．基于自適應(yīng)大鄰域搜索算法的外賣配送車輛路徑優(yōu)化[J]．工業(yè)工程與管理，2021，26（3）：115-122.

[9] 夏小云，莊鶴林，楊火根，等．自適應(yīng)大鄰域搜索的人工蜂群算法求解帶容量約束車輛路徑問(wèn)題[J]．計(jì)算機(jī)集成制造系統(tǒng)，

2022，28（11）：3545-3557.

[10] ?李珍萍，趙雨薇，張煜煒，等．共同配送選址-路徑問(wèn)題及大鄰域搜索算法[J]．系統(tǒng)仿真學(xué)報(bào)，2021，33（10）：2518-2531.

[11] ?黃新林，張隆飛，唐小偉．基于改進(jìn)遺傳算法的家電回收車輛路徑規(guī)劃方法[J]．同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版），2024，52（1）：27-34.

[12] ?呂東許，李少梅，周炤，等．基于改進(jìn)變鄰域搜索算法的多批次協(xié)同任務(wù)規(guī)劃[J]．包裝工程，2023，44（5）：222-229.

[13] ?唐堅(jiān)強(qiáng)，祁超，王紅衛(wèi)．帶時(shí)間窗的多倉(cāng)庫(kù)訂單拆分與異構(gòu)車輛路徑聯(lián)合優(yōu)化方法[J]．系統(tǒng)工程理論與實(shí)踐，2023，43（5）：1446-1464.

[14] ?石建力，謝麗蓉．近似動(dòng)態(tài)規(guī)劃求解隨機(jī)需求分批配送車輛路徑問(wèn)題[J]．運(yùn)籌與管理，2023，32（5）：16-22.

[15] ?石海洋，孫麗君，胡祥培．考慮波次訂單動(dòng)態(tài)釋放的B2C電商訂單合并配送決策方法[J/OL]．管理工程學(xué)報(bào)，2024（2）：1-14. [2024-01-

27].https：//doi.org/10.13587/j.cnki.jieem.2024.02.011.