运输问题国内外研究评述

龙源期刊网运输问题国内外研究评述作者：王有鸿费威来源：《商业时代》2010年第24期◆中图分类号:F713文献标识码:A内容摘要:本文在综合国内外有关运输问题研究的文献基础上,对运输问题及其模型进行介绍,分别对国外和国内有关运输问题研究进行了评论性综述。国外主要以运输问题求解算法为研究主体,以表上作业法、最短路法、最小费用最大流以及智能算法等为代表;国内从算法、目标函数、约束函数这三个角度进行分类综述。最后对已有研究进行总结比较,提出在针对不同的具体问题时,应综合考虑多种算法的综合优化。关键词:运输问题算法评述运输问题是社会经济生活和军事活动中经常出现的优化问题。在经济建设和国防建设中,经常遇到煤、钢铁、木材、粮食、武器装备等物资的调运问题。如何制定调运方案,将物资运往指定地点,而且实现运输成本最小,即为运输问题。运输问题是特殊的线性规划问题,它是早期的线性网络最优化的一个例子。最早研究这类问题的是美国学者希奇柯克(Hitchcock),1941年他在研究生产组织和铁路运输方面的线性规划问题时提出运输问题的基本模型;后来柯普曼(Koopmans)在1947年独立地提出运输问题并详细地对此问题加以讨论;从上世纪40年代早期开始,康脱洛维奇(Kantorovich)围绕着运输问题作了大量的研究,因此运输问题又称为希奇柯克问题或康脱洛维奇问题。与一般线性规划问题不同,它的约束方程组的系数矩阵具有特殊的结构,这就需要采用不同的甚至更为简便的求解方法来解决这种在实际工作中经常遇到的问题。运输问题不仅代表了物资合理调运、车辆合理调度等问题,有些其他类型的问题经过适当变换后也可以归结为运输问题。运输问题国外相关文献评述由于运输问题的特殊数学结构,人们很早就意识到通过给出进基变量和离基变量的最优性条件,可以更有效地利用单纯形法对运输问题进行求解。Danzig(1951)提出的单纯形法作为求解运输问题的最初单纯形方法(PrimalSimplexTransportationMethod,PSTM)。随后Charnes和Cooper(1954)发展了逐级算法(Stepping-StoneMethod,SSM),该算法提供了决定单纯形方法信息的可选择途径。除了PSTM与SSM,Adriano和Claudio(1974)给出了求解经典运输问题的一种搜龙源期刊网索算法,该算法思想以Balas(1967)过滤算法为基础,最后给出了该运输问题在实际中的应用。Barr(1981)利用增加原有线路指标数据结构,对Kennington和Unger(1976)的算法进行了改进。CabotandErenguc(1984,1986)提出原问题的拉格郎日松弛问题,由此可获得条件惩罚函数,但由于缺少有效运输节点,使算法的计算结果并不理想。Dimitri和David(1989)给出求解运输问题的拍卖算法。拍卖算法是一种求解经典指派问题的平行松弛算法。他们将拍卖算法应用于线性运输问题的求解,该算法的思想是将运输问题转化为指派问题,然后修改拍卖算法,使其适用于运输问题的特殊结构。Vignaux和Michalewicz(1991)给出了求解线性运输问题的遗传算法(遗传算法是仿照自然选择的进化过程寻找问题的解),并举例说明了具有代表性的结构之间的关系,研究了遗传算法实现的程序,给出了多种不同结构的运输问题。Kleinschmidt和Schannath(1995)在改进网络流算法的基础上,给出了一般运输问题的网络流算法,算法使用了大量的检测迭代,是一种求解运输问题的强多项式算法。国外学者从算法角度考虑,对于运输问题的求解提出了很多可行的解法,如表上作业法、图上求解法以及应用计算机实现的启发式多种算法等,其基本上可以总结如下:表上作业法是解决一般运输问题最常用的解法,因其求解工作均在运输表上进行而得名。它是一种迭代算法,迭代步骤为:先按某种规则找出一个初始解;再对现行解作最优性判别;若该解不是最优解,就在运输表上对它进行调整改进,从而得出一个新解,再重复判别改进的过程,直至得到运输问题的最优解为止。最短路线法。当已知某物资从出发地运往目的地,可有多条运输路线供选择,这时可构造费用网络图,用求最短路线的方法,选择最优的运输方案,需画出各种运输路线的线路图及图上每一条边(或弧)上的距离或费用(也可以用邻接矩阵表示),然后用Dijkstra标号法或邻接矩阵法求最优运输路线。最小费用最大流是网络最大流问题加上对总费用最小这一约束条件后求最大流问题。其算法是从费用为0的最小费用出发,结合弧费用构造赋权有向图,再利用求最短路算法寻找最小费用增广链对原最小费用流进行调整,重复此过程直至最小费用增广链不存在为止。随着智能搜索算法的发展,近年来有许多有关解决这类运输问题的人工智能方法的研究,如神经网络算法、禁忌搜索算法、遗传算法等。尤其是遗传算法在解决运输问题方面,已经得到了不错的效果。Michalewicz(1991)等人首先讨论了使用遗传算法来解决线性和非线性运输问题。运输问题国内相关文献评述龙源期刊网国内学者对于运输问题的研究主要可以分为三个角度:一是在国外算法的基础上,对运输问题算法的改进研究;二是从目标函数的角度,在运输问题中有时要同时考虑运输成本最小、运输过程中货物损坏率最低以及单位运价变化的调整等多个目标;从约束函数的角度,有研究供给量和需求量在某个区间变化的不确定型运输问题、有时间窗口的运输问题等。(一)算法角度的运输问题评述臧运华(2002)将运输问题转化为图问题,通过构造赋权二分图G,应用图论理论,给出运输问题一种图上解法。郭强(2004)从基变量判断和寻找闭回路思想出发,提出不同于位势法和闭回路调整的运输问题迭代算法,但算法仍具有传统表上作业法的缺点,先求初始可行解再构造上述三个矩阵进行检测调整。刘徽(2005)讨论了两类运输问题的算法,传统运输问题的算法和受时间约束运输问题的方案及算法。该算法从运输问题可行域的内部出发,沿着中心路径的方向,通过反复迭代寻找运输问题的近似最优解。张美玉、黄翰等(2006)针对实数线性运输问题,提出了一种新型进化算法,在遗传算法的基础上引进了差异进化的思想,设计出具有全局搜索能力的重组算子,重组算子能够从理论上保证约束条件的满足,仿真实例显示了该算法的可行性和有效性。周先东等(2008)设计了基于遗传算法和粒子群优化算法的求解运输问题的GAPSO算法,为避开对非可行解的处理,该算法对迭代过程也进行了特殊设计,从而简化了运用随机搜索算法解决运输问题的过程。(二)目标函数角度的运输问题评述自从建立了基本的运输问题模型以来,根据不同的物资调运实际状况建立的运输问题各种扩展模型也层出不穷。根据运输问题优化目标不同,基本上可以将运输问题分为三大类:即以费用最小为目标的费用优化运输问题、以时间最短为目标的时间优化运输问题和两类目标综合最优化的多目标优化运输问题。费用最优化运输问题模型。此类运输问题模型将运输费用的最小化作为模型的优化目标,目前大多数运输问题模型都属于该类模型的扩展与引申。如变量有限制的运输问题,其在物资收发量约束的基础上还加入了对调运变量的约束;变约束的运输问题将物资收发量确定为某一个变化范围而不是一个确定的值。此外还有带中转点的运输问题、多运输方式综合运输模型等等。时间最优化运输问题模型。此类运输问题以缩短调运时间为模型的优化目标,从而实现物资的快速运输。迄今为止,围绕解决这类问题已经进行了大量卓有成效的研究。较早的有运筹学的网络最短路模型、生产管理的调度理论和所谓的瓶颈运输问题。时间优化运输问题的特点即整体运输时间最短成为优化的第一目标,这时运用费用优化运输问题模型就难以给出满意的结果。前面所述的费用优化运输问题模型的优化目标为整体运输费用最小,运输费用具有线性叠加特性,或认为具有串联特性,即整体运输费用等于各分段费用的线性叠加;而运输时间则不具龙源期刊网有线性叠加特性,因为各供应点的操作可同时或平行进行,整体完成时间并不是各分段时间的线性叠加,而是由各分段时间中的最大值控制,运输时间的这一特点使运输时间的优化具有明显的并联特性。程桦、宋执环(2003)将物流运输中以时间为第一目标加入到一般运输问题中作为目标,将其分为先后发货即以总运输时间最小为目标和同时发货以各地运输时间最长为目标的两类运输问题,并重点对后者求解给出了算法。白国仲(2007)提出了该类问题的简算法。该算法实则是对传统算法—表上作业法稍作改进,以每次所求最优解中非零变量的单位运价为界,变换单位运价矩阵,重复进行表上作业法进行求解。(三)约束函数角度的运输问题评述高峰记等(2002)对于运输问题含有区间数不能完全确定情况,建立了其区间数模型,并引入λ水平将该模型转化为一般运输问题进行求解。谢凡荣(2005)将需求区间型运输问题先转化为运输网络中求最小费用最大流问题,并利用计算机编程程序进行求解。但算法程序过于复杂,必须通过掌握其一系列算法为基础,不易理解,且编程及软件模块不具通用性。曾霁等(2008)针对运输问题中有些参数很难给出精确值的情况,考虑采用不确定型规划描述此类问题,提出运输问题的区间规划模型,采用区间不等式度的定义将不确定的运输问题区间模型转化为确定型运输问题模型,再用表上作业法求解,其实质为用表上作业法求解一般运输问题。运输问题算法比较从上述文献评述可以看出,许多学者对运输问题的基本模型和算法分别进行了扩展、更新和改进。但无论运输问题的扩展变形如何,都是从一般运输问题衍生出来的。从各类运输问题的算法来看,基本上分为表上作业法、图上求解法、网络解法和计算机智能解法。因为计算机智能解法有些也是在前三种传统算法基础上建立的,所以前三种算法是各种算法的理论依据。下面对表上作业法、图上求解法、网络解法进行比较。表上作业法一方面是在求解过程中首先要找出初始基可行解,需要一定计算工作量,即需要经过(m+n-1)次加减运算给出初始方案。另一方面是在初始基可行解基础上,还要用繁琐的闭回路法或位势法计算所有空格(非基变量)的检验数,再判别是否达到最优解。如果没有得出最优解,还需要在表上用闭回路法进行调整,确定换入变量和换出变量,找出新的基可行解,再进行检验等步骤,直到求出最优解为止。图上求解法与表上作业法相比,用图上求解法判别最优解时,需要验证(m+n-1)基变量边是否可以用非基变量对应边代替(其中m、n分别是产地和销地的数量)。当m、n较大时,mn-(m+n-1)龙源期刊网远远大于(m+n-1),因此当m、n较大时,理论上用图上求解法较方便。但同时当m、n很大时,图上边、权及边线太多,易混淆,不利于实际操作。表上作业法和网络解法相比,运用网络图求解运输问题,可以更直观、快速、形象地得到初始解,并且该初始解更接近最优解或已经是最优解,可以大大减少计算工作量。但当产销地数量较多时,网络图绘制可能相对麻烦些。而表上作业法无论用闭回路法或位势法,其检验数的计算都比较麻烦,特别是当初始解选取不合理时,中间的运输量调整过程增多,计算量的增加是可观的。解决各种运输问题的算法有多种,但是每一种算法都有局限性,也就是说每一种算法都是在满足某些条件下给出的算法,而且这些算法分别解决某一项或两项问题的优化,无法兼顾所有情况。因此,在考虑实际运输问题优化的时候,有时必须综合地应用各种优化方法来解决问题,或采用不同的算法解决问题的不同环节的子问题优化,最终得到运输问题的最优方案。参考文献:1.HitchcockFL.TheDistributionofaProductfromSeveralSourcestoNumerousLocations.JournalofMathematicalPhysics,1941,20(4)2.G.B.Dantizig.Applicatio