整車物流運(yùn)輸模型算法的研究

摘 要：針對(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=，以及一系列的小的長(zhǎng)方形Y=，Yi=，1≤i≤n。需要將X切分為寬為且長(zhǎng)為L(zhǎng)的條（長(zhǎng)方形）。一種切分模式λiX可定義如公式（2）：

λiX=T，Σjbj*wj≤W （2）

其中，是在切分模式λiX下，能切分出的寬為長(zhǎng)為L(zhǎng)的長(zhǎng)方形個(gè)數(shù)。記可能切分模式的總數(shù)為γX。

定義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=，其中Sk=（si為需要使用Пi型轎運(yùn)車的數(shù)量）為運(yùn)送到k地的指派方案。同時(shí)，該解決方案對(duì)應(yīng)成本Cost（S）=（式中Counts為該指派方案需要的轎運(yùn)車的總數(shù)，Lengths為該方案行駛的總里程）；成本之間的比較關(guān)系由式（3）定義：

（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)指派方案，以及每輛轎運(yùn)車的裝配方案。

圖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=。路徑優(yōu)化的問題優(yōu)化模型約束為： ； ； 。

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