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