基于匈牙利算法的物资运输的车辆分派问题研究

摘要：针对物资运输的车辆分派问题本文利用匈牙利算法，从使得运输总费用最小的角度出发，构建了运输车辆模型及车辆分派模型，以求得最佳的车辆运输分派方案。

关键词：匈牙利算法；运输车辆分派；优化

中图分类号：TP18 文献标识码：A 文章编号：1671-864X（2016）03-0000-01

一、武警部队物资运输车辆分派问题的由来

运输武警部队后勤部的车辆运输成本是年度财政计划的重要部分，其合理的开支也是关系部队科学发展、高效转型的关键因素。然而在实际的运输过程中，武警部队运输成本居高不低，这除了国内形势日趋复杂、运输频率和数量增加的原因外，还与指挥人员合理安排运输车辆，采取最优的运输分配方案息息相关。要想降低车辆运输的基本成本必须从运输方式的选择、运输路线的规划、车辆任务的分派三个方面考虑。

二、分配问题及匈牙利法的相关理论研究

运筹学中的分配问题，或称指派问题（AssignmentProblem），是一种特殊的整数规划问题，在许多应用领域中会经常遇到，例如：有N项任务，分配给N个人完成，并指定每人完成其中的一项，每项任务只交给一个人去完成，应如何分配，使得费用最低。这是经典分配问题的一个实例，问题中的任务可能是任何类型的活动，人可能是任何类型的资源，费用可能是任何类型的效能。

分配问题最简单的处理方法，就是进行所有可能的分配，共有N 的全排列个（N！）分配方案，再从中选出最优解，但当N较大时，分配数将产生组合爆炸，当今的高速计算机也都无法处理。分配问题也是个线型规划问题，若用正规的单纯形法，或借助于运输问题特点的一些特殊方法，也可以用来解决这个问题，但效果不好。

而一种称为“匈牙利法”的分配算法，是目前被认为是用来解决分配问题的最有效算法，“运筹学”和“最优化技术”等专著，都将它作为标准的算法进行介绍。 “匈牙利法”的计算基础和前提是：从效能矩阵的每一行（每一列）元素中分别减去（或加上）一个常数，使得每一行（每一列）里至少有一个0元素，得到新的效能矩阵，用它来取代原效能矩阵，将不改变分配问题的最优解。

三、武警部队物资运输路线的选择

武警部队物资运输路线的选择，主要是选择出发城市到任务城市的最短路径。不同运输方式的路线选择也不同。最短路径的度量单位可能是时间最短、距离最短或费用最小等。运输路线选择是将运输模式和路线选择结合在一起，因为路线选择的可能性在很大程度上取决于运输模式。一般而言路线选择问题可以分为以下几类：（1）中间点相同，起讫点不同；（2）中间点不同，但起讫点相同；（3）多个起点，多个终点，没有中间点；（4）多个起点，多个终点，有中间点或转运点。

假设某军工厂从生产站点A运输防爆武器装备器材，服务三个不同地点的军需地B、C、D。

从站点生产A到各军需地的距离为AB=22，AC=31，AD=45，BC=18，BD=27，CD=38。

现求解最佳的运输路线。

求解步骤如下：军需地B距离A最近，故先选军需地B；军需地C距离B最近，故选择C；只剩下军需地D没选，故选择D，然后返回军需地A，形成一条回路：A—B—C—D—A。总里程为123公里。需要说明的是，由于军需地D点与最后返回的军需地A点实际上并非最优选择，所有这种方法球的解也并不一定是最优解，只能是近似最优解。

关于一辆车一条路线上的任务安排，相当比较容易。而对于若干辆车服务于若干个任务的齐次运输任务的分派，则需要借助于运输模型的构建和求解。

四.基于匈牙利算法的最优方案求解

假定一个军工厂公司有两辆（A和B）载重量为5吨和三辆（C，D，E）载重量为lO吨的卡车，某天有5项防爆武器装备器材运输任务，不同的车辆完成任务的费用关系如表1所示。WA=（5，13，9，6，7），WB=（8，2，7，9，5），WC=（7，6，8，4，10）， WD=（9，7，10，3，6）， WE=（10，11，3，8，9）。

上述的军用运输车辆分派模型要求分派方案的总费用最小。可用匈牙利法求解，具体步骤如下：

（1）将表1构成矩阵形式，找出每一行中最小的费用元素，并用每一行减去对应的最小元素，构成每行都出现0元素的新矩阵。然后找出新矩阵中每一列的最小元素（包括0），用每一列将去该列对应的最小元素，这样便构成了每一行每一列都有0元素的新矩阵。

（2）在新矩阵中，画出能覆盖所有0元素的最少直线（横线或竖线，不含斜线）。如果直线的数目等于行或列的数目（n=5）便停止，得到最优解。如果直线数小于行或列的数目（n<5），则需进行第三步。本例新矩阵中，只需4条直线便可覆盖所有0元素，故有待进一步求解。

（3）在画完直线的新矩阵中，找出没有被直线覆盖的非0元素最小值（本例中最小非0元素为1），然后再没有画直线的各行上都减去这个非0元素，同时，再已画直线的各列上加上这个非0最小元素，得到新的矩阵。

（4）此时，能覆盖所有0元素的最少直线等于行或列数（n=5），得到了最优解，即最有车辆分派方案：第A辆车分派任务1，第B辆车分派任务2，第C辆车分派任务4，第D辆车分派任务5，第E辆车分派任务3。这种情况下，车辆任务分派总费用为20，为最优解。

对于拥有较多军用运输车辆、任务较多的情况，必须合理安排好每一辆车的任务分派。构建好齐次运输的费用计算模型，可以较为准确、快速地求出最优解，使得单次运输总成本最低。

参考文献：

[1]徐小林.基于匈牙利算法的多车型车辆调度问题.火力与指挥控制，2009.2

[2] 范鸣玉，张莹.最优化技术基础[M].北京：清华大学出版社，1982.

[3] 郭耀煌.运筹学与工程系统分析[M].北京：中国建筑工业出版社，1986.

作者简介：黎珂佚（1986.06-），武警警官学院管理系，讲师，硕士，研究方向：武警管理学。