货运车辆优化调度方法.doc

《货运车辆优化调度方法.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、货运车辆优化调度方法纪寿文1，缪立新1，李克强2，连小珉2摘要：本文首先介绍货运车辆调度问题的分类，根据问题的不同性质将货运车辆优化调度分为满载和非满载调度，有时间要求和无时间要求的调度等多种类型。然后，详细介绍求解货运车辆优化调度问题常用的启发式算法、神经网络方法和遗传算法的原理、模型和求解过程。文中还根据深圳市科技园的实际路网图，采用神经网络的方法对运输车辆优化调度进行试验研究，给出试验结果。本文所论述的方法对于实际的货运车辆调度问题具有指导意义。关键词：路径规划；启发式算法；神经网络；遗传算法引言据统计，美国2000年的运

2、输费用为5900亿美元，占当年GDP总值99600亿美元的5.92%，可见，减少运输费用是有效减少物流成本的重要方面。对于物流中心和第三方物流企业的货物配送，运输车辆的调度是工作的重点，正确合理的调度可以有效减少车辆的空驶率，实现合理路径运输，从而有效减少运输成本，节约运输时间，提高经济效益。1运输车辆调度规划问题分类货运车辆优化调度问题可根据不同性质具体分为以下几类[1~3]：按照运输任务分为纯装问题、纯卸问题以及装卸混合问题。按照车辆载货状况分为满载问题和非满载问题，满载问题是指货运量多于一辆车的容量，完成所有任务需要多辆运

3、输车辆。非满载问题是指车的容量大于货运量，一辆车即可满足货运要求。按照车辆类型分为单车型问题和多车型问题；按照车辆是否返回车场划分为车辆开放问题和车辆封闭问题，车辆开放问题是指车辆不返回其出发地，车辆封闭问题是指车辆必须返回其发出车场。按照优化的目标可分为单目标优化问题和多目标优化问题；按照有无休息时间要求可分为有休息时间的调度和无休息时间调度问题。实际中的车辆优化调度问题可能是以上分类中的一种或几种的综合。车辆优化调度问题是一个有约束的组合优化问题，属于NP难题（NondeterministicPolynomialProble

4、m）。随着问题输入规模的扩大，求解时间呈几何级数上升。求解车辆优化调度的方法可以分为精确算法、启发算法和智能算法。精确算法主要有分支界定法等；启发式算法主要有构造算法、两阶段法等；智能算法分为神经网络方法、遗传算法和模拟退火算法等。精确算法的计算量随着车辆优化问题规模的增大呈指数增长，如当卸货点的数目超过20个时，采用精确算法求解最短运输路径的时间在几个小时以上。精确算法不适合于求解大规模的车辆优化调度问题。2启发式算法启发式方法是从尚未安排的车辆、运输任务或行驶路径中按照构造算法进行选择，直到所有任务和车辆均被调度为止。构造的

5、每一步，根据某个判别函数，把当前的线路构形和另外的构形进行比较并加以改进，以最小代价把一个不在当前构形上的需求对象插入进构形，最后得到一个较好的可行构形。常见的构造算法有节约算法、最邻近法、最近插入算法等。启发式方法并不追求问题的最优解，而是强调问题解的满意性，只要决策者认为所得到的解能够较好的满足要求就可以了。集货或送货非满载车辆调度问题是车辆调度中的一个基本问题，下面简单介绍采用启发式算法求解的具体步骤：(1)模型的建立将车场编号为0，车辆编号为k，任务编号为1,2,…,l，考虑运输量约束、停车点车辆数目约束、集货和卸货时间

6、约束等约束，可定义如下的基本模型：式中，cij表示从点i到j的运输成本，它可以根据优化的目标具体体现为运输距离或运输费用或运输时间。xijk和yki为变量，定义为：式中，ETi和LTi分别为任务i允许的最早开始时间和允许的最迟结束时间；gi为第i点的货运量，q为运输车辆的额定载重量。(2)模型的求解C-W算法由Clarke和Wright提出，该算法简单易用，以改进的C-W节约启发式算法为例来求解车辆调度问题。其步骤如下：①首先计算各个点i和点j之间线路的费用节约值s(i,j)，形成集合M，并按照从大到小对s(i,j)进行排序，其

7、中：s(i,j)=ci0+c0j-cij。②若M为空，则终止叠代，否则对M中的第一项s(i,j)考察是否满足下列条件之一，如满足则转下步，否则转⑥。(a)点i和j均不在已构成的线路上；(b)点i和j在已构成的线路上，但不与车场相连；(c)点i和j位于已构成的不同线路上，均不与车场相连，且一个是起点，一个是终点。③考察点i和j连接后的线路上总货运量Q，若Q≤q，则转下步，否则转⑥④计算连接点i和j所在的线路后，车辆到达j点的时间比原路线上车辆到达j点的时间的变化量为：EFj=si+Ti+tij-sj。(a)若EFj＝0，转⑤；(b

8、)若EFj<0，则计算，当

9、EFj

10、≤，转⑤，否则转⑥；(c)若EFj>0，则计算，当

11、EFj

12、≤，转⑤，否则转⑥。式中，为线路上j点后面的各任务处均不需要等待的到达j点时间的最大允许提前量；为线路上j点后面的各任务不违反时间约束的到达j点时间的最大允许推迟量。