鄭愛萍，金福江

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

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

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

1.1 目標函數(shù)

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

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

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

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

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

1.2 約束方程

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

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

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

2 遺傳算法設計

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

1）編碼.采取二進制形式進行編碼，即將變量值代表的個體表示為二進制串.

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

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

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

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

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

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

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

3 應用實例

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

表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 單位運價數(shù)據(jù)Tab.3 Unit price data table 元·kg-1

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

其單位運價矩陣C為

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

而自然約束條件為

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

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

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

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

4 結論

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

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

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

［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］.北京：清華大學出版社，2009：170-176.

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

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

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

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

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

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

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