运筹学中运输问题求解算法及其扩展研究

王广民，马林茂，李兰兰(中国地质大学(武汉）经济管理学院，湖北 武汉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．