整車物流運(yùn)輸模型算法的研究
2014-12-31 00:00:00潘杭一
計(jì)算機(jī)光盤軟件與應(yīng)用 2014年23期
摘 要：針對(duì)乘用車物流運(yùn)輸計(jì)劃問題，本文建立了基于三維裝箱問題的最優(yōu)化裝箱問題模型，提出了基于兩階段線性規(guī)劃的處理算法。利用此算法，可在定義目標(biāo)函數(shù)和約束的基礎(chǔ)上，以較小的時(shí)間開銷完成搜索空間的搜索，以得到最優(yōu)化結(jié)果。在路徑規(guī)劃問題上，本文將路徑規(guī)劃問題簡(jiǎn)化為三角形路徑規(guī)劃問題，大幅減小了復(fù)雜度。最后，將兩種算法相結(jié)合，可解決一般性的物流規(guī)劃問題，并得到較優(yōu)結(jié)果。
關(guān)鍵詞：物流運(yùn)輸；組合優(yōu)化；路徑優(yōu)化；線性規(guī)劃；啟發(fā)式算法
中圖分類號(hào)：TP391
整車物流指的是按照客戶訂單對(duì)整車快速配送的全過程。隨著我國(guó)汽車規(guī)模的擴(kuò)大發(fā)展，乘用車的整車物流成為了當(dāng)前面臨的主要問題之一。
1 通用模型
1.1 兩階段線性規(guī)劃模型
1.1.1 模型定義
本文中假設(shè)所有轎運(yùn)車都是雙層；轎運(yùn)車到達(dá)目的地后不得返回；轎運(yùn)車在運(yùn)輸過程中可中途卸載部分乘用車；卸車成本忽略不計(jì)，總成本僅與派遣的轎運(yùn)車數(shù)量和行程有關(guān)。
在滿足假設(shè)前提的情況下，定義轎運(yùn)車集合П=<П1，…，Пp>與待運(yùn)乘用車集合Θ=<Θ1，…，Θi>，有任意轎運(yùn)車類型Пi=<πi，WiD，LiD，HiD，WiU，LiU，HiU>和待運(yùn)乘用車類型Θ=<θi，wi，li，hi>。其中，πi為轎運(yùn)車的數(shù)量，WiD，LiD，HiD，WiU，LiU，HiU分別為轎運(yùn)車上下兩層的寬、長(zhǎng)和高；θi為待運(yùn)乘用車的數(shù)量，wi，li，hi分別為待運(yùn)乘用車的寬、長(zhǎng)和高。則乘用車物流運(yùn)輸計(jì)劃問題可描述為：在滿足Constraint（1）的情況下，對(duì)于轎運(yùn)車和待運(yùn)乘用車集合П和Θ，求出Xmin，使得Cost（Xmin）=mini（Cost（Xi））。
在假設(shè)前提下，對(duì)于任意轎運(yùn)車Пi，可將其視為ПiD=<πi，WiD，LiD，HiD>（下層）與ПiU=<πi，WiU，LiU，HiU>（上層）。
（1）
1.1.2 兩階段線性規(guī)劃
定義1 切分模式：給定寬為W，長(zhǎng)為L(zhǎng)的長(zhǎng)方形X=
λiX=
其中，
定義2 兩階段線性規(guī)劃：給定Пp∈П和Θ，兩階段線性規(guī)劃問題分為兩個(gè)階段。
（1）將規(guī)格為Wi*Li的長(zhǎng)方形切分為wj*Li，θj∈Θ的“條”，Σwj≤Wi。
（2）給定規(guī)格wj*Li的條，將其切分為最終規(guī)格為wk*lk的塊，wk≤wj且Σlk≤Li。
0 0 2 120 1 0 0 10 1 0 0 0 0 0 1 0 0 0 0 0 0 0
W0=3.5 L0=24.3λ10λ20λ30λ40λ11λ12λ22λ32λ42λ52λ13λ23λ33λ43λ53λ63λ73λ83λ93λ103λ113λ123λ133λ143λ153
（wi，li）=（1.605，3.615）
（1.7，4.61）
（1.785，4.63）2 1 1
1 2
1-1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1=0
=0
=0
（wi，li）=（1.605，3.615）
（1.7，4.61）
（1.785，4.63） 65 4 2 1
1 2 3 4 55 4 2 1 4 2 2 1 1 1
4 3 2 1 1 2 1 3 2 1
1 2 3 4 1 2 3 4 1 1 2 1 2 3 5 ≥20
≥8
≥6
圖1 示例-兩階段劃分
假設(shè)只有一種規(guī)格的轎運(yùn)車П0=<π0，3.5，24.3>，三種待運(yùn)乘用車Θ1=<20，1.605，3.615>，Θ2=<8，1.7，4.61>和Θ3=<6，1.785，4.63>，則 。兩階段可描述為：第一步：將條形3.5?24.3編號(hào)為0。該條形能夠以γ0=4種方式，切分成包含寬分別為<1.605，1.7，1.785>，長(zhǎng)為24.3的條。如圖1，在切分模式λ30中，可得到<1.605，1.7，1.785>，長(zhǎng)為24.3的條各<1，0，1>塊。第二步：給定規(guī)格為1.785?24.3的條，給定切分模式λ83，可切分出規(guī)格為<1.605，3.615>，<1.7，4.61>，<1.785，4.63>的塊各<0，1，4>塊。
1.1.3 通用模型
通用模型FS首先，建立通用模型FS。記Пi∈П的規(guī)格W*L，Θ=<Θ1，…，Θm>中有 種不同的寬，分別為 。則在規(guī)劃過程中，總共有 種規(guī)格的條形，它們的規(guī)格分別為W*L， 。按順序?qū)⑦@些規(guī)格編號(hào)為 。
定義3 Ai定義Ai=[λ1i…λγii]。λji是針對(duì)規(guī)格編號(hào)i的形狀，能進(jìn)行的第j種切分方式。記Ai的行數(shù)和列數(shù)分別為ri，ci，則有：當(dāng) 或i≠0，ri=m時(shí)，ci=γi。
定義4 ，其中 表示的是對(duì)應(yīng)第j種切分方法需重復(fù)的次數(shù)。
定義5 Ni=[n1i…nmi]T，其中nji表示對(duì)應(yīng)切分方法j能產(chǎn)生史小塊的數(shù)量。
根據(jù)上述定義，給定規(guī)格編號(hào)為i的長(zhǎng)方形，其能分割出的長(zhǎng)方形數(shù)量可通過公式 求出。實(shí)際上，第一階段問題是是針對(duì)W*L的線性規(guī)劃問題，第二階段是針對(duì)第一階段wi*L的線性規(guī)劃問題，將兩者結(jié)合，可得到以下條件： ； 。其中 是指，第一階段的產(chǎn)出需要等于第二階段的消耗。
至此，可以得適用于單一規(guī)格的單層轎運(yùn)車的通用形式FS，通用模型FM可對(duì)適用單一規(guī)格的通用形式進(jìn)行修改，以形成適用于多規(guī)格的單層轎運(yùn)車構(gòu)造通用形式?？紤]到有q種不同的單層轎運(yùn)車，對(duì)于每一種轎運(yùn)車1≤i≤q，都有對(duì)應(yīng)的Ai，則適用于多規(guī)格的單層轎運(yùn)車的線性方程應(yīng)滿足以下基本形式：AX≥N′；A=diag[A1，…，Aq]；N′=[0 n11 n21 … nm1 … 0 n1p … nmp]T。
在建立好通用形式FS或FM之后，則可對(duì)其進(jìn)行求解，得出最優(yōu)解X*以及相應(yīng)能夠運(yùn)送的各型乘用車數(shù)量N*。對(duì)于求得的N*
1.2 基于蟻群算法的路徑優(yōu)化模型
將一般運(yùn)輸路徑問題簡(jiǎn)化為圖2所示。在滿足假設(shè)前提的條件下，乘用車路徑規(guī)劃問題可描述為：對(duì)于給定轎運(yùn)車集合П和待轎運(yùn)車集合Σ=<ΣA，ΣB，ΣC，ΣD，ΣE>，需要在指定的約束條件Constraint的情況下，使得轎運(yùn)車集合Σ運(yùn)送到目的地。
圖2 一般路徑規(guī)劃問題的路徑圖
因此，定義滿足Constraint的解決方案為元組S=
（3）
則乘用車路徑規(guī)劃問題可描述為：對(duì)于給定轎運(yùn)車集合П和待轎運(yùn)車集合Σ，在滿足Constraint的基礎(chǔ)上，求出Smin，使得Cost（Smin）=min（Cost（S））。
1.2.1 基本模型及建模
根據(jù)圖2，為使運(yùn)輸?shù)霓I運(yùn)車數(shù)量以及型號(hào)最優(yōu)（數(shù)量最少，轎運(yùn)車使用成本最低），可采取由遠(yuǎn)到近的分配策略，從而縮減較近節(jié)點(diǎn)的轎運(yùn)車需求。利用此策略，對(duì)原有路徑圖的簡(jiǎn)化為圖3。如圖4，利用上文所提到的兩階段線性規(guī)劃模型，可計(jì)算在E、A兩地的需求合并后，轎運(yùn)車的最優(yōu)指派方案
圖3 簡(jiǎn)化后路徑圖
圖4 E、A兩地的運(yùn)輸規(guī)劃問題
根據(jù)圖4，可把B地作為始發(fā)站。對(duì)E、A兩地的運(yùn)輸規(guī)劃問題可轉(zhuǎn)化為標(biāo)簽問題?？啥x標(biāo)簽A為0，E為1，解定義為Spath=
1.2.2 蟻群算法流程
初始狀態(tài)：上述問題模型可轉(zhuǎn)化為分層選擇模型。初始狀態(tài)，將m只螞蟻隨機(jī)放入第一層的0節(jié)點(diǎn)或1節(jié)點(diǎn)，隨機(jī)從下層中選擇一個(gè)標(biāo)簽來前進(jìn)；t時(shí)刻在節(jié)點(diǎn)i和下層節(jié)點(diǎn)j之間的殘留信息量用τij（t）表示；在初始時(shí)殘留信息量相同，設(shè)τij（0）=c。
轉(zhuǎn)移概率：螞蟻k（k=1，…，m）在運(yùn)動(dòng)過程中，由各條路徑上殘留的信息量決定其運(yùn)動(dòng)方向。螞蟻k在t時(shí)刻從節(jié)點(diǎn)i運(yùn)動(dòng)到下一層的節(jié)點(diǎn)j的概率用pkij（t）來表示，如式（4）：
（4）
其中，α為殘留信息量的信息素啟發(fā)因子；β為期望值的啟發(fā)因子；ηij為啟發(fā)值。
信息素更新：經(jīng)過n個(gè)時(shí)間段，所有螞蟻都完成對(duì)每個(gè)標(biāo)簽的選擇，將最新的螞蟻訪問過的路徑留下的新信息加入到τij（t）中。信息素根據(jù)以下公式進(jìn)行更新：
τij（t+1）=（1-p）τij（t）+Δτij； （5）
； （6）
其中，1*代表第k只螞蟻通過Pathij；2*代表第k個(gè)解決方案滿足約束。式中，p表示信息素?fù)]發(fā)因子，取[0.5，0.9]；Δτkij表示第k只螞蟻在此次循環(huán)中在ij路徑上的信息素增量，若該螞蟻訪問了該路徑，則增量為正數(shù)，否則為0；在計(jì)算增量上，Q為正常數(shù)，F(xiàn)k為第k只螞蟻的路徑所產(chǎn)生的解的適應(yīng)度；在計(jì)算適應(yīng)度時(shí)，若第k只螞蟻的標(biāo)簽方案符合所有的約束，則適應(yīng)度為正值，否則為0；fmax，fmin分別為當(dāng)前蟻群中產(chǎn)生的最優(yōu)解和最差解的適應(yīng)度函數(shù)值。
2 模型總結(jié)
針對(duì)多規(guī)格轎運(yùn)車裝配問題和多地點(diǎn)路徑規(guī)劃問題，本文分別提出了對(duì)應(yīng)的數(shù)學(xué)模型：兩階段線性規(guī)劃模型與基于蟻群算法的路徑優(yōu)化模型，并給出了相應(yīng)算法流程。模型最后可輸出對(duì)多規(guī)格轎運(yùn)車的最優(yōu)裝配方案，以滿足單一目標(biāo)地的乘用車需求。
對(duì)于路徑優(yōu)化問題，本文給出基于蟻群算法的優(yōu)化模型，利用啟發(fā)式算法正反饋的機(jī)制，以較少時(shí)間實(shí)現(xiàn)對(duì)復(fù)雜解空間最優(yōu)解的逼近。
參考文獻(xiàn)：
[1]P.C.Gilmore，R.E.Gomory，Multistage cutting stock problems of two and more dimensions，Operations Research[J]，Vol.13，No.1，Jan.-Feb.，Page 94 of 94-120，1965.
[2]Eugene J.Zak，Row and column generation technique for a multistage cutting stock problem，Computers Operations Research[J]，Vol.29，No.9.（2002），pp.1143-1156.
[3]吳宗彥，王景華，張建軍，基于蟻群算法的智能運(yùn)輸調(diào)度問題的研究[J].計(jì)算機(jī)工程與應(yīng)用，2006（35）.
[4]張志霞，邵必林.基于改進(jìn)蟻群算法的運(yùn)輸調(diào)度規(guī)劃[J].公路交通科技，2008（04）.
[5]楊菊花，朱昌鋒，田志強(qiáng).基于蟻群算法的應(yīng)急物資運(yùn)輸路徑優(yōu)化[J].鐵道科學(xué)與工程學(xué)報(bào)，2012（06）.
[6]歐邦才.基于線性規(guī)劃的物流運(yùn)輸方案探討[J].黑龍江水利科技，2009（06）.
[7]彭月.基于線性規(guī)劃的運(yùn)輸模型[J].科技致富向?qū)В?014（08）.
[8]吳雪琴.線性規(guī)劃在物流運(yùn)輸中數(shù)學(xué)模型的建立及應(yīng)用[J].江西電力職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2007（01）.
作者簡(jiǎn)介：潘杭一，女，滿族，黑龍江齊齊哈爾人，工學(xué)學(xué)士，軟件工程專業(yè)碩士在讀，研究方向：信息安全。
作者單位：同濟(jì)大學(xué) 軟件學(xué)院，上海 201804
