數(shù)學(xué)建模優(yōu)化物流運(yùn)輸路徑可行解的改進(jìn)算法及應(yīng)用

文/梁建梭 唐慧羽 王錄通

0.引言

基于遺傳算法的物流運(yùn)輸可行解改進(jìn)方法，主要是利用結(jié)合節(jié)約歷程法與遺傳算法的優(yōu)勢(shì)，建立一個(gè)路徑優(yōu)化模型，并從里程、成本等方面，確定優(yōu)化模型的可行性[1]。基于雙向搜索的物流運(yùn)輸可行解改進(jìn)算法，主要是建立自適應(yīng)尋優(yōu)網(wǎng)格分布模型，根據(jù)網(wǎng)格規(guī)劃特征進(jìn)行雙向搜索，找出最短運(yùn)輸路徑[2]。以上兩種方法均能夠進(jìn)行物流運(yùn)輸路徑尋優(yōu)，通過(guò)空間位置參數(shù)定位，提升物流運(yùn)輸效率[3]。但是，效率提升相應(yīng)地增加了經(jīng)濟(jì)成本，無(wú)法滿足運(yùn)輸需求。因此，本文結(jié)合數(shù)學(xué)建模的優(yōu)勢(shì)，設(shè)計(jì)了物流運(yùn)輸路徑可行解的改進(jìn)算法。

1.基于數(shù)學(xué)建模的物流運(yùn)輸路徑可行解改進(jìn)算法設(shè)計(jì)

1.1 提取物流運(yùn)輸需求特征

在物流運(yùn)輸路徑可行解改進(jìn)算法中，分析物流運(yùn)輸?shù)目偭啃枨?、價(jià)值特征、外延特征等，是運(yùn)輸路徑優(yōu)化的關(guān)鍵因素，為路徑規(guī)劃提供基礎(chǔ)條件。物流運(yùn)輸?shù)目尚薪飧倪M(jìn)主要以用戶需求為主，結(jié)合貨物物流總質(zhì)量、體積、運(yùn)輸時(shí)間、運(yùn)輸始發(fā)地與目的地等要求，規(guī)劃運(yùn)輸路徑，由此確定投入資源的規(guī)模[4]。單件貨物體積、毛重、重心、外包裝等情況，均與原廠取得聯(lián)系，確保貨物能夠完整地運(yùn)送到用戶手中?？紤]到貨物物流運(yùn)輸?shù)慕?jīng)濟(jì)性需求，在貨物運(yùn)輸目的地中適當(dāng)?shù)卦黾悠渌噜忂\(yùn)輸?shù)氐呢浳?，以最短的距離護(hù)送最多的貨物，最大限度上滿足貨物運(yùn)輸?shù)膬r(jià)值需求[5]。在實(shí)際貨物運(yùn)輸?shù)倪^(guò)程中，物流車從當(dāng)前站點(diǎn)去往下一目的地時(shí)，會(huì)出現(xiàn)交叉路口，運(yùn)輸轉(zhuǎn)折點(diǎn)如下圖1所示。

圖1 實(shí)際物流運(yùn)輸?shù)缆肥疽鈭D

如圖1所示，在實(shí)際物流運(yùn)輸過(guò)程中，物流車輛從物流運(yùn)輸節(jié)點(diǎn)A到物流運(yùn)輸節(jié)點(diǎn)B時(shí)，在平面規(guī)劃中顯示為距離D。但是，受到實(shí)際道路環(huán)境的影響，僅能通過(guò)轉(zhuǎn)折點(diǎn)C到達(dá)物流運(yùn)輸節(jié)點(diǎn)B[6]。在交通擁堵的條件下，轉(zhuǎn)折點(diǎn)C的車輛較多，物流運(yùn)輸時(shí)間相應(yīng)增加。

1.2 基于數(shù)學(xué)建模規(guī)劃物流運(yùn)輸路徑

在確定了物流運(yùn)輸需求之后，本文利用數(shù)學(xué)建模規(guī)劃運(yùn)輸路徑，優(yōu)化物流運(yùn)輸路徑可行解，在滿足物流運(yùn)輸需求的同時(shí)，縮短物流運(yùn)輸路徑距離，從而實(shí)現(xiàn)物流運(yùn)輸?shù)淖畲蠡?jīng)濟(jì)效益[7]。本文結(jié)合物流運(yùn)輸特征，引入決策變量，將每?jī)蓚€(gè)運(yùn)輸節(jié)點(diǎn)進(jìn)行最短路徑尋優(yōu)，避免運(yùn)輸擁堵問(wèn)題。決策變量表示為：

式（1）中，xij為決策變量表達(dá)式；i、j為兩個(gè)連續(xù)的物流運(yùn)輸節(jié)點(diǎn)。從物流運(yùn)輸節(jié)點(diǎn)i～j的過(guò)程中，如果i、j、不連接，不是直線距離，需要轉(zhuǎn)折點(diǎn)C才能完成運(yùn)輸，則xij=0；如果、為連接狀態(tài)，是一個(gè)直線距離，無(wú)需轉(zhuǎn)折點(diǎn)C就能完成運(yùn)輸，則xij=1。根據(jù)物流運(yùn)輸路徑可行解的數(shù)學(xué)描述，本文建立了物流運(yùn)輸路徑可行解的數(shù)學(xué)模型，表示為：

式（2）中，V為所選物流運(yùn)輸路徑中運(yùn)輸節(jié)點(diǎn)個(gè)數(shù)；f0為最小目標(biāo)函數(shù)；wij為節(jié)點(diǎn)i、j的距離權(quán)重。在Xij=1、Xji=1的條件下，節(jié)點(diǎn)i、j之間為連接狀態(tài)，節(jié)點(diǎn)j、i同為連通狀態(tài)。此時(shí)，物流運(yùn)輸所行走的運(yùn)輸路徑無(wú)回路，f0就是優(yōu)化后物流運(yùn)輸路徑可行解的最優(yōu)值，也就是運(yùn)輸最短路徑[8]。當(dāng)Xij=0的狀態(tài)下，節(jié)點(diǎn)i、j之間不連通，此時(shí)物流運(yùn)輸路徑可行解的數(shù)學(xué)模型表示為：

式（3）中，f0'為節(jié)點(diǎn)i、j之間不連通條件下，物流運(yùn)輸路徑可行解的最差值，也就是運(yùn)輸最長(zhǎng)路徑。此時(shí)物流運(yùn)輸所行走的運(yùn)輸路徑有回路，且不止一條。假設(shè)節(jié)點(diǎn)i、j之間存在2個(gè)轉(zhuǎn)折點(diǎn)，則此時(shí)的最短路徑為：

2.實(shí)驗(yàn)

為了驗(yàn)證本文設(shè)計(jì)的改進(jìn)算法是否具有優(yōu)化效果，對(duì)上述算法進(jìn)行了實(shí)驗(yàn)分析。分別使用文獻(xiàn)[1]基于遺傳算法的物流運(yùn)輸可行解改進(jìn)方法、文獻(xiàn)[2]基于雙向搜索的物流運(yùn)輸可行解改進(jìn)算法，以及本文設(shè)計(jì)的基于數(shù)學(xué)建模的物流運(yùn)輸可行解改進(jìn)算法，對(duì)物流運(yùn)輸路徑可行解進(jìn)行優(yōu)化，并將算法性能指標(biāo)進(jìn)行對(duì)比，找出最佳改進(jìn)優(yōu)化方案。實(shí)驗(yàn)準(zhǔn)備過(guò)程以及最終的實(shí)驗(yàn)結(jié)果如下所示。

2.1 實(shí)驗(yàn)過(guò)程

本次實(shí)驗(yàn)選用大城市的物流運(yùn)輸數(shù)據(jù)集作為算法測(cè)試集，城市交通在7:00～9:00、16:00～19:00的時(shí)間段較為擁堵，在10:00～15:00、20:00～6:00較為暢通。為了分析算法的可行性，本文選擇7:00～9:00、10:00～15:00、16:00～19:00的時(shí)間段進(jìn)行了3組實(shí)驗(yàn)。不考慮自身因素時(shí)，配送站點(diǎn)間道路均為直接連接，提升實(shí)驗(yàn)效率。根據(jù)道路實(shí)際情況，生成物流運(yùn)輸序列，如下圖2所示。

圖2 物流運(yùn)輸序列示意圖

如圖2所示，本次實(shí)驗(yàn)將不同的物流運(yùn)輸坐標(biāo)節(jié)點(diǎn)進(jìn)行編號(hào)，并將其連接成初始站點(diǎn)序列，根據(jù)各個(gè)物流運(yùn)輸節(jié)點(diǎn)的位置，設(shè)置更加符合運(yùn)輸需求的最短路徑。

2.2 實(shí)驗(yàn)結(jié)果

在上述實(shí)驗(yàn)條件下，本文進(jìn)行了3組實(shí)驗(yàn)，每組實(shí)驗(yàn)進(jìn)行10次，將每組實(shí)驗(yàn)的平均迭代次數(shù)記錄。在平均迭代次數(shù)最大時(shí)，得到物流運(yùn)輸路徑可行解的最優(yōu)值、最差值、平均值，作為改進(jìn)算法的性能指標(biāo)。在其他條件均一致的情況下，將文獻(xiàn)[1]基于遺傳算法的物流運(yùn)輸可行解改進(jìn)方法性能指標(biāo)、文獻(xiàn)[2]基于雙向搜索的物流運(yùn)輸可行解改進(jìn)算法性能指標(biāo)，以及本文設(shè)計(jì)的基于數(shù)學(xué)建模的物流運(yùn)輸可行解改進(jìn)算法性能指標(biāo)進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果如下表1所示。

表1 實(shí)驗(yàn)結(jié)果

如表1所示，物流運(yùn)輸路徑可行解的最優(yōu)值就是物流運(yùn)輸?shù)淖疃搪窂剑晃锪鬟\(yùn)輸路徑可行解的最差值就是物流運(yùn)輸?shù)淖铋L(zhǎng)路徑；物流運(yùn)輸路徑可行解的平均值就是物流運(yùn)輸?shù)钠骄窂?。物流運(yùn)輸路徑可行解的改進(jìn)算法平均迭代次數(shù)越少，可行解計(jì)算時(shí)間越短，物流運(yùn)輸路徑規(guī)劃效率越高。物流運(yùn)輸路徑的最優(yōu)值、最差值、平均值越滿足實(shí)際路徑最短需求，可行解改進(jìn)算法越有效。由此可見(jiàn)，在平均迭代次數(shù)最小的同時(shí)，最優(yōu)值、最差值、平均值最短的條件下，確定為最佳路徑規(guī)劃方案，改進(jìn)算法性能更佳。在其他條件均一致的情況下，使用文獻(xiàn)[1]基于遺傳算法的物流運(yùn)輸可行解改進(jìn)算法之后，平均迭代次數(shù)較多，最優(yōu)值、最差值、平均值中均顯示為較長(zhǎng)的物流運(yùn)輸路徑，無(wú)法適應(yīng)物流運(yùn)輸路徑規(guī)劃需求。使用文獻(xiàn)[2]基于雙向搜索的物流運(yùn)輸可行解改進(jìn)算法之后，平均迭代次數(shù)有所降低，物流運(yùn)輸路徑可行解的最優(yōu)值、最差值、平均值均得到了改進(jìn)，但從整體來(lái)看，迭代次數(shù)仍然較大，可行解仍然較高，亟須進(jìn)一步處理。而使用本文設(shè)計(jì)的基于數(shù)學(xué)建模的物流運(yùn)輸可行解改進(jìn)算法之后，平均迭代次數(shù)低于300次，最優(yōu)值低于550km，最差值低于600km，平均值低于560km。由此可見(jiàn)，使用本文設(shè)計(jì)的方法能夠更加快速地規(guī)劃出物流運(yùn)輸?shù)淖疃搪窂?，提升運(yùn)輸經(jīng)濟(jì)效益。

3.結(jié)束語(yǔ)

近些年來(lái)，電子商務(wù)快速發(fā)展，越來(lái)越多的人群選擇在網(wǎng)絡(luò)軟件上購(gòu)買商品，物流業(yè)也隨之發(fā)展。受到不同區(qū)域的商品購(gòu)買環(huán)境影響，物流成本、運(yùn)輸成本、管理成本不同，物流運(yùn)輸時(shí)間越長(zhǎng)，相應(yīng)的成本越高，無(wú)法滿足物流運(yùn)輸行業(yè)的經(jīng)濟(jì)效益。因此，本文利用數(shù)學(xué)建模，設(shè)計(jì)了物流運(yùn)輸路徑可行解的改進(jìn)算法。從需求特征、規(guī)劃路徑等方面，找出物流運(yùn)輸路徑可行解的最優(yōu)值，最大程度上縮短物流運(yùn)輸距離，為提升產(chǎn)業(yè)經(jīng)濟(jì)效益作出保障。