线性规划算法在车辆调度中的应用[全文].doc

线性规划算法在车辆调度中的应用

徐香

摘要

线性规划的理论和方法都比较成熟具有广泛的应用价值 在企业管理的各个领域都

发挥着重要作用本文对线性规划问题在车辆调度问题中的应用进行了研究认为采用线性规

划调派车辆可以压缩企业的运输成本提高企业竞争力首先我们介绍线性规划理论及其在一

般运输问题中的应用然后将其推广到车辆调度问题车辆调度问题是指在车辆数量一定的

情况下如何根据用户的需要静态的或动态的合理地调度有限的车辆资源从而最大程度满

绪论

车辆调度问题是指在车辆数量一定的情况下，如何根据用户的需求（静态的或动态的）合

理地调度有限的车辆资源，从而在最大程度满足拥护需要的前提下（约束条件）使运输成

本降到最低（目标函数）。该问题自提出以来，为了缓解城市交通压力，提高运输效率，

国内外专家、学者做了大量的研究，并针对不同的实际情况，提出了很多关于车辆调度问

题的模型和算法。

但是，纵观国内外学者关于运输调度问题的研究，大多属于车辆行程安排（一点到一点或

者一点到多点）的优化问题，或是适应一些特殊的情况。此外，由于缺少现代电子通讯技

术和全球定位技术的支持，调度中心既不能实时地掌握车辆信息和任务的变化，也不能在

车辆之间的进行实时通信，所采用的调度方法也大都是静态、封闭式的。因此，上述研究

具有较大的局限性，难以满足日益复杂的现代车辆调度任务的需要。

针对上述问题，本文利用先进的全球定位技术、无线通讯技术，运用动态规划理论，提出

并建立了一个动态的、开放的现代智能车辆管理调度系统。该系统可以实时监控车辆和对

车辆进行实时通讯，对任意时刻的任务请求和突发性事件都可以做出合理的调度。

对于运输问题，寻找较优的初始方案非常重要，在这个模型中，我们利用指派问题的匈牙

利法思想，并对它进行了推广，对运输问题建立了确定初始方案的一种新的计算方法——

函数的最大和最小值问题一般数学描述如下



 

!"

#

其中

…

称为目标函数$%&'"()'

&*…称为价值函数+!"+,'"

+*…称为价值向量&*…称为求解变量由系数组成的矩阵称

-*

为约束矩阵+!""".列向量 %*称为右端向量条件&称为

非负约束若某个向量 .*满足约束条件则称为可行解和可行点)!%/"记为 

对于一个线性规划问题必有以下三种情况

当 *其中表示空集时则该问题无解或不可行

（#）当 但是目标函数在  上无解时则称该问题无解

（）当 且目标函数有有限的最优解则该问题有最优解

#运输问题

相反的运输问题可以说是线性规划算法的起源因此运输问题可以说是线性规划算法的起

6

-* 行

求一组变量*#…8&*#…的值使它满足约束条件：

并且使目标函数 1*的值最小总运量最少

#车辆调度的数学模型

#问题的提出

车辆调度问题可以说是一种特殊的运输问题但与运输问题相比有所不同调度问题与实际问

题结合得更为紧密考虑的约束条件也比运输问题多因此它的复杂程度要远远大于运输问题

首先是对象的不同运输问题的对象是货物而调度问题的对象通常是人货物可以按照汽车

的载量不同分几次运输而人要尽可能一次接送其次运输问题一般对时间的要求不是非常

苛刻但在调度问题中时间便显得尤为重要此外运输问题一般行程长而调度问题涉及的主

要范围在城市所以对路径的选择也非常重要

##动态规划算法

用到调度问题中就是在第一个时间段 " 内对所有车辆根据需求做一次规划得出最佳的派遣

此递推便可得到每个时间段内最佳的调度方案

#模型的描述

养路费以及其它相关因素综合给出的为了减小调度模型的复杂度我们把车辆分为大、

中、小1三种车型当申请使用中型车时只能派遣大车和中型车中无任务的车

辆8当申请使用大车时只能派遣大车中无任务的车辆

在某个时段 " 内有  项车辆请求任务任务请求地点在数字地图上的坐标为*#…目

位置精确显示在监控中心的数字地图上其位置为&*#…/那么在数字地图上我们可以得

出任一车辆到任务申请地点的距离用表示车辆 & 到申请位置  的位置

根据以上假设有关车辆调度模型的数学表示如下设调度的总成本为 4

4**:

其中

*

由于每辆车只能完成一项请求所以约束条件Ⅰ 为

;

又由于每项请求只能由一辆车完成所以约束条件Ⅱ 为

<

4*'.=

!"

满足上述条件的一个可行解还可以表示为矩阵形式

.**

另外我们把矩阵 '*称为效率矩阵其中表示把车辆 & 派到任务  的运输成本

车辆调度模型的解法

 规划

在线性规划问题中一般情况下决策变量都是连续变量其最优解可以出现分数或小数但

在实际问题中有时要求决策变量只取整数值如果在解中出现分数或小数就不合要求要求

决策变量取整数值的数学规划问题称为整数规划问题如果只要求部分变量而不是全部变量

取整数值称为混合整数规划问题或称纯整数规划问题在应用中有大量的整数规划问题要

求决策变量只取  两个值这种特殊类型的整数规划问题称为  规划问题

#分派问题