應(yīng)急物流配送路徑優(yōu)化研究

導(dǎo)語(yǔ)：應(yīng)急物流配送路徑優(yōu)化研究一文來(lái)源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢(xún)客服老師，歡迎參考。

摘要：文章對(duì)應(yīng)急物流配送路徑進(jìn)行分析的基礎(chǔ)上，構(gòu)建了帶時(shí)間窗的應(yīng)急物流配送路徑最短優(yōu)化模型，提出了遺傳優(yōu)化算法，最后以漳縣公路網(wǎng)絡(luò)為算例進(jìn)行分析，利用MATLAB軟件編程實(shí)現(xiàn)，算例結(jié)果表明，遺傳優(yōu)化算法更好地解決應(yīng)急物流配送問(wèn)題，驗(yàn)證了遺傳算法解決應(yīng)急物流配送路徑的可行性。

關(guān)鍵詞：時(shí)間窗；應(yīng)急物流；配送路徑；遺傳算法；甘肅省

自然災(zāi)害具有強(qiáng)大的破壞力，給人類(lèi)帶來(lái)了巨大的財(cái)產(chǎn)損失和人員傷亡，經(jīng)常造成自然環(huán)境破壞，在不同程度上造成重大的經(jīng)濟(jì)損失和人們心理恐慌，為降低災(zāi)害造成的損傷，在短期內(nèi)災(zāi)區(qū)急需大量的救援物資，應(yīng)急物流開(kāi)辟了為快速有效地開(kāi)展救援工作同時(shí)提供滿足受災(zāi)群眾生活和醫(yī)療物資的需求，而應(yīng)急物流具有突發(fā)性和緊迫性等特點(diǎn)，為了提高應(yīng)急物資配送的及時(shí)性和有效性，要對(duì)應(yīng)急物流車(chē)輛配送路徑做出科學(xué)的決策。然而，由于災(zāi)情的不確定性和難以預(yù)測(cè)性以及救援的緊迫性使得應(yīng)急管理部門(mén)很難準(zhǔn)確獲得受災(zāi)地區(qū)對(duì)應(yīng)急物資的需求量。同時(shí)，應(yīng)急車(chē)輛配送物資的過(guò)程中常常面臨路徑通行能力差、山體滑坡和道路塌陷損壞等風(fēng)險(xiǎn)，也影響應(yīng)急物資的精準(zhǔn)送達(dá)。如何以最短路徑、高滿意度、最低成本等為目標(biāo)在最短的時(shí)間內(nèi)完成突發(fā)事件下應(yīng)急物資的配送問(wèn)題，成為國(guó)內(nèi)外學(xué)者高度關(guān)注的問(wèn)題。李志等研究了以物資分配公平性和需求效用最大化為目標(biāo)，建立基于多目標(biāo)的混合整數(shù)規(guī)劃方法應(yīng)急物資供應(yīng)點(diǎn)定位-分配模型；楊恩緣，李進(jìn)等提出了以運(yùn)輸成本最小為目標(biāo)，結(jié)合容量限制及應(yīng)急配送的多樣性和多級(jí)性特點(diǎn)，構(gòu)建了應(yīng)急物資多級(jí)配送選址-路徑的混合整數(shù)規(guī)劃模型；陳湉，林勇提出基于離散蜂群的災(zāi)害應(yīng)急物流車(chē)輛調(diào)度優(yōu)化問(wèn)題研究，以供應(yīng)過(guò)量、物資分配不足所造成的損失最小化、車(chē)輛調(diào)度成本最低為優(yōu)化目標(biāo)，以服務(wù)時(shí)間窗和車(chē)輛運(yùn)載能力為約束條件，構(gòu)建了應(yīng)急需求下的車(chē)輛調(diào)度優(yōu)化模型，并采用離散蜂群算法求解；張偉，楊斌等以運(yùn)輸距離最短化、運(yùn)輸時(shí)間最小化和路徑復(fù)雜性為目標(biāo)，建立多目標(biāo)應(yīng)急物流路徑規(guī)劃模型；蔣杰輝，馬良利用改進(jìn)智能水滴算法求解應(yīng)急物資配送中車(chē)輛路徑優(yōu)化問(wèn)題；朱娜，鄭亞平采用“矢量投影－理想點(diǎn)法”以車(chē)輛運(yùn)載能力等為限制條件，以應(yīng)急運(yùn)輸成本、應(yīng)急時(shí)間及救災(zāi)點(diǎn)數(shù)量為優(yōu)化目標(biāo)構(gòu)建了應(yīng)急物資分配模型；朱佳翔等以運(yùn)輸時(shí)間最少、成本最優(yōu)以及用戶(hù)滿意度最大等為目標(biāo)，構(gòu)建多階段多目標(biāo)應(yīng)急物流配送的灰色動(dòng)態(tài)規(guī)劃模型。

一、問(wèn)題的描述

帶時(shí)間窗的車(chē)輛運(yùn)輸路徑問(wèn)題（VRPTW）是應(yīng)急物流研究的基本問(wèn)題，也是實(shí)現(xiàn)在有限時(shí)間內(nèi)實(shí)現(xiàn)物資的及時(shí)送達(dá)，提高救援效率，將災(zāi)害降到最小化的有效途徑。本文針對(duì)甘肅應(yīng)急物流運(yùn)輸與配送問(wèn)題，構(gòu)建了帶時(shí)間窗路徑最短為目標(biāo)的車(chē)輛配送模型，設(shè)計(jì)遺傳算法對(duì)應(yīng)急物流配送路徑模型求解，兼顧考慮多個(gè)制約條件，如車(chē)輛載重量的限制，受災(zāi)點(diǎn)對(duì)物資需求時(shí)間窗的限制等。假設(shè)有一個(gè)配送中心對(duì)多個(gè)受災(zāi)點(diǎn)進(jìn)行應(yīng)急物資配送，配送中心有容量不同的車(chē)輛，受災(zāi)點(diǎn)對(duì)物資需求的時(shí)間各不相同，要求在規(guī)定的時(shí)間內(nèi)完成配送任務(wù)，規(guī)劃配送路線并要求每條路線上只有一輛車(chē)配送，規(guī)定車(chē)輛從配送中心出發(fā)完成配送任務(wù)后再返回配送中心，使車(chē)輛配送車(chē)輛總運(yùn)達(dá)的路徑最短，利用MAT-LAB軟件編程求解，計(jì)算出應(yīng)急物流最短配送路徑最優(yōu)解。

二、構(gòu)建帶時(shí)間窗的應(yīng)急物流配送路徑模型

（一）模型參數(shù)與變量定義

N={0，1，…，n，n+1}是節(jié)點(diǎn)集合，0，n+1表示配送中心，需求點(diǎn)編號(hào)為{1，…，n}；di：需求點(diǎn)i的需求量；K={1，2，…，k}是車(chē)輛集合，為了降低配送成本盡可能合理使用配送車(chē)輛，采用下列公式確定車(chē)輛數(shù)：A：弧的集合；xijk={0，1}，表示車(chē)輛k是否從i點(diǎn)出發(fā)前往j點(diǎn)，如果車(chē)輛k是從i點(diǎn)出發(fā)前往j點(diǎn)，則xijk=1，否則xijk=0；Cij：表示i點(diǎn)和j點(diǎn)之間的距離；Wik：表示車(chē)輛k對(duì)i點(diǎn)的開(kāi)始服務(wù)時(shí)間；si：表示受災(zāi)點(diǎn)i的服務(wù)時(shí)間；tij：表示從i點(diǎn)到j(luò)點(diǎn)的行駛時(shí)間；Mij：一個(gè)足夠大的數(shù)，可以取10的7次方；ai：受災(zāi)點(diǎn)i的左時(shí)間窗；bi：受災(zāi)點(diǎn)i的右時(shí)間窗；E：配送中心的左時(shí)間窗；L：配送中心的右時(shí)間窗；Ck：車(chē)輛k最大裝載量；s+（i）：表示從i點(diǎn)出發(fā)的弧的集合；s-（i）：表示回到j(luò)點(diǎn)的弧的集合。

（二）模型設(shè)計(jì)

其中目標(biāo)函數(shù)（1）表示車(chē)輛最短應(yīng)急物流配送路徑；（2）~（10）是約束條件，（2）表示每個(gè)需求點(diǎn)只能被分配到一條配送路徑上；（3）表示每條配送線路上從配送中心出發(fā)只能前往一個(gè)需求點(diǎn)；（4）表示車(chē)輛k在路徑上的流量限制；（5）表示車(chē)輛配送完畢都必須返回配送中心；（6）表示配送時(shí)間連續(xù)性；（7）表示需求點(diǎn)時(shí)間窗約束；（8）表示配送中心時(shí)間窗約束；（9）表示載重量約束；（10）表示變量取值的約束。

三、基于遺傳算法（GA）的應(yīng)急物流配送路徑模型求解

（一）算法設(shè)計(jì)

1.編碼在使用GA求解VRPTW問(wèn)題時(shí)，可以采用整數(shù)編碼的形式對(duì)染色體進(jìn)行編碼，當(dāng)配送車(chē)輛數(shù)最多為K，且節(jié)點(diǎn)數(shù)目為N時(shí)，染色體長(zhǎng)度為N+K-1，那么表達(dá)該染色體的基本形式為（1，2，3，…，N，N+1，…，N+K-1）。2.遺傳適應(yīng)度函數(shù)當(dāng)編碼的解碼不能保證都滿足每條配送路線上對(duì)時(shí)間窗的約束和載重量的約束條件時(shí)，為了解決違反約束問(wèn)題，進(jìn)行求解時(shí)采用懲罰函數(shù)。構(gòu)建的懲罰函數(shù)如下：f（s）=c（s）+αq（s）+βw（s），c（s）表示車(chē)輛總行駛距離，q（s）表示各條路徑違反的容量約束之和，w（s）表示所有顧客違反的時(shí)間窗約束之和。因?yàn)檫`反容量約束相對(duì)來(lái)說(shuō)不太容易，所以將α設(shè)為10。而較容易違反時(shí)間窗約束，所以將β設(shè)為100。目標(biāo)函數(shù)值越小越優(yōu)越，因此在選擇環(huán)節(jié)，將懲罰函數(shù)的倒數(shù)設(shè)置為適應(yīng)度函數(shù)，即為1/f（s）。3.初始化種群先構(gòu)建帶時(shí)間窗車(chē)輛路徑問(wèn)題的初始解，再進(jìn)行初始化種群。設(shè)節(jié)點(diǎn)數(shù)目為m。第一步：任意選擇某一節(jié)點(diǎn)i∈{1，2，3，…，m}；第二步：使用車(chē)輛數(shù)的初始化k=1；第三步：遍歷節(jié)點(diǎn)生成序列Sq=[i，i+1，…，m，1，2，…，i-1]第四步：遍歷節(jié)點(diǎn)j至節(jié)點(diǎn)m，形成初始解。按序列Sq遍歷節(jié)點(diǎn)Sq（j），將節(jié)點(diǎn)Sq（j）添加到第q條路徑中，在添加到對(duì)應(yīng)線路中時(shí)要考慮車(chē)輛的載重量和左時(shí)間窗的約束條件。得到的初始解就是一個(gè)配送方案，通過(guò)將個(gè)體賦值的方式轉(zhuǎn)換為種群初始化。4.選擇從群體中選擇優(yōu)良個(gè)體來(lái)繁殖子代的過(guò)程，并進(jìn)行優(yōu)勝劣汰操作，通過(guò)基于適應(yīng)度的過(guò)程選擇個(gè)體解決方案，即從群體中選擇多個(gè)適應(yīng)度值大的個(gè)體進(jìn)行交叉、變異以及局部搜索過(guò)程。5.交叉交叉是指兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新的個(gè)體，然后從前到后把重復(fù)的基因位刪除，形成兩個(gè)子代個(gè)體。6.變異變異過(guò)程是將父代染色體先選擇兩個(gè)位置，將這兩個(gè)位置上的基因互換形成子代染色體。7.終止條件遺傳算法具有隨機(jī)搜索特性，需要設(shè)置終止條件以在可接受時(shí)間內(nèi)獲得最優(yōu)解。比如設(shè)置最大進(jìn)化次數(shù)為終止條件，或達(dá)到最大迭代數(shù)時(shí)終止算法運(yùn)算，再如判斷種群適應(yīng)度值的收斂性，種群適應(yīng)度值不被繼續(xù)優(yōu)化時(shí)終止算法運(yùn)算。

（二）遺傳算法的運(yùn)算流程

遺傳算法（GA）是借鑒生物界的進(jìn)化論，適者生存，優(yōu)勝劣汰的遺傳機(jī)制演化而來(lái)，是一種隨機(jī)化搜索全局尋優(yōu)的生物進(jìn)化過(guò)程算法，具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力，采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，使群體不斷進(jìn)化，逐漸接近最優(yōu)。GA是解決VRPTW問(wèn)題的有效方法之一，在求解應(yīng)急物流配送模型中得到了廣泛的應(yīng)用。其流程圖1所示。

四、算例分析

以漳縣公路網(wǎng)絡(luò)應(yīng)急物流配送為算例進(jìn)行分析，漳縣有13個(gè)鄉(xiāng)鎮(zhèn)，其分布狀況如圖1所示，假定武陽(yáng)鎮(zhèn)是配送中心，配送中心有5輛載重量為68t的汽車(chē)，各鄉(xiāng)鎮(zhèn)對(duì)物資的需求量由各鄉(xiāng)鎮(zhèn)的人數(shù)來(lái)確定，需求點(diǎn)相關(guān)信息見(jiàn)表1。本算例采用MATLAB軟件對(duì)設(shè)計(jì)的GA算法進(jìn)行編程實(shí)現(xiàn)，通過(guò)仿真運(yùn)算結(jié)果發(fā)現(xiàn)，在求解配送路徑優(yōu)化問(wèn)題時(shí)，帶時(shí)間窗的遺傳算法收斂速度快、程序運(yùn)行時(shí)間短、效率高，有效實(shí)現(xiàn)了時(shí)間約束條件下應(yīng)急物流配送路徑優(yōu)化，在應(yīng)急物資配送中調(diào)用了3輛汽車(chē)，具體的最優(yōu)配送方案如圖2所示，車(chē)輛行駛路徑及載重量如表2所示。通過(guò)求解軌跡結(jié)果可以得出基于時(shí)間窗的總行駛里程最短的路徑安排。

五、結(jié)語(yǔ)

本文針對(duì)配送中心如何向?yàn)?zāi)區(qū)配送應(yīng)急物資這一問(wèn)題，提出了一個(gè)基于時(shí)間窗的遺傳算法的應(yīng)急物流車(chē)輛配送路徑優(yōu)化方案，考慮應(yīng)急物流的時(shí)間約束性，構(gòu)建了以配送路徑最短為目標(biāo)，滿足多個(gè)約束條件下優(yōu)化問(wèn)題模型，結(jié)合模型特點(diǎn)使用遺傳算法進(jìn)行求解，找到目標(biāo)函數(shù)最小時(shí)對(duì)應(yīng)的應(yīng)急五流配送路徑。研究結(jié)果表明，遺傳算法能有效解決應(yīng)急物流配送路徑問(wèn)題。本文假定只考慮一個(gè)配送中心的情況下車(chē)輛配送路徑優(yōu)化，實(shí)際上，應(yīng)急物流錯(cuò)綜復(fù)雜，如應(yīng)急物資有帳篷、衣物、食品、藥品等性質(zhì)不同的物資，配送要求不同，再如多配送中心問(wèn)題研究、應(yīng)急道路狀況等，針對(duì)復(fù)雜情況下對(duì)應(yīng)急物資配送規(guī)劃是未來(lái)研究的重點(diǎn)難點(diǎn)。

作者：尹耀杰 馬麗榮