基于遺傳算法的某物流公司配送路徑優(yōu)化設(shè)計

方俊豪 李俊玲

沈陽城市建設(shè)學(xué)院 遼寧 沈陽 110167

1 引言

本文主要研究某物流公司的物流配送情況，以該公司在金華的物流中轉(zhuǎn)站為配送中心，向金華七十多個工業(yè)區(qū)運(yùn)輸貨物的配送路徑為優(yōu)化對象，依據(jù)實(shí)際情況構(gòu)建數(shù)學(xué)模型，通過遺傳算法進(jìn)行求解，最終得出結(jié)論以解決該物流公司在工業(yè)區(qū)的物流配送過程中存在的問題，同時可以對該公司的其他運(yùn)輸業(yè)務(wù)進(jìn)行參考與借鑒，降低配送成本同時提高運(yùn)輸效率。而且，科學(xué)合理的路徑優(yōu)化，節(jié)約了運(yùn)輸路程，也減少了運(yùn)輸車輛的數(shù)量，能夠緩解城市中交通擁堵的情況，為城市道路降低碳排放量，減少噪音污染，發(fā)揚(yáng)低碳環(huán)保的理念，提高社會效益。

2 構(gòu)建數(shù)學(xué)模型

本文所建立模型的目標(biāo)函數(shù)Z為物流總成本，主要由固定成本Z1、運(yùn)輸成本Z2、和懲罰成本Z3三個要素構(gòu)成。其中懲罰成本主要由時間窗控制，每個客戶點(diǎn)都會設(shè)置固定的時間窗，要求配送中心在客戶所能接受的時間窗要求內(nèi)完成送貨，若違背了時間窗，則會產(chǎn)生一定的懲罰成本。

本設(shè)計所需的物流配送相關(guān)參數(shù)定義如下：Z表示目標(biāo)函數(shù)，N表示需要服務(wù)的配送點(diǎn)數(shù)量，K表示配送所需的車輛數(shù)，Qm表示車輛的額定載貨量，qi表示配送點(diǎn)i的需求量，tki表示車輛k到達(dá)配送點(diǎn)i的時間，k表示配送車輛的集合，其中k∈{1, 2，…， K}，dij表示配送點(diǎn)i到配送點(diǎn)j的間距，其中i,j∈｛1，2，…，33｝，Yki表示車輛的配送情況，若Yki=1，則代表車輛k對配送點(diǎn)i進(jìn)行配送，若Yki=0，則代表未配送。

物流公司的配送任務(wù)具有時效性、安全性以及可靠性，根據(jù)上述問題的描述，基于實(shí)際情況，構(gòu)建以運(yùn)輸成本最低為目標(biāo)的路徑優(yōu)化模型，本設(shè)計有以下約束條件：

（1）載貨量約束：運(yùn)輸車輛的車型和最大載貨量均一致，每條線路上的配送點(diǎn)所有貨物需求量的總和不能超過車輛的最大載重量。公式1表示車輛不超載。

（2）時間窗約束：物流公司最看重的就是配送時間，在規(guī)定的時間內(nèi)將貨物送至每一位客戶的手中是最基本的要求。若違背了時間窗，那么就會導(dǎo)致客戶拒收貨物，甚至下次不與公司合作等情況出現(xiàn)，從而產(chǎn)生相應(yīng)的懲罰成本。公式2表示時間窗的約束。

（3）配送點(diǎn)約束：每個配送點(diǎn)只能由一輛車進(jìn)行配送且只能配送一次，同時每個配送點(diǎn)的需求均能夠被滿足。由式公式3、公式4所示。

（4）運(yùn)輸車輛行為約束：在服務(wù)完每一個配送點(diǎn)之后，運(yùn)輸車輛立即離開，且在完成配送后立即返回配送中心。

3 算法實(shí)例

由于大部分地區(qū)的工業(yè)區(qū)均比較集中，例如婺城區(qū)、武義縣、永康市的工業(yè)區(qū)十分密集。于是考慮到實(shí)際因素和出于計算的需求，現(xiàn)將部分偏遠(yuǎn)或者配送量少的工業(yè)區(qū)數(shù)據(jù)信息進(jìn)行模糊處理，不納入計算。而在工業(yè)區(qū)密集處，則以某個工業(yè)區(qū)為中心進(jìn)行整合，并將整合后的“新工業(yè)區(qū)”進(jìn)行編號，查出所在地的經(jīng)緯度坐標(biāo)，同時把被整合的工業(yè)區(qū)的需求量進(jìn)行加和。經(jīng)分析后，考慮到多方面因素，最終將71個工業(yè)區(qū)整合為33個工業(yè)區(qū)集合體。

3.1 配送線路現(xiàn)狀

該公司出于實(shí)際配送因素的考慮，工業(yè)區(qū)的物流運(yùn)輸都是跨行政區(qū)的運(yùn)輸，所以公司的貨運(yùn)師傅基本上都會選擇分區(qū)域配送，以不同的行政區(qū)為配送對象，每個行政區(qū)出一趟車，進(jìn)行貨物配送。所以每個行政區(qū)一條或者兩條線路，運(yùn)輸成本也需要各個區(qū)域分別進(jìn)行計算。

配送成本Z包括運(yùn)輸固定成本、運(yùn)輸成本以及懲罰成本。運(yùn)輸固定成本是包含駕駛員的工資、運(yùn)輸車的購買或折舊費(fèi)用；運(yùn)輸成本包含燃料費(fèi)用、車輛維護(hù)費(fèi)等，一般計算中車輛的運(yùn)輸成本與形式距離成正比；懲罰成本則針對物流運(yùn)輸?shù)臅r效性要求，對于該物流公司來說，若是運(yùn)輸時間嚴(yán)重超出預(yù)計時間，那么則會降低客戶滿意度，有可能會放棄與公司合作，于是將懲罰成本設(shè)為配送點(diǎn)最大需求量所需收取的配送費(fèi)。

本設(shè)計中每輛車每天運(yùn)輸成本折合500元/輛·天；油價采取金華市柴油近日均價8.4元/升；百公里油耗30升；配送車車輛為17.5m長大貨車，額定載重45噸，可載貨32噸。每輛車在裝車完畢后應(yīng)在10個小時內(nèi)送至工業(yè)區(qū)，貨車在運(yùn)輸時往往走國道或者高速，故時速約60km/h，到貨后卸車時間約為5min/噸。計算后最終各區(qū)的配送線路以及運(yùn)輸成本如下：

路線1（蘭溪市）：0-1-2-3-4-5-0，配送里程198km，配送成本998.96元；

路線2（婺城區(qū)）：0-6-7-8-0，配送里程97km，配送成本744.44元；

路線3（婺城區(qū)）：0-9-0，配送里程30km，配送成本575.6元；

路線4：（金東區(qū)）：0-10-11-12-0，配送里程54km，配送成本636.08；

路線5：（武義縣）：0-13-14-15-16-0，配送里程139km，配送成本850.28元

路線6：（永康市）：0-17-19-20-0，配送里程129km，配送成本825.08元；

路線7：（永康市）：0-18-21-22-0，配送里程146km，配送成本867.92元；

路線8：（東陽市）：0-23-24-25-0，配送里程183km，配送成本961.16元；

路線9：（義烏市）：0-26-27-28-29-0，配送里程151km，配送成本880.52元；

路線10：（義烏市）：0-30-31-0，配送里程81km，配送成本704.12元；

路線11：（浦江縣）：0-32-33-0，配送里程160km，配送成本903.2元。

通過計算，此公司在金華的運(yùn)轉(zhuǎn)中心每天為各工業(yè)區(qū)配送的路線共有11條，需要11輛運(yùn)輸車輛，總計配送里程1368km，配送成本共計8947.36元。

3.2 程序有關(guān)數(shù)據(jù)設(shè)定

（1）配送點(diǎn)數(shù)量、需求量以及運(yùn)輸車輛最大載重量的設(shè)定

結(jié)合上文的相關(guān)數(shù)據(jù)說明，現(xiàn)對以下參數(shù)進(jìn)行賦值。首先，配送點(diǎn)總數(shù)N為34，包括33個門店以及配送起點(diǎn)0，配送車輛最大載重Qm為32噸，各配送點(diǎn)需求量qi在上文已有詳細(xì)介紹。

（2）各配送點(diǎn)間距離dij的設(shè)定

結(jié)合上文可計算出各個配送點(diǎn)之間的距離dij，計算公式如公式5所示。

（3）計算兩點(diǎn)間距離，形成二維距離矩陣

在完成數(shù)據(jù)初始化的編碼之后，還需要計算各個配送點(diǎn)之間的距離。在算例數(shù)據(jù)中只有各配送點(diǎn)的經(jīng)緯度坐標(biāo)，需要編寫一個計算距離的代碼，將任意兩個配送點(diǎn)之間的間距計算出來，并形成二維距離矩陣。由于配送點(diǎn)很多，各點(diǎn)間距共有561個數(shù)據(jù)，若是人工計算則需要耗費(fèi)大量的時間，并且容易出現(xiàn)計算錯誤，影響最終結(jié)果。但是通過編程即可又快又準(zhǔn)確的獲得各點(diǎn)之間的二維距離矩陣。編碼完成且運(yùn)行后可以獲得一個34*34規(guī)模的距離矩陣。具體編碼如下：

%根據(jù)配送點(diǎn)的經(jīng)緯度坐標(biāo)，求各點(diǎn)之間的距離矩陣

（4）遺傳算法相關(guān)參數(shù)設(shè)定

本文的遺傳算法的相關(guān)參數(shù)表示：初始種群數(shù)量為66，交叉的概率為0.7，變異的概率為0.4，迭代次數(shù)為500。

3.3 算法最終結(jié)果

在通過20次的程序迭代運(yùn)算之后，得到最優(yōu)配送路徑。優(yōu)化后得到的配送路徑共9條，結(jié)果如圖1所示。

圖1 優(yōu)化路徑圖

3.4 優(yōu)化后成本計算

優(yōu)化后得到的最優(yōu)路徑里程為1284.5304km。已知單位距離的運(yùn)輸成本為2.52元/km，故可算得運(yùn)輸成本為3237.016608元，保留兩位小數(shù)后結(jié)果為3237.02元。通過圖1可知，共有9條配送路線，故運(yùn)輸車輛為9輛，可算得運(yùn)輸固定成本為4500元。所以，優(yōu)化后的配送總成本為7737.02元。

出于研究的嚴(yán)謹(jǐn)性，本文將最優(yōu)結(jié)果進(jìn)行驗(yàn)算。由于是人工驗(yàn)算，數(shù)據(jù)均經(jīng)過處理，運(yùn)輸里程為實(shí)際距離保留整數(shù)后的結(jié)果，故運(yùn)算結(jié)果會存在一定誤差，不過此計算結(jié)果僅供驗(yàn)算使用，不必過于準(zhǔn)確。

綜上所述，本設(shè)計建立的遺傳算法模型可行有效，編寫的程序運(yùn)行無誤，可實(shí)現(xiàn)該公司對金華工業(yè)區(qū)貨物配送方案的設(shè)計優(yōu)化，節(jié)約運(yùn)輸里程和配送時間，降低配送成本，完成路徑優(yōu)化。

表1 優(yōu)化后成本計算（驗(yàn)算）

3.5 優(yōu)化前后方案對比

經(jīng)過遺傳算法的建模優(yōu)化，優(yōu)化后方案的配送線路由11條減少至為9條，所以配送車輛數(shù)也由原來的11輛降為9輛。此時的固定運(yùn)輸成本由原先的5500元將為4500元，降低1000元。

同時由于配送的改進(jìn)，使得車輛運(yùn)輸里程數(shù)由原先的1368km優(yōu)化為1284km，節(jié)約了運(yùn)輸里程84km，降低運(yùn)輸成本211.68元。與原運(yùn)輸方案相比，優(yōu)化后配送方案的配送總成本約降低1200元，降幅大概在13.4%，優(yōu)化效果顯著。

首先，優(yōu)化后的方案破除了原配送方案中需要按行政區(qū)進(jìn)行配送的要求，使運(yùn)輸線路上的配送點(diǎn)有更多的選擇，可以有效緩解運(yùn)輸路線重復(fù)和浪費(fèi)的問題。本研究以節(jié)約里程為目標(biāo)，將運(yùn)輸路徑優(yōu)化問題建立為基于遺傳算法的數(shù)學(xué)模型，以金華工業(yè)區(qū)為研究對象，將各配送點(diǎn)的經(jīng)緯度坐標(biāo)、需求量以及其它相關(guān)運(yùn)輸數(shù)據(jù)設(shè)為參數(shù)，再通過MATLAB軟件進(jìn)行編碼，得出在固定約束條件下解決問題的最優(yōu)解。經(jīng)過優(yōu)化后得到的配送方案節(jié)約了較多的配送成本和運(yùn)輸資源，不論是對于公司往后的發(fā)展還是對于社會的綠色環(huán)保都起到了一定的貢獻(xiàn)。

4 總結(jié)

本文對某物流公司的工業(yè)區(qū)貨物配送問題進(jìn)行研究，通過分析原配送方案，得出原方案存在配送路徑方面的不足。再依據(jù)金華工業(yè)區(qū)的配送特點(diǎn)，結(jié)合相關(guān)數(shù)據(jù)，對原有的金華工業(yè)區(qū)配送路徑進(jìn)行優(yōu)化，通過遺傳算法進(jìn)行科學(xué)合理的建模，并借助MATLAB軟件進(jìn)行編碼求解，最終在遵循配送條件的情況下，得出一個優(yōu)化配送方案。該方案與初始方案相比，在運(yùn)輸里程、運(yùn)輸車輛數(shù)、配送成本等方面均有優(yōu)化，節(jié)約了里程，減少了成本，優(yōu)化結(jié)果正確有效。