多產(chǎn)品運(yùn)輸問題的建模及優(yōu)化算法設(shè)計(jì)

鄭愛萍，金福江

（華僑大學(xué) 信息科學(xué)與工程學(xué)院，福建 廈門361021）

運(yùn)輸問題最早由Hichcock［1］于1941年提出的，是解決產(chǎn)地和銷地之間如何合理安排物資調(diào)運(yùn)方案的一類問題 .許多實(shí)際的問題如生產(chǎn)存儲(chǔ)等問題也可以通過相應(yīng)的變換轉(zhuǎn)為運(yùn)輸模型進(jìn)行求解，因此研究運(yùn)輸問題具有相當(dāng)重要的實(shí)際意義.多種產(chǎn)品條件下的運(yùn)輸模型及優(yōu)化算法研究對(duì)降低運(yùn)輸成本，提高企業(yè)經(jīng)濟(jì)效益具有重要作用.大多數(shù)運(yùn)輸問題都是在單一產(chǎn)品、多個(gè)生產(chǎn)地、多個(gè)銷售地模型的基礎(chǔ)上對(duì)優(yōu)化方法進(jìn)行研究，如表上作業(yè)法及其推廣［2-3］、圖上作業(yè)法及其他智能算法［4-5］，等等.企業(yè)實(shí)際的物資運(yùn)輸都是同時(shí)運(yùn)輸多種產(chǎn)品，因此要降低運(yùn)輸成本，提高企業(yè)經(jīng)濟(jì)效益，就需要對(duì)多種產(chǎn)品條件下的運(yùn)輸模型及優(yōu)化算法進(jìn)行研究.然而，目前有關(guān)多種物資運(yùn)輸問題的建模和優(yōu)化算法研究成果還很少.本文針對(duì)現(xiàn)代企業(yè)普遍存在有多個(gè)生產(chǎn)地、多種產(chǎn)品、多個(gè)銷售地的運(yùn)輸特點(diǎn)，建立多種產(chǎn)品條件下的物流運(yùn)輸模型.

1 運(yùn)輸問題的優(yōu)化模型

1.1 目標(biāo)函數(shù)

設(shè)Ci，k，j為第i（i＝1，…，m）個(gè)生產(chǎn)地向第j（j＝1，…，n）個(gè)銷售地運(yùn)輸?shù)趉（k＝1，…，p）種產(chǎn)品的單位運(yùn)費(fèi)，則可得到單位運(yùn)費(fèi)矩陣為

其中：矩陣C的行表示m個(gè)不同的生產(chǎn)地，列表示p種產(chǎn)品的n個(gè)不同銷售地.

設(shè)Xi，k，j為第i（i＝1，…，m）個(gè)生產(chǎn)地向第j（j＝1，…，n）個(gè)銷售地運(yùn)輸?shù)趉（k＝1，…，p）種產(chǎn)品的產(chǎn)品貨運(yùn)量，則可得到產(chǎn)品貨運(yùn)量矩陣為

其中：矩陣X的行表示m個(gè)不同的生產(chǎn)地，列表示p種產(chǎn)品的n個(gè)不同銷售地.

對(duì)上述兩個(gè)矩陣進(jìn)行點(diǎn)乘及求和運(yùn)算，即可得出多種產(chǎn)品運(yùn)輸問題的優(yōu)化目標(biāo)函數(shù)為

1.2 約束方程

1）產(chǎn)量約束 .第i個(gè)生產(chǎn)地生產(chǎn)的第k種產(chǎn)品被運(yùn)往r（r≤n）個(gè)銷售地的貨運(yùn)量等于i產(chǎn)地的k產(chǎn)品的產(chǎn)量，故多種產(chǎn)品運(yùn)輸問題的產(chǎn)量約束方程為

2）銷量約束.第j個(gè)銷售地的第k種產(chǎn)品的銷量等于i個(gè)生產(chǎn)地運(yùn)往d（d≤m）銷售地k產(chǎn)品的貨運(yùn)量，故多種產(chǎn)品運(yùn)輸問題的銷量約束方程為

3）變量值的約束 .由變量值的定義可知，其約束方程為

2 遺傳算法設(shè)計(jì)

基本的遺傳算法［6］是某一代種群經(jīng)過對(duì)生物基因的復(fù)制、變換和變異，產(chǎn)生新一代種群；然后，重復(fù)此過程，直到群體或最優(yōu)點(diǎn)的性能達(dá)到滿意程度.圖1為所設(shè)計(jì)的遺傳算法的流程圖，主要有如下8個(gè)基本步驟［7］.

1）編碼.采取二進(jìn)制形式進(jìn)行編碼，即將變量值代表的個(gè)體表示為二進(jìn)制串.

2）初始群體的生成 .初始化種群是產(chǎn)生優(yōu)化問題的一組初始可行解，故文中設(shè)定種群的大小為20，采用隨機(jī)的方式產(chǎn)生初始種群.

3）適應(yīng)度函數(shù).為了把目標(biāo)函數(shù)轉(zhuǎn)化為求極大值問題，故構(gòu)造適應(yīng)度函數(shù)為f（x）＝0.95z／10000，則總成本z越小的染色體其適應(yīng)度越大.

4）約束條件 .由于運(yùn)輸問題的約束條件可轉(zhuǎn)化成只含有｛0，1｝兩個(gè)元素的特殊矩陣，故應(yīng)對(duì)約束條件進(jìn)行處理 .即將約束條件的左邊轉(zhuǎn)化成（mp+np，mnp）階矩陣形式，約束條件的右邊轉(zhuǎn)化成（mnp，1）階矩陣形式.

5）選擇.傳統(tǒng)的單純采用賭輪選擇機(jī)制的方法偶然性很大，極易導(dǎo)致種群的退化，故文中采用精英原則的賭輪選擇機(jī)制.當(dāng)一對(duì)染色體交叉時(shí)，僅當(dāng)其子代的適應(yīng)度大于其父代的適應(yīng)度，才讓子代替換父代進(jìn)入種群；否則保留父代.這樣不僅能有效地保持種群的最優(yōu)解，又能防止種群的退化.

圖1 遺傳算法流程圖Fig.1 Flow chart of genetic algorithm

6）交叉 .交叉步驟模仿自然界的基因重組過程 ，其作用在于將已有的優(yōu)良基因遺傳給下一代個(gè)體，并生成包含更復(fù)雜基因結(jié)構(gòu)的新個(gè)體.即將父代按適應(yīng)度值進(jìn)行排序，讓前半部分與后半部分分別進(jìn)行交叉，并首先在兩個(gè)交叉的雙親中任意選取一個(gè)交叉位置；然后，根據(jù)交叉長(zhǎng)度確定另一個(gè)交叉位置，由此確定交叉的基因段.交叉長(zhǎng)度取Nc＝Pc·N，其中Pc為交叉概率，N為染色體長(zhǎng)度.

7）變異.變異的作用是為選擇、交叉過程中可能丟失的某些遺傳基因進(jìn)行修復(fù)和補(bǔ)充.即隨機(jī)選擇個(gè)體某列，并給該列一個(gè)增量.為了較好地改進(jìn)局部爬山能力，算法中采用多次變異的方法，直到本次變異的染色體序列的適應(yīng)度比前一次小為止.

3 應(yīng)用實(shí)例

采用晉江某紡織企業(yè)實(shí)際運(yùn)輸問題的數(shù)據(jù)，對(duì)文中提出的多種產(chǎn)品運(yùn)輸問題模型及其優(yōu)化算法進(jìn)行驗(yàn)證.該紡織企業(yè)共有3個(gè)生產(chǎn)車間，分別為漂染一廠、漂染二廠、漂染三廠，分別記為A1，A2，A3；生產(chǎn)的產(chǎn)品可大致劃分為4大類：純棉、滌棉、滌綸和人棉，分別記為C1，C2，C3，C4；3個(gè)車間生產(chǎn)的產(chǎn)品全部銷往5個(gè)銷售地，分別記為B1，B2，B3，B4，B5.表1～3分別是每天生產(chǎn)車間的產(chǎn)量數(shù)據(jù)表、銷售地產(chǎn)品銷量數(shù)據(jù)表以及單位運(yùn)價(jià)表.

表1 各生產(chǎn)車間產(chǎn)量數(shù)據(jù)表Tab.1 Production data table of different manufacturing shops kg·d-1

表2 銷售地各產(chǎn)品銷量數(shù)據(jù)表Tab.2 Product sales data table of sellers kg·d-1

表3 單位運(yùn)價(jià)數(shù)據(jù)Tab.3 Unit price data table 元·kg-1

根據(jù)實(shí)例可知：產(chǎn)量和銷量都是2 733kg，是一個(gè)產(chǎn)量等于銷量的運(yùn)輸問題 .將以上數(shù)據(jù)代入式（1）中，可得此多產(chǎn)品運(yùn)輸問題的模型為

其單位運(yùn)價(jià)矩陣C為

由式（2），（3）可知，其約束方程為

而自然約束條件為

將運(yùn)輸模型中的單位運(yùn)價(jià)系數(shù)及等式約束系數(shù)轉(zhuǎn)換成矩陣形式，分別使用內(nèi)點(diǎn)算法［8］和遺傳算法進(jìn)行優(yōu)化，并求解該多產(chǎn)品運(yùn)輸問題，如表4所示.表4中：算法編程以Matlab 2009A為平臺(tái)，運(yùn)用謝菲爾德（Sheffield）遺傳算法工具箱［9］；種群大小為20；最大迭代次數(shù)為100；交叉率為0.8；變異率為0.2.

表4 不同算法優(yōu)化后的銷售地貨運(yùn)量Tab.4 Sales freight volume of different optimization algorithms kg·d-1

從運(yùn)行結(jié)果可以看出：使用內(nèi)點(diǎn)算法和遺傳算法時(shí)，參數(shù)exitflag皆為1，說明該函數(shù)收斂，二者運(yùn)算的結(jié)果都是正確有效的 .從表4可知：對(duì)生產(chǎn)車間生產(chǎn)出的各種產(chǎn)品進(jìn)行物資調(diào)撥，調(diào)撥出去的貨運(yùn)量等于產(chǎn)品的總生產(chǎn)量2 733kg，得到的最優(yōu)調(diào)撥方案滿足各個(gè)約束條件 .這說明該多產(chǎn)品的運(yùn)輸模型是正確的，兩種求解方法都是可行的.

實(shí)例數(shù)據(jù)計(jì)算表明：內(nèi)點(diǎn)算法與遺傳算法的總運(yùn)輸費(fèi)用分別為3 753.0，2 355.9元；總運(yùn)輸時(shí)間分別為18.432 2，8.182 6s.由此可知，采用遺傳算法求出的運(yùn)輸總費(fèi)用優(yōu)于用內(nèi)點(diǎn)算法計(jì)算出的結(jié)果，說明了對(duì)于大規(guī)模的多產(chǎn)品運(yùn)輸問題，采用遺傳算法優(yōu)化性能更好，不易陷入局部最優(yōu) .同時(shí)，遺傳算法的收斂速度也優(yōu)于內(nèi)點(diǎn)算法，具有精確、快捷的特點(diǎn).

4 結(jié)論

根據(jù)企業(yè)對(duì)產(chǎn)品運(yùn)輸高效低成本的需求，建立了多種產(chǎn)品運(yùn)輸問題的優(yōu)化模型 .利用遺傳算法解決了多種產(chǎn)品運(yùn)輸?shù)膬?yōu)化求解問題，并通過實(shí)例進(jìn)行驗(yàn)證.

研究結(jié)果表明：所建立的多種產(chǎn)品運(yùn)輸模型是與企業(yè)實(shí)際的運(yùn)輸問題相符合；遺傳算法可快速地分析和計(jì)算出運(yùn)輸問題的最佳貨物配送方案，不僅有效地改善了表上作業(yè)法所面對(duì)的“維數(shù)障礙”問題，也改善了內(nèi)點(diǎn)算法在尋找最優(yōu)解上的準(zhǔn)確性，并有易于編程實(shí)現(xiàn)、收斂速度快等特點(diǎn).

在實(shí)際生產(chǎn)和銷售網(wǎng)絡(luò)中，生產(chǎn)地和銷售地都有庫(kù)存，因此，進(jìn)一步研究考慮庫(kù)存條件下的運(yùn)輸問題模型及最優(yōu)求解算法將更具有實(shí)際意義.

［1］ HICHCOCK F L.The distribution of a product from several sources to numerous localities［J］.J Math Phys，1941，20：224-230.

［2］ 陳寶林.最優(yōu)化理論與算法［M］.北京：清華大學(xué)出版社，2009：170-176.

［3］ 蔣宏鋒.運(yùn)輸問題一種新的表上作業(yè)法［J］.科學(xué)技術(shù)與工程，2006，24（6）：3941-3948.

［4］ 臧運(yùn)華.運(yùn)輸問題的一種圖上解法［J］.運(yùn)籌與管理，2002，11（4）：81-85.

［5］ 戴慶，申靜波.基于遺傳算法的運(yùn)輸問題最優(yōu)解研究［J］.天津理工大學(xué)學(xué)報(bào)，2008，24（3）：43-45.

［6］ 龔純，王正林.精通 MATLAB最優(yōu)化計(jì)算［M］.北京：電子工業(yè)出版社，2009：349-353.

［7］ 柏暉，費(fèi)樹岷.基于遺傳算法的紡織企業(yè)機(jī)配件庫(kù)存控制［J］.工業(yè)控制計(jì)算機(jī)，2011，24（11）：62-63.

［8］ 王雪.內(nèi)點(diǎn)算法的若干基本框架及其發(fā)展［J］.泰山學(xué)院學(xué)報(bào)，2007，29（3）：13-16.

［9］ 李明.詳解MATLAB在最優(yōu)化計(jì)算中的應(yīng)用［M］.北京：電子工業(yè)出版社，2011：382-397.