運籌學中運輸問題求解算法及其擴展研究

王廣民，馬林茂，李蘭蘭(中國地質大學(武漢）經濟管理學院，湖北 武漢430074）

運輸問題是社會經濟生活和軍事活動中經常出現的優化問題，是特殊的線性規劃問題，它是早期的線性網絡最優化的一個例子。最早研究這類問題的Hitchcock[1]以及后來的Koopmans[2]獨立地提出運輸問題并詳細地對該問題加以討論；同時Канторович[3]也圍繞著運輸問題作了大量的研究，因此運輸問題又稱為Hitchcock問題或Kantorovich問題。運輸問題不僅代表了物資合理調運、車輛合理調度等問題，有些其他類型的問題經過適當變換后也可以歸結為運輸問題，如指派問題、最短路問題、最小費用流問題可轉化為運輸問題或轉運問題。

運輸問題在運籌學教學過程中占有重要地位，并且得到了眾多學者的廣泛關注，取得了許多重要的研究成果。但在常用的運籌學教材中僅僅介紹運輸問題的基礎知識，對于運輸問題的前沿發展沒有涉及，這遠遠不能反映當前對運輸問題的深入研究。為此，筆者在介紹運輸問題的基本理論和方法的基礎上，運用綜述文獻的方法介紹運輸問題的研究進展?中國地質大學研究生培養模式與教學改革項目(CUGYCXK0813）。。

1 運輸問題及其求解算法

1．1 運輸問題

設某物資有m個產地Ai（i=1，2，…，m），其產量分別為ai（i=1，2，…，m）；有n個銷地Bj（j=1，2，…，n），其銷量分別為bj（j=1，2，…，n）；從Ai到Bj運輸單位物資的運價（單價）為cij（i=1，2，…，m；j=1，2，…，n），如表1所示，試求總運費最小的調運方案。

表1 運輸問題

但是一般來說，產銷平衡總不一定能夠滿足，所以可以通過下面2種方法將不滿足產銷平衡的運輸問題轉化為產銷平衡的運輸模型。

1．2 求解算法

1）表上作業法 傳統運輸問題的類型是線性、單目標、平衡、二維問題，由于它的約束方程組的系數矩陣具有特殊的結構，因此一般使用表上作業法求解。表上作業法是單純形法在求解運輸問題時的一種簡化方法，其實質是單純形法[4-5]。并且有許多學者對該方法進行了深入研究，如陳紹順等[6]提出了最小損失閉回路調整法；張鳴龍[7]指出當運輸問題的基可行解出現退化時，用閉合回路法和位勢法有時會出現算出某個檢驗數為負，卻找不出調優回路的現象。劉家學等[8]針對這一情況給出了判斷和尋找調優回路的方法。但是表上作業法計算量龐大，且表上計算很難用計算機語言編程計算來實現龐大計算量的求解，因此該法一般較適合于求解少量個數產銷地的運輸問題。

2）圖上作業法 圖上作業法就是要找出沒有對流和迂回的最優運輸方案，它是一種在交通路線圖上進行編制調運方案的方法，其基本思想：先找出一個沒有對流的初始方案，再檢查有沒有迂回，如果沒有迂回，該方案為最優方案；如果有迂回，則調整這一方案，直至無迂回為止[9]。在有許多圈的交通圖中，若已求得一個無對流的方案，然后通過調整舊方案，可以盡快得到最優方案。文獻 [10]引入迂回數的概念，根據運輸量減少最快的思想，得到了改進的圖上作業法能盡快得到最優方案。圖上作業法雖然簡便易行，但是遇到線路復雜的情況時，用計算機程序解決會有許多困難。而且圖上作業法找到的最優調運方案，可能平均運費值最小，但總的運費不一定最小。

3）智能算法 目前用于求解運輸問題的智能算法主要是遺傳算法和Hopfield神經網絡算法。

遺傳算法在運輸問題中的應用主要有平衡非線性運輸問題[11]、雙目標運輸問題及多目標三維運輸問題[12]、產銷不平衡運輸問題[13]。然而這些算法具有速度慢，交叉變異算子全局搜索能力差等缺點，而且還不能直接求解實數問題。因此，張美玉等[14]提出一種新的進化算法，該算法在GA操作的基礎上，引進差異進化[15]的思想，增加了重組操作，并結合變異操作，以增強全局搜索能力，同時能在理論上確保LTP約束條件的滿足。文獻 [16-17]則采用自適應偽并行遺傳算法求解三維運輸問題。

Hopfield神經網絡在運輸問題中的應用主要有物資調配優化問題[18]，物流配送運輸規劃算法[19]，以及文獻 [20]利用Hopfield神經網絡中能量函數的概念和含義確定網絡電路的參數并證明系統的穩定性。

雖然智能算法在求解優化問題上有傳統方法不可比擬的優勢，而且在求解運輸問題上取得了成功的應用，但是它們也有自身的缺陷。因此很難用它來描述層次化的問題，也就不能描述計算機程序，從而缺乏動態可變性。神經網絡易收斂于局部最優解且帶有一定的 “黑箱”操作，在一定程度上限制了它的應用。

2 運輸問題的擴展

2．1 單目標運輸問題

1）帶時間約束的運輸問題 傳統的運輸問題是在給定的條件下，求總運費最少的運輸方案。但是在特殊情況下，如戰時軍用物資的運輸，搶險救災物資的運輸等，首要考慮的應該是在最短的時間內把物資運送到所需要的地點，即運輸的時效性，其次才是運輸費用的問題。這類問題稱為帶時間約束的運輸問題。1989年，Hammer[21]就提出了時間最小化的運輸問題。1997年，白國仲[22]把這類帶時間約束的運輸問題總結為B運輸問題，并給出了B運輸問題的數學模型及其解法——表上作業法。然而表上作業法過程繁瑣，計算量大，在實際中不易于掌握和應用。后來很多學者在此基礎上又提出了一些改進算法。賈春玉等[23]等利用簡單的數學方法把多目標規劃法簡化為單一目標，簡化為傳統運輸問題模型，給出了一種帶時間約束運輸問題的簡便解法。陸朝榮，朱煥勤[24]等分析了有嚴格時間限制的大宗物資運輸車輛配置問題的特點，對各需求點時間限制進行排序、分級，將問題分為若干個階段，建立了任一階段的整數目標規劃模型，采用序貫式算法求解模型。董麗，林琳[25]等提出了基本最短時限運輸問題的一個推廣模型，即運輸時間與運輸量相關的最短時限運輸問題，把時間函數推廣到單調遞增函數，并針對這種推廣模型建立了多項式時間算法。程國忠[26]，莫松海和喻曉峰[27]提出利用連續Hopfield網絡求解B運輸問題。

2）帶容量限制的運輸問題 傳統的運輸問題只含有資源和需求2個約束，但在現實問題中往往還需要考慮運輸容量的限制。1955年，Haley[28]首次提出了不同的運輸方式有不同的容量限制的運輸問題，并稱之為立體運輸問題。在近幾十年的發展中基于確定和不確定環境的立體運輸問題的解法和算法不斷涌現，比較代表性的有：模糊立體運輸問題(FSTP）[29]及神經網絡算法[30]和遺傳算法[31]具有模糊權重的立體運輸問題的可信性理論和機會測度理論[32]。1959年，Wagner[33]又提出了變量有界的運輸問題，即每條運輸路線上都有其容量限制。最初，學者們大多采用各類推廣的對偶算法和表上作業法來求解該模型[34-35]。文獻 [36-39]也是在求解一般運輸問題的方法基礎上，各自提出了變量有上界的運輸問題的解法。而董鵬等[40]，薛強等[41]提出了一類帶配送中心運輸問題的容量擴張模型，采用一種構造輔助網絡的方法：在運輸網絡中將每個配送中心均拆分成2個點，連接2點形成新弧，構造出新的網絡，給每條弧賦予參數，將此類運輸問題轉換為最小費用流模型來解決，并在此基礎上，考慮運輸網絡中配送中心的容量擴張問題，簡化了運算。Yang等[42]，Simampo等[43]也研究了關于容量擴展的運輸問題。

2007年，白國仲等[44]提出了一種有效的求解變量有界運輸問題的新方法，其基本思想是：用類似最小元素法確定初始解，即就近供應，但限制變量的取值范圍，對于可能超過上界約束的情況，用拆分銷地并限制其銷量的方法加以控制；得到最優解后將拆分的銷地合并，若合并后各變量的取值均未超過上界，就得到原問題的最優解；若合并后各變量的取值有超過上界的，則進一步拆分銷地，直到合并后各變量的取值均不超過上界為止。

3）其他幾類單目標運輸問題 其他單目標運輸問題還有灰色運輸問題[45-47]、D運輸問題[48-49]及帶轉運中心的運輸問題[50-52]。

2．2 多目標運輸問題

隨著運輸網絡的發展和貨運量的增加，運輸問題變得越來越復雜。以總運費最小為優化目標的單目標優化模型得到的解，往往并不是決策者最滿意的解，人們希望得到的是多目標的最優解。目前解決多目標運輸問題的算法主要有交互式算法[53]、模糊規劃法[54-55]、模糊折衷規劃方法[56-57]和遺傳算法[58-60]。

3 運輸問題的悖論

在產地、銷地、單位運價均相同的情況下，運輸總量增加，運費反而減少的情況稱為運輸問題悖論。文平等[61]討論了運輸問題悖論出現的條件，并指出造成運輸問題悖論出現的根本原因是產銷地的布局不合理，其表現是產銷地的單位運價不合理。楊桂元[62]也探討了運輸問題 “悖論”存在的條件和表上作業法的調整方法，并指出了通過運輸問題數學模型挖潛的方法，最后給出了 “多反而少”現象存在的對偶條件。吳其苗[63]針對運輸問題的悖論，給出了數學解釋，并對運輸問題的悖論作出了經濟解釋。

對于國民經濟的重大運輸問題，在最優運輸計劃得到的前提下，還應考察運輸問題悖論是否發生，實現運輸計劃的再優化。如果運輸問題悖論發生，能調整產銷地布局，就調整產銷地布局，不能調整產銷地布局，就對產銷地的運輸網絡的關鍵線路重建、改建，或適當調整某產銷地的產銷量，使總運費下降，為國家節約更多的人力、物力、財力。

[1]Hitchcock F L．The distribution of a product from several sources to numerous locations [J]．Journal of Mathematics and Physics，1941，20(4）：224-230．

[2]Koopmans T C．Optimum utilization of the transportation system [A]．In proceedings of the international statistical conference [C]．Washington，DC，1947．

[3]（蘇）П．В．康特洛維奇(П．В．Канторович）．生產組織與計劃中的數學方法 [M]．中國科學院力學研究所運籌室譯 ．北京：科學出版社，1959．

[4]運籌學教材編寫組 ．運籌學 [M]．北京：清華大學出版社，2005．

[5]韓伯棠 ．管理運籌學 [M]．北京：高等教育出版社，2005．

[6]陳紹順，郭乃林，姜思山 ．受時間約束的運輸問題的表上作業法 [J]．空軍工程大學學報(自然科學版）．2002，3（4）：91-94．

[7]張鳴龍 ．在最解上挖潛——運輸問題的研究 [J]．系統工程理論與實踐，1987，（1）：1-6．

[8]劉家學，陳世國 ．一種尋求退化型運輸問題最優解方法研究 [J]．系統工程與電子技術，2001，10（23）：39-42．

[9]范艷峰，余漢印 ．利用計算機實現最優糧食調運方案 [J]．平原大學學報，2000，7（3）：75-76．

[10]左光紀 ．求解線性規劃的快速換基迭代法 [J]．運籌與管理，2000，19（4）：9-15．

[11]Michalewicz Z，Vignaux G A，Hobbs M．A non-standard genetic algorithm for the nonlinear transportation problems [J]．ORSA Journal on Computing，1991，3(4）：307-316．

[12]Gen M，Ida K，Li Y Z．Solving Multiobjective Solid Transportation Problem by Genetic Algorithm [J]．Journal of Japanese Industrial，Management Association，1995，46(5）：446-454．

[13]李然，王華 ．產銷不平衡運輸問題的遺傳算法研究 [J]．鐵道運輸與經濟，2005，28（7）：66-68．

[14]張美玉，黃 翰，楊曉偉，等 ．求解線性運輸問題的新型進化算法 [J]．廣西師范大學學報：自然科學版，2006，24（4）：74-78．

[15]Sun J Y，Zhang Q F，Tsang E P K．DE／EDA：A new evolutionary algorithm for global optimization [J]．Information Sciences，2005，169：249-262．

[16]張春梅，李嶸，梁治安 ．用自適應的遺傳算法求解雙準則三維運輸問題 [J]．內蒙古大學學報(自然科學版），2005，36（1）：15-20．

[17]張春梅，武鈞，梁治安 ．用自適應偽并行遺傳算法求解雙準則三維運輸問題 [J]．數學的實踐與認識，2006，37（11）：19-26．

[18]陳建民，張仲義 ．神經網絡求解物資運輸問題 [J]．測試技術學報，1999，13（2）：106-110．

[19]蘇一丹，李桂 ．流體神經網絡模型在規劃物流配送運輸方案中的應用 [J]．廣西大學學報(自然科學版），2002，27(3）：203-206．

[20]杜福銀，徐揚，盧明立，等 ．一種基于Hopfield神經網絡運輸問題的優化方法 [J]．鐵道運輸與經濟，2006，28（1）：70-72．

[21]Hammer P L．Time-minimizing Transportation Problems[J]．Naval Research Logistics Quarterly（S0894-069X），1989，16(3）：345-357．

[22]白國仲．B運輸問題求解及應用 [J]．系統工程理論與實踐，1997，17（1）：122-126．

[23]賈春玉，胡若飛，洪琦 ．帶時間約束的運輸問題簡便解法 [J]．系統工程，2004，22（8）：14-16．

[24]陸朝榮，朱煥勤，劉新建 ．有嚴格時間限制大宗物資運輸問題研究 [J]．工業工程，2006，9（5）：101-103．

[25]董麗，林琳，湯京永 ．最短時限運輸問題的推廣 [J]．大學數學，2007，23（5）：139-142．

[26]程國忠 ．運輸問題的神經網絡解法 [J]．計算機應用研究，2001（11）：16-18．

[27]莫松海，喻曉峰 ．基于神經網絡的B運輸問題求解算法 [J]．計算機應用與軟件，2008，25（3）：217-218．

[28]Haley K B．The solid transportation problem [J]．Operational Research，1962，11：446-448．

[29]Jimnez F，Verdegay J L．Uncertain solid transportation problems[J]．Fuzzy Sets and Systems，1998，100：45-57．

[30]Li Y，Ida K，Gen M，et al．Neural network approach for multicriteria solid transportation problem [J]．Computers and Industrial Engineering，1977，33：465-468．

[31]康旭輝，劉林忠 ．基于遺傳算法的隨機模糊立體運輸問題 [J]．數學的實踐與認識，2007，37（6）：102-107．

[32]劉寶碇 ．不確定規劃及應用 [M]，北京：清華大學出版社，2003．

[33]Wagner H M．On a Class of Capacitated Transportation Problems [J]．Management Science，1959，5（3）：304-318．

[34]李登峰 ．變量帶上界的運輸問題的一種新的對偶算法 [J]．系統工程，1989，7（1）：54-58．

[35]梁俊國 ．帶上界約束的運輸問題及其求解 [J]．太原重型機械學院學報，1997（12）：328-332．

[36]劉家學，鄭昌義，劉耀武 ．帶有約束的運輸問題及其推廣應用 [J]．系統工程理論與實踐，2002，（2）：127-130．

[37]Liu S T．The total cost of the transportation problem with varying demand and supply [J]．Omega，2003，31：247-251．

[38]Ghiani G，Guerriero F，Musmanno R．The capacitated plant location problem with multiple facilities in the same site [J]．Computers＆Operations Research，2002，29：1903-1912．

[39]Sun M H．The transportation problem with exclusionary side constraints and two branch and bound algorithms[J]．European Journal of Operational Research，2002，140：629-647．

[40]董鵬，楊超，陳新 ．一類帶容量限制的運輸問題 [J]．海軍工程大學學報，2004，16（5）：96-99．

[41]薛強，董鵬，羅朝暉 ．一類帶配送中心運輸問題的容量擴張模型研究 [J]．海軍工程大學學報，2006，18（1）：6-10．

[42]Yang C，Liu J．A capacity expansion problem with budget constraint and bottleneck limitation [J]．Acta Mathematica Scientia，2001，21B（3）：428-432．

[43]Simampo A，Ryan S M．Capacity expansion for a loss system with exponential demand growth [J]．Computers and Operations Research，2003，30：1525-1537．

[44]白國仲，朱小琨，陳雯 ．求解變量有界的運輸問題的新方法 [J]．華中師范大學學報(自然科學版），2007，41（4）：505-508．

[45]鄧聚龍 ．灰理論基礎 [M]．武漢：華中科技大學出版社，2002．

[46]白國仲 ．運費不確定的運輸問題 [J]．佛山科學技術學院學報(自然科學版），2007，25（1）：6-10．

[47]Bai G Z，Mao J Z，Lu G．Matrix games with grey payoffs [J]．Advances in Systems Science and Applications，2004，4(4）：511-514．

[48]白國仲，毛經中．D運輸問題 [J]．系統工程，2004，22(4）：21-25．

[49]陳四軍，熊少華．D運輸問題在物資調度中的應用 [J]．火力與指揮控制，2006，31（11）：100-102．

[50]趙秋紅 ．幾類物流優化模型的研究 [D]．北京航空航天大學，2003．

[51]楊豐梅，肖輝君 ．帶轉運中心的車輛組合運輸問題的模型與算法 [J]．系統工程理論與實踐，2007（3）：28-35．

[52]杜福銀，徐揚 ．有轉運運輸問題的Hopfield神經網絡優化方法 [J]．鐵道學報，2006，28（2）：17-20．

[53]Ringuest J L，Rinks D B．Interaction Solutions for the Linear Multiobjective Transportation Problem [J]．European Journal of Operational research（S0377-2217），1987，32(1）：96-106．

[54]Lau H C W，Chan T M，Tsui W T．A fuzzy guided multi-objective evolutionary algorithm model for solving transportation problem [J]．Expert Systems with Applications，2009，36：8255-8268．

[55]Li Lushu，Lai K K．A fuzzy approach to the multiobjective transportation problem [J]．Computers ＆ Operations Research，2000，27：43-57．

[56]Han S L，Li X H．Fuzzy programming approach solution for multi-objective solid transportation problem [J]．Journal of Southeast University（English Edition），2004，20(1）：102～107．

[57]韓世蓮，劉新旺 ．多目標多模式模糊運輸問題的最優折衷解 [J]．系統工程，2007，25（9）：26-32．

[58]Gen M，Li Y．Spanning tree-based genetic algorithm for bicriteria fixed charge transportation problem，in proceeding of the Congress on Evolutionary Computation [J]．Washington，DC，1999：2265-2271．

[59]苑清敏 ．遺傳算法在多目標運輸問題的應用 [J]．天津理工學院學報，2003，19（3）：57-60．

[60]林勇，張洪偉，沈哲宇．改進ST-GA遺傳算法在多目標運輸問題中的應用 [J]．西南民族大學學報(自然科學版），2009，35（6）：1161-1164．

[61]文平，王生喜 ．運輸問題悖論及其研究 [J]．數學的實踐與認識，2005，35（9）：129-133．

[62]楊桂元 ．運輸問題 “悖論”存在的條件及解決方法 [J]．運籌與管理，2007，16（1）：37-40．

[63]吳其苗 ．運輸問題的悖論及其數學、經濟解釋 [J]．紹興文理學院學報，2004，24（7）：45-48．