基于兩種隨機規劃方法的取送車一體化路徑優化

文/王建婷

引言

物流配送在我們生活中起著重要作用，已經成為貨物運輸中必不可少的一個環節。配送路徑的優劣程度直接關系到物流公司、客戶和社會環境的利益。所以，求解最優的配送路徑是至關重要的。取送貨一體化可以提高車輛利用率，解決空載問題，廣泛地應用于實際生活中[1]。目前，已經有許多的國內外學者研究了考慮不確定因素的物流配送的路徑規劃。孫華麗和李鈺峰等考慮了需求的不確定，分別以建立了多物資應急物流定位-路徑模型和生鮮農產品物流配送路徑規劃模型[2，3]。方伯芃等考慮了不確定性因素，建立了不確定規劃模型，并使用混合遺傳算法對其進行了求解[4]。朱澤國以路段通行時間為不確定因素，建立了多車型物流配送路徑規劃模型[5]。DaratDechampai和EshetieBerhan等用差分進化法解決了具有取送車一體化的車輛路徑優化問題[6，7]。EdwarLujanSegura等使用定位-路線禁忌搜索法解決了取送一體化的物流配送問題[8]。馬春玲建立以總成本最小為目標的高鐵末端取送路徑優化模型[9]。AgustínMontero等用ILP方法解決了取送車一體化的物流配送車輛路徑問題[10]。在以往的研究中，缺少用兩種隨機規劃方法對取送車一體化配送問題進行建模。本文將用隨機機會約束規劃和隨機相關機會規劃對物流配送路徑優化問題進行建模，并設計一定的混合遺傳算法解決該模型的實際問題。

1.物流配送路徑優化模型構建

1.1 問題描述

本文研究的是一個企業派多輛車在多個服務點取送貨物過程中的路徑規劃問題。已知服務點的位置，服務點的送貨量和取貨量為不確定因素，其目標是使得車輛取送貨物完成后的總成本最小。

1.2 基本假設和模型變量說明

1.2.1 假設條件

（1）假設車輛的起點和終點都為企業。（2）假設個服務點的取貨量和送貨量都不超過車輛的最大載重量。（3）假設每個服務點只能由一輛車服務，且不會出現服務不足。

1.2.2 模型變量說明

N為客戶i的集合；K為從配送中心出發的車輛數；ck為車輛k的單位固定成本；dij為客戶i點與j點的距離；Vk為車輛的行車速度；Qk為車輛k的最大載重量；cfk為配送車輛單位距離運輸成本；qi和pi分別為客戶點的配送量和取貨量；[ei，li]為客戶i的時間窗；tik為車輛k到達客戶i點的時間；xijk為車輛k從客戶點i到j則為1，否則為0；yik車輛從訪問客戶點則為1，否則為0。

1.3 數學模型

目標函數是總成本最小，包括運輸、固定和時間懲罰成本；約束條件分別為：車輛的起終點都是配送中心、車輛流守恒約束、客戶點被服務次數約束、車輛服務路徑數約束、決策變量之間的關系，保證車輛在客戶點服務時有路徑連接、車輛的載重量限制約束、車輛在相鄰節點間的載重量的關系、車輛到達客戶點的時間。

2.物流配送路徑優化的兩種隨機規劃模型

實際生活中，往往有許多的不確定因素，本模型中考慮了客戶需求和取貨量的不確定性。并且不確定變量均服從正態分布。將以上兩個不確定因素加入到上節的模型中并解決。

2.1 隨機機會約束規劃

本小節采用隨機機會約束規劃解決含有不確定因素的不確定模型。則可建立的隨機機會約束規劃模型為在上述模型的基

礎上對部分約束條件進行如下修改：

2.2 隨機相關機會目標規劃

本小節采用隨機相關機會目標規劃解決含不確定因素的不確定模型。則建立的隨機相關機會目標規劃模型為上述模型的基礎上對目標函數和部分約束條件如下修改：

3.算法設計

根據建立的模型，本文在遺算法的基礎上引入隨機模擬求解建立的模型。具體步驟如下所示：

隨著國家中長期鐵路網規劃中四縱四橫鐵路快速客運通道逐步建設完成，客運專線已成為主要城市之間的重要運輸通道。同時隨著經濟和城市建設的發展，各地主要城市均在大規模修建地鐵，不可避免鐵路客運專線與城軌交通交叉的工程實例漸多。

Step1：用神經網絡預測送貨和取貨量，采用0，1，2，…n的自然數進行編碼，配送中心用0表示，客戶點的編號用其它整數表示；

Step2：初始化PS個染色體，并檢驗染色體是否滿足約束條件；

Step3：利用訓練好的神經網絡計算所有配送方案的總成本；

Step4：根據適應度函數fi=1000/zii=1，2，…ps，計算每個染色體的適應度；

Step5：通過輪盤賭法以一定的概率選擇較好的染色體；

Step6：設計交叉和變異算子，更新染色體。交叉操作為配送中心位置不變，將兩個父代染色體的客戶點基因位置交換，變異算子為將隨機選中位置的基因顛倒插入。

Step8：最終找到最優解。

4.計算舉例和結果分析

4.1 算例描述

本文以某商品配送公司開展的配送業務為例，有一個配送中心和15個配送點。假設該公司總共派5輛車進行本次運輸，具體的車型參數信息如表1所示。

表1：車型參數信息

4.2 運算結果分析

利用MicrosoftVisualC++對實例進行求解，并以迭代次數為100，種群數為30，交叉概率為0.8，變異概率為0.1，對問題進行仿真得到的曲線圖如圖2所示，在迭代前期，適應度上升較快，隨著迭代次數的增加，曲線逐漸趨于平穩，在迭代46次以后，適應度值穩定到一個固定值，進而得到最優解。

圖2：目標值收斂趨勢圖

通過混合遺傳算法對取送車一體化配送問題的求解，得到本次配送業務的總成本為1267.47元，其中運輸、固定和時間懲罰成本分別為473.767元、560元和233.7元。最優運輸線路0→6→12→11→0→7→8→10→0→2→15→5→0→1→4→0→14→9→3→13→0。例如車輛1表示從配送中心出發前往客戶點6再到客戶點12再到客戶點11，最后返回配送中心,其余車輛路徑的表示也與車輛1相同。

5.結論

通過兩種不確定規劃方法，研究了考慮不確定因素（取送貨量）的取送車一體化的車輛路徑優化問題，以配送總成本最小為目標建立了數學模型，并使用混合遺傳算法驗證算例，找到最優的配送路徑。在以后的研究中，可以考慮多個不確定因素的車輛路徑優化問題，找到更符合實際情況的車輛路徑。

引用出處

[1]孟鷺.考慮客戶需求重疊的取送貨一體化車輛路徑優化問題[D].大連海事大學.2017,6.

[2]李鈺峰李攀郭盼雨.不確定需求下生鮮農產品物流配送路徑優化研究[J].科學技術創新.2021.27:177-179.

[3]孫華麗，曹文倩，薛耀鋒，王循慶.考慮路徑風險的需求不確定應急物流定位-路徑問題[J].運籌與管理.2018.27（7）：0037-0042.

[4]方伯芃，孫林夫.不確定環境下的產業鏈生產與配送協同調度優化[J].計算機集成制造系統.2018.24(1):225-245.

[5]朱澤國,廣曉平,郭敏.不確定環境下的多車型物流配送路徑優化[J].交通科技與經濟.2021,23(2):6-12.

[6]Darat Dechampai,Ladda Tanwanichkul,Kanchana Sethanan,Rapeepan Pitakaso.Adifferentiale volution algorithm for the capacitatedVRPwithflexibility of mixing pickupanddeliveryservicesand the maximumdurationofarouteinpoultry in dustry[J].Intell Manuf.2017.28:1357-1376.

[7]Eshetie Berhan,Pavel Kr¨omer,Daniel Kitaw,Ajith Abraham,and-VaclavSn?aˇsel.Solving Stochastic Vehicle Routing Problemwith Real Simultaneous Pickupand Delivery Using Differential Evolution[J].Advancesin Intelligent Systemsand Computing237:187-200.

[8]Edwar Lujan Segura,JoséRodríguez Melquiades,Flabio Gutiérrez Segura.Tabu Searchfor Locating-Routingin the Goods Deliveryand Waste Pickupin Trujillo-Peru[J].exclusivelicenseto Springer Nature Switzerl and AG2021.295:51-69.

[9]馬春玲.高鐵快遞物流末端取送系統優化研究[D].西安建筑科技大學.2020,6.

[10]Agustín Montero, Juan JoséMiranda-Bront, Isabel Méndez-Díaz.AnILP-basedlocal search procedure for the VR Pwithpickupsand deliveries[J].Ann Oper Res.2017.259:327-350.