模糊時間窗下的車機并行取送貨問題研究

摘 要：為解決農村“最后一公里”的取送貨以及客戶滿意度低的難題，文章提出卡車搭配無人機配送的模式，以配送總成本最小化和客戶滿意度最大化為目標建立數學約束模型，采用改進的遺傳算法求解，并以江西省贛州市定南縣的村莊為例進行應用研究，結果表明卡車搭配無人機并行的運輸模式與單獨使用卡車的運輸方式相比，總成本得到充分降低，客戶滿意度也顯著提高。因此文章研究成果有望為解決農村“最后一公里”配送降本增效以及提高客戶滿意度提供新思路和參考價值。

關鍵詞：模糊時間窗；無人機；取送貨；物流路徑規劃

中圖分類號：F252 文獻標志碼：A DOI：10.13714/j.cnki.1002-3100.2024.14.017

文章編號：1002-3100（2024）14-0085-07

Research on the Parallel Pick-up and Delivery of Vehicles and Drones Under the Fuzzy Time Window

（1. School of Management， Wuhan University of Science amp; Technology， Wuhan 430065， China; 2. Center for Service Science and Engineering， Wuhan University of Science amp; Technology， Wuhan 430065， China）

Abstract： To solve the problems of picking up and delivering goods in the \"last kilometer\" and low customer satisfaction of rural areas， this article proposes a model of truck and drone delivery， with the goal of minimizing the total delivery cost and maximizing customer satisfaction. A mathematical constraint model is established， and an improved genetic algorithm is used to solve the problem. An application study is conducted，taking a village in Dingnan County， Ganzhou City， Jiangxi Province as an example. The results indicate that the transportation mode of trucks paired with drones in parallel significantly reduces the total cost and improves customer satisfaction compared to the transportation mode of using trucks alone. Therefore， the research results of this article are expected to provide new ideas and reference value for solving the problem of cost reduction and efficiency increase in rural \"last kilometer\" delivery， as well as improving customer satisfaction.

Key words： fuzzy time window; drones; picking up and delivering the goods; logistics path planning

0 引 言

隨著經濟的迅速蓬勃發展，農村物流市場規模不斷擴大。然而，農村地區獨特的地理特點也帶來了諸多挑戰：農村地域廣闊，村莊之間距離遙遠，居民點分布不均，導致物流成本居高不下，配送效率不高。盡管近年來，諸如京東和順豐等快遞企業已將物流網絡擴展至縣鎮區域，但農村地區的快遞網點仍相對稀缺，配送工作人員也較少，僅依靠傳統的人力配送很容易受到交通、天氣、個人突發狀況等因素的影響而導致未能在客戶要求的時間內送達，從而產生時效性差、客戶滿意度低等問題。因此，如何改進傳統的配送方式，發展農村電商物流的“最后一公里”，已經成為亟待解決的問題。另一方面，隨著電商平臺的蓬勃發展和“直播帶貨”助農模式的興起，農村地區的快遞需求得到了極大推動，客戶退換貨需求不斷增加，逆向物流也嶄露頭角，這就意味著農村物流的研究不應只局限于配送問題上，還應更加關注寄件問題。因此，如何采用高效的方式來解決農村地區的同時取送貨問題已成為更多學者關注的議題。

近年來，隨著無人機技術的不斷演進，其獨特的優勢，包括成本效益、高速度、卓越的實際應用潛力以及免受地理地形和道路限制的機動性，使無人機成為物流業的新趨勢。有研究報告指出，大約90%～95%的包裹重量約2.27公斤，在最后一公里使用無人機配送，能夠降低80%的配送成本[1]。此外，中國農村地域廣闊，鄉村聚落通常以緊湊的方式分布，因其缺乏高層建筑和電磁環境復雜性，使其成為物流無人機應用的理想環境。但是無人機具有承載能力較小和續航里程有限的特點，單獨運用時難以滿足配送需求。因此，采用“運輸工具+無人機”的配送方式，能夠有效彌補無人機的短板。

關于應對農村物流的“最后一公里”配送挑戰，最早由Murray等學者提出了無人機與卡車協同配送模式，旨在優化配送時間[2]。此后，越來越多的研究者開始探討這一模式，許文鑫等提出了配送車+無人機協同配送模式，以總成本最小為目標，利用聚類算法和改進遺傳算法求解[3]；曹英英等提出帶時間窗的卡車+無人機的配送模式，以總運營成本最小為目標，并通過改進后的K-means算法和遺傳模擬退火算法求解[4]；在對同時取送貨問題的研究上，大多數學者主要針對傳統配送車輛。劉虹等建立帶隨機需求和同時取送貨的多行程車輛路徑優化模型來解決配送過程中客戶需求的動態性和不確定性[5]。也有部分學者在同時取送貨的基礎上，加入了時間窗的變量，研究考慮時間窗的同時取送貨問題。李博威等考慮軟時間窗下的車輛路徑問題，構建多目標的非線性規劃[6]。總的來說，一些學者在解決車輛路徑優化問題時已經開始考慮軟時間窗的限制。這意味著車輛可以在時間窗范圍之外進行配送，但需支付一定的懲罰成本。然而，在軟時間窗的實際應用情況中，服務時間超出時間窗范圍通常僅導致客戶對服務的滿意度下降，而不會引發實際罰款。并且在實際配送中，客戶對服務時間的要求通常并非嚴格固定，因此采用模糊時間窗能更準確地反映客戶的需求和期望。胡志華等率先在國內將模糊時間窗應用于物流問題研究中，他在模糊時間窗的基礎上采用改進節約里程法求解車輛調度問題[7]；由于冷鏈物流的獨特性質，時間窗口的設定需更富彈性，因此一部分學者將模糊時間窗主要應用于冷鏈物流的研究上，梁承姬等為了追求最低的配送成本和最高的客戶滿意度，采用了改進的遺傳算法來解決帶有模糊時間窗的冷鏈配送問題[8]。

雖然目前研究車機合作問題、同時取送貨問題和模糊時間窗的物流文章較多，但是大部分同時取送貨文章僅考慮傳統車輛在城市地區，鮮有同時將模糊時間窗和同時取送貨與車機合作相結合的文章，因此為了完全貼合現實，本文在前人研究的基礎上提出了模糊時間窗下的車機并行取送貨問題，以最小化物流配送總成本和最大化客戶滿意度為研究目標，構建數學約束模型，并采用改進的遺傳算法來解決農村最后一公里配送問題。

1 問題描述

假設配送中心擁有N輛卡車和一架無人機，對我國某農村需求量不同的N個居民點進行服務。配送模式為：卡車和無人機首先從配送中心獲取待派送的貨物，然后啟程前往客戶點。無人機在一次飛行中可以分配貨物到一個或多個目的地，但每次分配的貨物數量受限于其承載和續航能力。完成派送后，無人機可以返回配送中心以獲取新的貨物或更換電池以繼續下一輪派送。鑒于部分居民點距離超過了無人機的續航范圍，以及有些貨物的重量超出了無人機的負載能力，因此在續航和負載范圍內的貨物將由無人機派送，而續航和負載范圍之外的貨物則由卡車負責派送。卡車和無人機在完成各自的派送任務后，返回到配送中心。當客戶在其期望的時間范圍內得到服務時滿意度最高。當派送時間早于或晚于期望時間范圍，但仍在可接受的最大時間范圍內時，物流企業需承擔經濟懲罰，同時客戶滿意度降低。如果派送時間超出了客戶可接受的最大時間范圍，那么客戶滿意度將降至零，同時物流企業將面臨無限大的經濟懲罰。問題假設如下。

第一，整個鄉鎮只有一個配送中心；第二，一個客戶點只能被卡車或無人機其中一個工具服務，一輛車或一架無人機可服務多個居民點；第三，同一顧客點，先完成送貨服務再完成取貨服務；第四，不考慮貨物體積因素；第五，采用更換鋰電池方法解決無人機鋰電池儲能小的問題，充電時間忽略不計；第六，由于卡車實際的最大載重較大，所以不考慮卡車載重對運輸過程的影響。

2 模型構建

2.1 模型變量說明

2.2 引入客戶滿意度

假設客戶期望的服務時間為[，]，當物流實際執行中，配送受到多種因素，如配送計劃和交通狀況等的影響，導致實際配送時間窗偏離客戶的預期。這在實際操作中可能導致配送時間要么提前，要么延遲，進而影響了客戶的滿意程度。假設和分別為客戶能忍受的最早和最晚時間，若在[，]和[，]時間范圍內配送，則客戶滿意度隨著與期望時間窗差值的增大而減小；若在[，]范圍外進行配送，則客戶滿意度為0。

客戶滿意度函數如下。

fit=

2.3 模型建立

s.t.

目標函數（1）為最小化路徑成本即無人機路徑成本、卡車路徑成本和模糊時間窗懲罰成本。目標函數（2）為客戶滿意度之和的最大值。約束（3）表示每個客戶點必須被訪問一次，且只能被一個運輸工具的一個行程訪問一次。約束（4）和（5）表示每個運輸工具的每個行程都從配送中心出發并回到配送中心。約束（6）確保路徑的連續性。約束（7）表示客戶點i和j被同一輛車的同一次行程訪問，并且車輛訪問i點之后立即訪問j點時，需要滿足的時間先后連續性。約束（8）和（9）表明運輸工具在一次行程結束后的出發時間要晚于上一次行程的結束時間，如果是首次行程，其起始時間不得早于最早的配送開始時間。約束（10）和（11）表示客戶點i和j被同一輛車的同一次行程訪問，并且車輛訪問i點之后立即訪問j點，則需滿足載重連續性。約束（12）表示需滿足運輸工具的載重約束。約束（13）和（14）表示需滿足運輸工具的最大行駛里程約束。約束（15）表示客戶最大可容忍時間窗。約束（16）—（20）定義了模型中的各變量。

3 算法設計

本文研究的車機并行配送問題屬于車輛路徑問題。由于車輛路徑問題被認為是NP-hard問題，傳統的解決方法往往面臨困難，通常采用啟發式算法來解決這類問題。啟發式算法具有高效性和較好的收斂性，并且不容易陷入局部最優。因此本文選擇改進的遺傳算法為解決方案。改進的遺傳算法流程如下所示。

3.1 染色體編碼

首先需要對遺傳算法的染色體進行編碼，以將問題參數映射為遺傳算法可處理的個體。本文則采用實數編碼方式，設定編碼長度維度為N，各維度取值范圍在1到m+1之間，其中，第i位編碼對應的是客戶i。如圖1所示，其中整數部分的客戶1對應的數字為1，代表客戶1分配以運輸工具1；客戶3對應的數字為0，代表客戶3分配以運輸工具0；而小數部分則用于確定具體行程。

3.2 染色體解碼

在解碼過程中，首先通過編碼的整數部分，可以獲知各個客戶所對應的配送車編號，因此就可以得到各個配送車所負責的客戶集合。再根據輪盤賭規則進行同一配送車程的分配，以此完成解碼過程。

具體過程：首先通過整數部分可以獲得圖2左下角各運輸工具所服務的客戶集合。再生成具體行程，以卡車2為例：卡車2服務客戶2、客戶5、客戶6，共三個客戶，因此卡車2最多包含三個行程（每個行程服務一個客戶），據此建立輪盤賭模型分為三個區間[0， 0.33），[0.33， 0.67），[0.67， 1）， 三個區間分別對應三個行程，在小數部分每個客戶對應的小數落在哪個區間，這個客戶就分配到哪個行程。具體而言，卡車2的客戶2對應0.4，因此分配到行程2；客戶5對應0.3，分配到行程1；客戶6對應0.1，分配到行程1。注意到客戶5和客戶6同時分配到行程1，而客戶6的小數小于客戶5，因此在該行程的訪問順序中，卡車2先訪問客戶6再訪問客戶5。最終可以得到染色體對應的所有行程（見圖3）。

3.3 染色體更新操作

3.3.1 選擇操作

本文選擇操作是將個體的適應度值取倒數，根據個體的適應度值，采用輪盤賭以概率的方式選擇個體，以構建下一代的種群。適應度值較高的個體有更大的概率被選中，適應度值較低的個體也仍有一定概率被選中，以保持種群的多樣性。

3.3.2 交叉操作

本文交叉操作首先在兩個父代個體中隨機選擇一個或多個交叉點，如父代1：1.3、2.4、0.7、3.7、2.3、2.1、3.6，父代2：0.8、3.9、2.2、1.3、1.5、2.5、3.3，選擇第五位到第七位為交叉片段，則父代1：1.3、2.4、0.7、3.7、|2.3、2.1、3.6|，父代2：0.8、3.9、2.2、1.3、|1.5、2.5、3.3|；然后將父代2的交叉片段和父代1的交叉片段進行交換。最終變成子代1：1.3、2.4、0.7、3.7、1.5、2.5、3.3，子代2：0.8、3.9、2.2、1.3、2.3、2.1、3.6。見圖4。

3.3.3 變異操作

本文變異操作首先隨機選擇一個變異點，將該變異點上的數值換成其他隨機數值。例如父代1：1.3、2.4、0.7、3.7、2.3、2.1、3.6，選擇第四位為變異點，并賦值一個隨機數值，將3.7變異為2.8，則新的子代為1.3、2.4、0.7、2.8、2.3、2.1、3.6。見圖5。

3.3.4 2-opt優化算子

遺傳算法本身具有良好的全局搜索能力，然而在局部搜索方面卻表現相對不足， 因此，本文引進2-opt優化算子以增進算法性能。2-opt優化算子具體操作如下：首先，將父代復制給子代，以便在子代上執行2-opt操作；其次，隨機選擇一個起始位置和結束位置，通常在0到倒數第三個城市之間，以確保至少留下兩個城市不被改變；然后交換路徑中的兩個城市，以改變路徑的一部分；最終將經過2-opt操作改進的子代添加到新的種群中。見圖6。

3.3.5 精英保留策略

本文精英保留策略，首先，采用輪盤賭的方式，保留最優的80%的個體進行交叉變異；其次，每一代保留最優的20%的個體不做交叉變異，插入到選擇后的種群中，保持種群總數不變。

4 算例分析

4.1 算例數據

江西省贛州市是我國較早的物流無人機試飛點，這里有高低起伏的丘陵地貌，使得傳統物流難以抵達偏遠農村，但是卻極其適合無人機的應用，使無人機在農村地區的優勢明顯，因此本文在案例上選取了江西省贛州市定南縣的30個村莊為客戶點，為其提供取貨或送貨服務。見表2和表3。

假設該地區有一架無人機和兩輛卡車為客戶提供服務，通過高德地圖獲取30個村莊的具體地理位置，并隨機生成各個客戶點的取貨量和送貨量以及時間窗，配送服務開始時間設置為早上8：00，以min計算為480min。具體模型參數見表4。

4.2 案例驗證

本文采用Python軟件進行編程，其中種群規模設為200，最大迭代次數為300，交叉概率為0.9，變異概率為0.1。遺傳算法迭代情況如圖7所示，可以看出遺傳算法在迭代30次左右就趨于收斂。

經過多次迭代運行，無人機與卡車并行的路徑結果見表5和圖8（虛線為無人機，實線為卡車），求得最低總成本為875.59元，平均客戶滿意度為95%，無人機配送客戶點占總客戶點的41%，說明無人機可以在滿足時間窗的情況下高效率地完成其配送里程和載重范圍內的配送任務，極大地提高了客戶的滿意度。

為了表明無人機和卡車并行配送的優越性，本文與單獨使用兩輛卡車運輸的方式進行對比求解，其路徑結果如表6和圖9。

通過對比表5和表6的求解結果可知單獨兩輛卡車的最低總成本為1 003.19元，而卡車和無人機并行配送總成本為875.59元，相較于卡車單獨配送節省了127.6元。單獨兩輛卡車的平均客戶滿意度為88%，而卡車和無人機并行配送的平均客戶滿意度為95%，相較于單獨卡車配送模式提高了7%，結果表明無論是從成本降低還是客戶滿意度提高的角度來看，無人機在農村地區都具有顯著的優勢。因此，卡車和無人機并行配送模式不僅可以有效減少總成本，還能提升客戶滿意度。

4.3 靈敏度分析

本文分別對無人機行駛里程、無人機載重參數進行靈敏度分析，探討無人機性能參數對配送成本的影響。

4.3.1 無人機行駛里程靈敏度分析

本文將無人機最大載重量設定為10kg，對無人機行駛里程分別設定為15km、20km、25km進行靈敏度實驗測試，分析無人機行駛里程對總成本的影響，其結果對比如表7所示。

綜合比較結果表明，隨著無人機行駛里程的逐漸增加，配送成本呈現不斷下降的趨勢。這一趨勢的分析如下：在無人機行駛里程較短的情況下，由于農村配送區域廣闊，無人機所能承擔的配送任務相對有限。然而，隨著無人機行駛里程的不斷增加，其能夠承擔的配送任務逐漸增多，并發揮了其成本較低的優勢，最終使配送成本下降。

4.3.2 無人機載重靈敏度分析

本文將無人機最大行駛里程設定為20km，對無人機載重量分別設定為10kg、15kg、20kg進行靈敏度實驗測試，分析無人機載重量對配送成本的影響，其結果對比如表8所示。

綜合算例結果可以發現，隨著無人機載重的不斷提高，配送成本降低，但下降幅度較小。其原因為：隨著無人機承載能力的提高，首先，過重的客戶點數量減少，同時能夠滿足無人機承載需求的客戶點數量增加，因此，無人機能夠承擔更多的配送任務，其效益也相應提高，最終使總成本下降。其次，盡管無人機的承載能力增加，但其行駛里程并未改變，依然受到一定的限制。此外，本文所研究的取送貨數據之間的數值差異不大，這也是導致無人機配送成本下降幅度較小的原因。

5 結 語

隨著農村電商的迅速發展，農村最后一公里物流配送面臨著重大挑戰。然而，隨著無人機技術的不斷成熟，它已經成為解決農村最后一公里難題的重要突破口。鑒于農村實際情況，同時考慮到需要在取貨和送貨過程中維護客戶滿意度的問題，本文提出了卡車和無人機并行的配送模式，即模糊時間窗下的車機并行取送貨問題。并建立以最小化車機配送總成本和最大化客戶滿意度為目標的數學模型，采用改進的遺傳算法進行求解。研究結果表明，該配送模式能夠有效完成物流運輸任務，相較于傳統的獨立卡車配送方式，其能夠顯著降低物流成本并提高客戶滿意度。這為物流企業進一步拓展農村市場提供了解決方案。雖然本文為解決農村最后一公里問題提出了卡車和無人機并行的配送模式，但無人機和卡車處于獨立配送的情況，沒有更深度的協同合作，未來的研究可以考慮更有效地將卡車和無人機結合在一起，以進一步解決最后一公里問題。

參考文獻：

[1] 許菱，楊林超，朱文興，等．農村電商物流下無人機與車輛協同配送路徑優化研究[J]．計算機工程與應用，2024，60（1）：310-318.

[2] MURRAY C C，CHU A G．The flying sidekick traveling salesman problem： Optimization of drone-assisted parcel delivery[J].

Transportation Research Part C： Emerging Tecknologies，2015，54：86-109．

[3] 許文鑫，張敏，熊國文．配送車與無人機的農村物流配送路徑優化仿真[J]．計算機仿真，2022，39（6）：151-157．

[4] 曹英英，陳淮莉．基于集群的卡車與無人機聯合配送調度研究[J]．計算機工程與應用，2022，58（11）： 287-294．

[5] 劉虹，傅曉敏．考慮同時取送隨機需求的多行程車輛路徑研究[J]．西安電子科技大學學報（社會科學版），2019，29（3）：87-95.

[6] 李博威，戶佐安，賈葉子，等．帶軟時間窗的同時取送貨車輛路徑問題研究[J]．工業工程，2020，23（5）：75-81．

[7] 胡志華，孫志強，郭曉汾．基于模糊預約時間窗的車輛調度問題研究[J]．交通科技與經濟，2008（2）：94-97．

[8] 梁承姬，黃濤，徐德洪，等．改進遺傳算法求解帶模糊時間窗冷鏈配送問題[J]．廣西大學學報（自然科學版），

2016，41（3）：826-835.

收稿日期：2023-11-01

基金項目：湖北省教育廳哲學社會科學研究項目“助農直播視域下主播類型對受眾直播參與度的影響研究”（22Y029）；2022年度武漢城市圈制造業發展研究中心開放基金——基于“雙谷”聯動的武漢城市圈制造業協同創新研究（WZ2022Y02）

作者簡介：李四蘭（1974—），女，湖北仙桃人，武漢科技大學管理學院，武漢科技大學服務科學與工程研究中心，副教授，博士，碩士生導師，研究方向：物流管理與消費行為；李 佳（2000—），女，河南鄭州人，武漢科技大學管理學院碩士研究生，研究方向：物流系統優化與決策。

引文格式：李四蘭，李佳．模糊時間窗下的車機并行取送貨問題研究[J]．物流科技，2024，47（14）：85-91.