基于共同配送的農村快遞車輛調度問題

（華南理工大學 經濟與貿易學院，廣東 廣州 510006）

0 引言

近年來，互聯網電子商務在農村地區發展迅速。據統計，2019年全國農村網絡零售額達17 000億元，同比增長19.1%；全國農產品網絡零售額達3 975 億元，同比增長27%[1]。然而，作為農村電子商務的支柱性產業，農村快遞物流業卻依舊存在資源配置失衡、資源閑置與資源瓶頸并存的怪象。雖然基礎路網設施不完善是導致這一現象的根本性原因，但在現有條件下，如何提高“最后一公里”配送資源的有效性，完善配送網絡，解決當前農村快遞配送服務中存在的碎片化、高成本等問題[2]，是降低農村物流成本，響應中央“快遞下鄉”工程，推動消費品下鄉，促進農村電子商務加速發展的關鍵。

在地區中心城市或人口規模較大的鄉鎮開設網點，并由單一物流企業獨立完成其末端的配送業務是當前農村快遞物流的主要模式。而在一定時期內，由于各物流企業擁有的資源相對固定，因此該運營模式僅適于需求穩定、訂單量大、客戶地理分布相對集中的地區。我國農村人口分布較為零散，人口密度遠低于城市，同時村落之間距離遠大于城市社區間距離。因此，各物流企業獨立完成配送服務的運營方式是導致當前農村快遞配送出現需求難以及時滿足而供給方資源配置失衡、利用率不高、配送成本居高不下等問題的原因之一。

共同配送[3]模式是目前從資源配置角度解決上述問題的主要策略。該策略強調通過物流資源的共享和集中調度來最大化資源收益。我國農村地區的公路網大多以地級市為中心呈星狀射線分布，同一片區域的鄉鎮運輸車輛都會經過該區域的主干道路往返于地級市與所屬鄉鎮。因此，同區域內的鄉鎮具備協同聯合運輸的條件。目前已有學者對共同配送模式在農村物流中的應用展開研究。宋麗敏[4]以河南省某農村為例，實證分析了農村電商共同配送模式，發現共享物流下農村電商共同配送模式可對配送點的實際物流需求產生精確響應，從而提高配送效率。盛虎宜等[5]引入共同配送策略，構建以總配送費用最少為目標的多中心共同配送的車輛路徑模型，有效減少了農村配送過程中車輛的使用數量，降低了總配送費用。趙廣華[6]提出基于要素共享、契約分包等四種農村電商共同配送模式，并分析了其在不同情境下的適用范圍。

然而，新的模式也會帶來新的問題，例如資源的統籌安排與合理調度、利益分配[7]、責任分割等。其中，配送車輛的調度是提高配送效率與共同運營收益、降低農村配送成本的關鍵環節。而該領域已有的研究成果更多關注的是單個配送企業在城市路網中的優化調度，針對多個配送企業基于農村路網特點的統一調度研究較少。

車輛統一調度決策是一個考慮了重量、體積、訂單、路徑等約束情況，以利潤最大化為目標的調度優化問題。其實質是求解一個多約束的多背包問題，解空間維度相當高，在優化領域屬于NP-hard 的難題。當前，學者們多傾向于采用人工智能算法來解決該難題[8-12]，而改進遺傳算法是其中一個主流方法。Rezoug 等[13]通過采用基于效率的方法對問題數據進行預分析，獲得先驗知識來對后續遺傳操作進行引導，提出了啟發式的引導遺傳算法來求解多維背包問題，使遺傳算法具有較高的搜索效率。Manicassamy 等[14]通過抑制環境中的沖突基因來修復遺傳算法交叉變異過程中產生的非可行解，提高搜索效率，對于求解多目標背包問題有良好效果。標準遺傳算法處理多約束且解空間維度較高的優化問題時，會進化出大量非可行解的個體，嚴重影響尋優的效率。合理引導進化過程，并且及時對非可行解進行糾正是目前改進遺傳算法的重要措施。

因此，本文從我國農村電商發展的實際問題出發，在借鑒前人研究的基礎上，重點研究共同配送模式下的農村快遞車輛調度優化問題。構建考慮農村路網特性、統一決策的快遞車輛調度模型，并運用遺傳算法求解該問題，根據模型特點在原算法基礎上提出隨機修復非可行解策略以及多種群策略來提高算法的求解效率和效果。最后通過仿真實驗來驗證算法的一般適用性。

1 基于共同配送的農村快遞物流改進模式

當前農村快遞物流多在地區中心城市或人口規模較大的鄉鎮開設網點，并由單一物流企業獨立完成末端配送業務，即配送人員、車輛與客戶訂單等均隸屬于某個特定的物流公司，本文將該模式定義為獨立配送模式（如圖1所示）。在貨品抵達地區中心城市的倉庫后，農村地區的貨主需要委托當地鄉鎮運輸企業將其貨物托運回來。鄉鎮運輸企業是末端配送業務的實際服務方。在獨立配送模式下，物流公司的投入大、日常運營成本負擔重、對資金流管理的要求較高[15]，鄉鎮運輸企業往往經營困難，需要大量資金的扶持。

圖1 農村物流獨立配送模式

因此，對于當前農村物流業務量少、客戶點分布密度特別小的現狀，本文綜合考慮適用于超低密度配送區域的三級、四級共同配送模式的運行方式[16]，提出以整合同一區域鄉鎮運輸企業資源為核心策略的農村物流共同配送模式，如圖2所示。

圖2 農村物流共同配送模式

農村物流共同配送模式與傳統獨立配送模式的區別在于：

（1）運輸資源的集中調度。對各鎮運輸資源和力量進行整合，聯合各鄉鎮運輸企業共同成立第三方物流公司，以加強各鎮訂單資源需求信息的共享，形成集中調度的決策機構。原各鄉鎮的運輸企業分別負責不同線路的配送任務。新成立的第三方物流公司統一接受流通渠道上游物流企業的委托，管理并運營各線路鄉鎮級快遞配送業務。

（2）網點資源的整合。在地區中心城市或鄉鎮建立一個農村物流共同配送中心，使其成為各鄉鎮運輸企業存放農村貨物的倉庫，形成統一的倉儲基地與共有的網點資源。

2 農村快遞車輛調度模型構建

2.1 問題描述

基于共同配送模式，第三方物流公司負責某一農村區域的配送工作。公司目前有有限的n輛車與眾多件貨物，貨物數量遠大于車的容納量，特定目的地的貨物只可以由其目的鎮以及附近鎮的車輛裝載，在成本與運力約束的情況下，公司需根據當天所有貨物訂單的運輸價格與成本，合理規劃車輛配送方案，使運輸的物品價值最大，即當天配送獲得的總利潤最高。

2.2 條件假設

為便于建模，提出如下假設：

（1）假設各物流快遞件兼容性良好，可混裝，不考慮任意兩種貨品無法放置于同一車輛的特殊情況；

（2）假設各物流快遞件均為規則的長方體，車輛有效容積等于車輛載貨體積；

（3）不考慮貨物在車內擺放情況，包括裝車順序、堆碼的層次與方式等；

（4）每單貨物的重量不超過運輸車輛的額定載重，貨物的體積不超過運輸車輛的有效容積。

2.3 車輛調度模型構建

優化模型的目標為當日配送利潤最大，該利潤與運輸訂單的總收入正相關，與發車成本負相關，具體如式（1）所示：

同時該模型受如下約束：

式（1）～式（6）中：xijz為1，表示運往j地的第i單貨物采用z車運輸，若運往j地的第i單貨物不采用z車運輸，則xijz為0；pij為運往j地的第i單貨物的利潤；Bz為1，表示當天啟用z車，若不啟用，則Bz為0；Cz為z車每趟的運輸成本；wij為運往j地的第i單貨物重量；Wz為z車的額定載重；vij為運往j地的第i單貨物體積；Vz為z車的有效載貨容積；I為鄉鎮企業每日接收訂單數的上限；J為鄉鎮總數；n為車輛總數；Rz為z車的不可配送集合，集合中的元素j表示j地的貨物無法用z車運輸，M為無窮大。

式（2）～式（3）分別為重量與體積約束，即每輛車所裝貨物的總重量不能超過該車的額定載重，總體積不能超過該車的有效容積。式（4）為訂單約束，即同一訂單的貨物只能指派其中一輛車運輸，同時存在當日訂單不被配送的情況。式（5）為發車約束，若當天決策不啟用z車進行運輸作業，則z車無法配送任何貨物。式（6）為路徑約束，表示不在z車最短往返路徑途中的鄉鎮的貨物無法由z車順路捎帶運輸。

3 算法設計

3.1 基于隨機修復策略的混合遺傳算法

上文描述的模型是一個多背包決策模型，其決策變量的數目會隨貨物數量增長而增加，已被證明是NP-hard 問題。傳統的方法并不適用于解決解空間維度較高的大規模優化問題。而仿生智能算法中的遺傳算法可用于求解這類有約束最優化問題的近似解，其在近幾年被廣泛運用于求解訂單分配及調度問題。遺傳算法具有較強的全局搜索能力，在解空間維度較高的優化問題時有著良好的求解效果及穩定性。但是遺傳算法的局部搜索能力較弱，容易得到次優解以及部分違反約束的非可行解。為了提高求解的效率和效果，對于解空間維度較高的問題應盡可能使算法在可行域內尋優。因此，本文在標準遺傳算法的基礎上提出隨機修復策略來糾正遺傳過程中產生的非可行解，用于本研究的模型求解，其關鍵算法步驟描述如下。

3.1.1 編碼方式與初始種群生成

在遺傳算法中，不同的編碼方式決定決策變量在染色體基因上不同的映射情況，進而影響算法的執行效率。由于本文的決策變量均為0-1 變量，因此采取二進制編碼方式最為契合。種群的初始化是隨機地為每個個體的基因賦值0或1。

3.1.2 適應度函數與適應度值的分配

本文將模型的目標函數定義為適應度函數，如下式所示：

同時，基于排序來為個體確定適應度的分配值。其方法是按適應度函數值對個體進行排序，然后按線性排序的方法計算個體的選擇概率。

3.1.3 選擇交叉變異操作

本文采取輪盤賭的選擇機制，并對選擇出的個體進行單點交叉以及反轉位值的變異操作。

3.1.4 非可行解的修復

在每次交叉遺傳變異后，必須對新種群中的非可行個體進行糾正，以保證算法在可行域內尋優。對于多背包問題，若采用某種貪心規則來糾正非可行解，雖可加快算法收斂速度，但是在多約束條件下，這樣的處理容易導致種群后代產生偏向，減少種群多樣性，使算法陷入局部最優解，產生早熟現象。因此，本文采取隨機修復策略來糾正非可行解，具體的修復步驟如下。

步驟1：對種群中的每個個體進行約束檢驗，若檢驗到某個個體違反了約束j，找出與該約束相關的那段基因序列vj[i]，即找出造成違反約束的關聯決策變量。

步驟2：以滿足約束條件的方向作為序列改進的方向s[i]，以α作為改進的步長，對vj[i]進行糾正：

其中，改進步長α的取值為1。當個體違反某個約束時，將會隨機地把該約束對應的基因序列上的其中一個位置為1 的基因改為0（如圖3所示）。

圖3 非可行解修復示意圖

步驟3：重新判斷改進后的個體是否滿足約束j，若滿足，則修復結束，進入下一個約束檢驗；否則返回步驟2。

3.1.5 算法中止規則

本文結合最優個體中的記錄，采用最優個體最少保持代數作為中止依據。若最優個體連續10代保持不變，則算法中止。

3.2 多種群機制的補充

對非可行解進行修復的遺傳算法比較容易陷入局部最優解，采用隨機修復策略能一定程度上減少偏向性的副作用，但無法完全消除，同時會在一定程度上影響算法本身的求解效率。因此，本文在上述算法的基礎上引入多種群機制，利用其優秀的全局搜索能力以及協同進化的思想進一步優化求解算法。具體的設計如下：

（1）增加種群個數

突破單種群進行遺傳設計的框架，引入多個種群同時進行優化搜索。

（2）引入移民機制

各種群的遺傳操作是獨立進行的，但彼此之間可以通過移民機制來聯系。本文采用閉環串行式移民機制，即從第一個種群開始，不斷地用前一個種群的最優個體替換當前種群中的最差個體，直到所有種群都引入完畢為止。

（3）設置精華種群

在進化的每一代，都會把各種群的歷史最優個體選入精華種群加以存儲。為確保進化過程中，各種群的最優個體不會被丟失或遺忘，不對精華種群進行選擇、交叉、變異等遺傳操作。

3.3 算法流程

算法流程如圖4所示。

圖4 算法流程圖

4 算例驗證與結果分析

本文選取湖北省天門市中西部的農村地區作為分析對象，結合實踐調研所獲得的樣本數據進行算例驗證，通過與獨立配送模式的調度方案對比，評價基于共同配送的農村快遞車輛調度模型的有效性。同時設計多組不同訂單規模的仿真算例，分別使用標準遺傳算法以及本文提出的改進遺傳算法進行求解，對比算法的求解性能。

4.1 算例描述

已知Z 物流快遞公司的集散倉庫位于天門市城區的某個物流園中。其在西線的末端配送業務主要覆蓋黃潭、漁薪、汪場、蔣場、拖市、多寶、張港等7 個天門市的下屬鎮。鎮與鎮之間的路網通達，目前分布有S106,S49,S214 等3 條省道，以及X105,X009等多條縣道，如圖5所示。

圖5 天門市七鎮路網示意圖

該物流快遞公司尚無力建立末端配送體系，因此采取與各鄉鎮運輸企業合作的方式。各鄉鎮運輸企業的貨車司機只負責所屬鄉鎮的配送業務，在自身利潤最大化的目標導向下，自行選擇所要運輸的貨物。各鄉鎮運輸企業的配送車輛以中小型貨車為主，如表1 所示。其中，車輛取送快遞的固定成本是15 元/次，另根據不同的車型，再收取1～2.5 元/km 左右的燃油費。由此計算得出各鄉鎮運輸企業的貨車每次的出車成本，如表2所示。該地區的快遞訂單以多品種、小件、小批量類型為主，外觀是規整的長方形箱體。每個訂單的運費取決于貨物的體積、重量、數量以及運輸距離，單件運價在1.5～50 元之間。調研搜集了30位客戶訂單數據，部分數據如表3所示。

表1 車輛參數

表2 出車成本

表3 訂單數據

4.2 模型分析

根據調研情況和相關數據，運用基于共同配送模式的農村快遞車輛調度模型進行車輛與貨物的匹配，得到實現當天配送工作利潤最大化的共同配送方案。

在共同配送方案中，啟用了汪場、拖市、多寶、張港四鎮的貨車運輸貨物。沒有發車的鄉鎮，如漁薪鎮的部分貨物交由拖市、多寶、張港鎮的貨車運輸，黃潭鎮的貨物交由汪場和多寶鎮的貨車運輸；而張港鎮的貨車除了運輸本鎮及漁薪鎮的貨物以外，還會運輸蔣場的部分貨物。最終所獲得的收入為2 274.5元，總成本為221.6元，凈利潤為2 052.9元。

基于同樣的訂單數據，各鄉鎮運輸企業獨立決策安排車輛進行配送，即只要當天該鎮的貨物運輸所能獲得的收入大于發車成本便安排車輛配送。獨立配送方案啟用了所有貨車進行運輸，最終收入為1 919.5 元，總成本為317.9 元，凈利潤為1 601.6元。

如表4所示，通過兩個方案的對比可以發現，基于共同配送模式的農村快遞車輛調度模型所得到的優化方案的利潤比各鄉鎮運輸企業分散決策的配送方案提高了25%。另外，前者在減少了出車數量、總配送成本降低了約30%的同時，高效地配送了更多的貨物，提高了服務水平。

表4 配送模式對比結果

4.3 算法性能分析

為了更好地展示算法性能的改進程度，本文基于調研訂單數據，采用隨機模擬的方式生成訂單數量分別為25,50,75,100的多組仿真算例。算例訂單隨機生成的過程為：（1）在調研樣本數據中隨機抽取一位客戶i；（2）在客戶i送貨需求量di的區間[di-10,di+10]內隨機產生該客戶的訂單需求量；（3）隨機為該客戶分配一個送貨目的地，由此得到一個新的訂單數據。重復步驟（1）～步驟（3），直到滿足算例規模要求的訂單數量。

對于每個仿真算例，分別使用基于罰函數法處理約束的標準遺傳算法以及本文提出的多種群隨機修復遺傳算法進行求解，在MATLAB R2013a環境下進行10 次同樣條件下的運行實驗。其中，基本參數設置為：迭代次數為2 000，最優個體最少保持代數為10，雜交率為0.9，變異率為0.005，代溝為0.9。基于罰函數法的遺傳算法種群個數為1，群內個體數目為40。引入多種群機制的遺傳算法種群個數為15，群內個體數為40。

實驗結果如表5 所示，展示了10 次求解中的最優解、最差解、平均解以及算法的平均計算時間。“—”表示數據缺失，原因是在10 次運行中均無法找到可行解。

表5 算法對比實驗結果

由表5 可知，基于罰函數法來處理約束，隨著訂單數量的提高，遺傳算法的求解結果變得越來越不理想。在客戶訂單數達到100 時，已經無法找出不違反模型約束的可行解。而基于隨機修復策略的多種群遺傳算法在各個算例中的平均求解結果均優于標準遺傳算法，并且其求解的時間遠少于標準遺傳算法，求解的效率較高。隨著訂單數量的增大，基于隨機修復策略的多種群遺傳算法的求解性能依舊保持在較高的水平，求解的穩定性與時間均在可接受范圍內。

5 結語

農村電商物流是農村互聯網購物、電商農產品進城的關鍵所在。為降低農村物流成本，本文綜合分析了農村快遞配送的特性，引入共同配送模式，構建以車輛運營總利潤最大化為目標的農村快遞車輛調度模型。鑒于農村快遞車輛調度模型的求解是一個多約束的多背包問題，本文在標準遺傳算法的基礎上，提出采用隨機修復策略來處理約束的混合遺傳算法求解該模型，減少了糾正非可行解過程中偏向性的影響。并且，為了提高算法的求解效率，引入多種群機制對該算法作進一步改進。最后，通過某農村地區物流企業實際算例，驗證了共同配送模式下農村快遞車輛調度模型良好的資源配置性能，與獨立配送模式相比，該模式可以有效地降低配送成本和減少發車數量；并通過設計仿真實驗證明了基于隨機修復策略的多種群遺傳算法具有更好的最優解搜索能力與更快的求解速度。

由于農村共同配送體系涉及快遞公司、鄉鎮運輸企業等多個參與主體，因此如何平衡多方的利益訴求，同時兼顧公平和效益，將是維持物流聯盟穩定和加強合作關系的重點。而本文的模型更專注于效益和成本問題的優化，對于效益的分配以及合作的博弈考慮不足，在未來的研究中還可以繼續對模型進行優化完善。