基于兩種隨機(jī)規(guī)劃方法的取送車一體化路徑優(yōu)化

文/王建婷

引言

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

1.物流配送路徑優(yōu)化模型構(gòu)建

1.1 問題描述

本文研究的是一個(gè)企業(yè)派多輛車在多個(gè)服務(wù)點(diǎn)取送貨物過程中的路徑規(guī)劃問題。已知服務(wù)點(diǎn)的位置，服務(wù)點(diǎn)的送貨量和取貨量為不確定因素，其目標(biāo)是使得車輛取送貨物完成后的總成本最小。

1.2 基本假設(shè)和模型變量說明

1.2.1 假設(shè)條件

（1）假設(shè)車輛的起點(diǎn)和終點(diǎn)都為企業(yè)。（2）假設(shè)個(gè)服務(wù)點(diǎn)的取貨量和送貨量都不超過車輛的最大載重量。（3）假設(shè)每個(gè)服務(wù)點(diǎn)只能由一輛車服務(wù)，且不會(huì)出現(xiàn)服務(wù)不足。

1.2.2 模型變量說明

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

1.3 數(shù)學(xué)模型

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

2.物流配送路徑優(yōu)化的兩種隨機(jī)規(guī)劃模型

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

2.1 隨機(jī)機(jī)會(huì)約束規(guī)劃

本小節(jié)采用隨機(jī)機(jī)會(huì)約束規(guī)劃解決含有不確定因素的不確定模型。則可建立的隨機(jī)機(jī)會(huì)約束規(guī)劃模型為在上述模型的基

礎(chǔ)上對(duì)部分約束條件進(jìn)行如下修改：

2.2 隨機(jī)相關(guān)機(jī)會(huì)目標(biāo)規(guī)劃

本小節(jié)采用隨機(jī)相關(guān)機(jī)會(huì)目標(biāo)規(guī)劃解決含不確定因素的不確定模型。則建立的隨機(jī)相關(guān)機(jī)會(huì)目標(biāo)規(guī)劃模型為上述模型的基礎(chǔ)上對(duì)目標(biāo)函數(shù)和部分約束條件如下修改：

3.算法設(shè)計(jì)

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

隨著國(guó)家中長(zhǎng)期鐵路網(wǎng)規(guī)劃中四縱四橫鐵路快速客運(yùn)通道逐步建設(shè)完成，客運(yùn)專線已成為主要城市之間的重要運(yùn)輸通道。同時(shí)隨著經(jīng)濟(jì)和城市建設(shè)的發(fā)展，各地主要城市均在大規(guī)模修建地鐵，不可避免鐵路客運(yùn)專線與城軌交通交叉的工程實(shí)例漸多。

Step1：用神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)送貨和取貨量，采用0，1，2，…n的自然數(shù)進(jìn)行編碼，配送中心用0表示，客戶點(diǎn)的編號(hào)用其它整數(shù)表示；

Step2：初始化PS個(gè)染色體，并檢驗(yàn)染色體是否滿足約束條件；

Step3：利用訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)計(jì)算所有配送方案的總成本；

Step4：根據(jù)適應(yīng)度函數(shù)fi=1000/zii=1，2，…ps，計(jì)算每個(gè)染色體的適應(yīng)度；

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

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

Step8：最終找到最優(yōu)解。

4.計(jì)算舉例和結(jié)果分析

4.1 算例描述

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

表1：車型參數(shù)信息

4.2 運(yùn)算結(jié)果分析

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

圖2：目標(biāo)值收斂趨勢(shì)圖

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

5.結(jié)論

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

引用出處

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

[2]李鈺峰李攀郭盼雨.不確定需求下生鮮農(nóng)產(chǎn)品物流配送路徑優(yōu)化研究[J].科學(xué)技術(shù)創(chuàng)新.2021.27:177-179.

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

[4]方伯芃，孫林夫.不確定環(huán)境下的產(chǎn)業(yè)鏈生產(chǎn)與配送協(xié)同調(diào)度優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng).2018.24(1):225-245.

[5]朱澤國(guó),廣曉平,郭敏.不確定環(huán)境下的多車型物流配送路徑優(yōu)化[J].交通科技與經(jīng)濟(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]馬春玲.高鐵快遞物流末端取送系統(tǒng)優(yōu)化研究[D].西安建筑科技大學(xué).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.