基于线性规划模型的物流运输调度问题研究

安立军，刘 进，郝建林,2

（1.承德石油高等专科学校，河北 承德 067000；2.河北大学 管理学院，河北 保定 071000）

1 引言

物流运输调度问题是指物流企业在一定数量车辆的情况下，通过静态或动态的方法求解满足客户需求的车辆调度问题。在物流产业发展初期，由于物流企业的规模较小、管理方式落后以及经验缺乏等原因，导致物流运输的调度成本偏高，从而抑制了物流运输调度的发展，也导致客户满意度普遍偏低。现代物流产业的发展，采用先进的运输技术和高效的管理方法，能够实时根据客户的需求来制定相应的物流运输调度方案。因此，物流运输调度是降低物流企业成本、提高其运行效率的有效方法。

基于此，本文将现代化无线通讯技术和GPS技术相结合，运用动态的线性规划模型，建立现代化物流运输调度管理系统，利用匈牙利算法求解物流运输中的调度问题，并运用实例来分析这种算法的有效性。

2 线性规划理论

线性规划问题（LP）是指在一定的人力、物力、财力等的条件下，设计一种运输方案，以达到某个目标（如成本最小化）。用数学语言描述为：求一个线性函数在一组线性的等式或不等式条件约束情况下的最小值或最大值问题。由于线性规划问题可采用对偶方法求解，因此可将最小值问题转化为最大值问题。本文以最大值为例，规定线性规划问题的标准形式是：

改写成累加的形式，具体如下所示：

其中c1x1+c2x2+…+cnxn为目标函数；x1,x2,…,xn分别代表n种不同的资源，也就是求解变量，其值均不能为负值；c1,c2,…,cn是价值系数向量，由aij组成的矩阵为约束矩阵，向量bi表示资源的限制，标准形式的定义规定等式右边的bi≥0，否则要进行相应的转化才能成为线性规划问题的标准型。

线性规划问题解法有很多种，可采用坐标轴画图、分析可行域和可行解得到。但由于物流调度的约束条件太多，导致这种方法并不可行。此外，单纯形法也不适合求解约束条件过多的调度问题。因此，本文采用匈牙利方法来求解此类问题。

3 物流运输调度的数学模型

物流运输调度问题是一种特殊的运输问题，调度问题的约束条件比一般的物流运输问题多，且更需要结合实际，导致其复杂程度也远大于运输问题。物流调度的对象一般是运输车辆，且调度问题涉及的行程也较长，因此需要选择最佳的调度路径。

在物流运输调度时，由于车辆选择具有较强的随机性，导致很难预测下一时刻需求的车辆数量、车辆类型以及需求所在地点。因此，物流运输调度需要采用动态线性规划的方法，将调度问题按时间分为若干个阶段，每个阶段需要做出相应的决策，最终实现最优的调度结果。在车辆的调度问题中，本文将车辆分为大（L）、中（M）、小（S）三种类型，在每一个时间段t内，根据客户需求对车辆进行一次规划，得出最佳的调度方案。为了简化物流运输调度问题，需要在每个阶段的前期对车辆使用情况进行检查，根据车辆调度的约束条件，排除一些无法完成任务的车辆，对剩余的车辆进行调度处理，将任务的运输调度成本降到最低。

假定物流运输中心共有n辆车辆，每辆车每公里的运输费用为ci（i=1,2,…,n），运输费用包括燃油费、人工费及其他相关费用。在某个时间段t内，共有m项运输调度的请求任务，任务地点的坐标分别为（xi,yi），i=1,2,…,m。此时，共有l辆可供调度的车辆，其中l≥m。根据GPS定位系统可知，每辆可供调度车辆的地理位置为（Xi,Yi），i=1,2,…,l。可采用大中小三种车型进行调度，若可以派遣任意一种没有任务的车型时，可采用小车进行调度，若无小车，则中型、大型车按顺序依次替补；若申请调度中型车时，则可派遣中型车，当无中型车时，则采用大型车来替补；若申请调度大型车时，则只能派遣大型车。

根据上述假定，可知在t时间段内，物流运输调度模型的调度总成本z表达式如下：

其中cj表示第j辆车每公里的运输费用；dij表示第j个车辆到第i个客户的距离；xij为车辆的调度情况，其值可表示如下：

由于每辆调度车辆仅能完成一项请求，则该运输调度约束条件可表示为：

由于每项请求有且仅有一辆车辆完成，则该运输调度约束条件可表示为：

根据式（4）、（5）、（6），可将物流调度问题改写为：

其中x为解矩阵，c为效率矩阵，A为约束矩阵，具体可表示如下：

匈牙利算法的基本思想是设法调整矩阵c的元素，使得新的效率矩阵c′的每一行和每一列至少含有一个零元素，但是不能存在负数。当然，在线性变化的过程中，要求新效率矩阵与原效率矩阵是等效的，即所表达的调度问题存在相同的可行解。若存在这样的新效率矩阵，则对应的c'的不同行不同列的零元素，在解矩阵中的相应位置的元素为1，其余的元素全部为零，那么就得到了调度的最优解，也就是总运输成本最低下的调度方案。新的效率矩阵与原效率矩阵所表达的目标函数值，只相差一个常数，表明新问题与原问题具有相同的解。

当请求数量与调度车辆不相等时，可采用虚拟调度请求，将其完成的成本设为0，即在效率矩阵下面添上k行，其中k为请求数量与调度车辆两者之间的差值，再用匈牙利算法来求解调度问题。

4 案例分析

某物流企业在t时刻共有6个调度请求，此时共有12辆可供调度的汽车，假定它们均能在任务要求的时间内到达任务的指定地点。在这12辆汽车中，大中小三类车辆均有，其中大、中、小型车辆每公里的运行成本分别为4元、3元和2元。

表1 物流运输调度车辆与任务地点的运输距离

根据GPS、GIS和GSM技术，可以准确的测定车辆与任务地点的距离，具体的调度车辆与任务地点之间的距离见表1。

根据调度车辆的运输距离以及各个车辆的运输费用和任务要求的车辆，可得物流运输调度成本，见表2。

表2 物流运输调度的成本

根据表2可知，效率矩阵可表示如下：由于可供调度的车辆与任务请求的数量不等，为了满足车辆调度与请求数量相等这一条件，本文将虚构六个请求，则可得到新的效率矩阵，具体如下：

首先，调整效率矩阵，使其每一行和每一列都至少含有一个零元素，具体的做法可仿照线性规划中的线性变化方法，从c的每一行减去该行的最小元素，可得如下的新效率矩阵：

在矩阵c'中，选出不同行不同列的12个零元素，具体的做法是从0元素最少的行开始标记，直到标出所有的零元素。依照上述的算法，可得该物流运输调度问题的最优解矩阵为：

根据最优解矩阵可知：调度车辆8完成请求任务1，调度车辆3完成请求任务2，调度车辆10完成请求任务3，调度车辆6完成请求任务4，调度车辆11完成请求任务5，调度车辆9完成请求任务6。根据匈牙利算法可知，最优的调度成本为：

将匈牙利算法得出的结果与表2对比可知，该调度方案是最佳方法，是所有调度中成本最低的，通过这一处理可以非常迅速地获得最优方案，避免了复杂的矩阵乘法运算，提高了物流运输调度方案的决策效率，非常适合高阶的矩阵运算。

5 结语

线性规划理论在运输问题中有着广泛的用途，本文建立了物流运输的调度系统模型，该系统实时监控物流企业的车辆，并与车辆进行实时通讯，及时响应任意时间每一个客户的需求，及时处理物流运输中的突发事件和临时性请求，完善物流企业的运输调度管理。

[1]覃运梅.多源点物流配送车辆调度模型探讨[J].物流科技,2010,(9):32-35.

[2]李惠珠,宋海清.基于GIS的物流配送车辆调度实现与应用[J].长春师范学院学报(自然科学版),2011,30(2):20-24.

[3]曹克官,陈峰.多车辆直运越库调度的建模与启发式算法[J].上海交通大学学报,2009,43(9):1403-1406,1416.

[4]裴志松.一种新型物流调度算法的优化研究[J].长春工程学院学报(自然科学版),2011,12(2):117-119.

[5]张建中,许绍吉.线性规划[M].北京:科学技术出版社,1997.

[6]张潜.物流配送路径优化调度建模与实务[M].北京:中国物资出版社,2006.