考慮具有不同交付選擇的物流配送路徑問題研究

摘 要：為了滿足城市配送中顧客對交付方式及特定時間的個性化需求，引入顧客偏好概念刻畫送貨上門與自提服務的交付需求，以總運營成本最小化為優化目標建立了具有不同交付選擇的車輛路徑優化模型。考慮到模型的復雜性引入多種算子，設計并改進自適應大鄰域搜索算法對模型進行求解。最后結合重慶市南岸區某配送案例進行實例分析，驗證了該模型與算法的有效性。

關鍵詞：城市配送； 末端交付選擇； 車輛路徑問題； 自適應大鄰域搜索算法

中圖分類號：TP399

文獻標志碼：A

文章編號：1001-3695（2023）07-007-1964-06

doi：10.19734/j.issn.1001-3695.2022.11.0771

Research on problem of logistics distribution routes with different delivery options

Ge Xianlong^?， Liu Xiaoning， Liang Yonghong

（School of Economics amp; Management， Chongqing Jiaotong University， Chongqing 400074， China）

Abstract：In order to meet customers’ individual needs for delivery methods and specific time in urban distribution，this paper introduced the concept of customer preference to describe the delivery needs of home delivery and self-pickup services， and established vehicles path optimization model with different delivery options with the optimization goal of minimizing the total ope-rating cost." Considering the complexity of the model， it introduced a variety of operators， and designed an adaptive large neighborhood search algorithm and improved to solve the problem. Finally， combined with a case analysis of a distribution case in Nan’an district of Chongqing city， the validity of the model and algorithm is verified.

Key words：urban distribution; delivery option; vehicle routing problem; adaptive large neighborhood search

0 引言

經濟的增長促使消費者的消費觀念發生轉變，個性化的需求對物流配送提出了更高的要求，快遞行業從追求高速發展階段逐漸轉向高質量競爭。如人們在選擇快遞末端配送服務時，出現了從最初的價格導向到現在更加注重服務質量，定制化配送服務成為末端配送的標配，“準時達”服務^［1］、送貨上門等服務^［2］應運而生。由于年齡結構、職業類型、購物習慣等呈現較大差異，不同顧客對于配送服務時效性及配送方式的選擇有不同的偏好程度。各大物流企業開始聚焦于根據顧客的偏好程度提供個性化的配送服務，從而提升服務質量、增加客戶滿意度、提高顧客粘性以及企業競爭力。然而，基于偏好程度的個性化配送服務不僅會影響顧客的滿意度，也影響著物流企業的配送成本。如何在盡可能滿足顧客偏好程度時降低配送成本，是當前智慧物流大背景下物流服務商亟需解決的問題。

目前常見的末端交付方式包括送貨上門和顧客自提兩種，針對末端交付問題已有不少學者進行了研究。陳義友等人^［3］考慮了自提點距離和覆蓋距離對消費者滿意度的影響，建立了基于逐漸覆蓋的自提點選址模型，并進行算法求解。郭放等人^［4］考慮了客戶自取服務和電動汽車送貨上門的多樣化服務策略并建立了整數規劃數學模型并設計啟發式算法進行求解。Enthoven等人^［5］研究了帶交付選擇的兩級車輛路徑問題，通過結合貨運自行車送貨上門和自提點交付，以此來達到減少擁堵和保護環境的目的。Mancini等人^［6］提出了送貨上門和顧客自取相結合的混合交付方法，對使用自提服務的客戶進行了補償。Mommens等人^［7］考慮了根據地區類型使用送貨上門和自提取貨的最后一公里配送問題，使用基于代理的運輸模型模擬解決方案。Carotenuto等人^［8］考慮使用不同車型對送貨上門和自提取貨的客戶進行服務，比較了兩種交付方式對于最后一公里配送的影響。邱晗光等人^［9］在顧客可選末端交付方式和配送時間窗的情境下，基于利潤最大化構建了城市配送動態訂單接受決策框架，以配送成本最小化和期望收益最大化建立了服務選項多目標聯合定價模型，并設計算法求解。Dumez等人^［10］研究了最后一公里具有交付選項的車輛路徑問題，通過大型鄰域搜索對問題進行求解，并提出了新的算子與其他文獻中的眾多算子相結合，并通過實驗證明所提算法優于現有算法。以上文獻分析了城市末端交付的研究情況，且大多數傾向于研究末端交付方式對于配送成本的影響，鮮有學者將顧客對末端交付方式的偏好作為影響因素研究城市物流配送問題。為此在分析現有多種配送模式的研究基礎上，通過引入客戶可選擇的末端交付方式研究城市物流配送問題。

隨著顧客的需求趨向多樣化、個性化，物流企業需要根據客戶需求提高配送服務質量。已有不少學者對考慮顧客需求的車輛路徑問題進行了研究。葛顯龍等人^［11］針對客戶動態配送需求，建立了基于需求預測的兩級動態車輛路徑問題模型并設計算法求解。Arslan等人^［12］考慮了一種按需服務平臺，該平臺可在每次信息更新時自動在包裹遞送任務和臨時司機之間進行匹配。李珍萍等人^［13］針對客戶具有多種服務需求，建立了多需求車輛路徑問題聯合優化模型并設計聯合優化遺傳算法進行求解。Tao等人^［14］對O2O按需送貨服務進行了研究，建立了訂單分配和路徑模型并采用禁忌搜索的方法進行求解。還有不少學者通過將顧客劃分成不同的群體進行配送服務，以滿足不同類型客戶的需求提高整體滿意度。馬俊等人^［15］研究了客戶分類的隨機時間車輛路徑問題，建立了機會約束規模模型并設計變鄰域迭代局部搜索算法求解。Binart等人^［16］將客戶分為必須在給的時間窗口內進行服務的強制客戶和服務時間沒有硬性規定的可選客戶，并設計了一種兩階段方法求解。于江霞等人^［17］根據客戶的消費行為將客戶分為多個層級并分別設置超時懲罰成本，構建了基于客戶分類的即時配送路徑優化模型，設計遺傳算法進行求解。Calvet等人^［18］針對客戶進行分類并根據客戶之間關聯設計配送服務，使用迭代局部搜索和混合遺傳算法對問題進行求解。夏揚坤等人^［19］考慮客戶分類，以總配送成本最小為目標建立了優化模型，并設計兩階段啟發式算法求解。以上文獻根據客戶優先級等因素對客戶進行區分，研究考慮不同客戶群體的物流配送問題，但沒有考慮通過對客戶提供不同末端交付方式進行個性化配送服務。為此，考慮顧客偏好程度并結合不同交付方式的優勢研究城市末端配送問題，進一步提高顧客滿意度及企業競爭力。

因此，針對客戶送貨上門及自提取貨等不同個性化偏好需求，研究具有不同交付選擇的車輛路徑問題（vehicle routing problems with delivery options，VRPDO）。結合送貨上門客戶滿意度以及自提點取貨配送企業成本建立考慮不同交付選擇的車輛路徑優化模型，分析顧客配送任務信息，設計送貨上門、自提取貨和混合交付三種模式，平衡顧客的感知服務質量和企業的總配送成本。設計并改進自適應大鄰域搜索算法（adaptive large neighborhood search，ALNS）對模型進行求解。

1 問題描述

城市物流配送企業在指定范圍內為顧客提供配送服務，并為顧客提供送貨上門（home delivery，HD）及自提服務（custo-mer’s pickup，CP）兩種末端交付方式。顧客在下單時可以對交付方式作出選擇，并對所選交付方式作出評分（即對所選交付方式的偏好程度），預先提供兩類交付地址：第一類是客戶自選的私人交付位置，配送車輛需要在客戶給定的時間窗內送達，配送方式為HD；第二類是無交付時間要求的配送方式，即CP交付，配送車輛可以在任何時間內將包裹送往客戶所提供的共享交付位置，配送人員無須與顧客面對面進行商品交接，如快遞柜、菜鳥驛站等非接觸交付方式等。物流企業以最小化運營總成本為目標，考慮客戶所選交付方式的偏好需求及客戶位置信息進行配送服務。當客戶選擇HD交付方式的偏好需求較低或配送時間窗與配送車輛行程不相符時，考慮使用CP交付方式服務HD客戶，提高客戶整體滿意度和配送成本最小化是研究的重點。具體如圖1所示。

在圖（a）中滿足所有顧客送貨上門要求時，由于時間窗的沖突，配送企業需要派送兩輛車完成對所有客戶送貨上門的要求，這種交付方式可以有效提高客戶滿意度，但增加了企業的配送成本；在圖（b）中為所有顧客提供僅自提點交付方式，對于配送企業來說，這種交付方式可以降低配送成本，但需要面臨客戶滿意度降低的風險；在圖（c）中，配送企業采用混合交付方式，通過滿足部分顧客送貨上門的需求達到客戶滿意度與配送總成本的平衡。

2 模型建立

2.1 問題假設

為了便于研究與模型建立，作出如下假設：a）客戶所提供的交付地址及其對應的時間窗已知的；b）配送車輛送貨上門時服務時間固定；c）自提點的容量已知，且配送人員在自提點服務時間固定；d）客戶可在CP交付及HD交付中任選一種配送方式服務；e）在配送過程中，企業無法滿足客戶送貨上門需求時采用CP交付方式，所產生的影響體現為增加配送成本。其中：假設a）表明企業配送前對客戶的信息是已知的；假設b）簡化配送流程；假設c）表明自提點的屬性；假設d）e）表明客戶的需求必須由HD交付或者CP交付方式滿足。

2.2 數學模型

帶有交付選擇的車輛路徑問題（VRPDO）是經典車輛路徑問題（VRP）的拓展，引入了不同的末端交付方式，并考慮客戶對不同交付方式的偏好程度。由于客戶所提供的對交付方式的偏好信息往往是模糊的，考慮使用客戶所選的交付方式、配送時間準確性以及快遞人員服務態度來量化客戶偏好程度。利用BWM方法^［20］確定各評價指標的權重，然后通過顧客對各指標的評價值，計算顧客的偏好程度值。配送企業通過不同交付方式對客戶進行服務，當配送企業決定使用CP交付方式為HD客戶提供服務時，根據客戶前往自提點的距離對客戶作出補償。具體的符號參數說明如表1所示。

根據上述分析，在此建立VRPDO的數學模型。

其中：目標函數式（1）是最小化總成本，其中包括車輛的路徑成本，車輛使用成本，使用CP服務交付HD客戶時產生的懲罰成本以及使用HD交付方式的服務成本；約束式（2）表示客戶只能被一種交付方式服務，且必須被服務；約束式（3）表示路徑網絡的流量平衡；約束式（4）表示車輛載重能力約束；約束式（5）為自提點的容量約束；約束式（6）為滿足客戶偏好需求約束；約束式（7）為客戶的時間約束，表示車輛k到達點j的時間等于其離開其前一點i的時間加上從點i行駛到點j所需要的時間；約束式（8）表示當且僅當選擇HD配送方式時，才應遵守客戶指定的時間窗，而選擇CP配送方式時，車輛可以在任意時間內訪問自提點；約束式（9）表示配送車輛均從配送中心出發并最終返回配送中心；約束式（10）確保路線的連續性；約束式（11）～（13）表示決策變量的取值范圍。

3 算法設計

具有不同交付選擇的車輛路徑問題（VRPDO）是對于VRP的擴展，同屬于NP難問題，該問題在VRP的基礎上所包含的客戶交付偏好特征以及交付方式所對應的配送時間窗變化加劇了求解的復雜性，對于大中型規模問題，采用精確式算法難以在有效時間內獲得解。為對模型進行有效求解，不同文獻設計了不同的啟發式算法，Tao等人^［14］使用禁忌搜索算法對訂單分配及路徑規劃問題進行求解；于江霞等人^［17］使用遺傳算法對帶時間窗的車輛路徑問題進行求解；楊翔等人^［21］使用蟻群算法對多中心開放式車輛路徑問題進行求解。然而以上啟發式算法都有一定的局限性，如禁忌搜索算法的全局搜索能力較弱，且其算法性能更多依賴于鄰域算子的設計；遺傳算法是以一定概率從父代遺傳基因至子代，難以保證優秀的基因被保留，容易導致求解的結果差異性較大；蟻群算法性能依賴于初始參數的設置，容易陷入局部最優。本文基于已有算法基礎上設計了一種改進的自適應大鄰域搜索算法。該算法是由Ropke等人^［22］在Shaw^［23］的大鄰域搜索算法（large neighborhood search，LNS）的基礎上提出的擴展算法，最初被用來解決帶時間窗的取送貨車輛路徑問題，對于其他類型的VRP同樣擁有良好的求解能力。ALNS算法能夠提供類似模塊化的組合方案，根據求解問題對算子進行改進和組合，同時對于具有時間窗要求的大中型VRP問題的實例，ALNS算法能夠有效地進行解決，據此選擇該算法開展設計研究。自適應大鄰域搜索算法具有很強的適應性，在較短的時間內均能得出高質量的可行解，在自適應大鄰域搜索算法中加入眾多破壞算子和修復算子來對路徑規劃問題進行求解，為避免陷入局部最優解的可能性，采用Metropolis接受準則。ALNS算法步驟如下所示。

算法1 自適應大鄰域搜索算法

3.1 生成初始解

隨著顧客的增多，VRPDO問題的解的空間急劇增大，而一個優質的初始解能夠促進算法找到問題的最優解。在生成初始解時，首先根據顧客的偏好程度分為偏好送貨上門和自提點交付兩種類型，對偏好送貨上門的顧客按其時間窗進行排序，并將排序后的目標放入顧客集H中，剩余顧客放入集合G中，集合H和G作為當前可訪問列表。然后，考慮所有未被訪問的顧客點，從顧客集H中依次選擇目標構建配送順序，若一條路徑因時間窗限制而無法訪問任何新顧客時，就會構建一條新路線，直到顧客集H的顧客被訪問完為止，得到一組路徑R。再在不違反車輛容量約束以及R路線已訪問顧客點的時間窗的條件下將集合G中的顧客隨機插入其中。重復此操作，直到訪問完所有客戶。

3.2 鄰域搜索算子

在ALNS算法中，鄰域結構包含破壞鄰域和修復鄰域兩部分，其中破壞算子和修復算子作用于解的鄰域搜索空間后產生新解。鄰域搜索算子的設計對于整個算法至關重要，關系到整個算法的性能。破壞鄰域主要是通過采用不同的破壞算子從解決方案中刪除顧客。移除后，顧客被放置在解決方案的請求列表中。根據問題特征所采用的破壞算子分別為random removal、route removal、worst removal、T-oriented random removal四種算子。

a）random removal算子。從當前解S中隨機選擇q個顧客進行移除并放至請求列表中。

b）route removal算子。從當前解S中隨機選擇一條路徑，將該路徑中的全部顧客進行移除并放至請求列表中。

c）worst removal算子。計算當前解S中每個顧客點移除前后成本差值，選擇差值最大的客戶點進行移除，重復執行移除操作直到q個客戶被移除。

d）T-oriented random removal算子。隨機選擇解決方案中的顧客，若所選的為送貨上門服務的顧客，則被移除的概率僅為10%。如果該客戶是在共享位置交付的，則其被刪除。重復執行移除操作直到q個客戶被移除。

修復鄰域主要是通過采用不同的修復算子將請求列表中的顧客重新插入到各路徑中獲得新可行解。根據問題特征所采用的修復算子主要包括random order best insertion、greedy best insertion、regret-2 insertion和preferred best insertion四種算子。

a）random order best insertion算子。找到請求列表中每個顧客插入成本最小且滿足約束的路徑，以隨機順序進行插入。

b）greedy best insertion算子。迭代地計算請求列表中每個顧客在每條路徑的最優插入位置以及相應的最小成本，選取插入成本值最小的顧客按其最優路徑的最佳位置進行插入。

c）regret-2 insertion算子。迭代地計算請求列表中的每個顧客最優插入路徑成本與次優插入路徑成本的差值，對該值進行從大到小的排序并按照該順序將對應的顧客按其最優路徑的最佳位置進行插入。

d）preferred best insertion算子。該算子是對經典的best insertion的改編。計算請求列表中所有帶交付選項顧客所有插入位置的成本，通過考慮客戶偏好程度p以及插入成本按照字典順序將對應的顧客按其最優路徑的最佳位置進行插入。

在生成初始解后，使用選擇的破壞算子從當前解中刪除客戶，刪除的客戶被放置在請求列表中，再通過修復算子將列表的客戶插入解決方案中，產生新的解決方案。

3.3 自適應搜索與算法接受準則

ALNS算法通過迭代地應用破壞算子和修復算子改進解決方案，整體搜索過程被劃分為幾個階段。在ALNS的每次迭代中利用輪盤賭的方式選擇破壞算子和修復算子，其中破壞算子被選擇的概率為p^-，修復算子被選擇的概率為p⁺。選擇概率是通過這些算子的權重（算子的歷史表現）w^-_i、w⁺_i進行分配，每個算子最初都有相同的權重。各個算子被選擇的概率計算方式如下：

由式（14）（15）可知，算子權重越大，被選擇的概率越大。在搜索過程中，ALNS會對各個破壞算子和修復算子的權重進行動態調整，以便獲得更好的鄰域和解。

在ALNS算法主框架中，采用模擬退火算法來判斷是否接受新可行解，其接受概率為e^{-（f（S′）-f（S））/T}。如果f（S′）＜f（S），則直接接受新可行解，否則該可行解被接受的概率取決于f（S′）-f（S）值與T的比值，T為當前溫度。設T初始溫度為T₀，在每次迭代中T與冷卻系數τ（0＜τ＜1）相乘以τT的方式更新使得溫度T值逐漸下降，接受較差解的概率也不斷減小。利用該接受標準的目的是允許ALNS在早期迭代中廣泛地探索解決方案空間，并專注于在后期迭代中尋找更高質量的解決方案。

3.4 算法時間復雜度分析

由于ALNS算法在每次迭代中會選擇不同算子進行鄰域搜索，而不同算子計算復雜度不同。在移除算子中，random remo-val算子在刪除節點時不考慮任何標準，其最壞情況的時間復雜度為O（n）；route removal算子從解決方案中隨機選擇一條路徑，從該路徑中迭代移除所有節點，執行該算子的時間復雜度取決于所選路徑中的節點數量，其時間復雜度為O（1）；worst removal算子迭代地刪除高成本客戶，每次移除節點后更新解決方案，其最壞情況的時間復雜度為O（n²）；T-oriented random removal算子盡可能多地移除在共享交付位置的客戶節點，其最壞情況的時間復雜度為O（n）。在修復算子中，random order best insertion算子的時間復雜度取決于移除列表中的客戶數量以及插入位置的數量，其最壞情況的時間復雜度為O（n²）；greedy best insertion算子與第一種修復算子類似，其最壞情況的時間復雜度為O（n²）；regret-2 insertion算子的最壞情況的時間復雜度為O（n³）。preferred best insertion算子與第一種修復算子類似，其最壞情況的時間復雜度為O（n²）。由此可知，幾個鄰域搜索算子中復雜度最大的算子為regret-2 insertion算子，其復雜度為O（n³），假設算法的最大迭代次數為I，則改進后的自適應大鄰域搜索算法的時間復雜度為O（I×n³）。

4 算例分析

4.1 實例分析

以重慶市南岸區某大型連鎖超市的配送任務為實例，圖2為客戶在百度地圖中的實際位置分布，其中零售超市DT0位置作為配送中心，CT-1至CT-50表示需要配送的客戶。

假設客戶已經選擇了交付方式及服務時間窗，則客戶的配送量、時間窗等信息如表2所示?？蛻舻姆諘r間窗以分鐘為單位計算，如顧客的時間窗為8：00～9：00，則實際計算時的時間窗為0～60 min。其中，某些客戶的時間窗為8：00～19：00，說明該客戶沒有時間限制。

在實際情況中，對于選擇送貨上門顧客來說，快遞員需要與顧客溝通、當面簽訂等時間，結合實際并參考文獻最終設定快遞員送貨上門配送時間服從均值為8 min，方差為2 min的正態分布；而對于自提點來說，考慮智能快件箱自提模式，快遞員僅需將快件放入柜中，因此不考慮自提交付方式的服務時間。由于送貨上門單次只能服務單個客戶，所產生的時間成本遠高于自提點交付方式，所以根據快遞員的時薪考慮其送貨上門的服務成本，設定快遞員送貨上門的服務成本為ρ=0.3元/min。同時參考文獻［24］設定配送車輛的固定使用成本為80元，單位行駛成本為0.3元/km，最大裝載量為180 kg，行駛速度為30 kg/h。由于目前沒有對顧客偏好程度采集的工具，采用隨機設定形式描述顧客對于送貨上門需求的偏好程度，后期可以通過客戶選擇交付方式的推行采集具體數據。當配送車輛未滿足顧客首選偏好時，設定λ=0.1計算產生的懲罰成本。在此參數假設下，對實例進行5次測算。測算平均結果如表3所示。

由表3～5結果表明，在僅滿足部分顧客的首選偏好的情況下，總配送成本有所下降，且配送時間也有所下降。這是由于在滿足更多首選偏好為HD的客戶服務需求時，配送人員需要花費更多時間平衡多個交付任務。當這些訂單相隔不遠時（比如同一社區），可以節省在路上的旅行時間，同時交付多個訂單；當這些訂單相距較遠時，配送人員會消耗更多的時間浪費交付能力。因此通過改變某些較遠客戶的送貨上門的交付方式，減少配送人員的服務時間，使其可以完成更多的交付請求?？梢?，在考慮滿足部分顧客的首選交付方式，可以在一定程度上提高物流服務配送效率，降低企業的配送成本。表4中為了簡化，將DT-0簡寫為0，CT-1簡寫為1，下同。

為了考慮實際情況中選擇不同交付方式的顧客類型比例對于總配送成本的影響，考慮對50個客戶中含有不同顧客類型比例的問題進行分析，如表6所示。

由圖3結果表明，HD客戶類型比例越高，企業的配送成本也越高，而隨著滿足首選偏好比例的上升，總配送成本的節約趨于平緩。這是因為雖然滿足顧客傾向的交付選擇能夠帶來較好的服務質量，獲得更高的顧客滿意度，但是送貨上門導致企業的時間成本增加，總配送成本也相應增加。

為考慮不同客戶規模對于總配送成本的影響，在50、75及100個客戶三種不同客戶規模下對問題進行分析，由圖4所示。

上述結果表明，客戶規模越大，企業的配送成本相應增高，且隨著滿足首選偏好比例的上升，總配送成本的節約也呈上升趨勢。即當客戶規模越大，滿足部分首選偏好所帶來的成本節約會越大。因此，在實際配送情況中，企業可以根據顧客的偏好更好地匹配服務和需求，利用不同配送模式的優勢滿足部分時間成本較低的顧客送貨上門請求，同時兼顧企業運營成本以及顧客滿意度，提高企業物流服務水平和效率。4.2 算法性能分析

為驗證所提改進的自適應大領域搜索算法的有效性，進行了算例的分析驗證，通過使用該算法來解決與研究問題緊密相關的VRPTW問題，從Solomon算例中選取了三種不同客戶分布的實例來進行驗證。Solomon數據集共分為 C1、C2、R1、R2、RC1、RC2六類。C1和C2類的客戶呈現分塊聚集分布；R1和R2 類的客戶是隨機分布的；RC1 和RC2 類的客戶既有隨機分布，又有分塊聚集分布。R1、C1、RC1 數據集的車輛容量小、時間窗口窄，每條路線只允許少數客戶；R2、C2 和 RC2 數據集的車輛容量大，且在較長的計劃周期內允許許多客戶使用同一輛車進行服務。首先對算法的求解性能進行分析，從Solomon的六類數據中選取部分算例測試改進后自適應大鄰域搜索算法，然后將實驗結果與離散蝙蝠算法^［25］（discrete bat algorithm，DBA）進行比較，結果如表7所示，其中NV列為每類算例集使用的平均車輛數、TD為總行駛距離，time是算法獨立運行5次的平均時間耗費。

根據上述實驗結果可知，所設計的ALNS算法在平均車輛數方面略差于DBA，但在平均總行駛距離以及求解時間方面，ALNS優于DBA算法可以得到較優的解及較快的求解時間。為進一步驗證算法有效性，使用改進的ALNS算法在每個測試算例上求解五次，將全部測試算例與其他文獻中的混合遺傳算法^［26］（hybrid genetic algorithm，HGA）及蟻群禁忌搜索的混合算法^［27］（consists of ant colony optimization and tabu search，ACO-Tabu）分別進行比較，結果如表8所示，其中NV列為每類算例集使用的平均車輛數、TD為總行駛距離。

通過分析上述測試結果可知，所設計的ALNS算法與HGA、ACO-Tabu兩種算法相比，在求解C1、C2類算例時，配送車輛數量與其他兩種算法中的最優配送車輛數相同，且配送車輛行駛的總里程均優于其他兩種算法的總里程；在求解R1、R2、RC1、RC2類算例時，配送車輛數量與配送車輛數量劣于HGA，但配送車輛行駛的總里程明顯優于其他兩種算法。綜上所述，針對VRPDO問題設計的算法能表現出良好的求解質量和性能，驗證了其可行性和有效性。

5 結束語

針對城市末端配送服務中客戶傾向的交付方式以及對應的時間窗具有差異性問題，對考慮不同交付選擇的物流配送路徑問題進行了研究。通過考慮企業配送成本，客戶的偏好程度以及交付時間窗等因素，以總運營成本最小為優化目標，建立了考慮不同交付選擇的配送模型，設計引入多種算子的自適應大鄰域搜索算法進行求解。通過實例分析和算例仿真實驗驗證了算法的有效性，并且發現顧客個性化需求比例及滿足顧客首選交付方式的比例對企業的配送成本影響顯著。對于未來研究，企業可以考慮推出不同的時間窗定價服務，根據客戶對于服務質量的敏感性制定針對性的配送服務。對于一些服務質量要求不高的客戶群體，可以采取減少配送成本、損失一定的客戶滿意度的策略；對于一些對服務質量要求嚴格的客戶群體，可以采取增加配送成本，提高客戶滿意度的策略。

參考文獻：

［1］張力婭， 張錦， 肖斌. 考慮顧客優先級的多目標O2O外賣即時配送路徑優化研究［J］. 工業工程與管理， 2021，26（2）：196-204. （Zhang Liya， Zhang Jin， Xiao Bin. Multi-objective O2O take-out instant delivery routing optimization considering customer priority［J］. Industrial Engineering and Management， 2021，26（2）：196-204.）

［2］邱晗光， 高敏， 甄杰， 等. 可選交付方式及時間窗下城市配送服務選項多目標聯合定價［J］. 計算機集成制造系統， 2020，26（7）： 1965-1975. （Qiu Hanguang， Gao Min， Zhen Jie， et al. Multi-objective joint pricing of delivery options in urban distribution considering customers’ choice of last-mile delivery and time slots［J］. Computer Integrated Manufacturing Systems， 2020，26（7）： 1965-1975.）

［3］陳義友， 陳以衡. 基于逐漸覆蓋的自提點選址模型與算法研究［J］. 計算機應用研究， 2016，33（8）： 2275-2277，2297. （Chen Yiyou， Chen Yiheng. Research on pickup point location model and algorithm in presence of gradual coverage［J］. Application Research of Computers， 2016，33（8）： 2275-2277，2297.

［4］郭放， 黃志紅， 黃衛來， 等. 考慮自取服務和門到門服務的電動汽車物流網絡優化策略研究［J］. 中國管理科學， 2022，30（2）： 264-275. （Guo Fang， Huang Zhihong， Huang Weilai， et al. Optimal planning of the electric vehicle routing and battery charging problem with self-pickup and door-to-door delivery service［J］. Chinese Journal of Management Science， 2022，30（2）： 264-275.）

［5］Enthoven D L J U， Jargalsaikhan B， Roodbergen K J， et al. The two-echelon vehicle routing problem with covering options： city logistics with cargo bikes and parcel lockers［J］. Computers amp; Operations Research， 2020，118：1-17.

［6］Mancini S， Gansterer M. Vehicle routing with private and shared delivery locations［J］. Computers amp; Operations Research， 2021，133： 1-38.

［7］Mommens K， Buldeo R H， Van Lier T， et al. Delivery to homes or collection points？A sustainability analysis for urban， urbanised and rural areas in Belgium［J］. Journal of Transport Geography， 2021，94：1-9.

［8］Carotenuto P， Ceccato R， Gastaldi M， et al. Comparing home and parcel lockers’delivery systems： a math-heuristic approach［J］. Transportation Research Procedia， 2022，62： 91-98.

［9］邱晗光， 周繼祥， 龍躍. 顧客可選末端交付方式和時間窗的城市配送動態訂單接受優化研究［J］. 中國管理科學， 2020，28（8）： 114-126. （Qiu Hanguang， Zhou Jixiang， Long Yue. Research on the dynamic order acceptance in urban delivery considering customer choice of the last-mile delivery modes and time slots［J］. Chinese Journal of Management Science， 2020，28（8）： 114-126.）

［10］Dumez D， Lehuédé F， Péton O. A large neighborhood search approach to the vehicle routing problem with delivery options［J］. Transportation Research Part B： Methodological， 2021，144：103-132.

［11］葛顯龍， 溫鵬哲， 薛桂琴. 基于需求預測的兩級動態配送路徑優化研究［J］. 中國管理科學， 2022，30（8）： 210-220. （Ge Xianlong， Wen Pengzhe， Xue Guiqin. Two-echelon dynamic vehicle routing problem with request forecasting［J］. Chinese Journal of Management Science， 2020，30（8）： 210-220.）

［12］Arslan A M， Agatz N， Kroon L， et al. Crowdsourced delivery—a dynamic pickup and delivery problem with Ad hoc drivers［J］. Transportation Science， 2019，53（1）： 222-235.

［13］李珍萍， 張煜煒. 帶時間窗和服務順序約束的多需求車輛路徑問題［J］. 控制與決策， 2019，34（7）： 1565-1570. （Li Zhenping， Zhang Yuwei. Multiple demands vehicle routing problem with time windows and service order constraints［J］. Control and Decision， 2019，34（7）： 1565-1570.）

［14］Tao Jiawei，Dai Hongyan，Chen Weiwei， et al. The value of persona-lized dispatch in O2O on-demand delivery services［J］. European Journal of Operational Research， 2023，304（3）： 1022-1035.

［15］馬俊， 張紀會， 郭乙運. 考慮客戶分類的隨機時間車輛路徑優化模型與算法［J］. 計算機應用研究， 2022，39（7）：1979-1984. （Ma Jun， Zhang jihui， Guo Yiyun. Optimization model and algorithm for vehicle routing problem with stochastic time and customer classification［J］. Application Research of Computers， 2022，39（7）： 1979-1984.）

［16］Binart S， Dejax P， Gendreau M， et al. A 2-stage method for a field service routing problem with stochastic travel and service times［J］. Computers amp; Operations Research， 2016，65： 64-75.

［17］于江霞， 杜紅亞， 羅太波. 基于客戶分類的即時配送路徑優化研究［J］. 交通運輸系統工程與信息， 2020，20（4）： 202-208. （Yu Jiangxia， Du Hongya， Luo Taibo. Real-time delivery routing optimization based on customer classification［J］. Journal of Transportation Systems Engineering and Information Technology， 2020，20（4）： 202-208.）

［18］Calvet L， Ferrer A， Gomes M I， et al. Combining statistical learning with metaheuristics for the multi-depot vehicle routing problem with market segmentation［J］. Computers amp; Industrial Engineering， 2016，94：93-104.

［19］夏揚坤， 鄧永東， 龐燕， 等. 帶客戶分級和需求可拆分的生鮮車輛路徑問題［J］. 計算機集成制造系統， 2021，27（4）： 1238-1248. （Xia Yangkun， Deng Yongdong， Pang Yan， et al. Fresh food vehicle routing problem with split deliveries and customer classification［J］. Computer Integrated Manufacturing Systems， 2021，27（4）： 1238-1248.）

［20］Rezaei J. Best-worst multi-criteria decision-making method：some pro-perties and a linear model［J］. Omega， 2016，64：126-130.

［21］楊翔， 范厚明， 張曉楠， 等. 基于模糊時間窗的多中心開放式車輛路徑問題［J］. 計算機集成制造系統， 2016，22（7）：1768-1778. （Yang Xiang， Fan Houming， Zhang Xiaonan， et al. Optimization of multi-deport open vehicle routing problem with fuzzy time window［J］. Computer Integrated Manufacturing Systems， 2016，22（7）：1768-1778.）

［22］Ropke S， Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows［J］. Transportation Science， 2006，40（4）： 455-472.

［23］Shaw P. Using constraint programming and local search methods to solve vehicle routing problems［C］//Proc of International Conference on Principles and Practice of Constraint Programming. Berlin：Sprin-ger， 1998： 417-431.

［24］陳欣慰. 多模糊時間窗約束下基于純電動汽車的城市配送車輛路徑問題研究［D］. 成都：西南交通大學， 2020. （Chen Xinwei. Research on urban distribution vehicle routing problem based on pure electric vehicle under multiple fuzzy time window constraints［D］. Chengdu：Southwest Jiaotong University， 2020.）

［25］戚遠航， 蔡延光， 蔡顥， 等. 帶時間窗的車輛路徑問題的離散蝙蝠算法［J］. 電子學報， 2018，46（3）： 672-679. （Qi Yuanhang， Cai Yanguan， Cai Hao， et al. Discrete bat algorithm for vehicle routing problem with time window［J］. Acta Electronica Sinica， 2018，46（3）： 672-679.）

［26］儀孝展. 基于改進遺傳算法的物流車輛路徑規劃方法研究與應用［D］. 西安：西安理工大學， 2018. （Yi Xiaozhan. Research and application of logistics vehicle path planning method based on improved genetic algorithm［D］. Xi’an：Xi’an University of Technology， 2018.）

［27］Yu B， Yang Z Z， Yao B Z. A hybrid algorithm for vehicle routing problem with time windows［J］. Expert Systems with Applications， 2011，38（1）： 435-441.