《线性规划算法在车辆调度中的应用》由会员分享，可在线阅读，更多相关《线性规划算法在车辆调度中的应用（35页珍藏版）》请在金锄头文库上搜索。
1、线性规划算法在车辆调度中的应用 徐香摘 要线性规划的理论和方法都比较成熟,具有广泛的应用价值3.在企业管理的各个领域都发挥着重要作用.本文对线性规划问题在车辆调度问题中的应用进行了研究,认为采用线性规划调派车辆可以压缩企业的运输成本.提高企业竞争力.首先我们介绍线性规划理论及其在一般运输问题中的应用,然后将其推广到车辆调度问题,.车辆调度问题是指在车辆数量一定的情况下,如何根据用户的需要(静态的或动态的)合理地调度有限的车辆资源,从而最大程度满足用户需要(约束条件)，并使运输成本降到最低(目标函数),它是运输问题的特殊情形,也是0-1规划的特殊情形.运输问题既然是一种线性规划问题当然可以用单纯
2、形法求解,但解这个模型较简便的方法是匈牙利法,最后我们介绍了把匈牙利法推广到求解一般运输问题的方法，并建立了确定运输问题初始方案的广义匈牙利法。【关键词】线性规划 车辆调度 匈牙利法 最小元素法 运输问题 绪论车辆调度问题是指在车辆数量一定的情况下，如何根据用户的需求（静态的或动态的）合理地调度有限的车辆资源，从而在最大程度满足拥护需要的前提下（约束条件）使运输成本降到最低（目标函数）。该问题自提出以来，为了缓解城市交通压力，提高运输效率，国内外专家、学者做了大量的研究，并针对不同的实际情况，提出了很多关于车辆调度问题的模型和算法。但是，纵观国内外学者关于运输调度问题的研究，大多属于车辆行程安
3、排（一点到一点或者一点到多点）的优化问题，或是适应一些特殊的情况。此外，由于缺少现代电子通讯技术和全球定位技术的支持，调度中心既不能实时地掌握车辆信息和任务的变化，也不能在车辆之间的进行实时通信，所采用的调度方法也大都是静态、封闭式的。因此，上述研究具有较大的局限性，难以满足日益复杂的现代车辆调度任务的需要。针对上述问题，本文利用先进的全球定位技术、无线通讯技术，运用动态规划理论，提出并建立了一个动态的、开放的现代智能车辆管理调度系统。该系统可以实时监控车辆和对车辆进行实时通讯，对任意时刻的任务请求和突发性事件都可以做出合理的调度。对于运输问题，寻找较优的初始方案非常重要，在这个模型中，我们利
4、用指派问题的匈牙利法思想，并对它进行了推广，对运输问题建立了确定初始方案的一种新的计算方法广义匈牙利法。这种方法将原问题经过某种等价交换，然后根据变换后的运输问题给出一种比最小元素法更具有全局概念的就近供应算法，通过数值计算表明，广义匈牙利法对很多问题获得的初始方案往往就是原问题的最优方案。1 线性规划理论1.1 一般描述线性规划是科学与工程领域广泛应用的数学模型,它研究一个线性函数在一组由线性等式或不等式组成的约束条件下的极值.在工农业生产、交通运输、财贸工作等各项经济活动中,必须提高经济效果,做到耗费较少的人力、物力、财力,创造出较多的经济价值.这就是运筹学研究的内容.运筹学是一门应用科学
5、,线性规划作为运筹学的一个基本分支,是实现管理现代化的有力工具,线性规划问题(Linear Programming)就是在一组线性的等式或不等式的约束之下,求一个线性函数的最大和最小值问题.一般数学描述如下: min( EMBED Equation.3 + EMBED Equation.3 EMBED Equation.3 + EMBED Equation.3 + EMBED Equation.3 ) (1) s.t EMBED Equation.3 EMBED Equation.3 (2) 其中: EMBED Equation.3 + EMBED Equation.3 EMBED Equat
6、ion.3 + EMBED Equation.3 + EMBED Equation.3 称为目标函数 (Objective Function) (j=1,n)称为价值函数.(Cost Coefficient) C= (,)称为价值向量,(j=1, n)称为求解变量.由系数组成的矩阵,称 A= 为约束矩阵.(Constraint Matrix).列向量b=称为右端向量,条件 EMBED Equation.3 0(1jn)称为非负约束.若某个向量x=满足约束条件,则称为可行解和可行点 (Feasible Point).记为D. 对于一个线性规划问题,必有以下三种情况:当D=,其中表示空集时,则该问
7、题无解或不可行.（2）当D,但是目标函数在D上无解时,则称该问题无解.（3）当D,且目标函数有有限的最优解,则该问题有最优解.求解线性规划问题时需要判别该问题属于哪一种情况,当问题有最优解时,还要在可行区域中找出使目标函数达到最小(或最大)的点,也就是最优解(Optional Solution),以及目标函数的最优解2. 1.2 运输问题运输问题是一类特殊的线性规划问题,从历史角度来说并非有了单纯型法才去研究运输问题,相反的,运输问题可以说是线性规划算法的起源.因此,运输问题可以说是线性规划算法的起源,现实生活中的很多问题都可以转化为运输问题来求解.假设有m个产地,每个产地的产量分别为,另有n
8、个销地,每个销地需求量分别为,表示从产地运往销地的单位运输费用,是决策变量,表示产地运往销地的调运量,则运输问题的一般数学形式如下:min(f)= (3)s.t (4) (调运量不能为负)特殊的,当=时,上述问题转化为产销平衡问题,写成矩阵形式如下: (5)A=m+n行如果运输问题中,没有产销平衡这一限制,当产大于销时(即>),这一问题的数学模型应为:求一组变量(i=1,2,m;j=1,2,n)的值,使它满足约束条件：并且使目标函数S=的值最小.(总运量最少)2 车辆调度的数学模型2.1 问题的提出车辆调度问题可以说是一种特殊的运输问题,但与运输问题相比有所不同,调度问题与实际问题结合得
9、更为紧密,考虑的约束条件也比运输问题多,因此它的复杂程度要远远大于运输问题.首先是对象的不同,运输问题的对象是货物,而调度问题的对象通常是人.货物可以按照汽车的载量不同分几次运输,而人要尽可能一次接送.其次,运输问题一般对时间的要求不是非常苛刻,但在调度问题中,时间便显得尤为重要.此外,运输问题一般行程长,而调度问题涉及的主要范围在城市,所以对路径的选择也非常重要.2.2 动态规划算法在车辆调度的时候,由于车辆请求的随机性,因此很难预测下一时刻的车辆需求量、需求的车辆类型以及需要的地点.所以,必须采用动态规划的方法来进行车辆调度管理.所谓动态规划就是按时间分为若干阶段,每个阶段都需要做出决策,
10、以便在过程的最后达到最优的结果.应用到调度问题中,就是在第一个时间段t内,对所有车辆根据需求做一次规划,得出最佳的派遣方案.等到下一个时间段,再根据该车辆的需求和目前无任务的车辆情况再做相同的规划.如此递推,便可得到每个时间段内最佳的调度方案.为了简化车辆调度问题,必须在每个阶段的初期对车辆便用情况进行检查,按照一定的约束条件,排除一些不可能用来完成任务的车辆,再对剩余的车辆进作调度处理,使完成任务的运输成本减少到最低限度.首先,要排除那些已经有任务要执行的车辆,这些车辆只能在它们完成任务,并把空车信息通过短信方式报告到调度中心后,才能重新参与调度.其次,任务不能无限期等待,只有在请求任务限定
11、的时间内能够到达任务地点的车辆才能够被调度使用.这样,就把可供调度的车辆的范围缩小到那些既没有任务又可以按时间到达任务请求地点的车辆3.2.3 模型的描述假设:运输中心的车辆有n辆,每辆车每公里的运输费用为(i=1,2,n),它是根据每公里的耗油量、养路费以及其它相关因素综合给出的.为了减小调度模型的复杂度,我们把车辆分为大(B)、中(M)、小(S)三种车型,当申请使用中型车(M)时,只能派遣大车(B)和中型(M)车中无任务的车辆;当申请使用大车(B)时,只能派遣大车(B)中无任务的车辆.在某个时段t内有m项车辆请求任务,任务请求地点在数字地图上的坐标为(,), i=1,2,m.目前可以用来调
12、度的无车辆任务的车辆共有l(im)辆，由于每辆车上都装有GPS系统,它们的位置精确显示在监控中心的数字地图上,其位置为(,),j=1,2,l.那么,在数字地图上我们可以得出任一车辆到任务申请地点的距离,用表示车辆j到申请位置i的位置.根据以上假设,有关车辆调度模型的数学表示如下(设调度的总成本为f): min(f)= (6)其中: =由于每辆车只能完成一项请求,所以约束条件-为: (7)又由于每项请求只能由一辆车完成,所以约束条件-为: (8)用矩阵表示: min(f)=cx (9)s.t. Ax=1,x0 (10)式中,x=C=(, ,)=( EMBED Equation.DSMT4 EMB
13、ED Equation.DSMT4 ); A=m+n行 满足上述条件的一个可行解()还可以表示为矩阵形式: x =称x为解矩阵.满足上述条件的解矩阵每一行有且只有一个元素为1,其余元素为0;它的每一列也有且只有一个元素为1,其余元素为0. 另外,我们把矩阵c=称为效率矩阵,其中()表示把车辆j派到任务i的运输成本.3 车辆调度模型的解法3.1 0-1规划 在线性规划问题中,一般情况下,决策变量都是连续变量,其最优解可以出现分数或小数.但在实际问题中,有时要求决策变量只取整数值,如果在解中出现分数或小数就不合要求.要求决策变量取整数值的数学规划问题称为整数规划问题.如果只要求部分变量而不是全部变量取整数值,称为混合整数规划问题(或称纯整数规划问题).在应用中有大量的整数规划问题要求决策变量只取0,1两个值,这种特殊类型的整数规划问题称为0-1规划问题.3.2 分派问题 分派问题也是计划管理中常见的一类特
