《货运车辆优化调度方法》由会员分享，可在线阅读，更多相关《货运车辆优化调度方法（11页珍藏版）》请在金锄头文库上搜索。
1、货运车辆优化调度方法纪寿文 1， 缪立新 1， 李克强 2，连小珉 2 摘要 ：本文首先介绍货运车辆调度问题的分类，根据问题的 不同性质将货运车辆优化调度分为满载和非满载调度，有时 间要求和无时间要求的调度等多种类型。然后，详细介绍求 解货运车辆优化调度问题常用的启发式算法、神经网络方法 和遗传算法的原理、模型和求解过程。文中还根据深圳市科 技园的实际路网图，采用神经网络的方法对运输车辆优化调 度进行试验研究，给出试验结果。本文所论述的方法对于实 际的货运车辆调度问题具有指导意义。关键词 ：路径规划；启发式算法；神经网络；遗传算法 引言据统计，美国 2000 年的运输费用为 5900 亿美元，
2、占当 年GDP总值99600亿美元的5.92%，可见，减少运输费用是 有效减少物流成本的重要方面。对于物流中心和第三方物流 企业的货物配送，运输车辆的调度是工作的重点，正确合理 的调度可以有效减少车辆的空驶率，实现合理路径运输，从 而有效减少运输成本，节约运输时间，提高经济效益。1 运输车辆调度规划问题分类货运车辆优化调度问题可根据不同性质具体分为以下 几类13 ： 按照运输任务分为纯装问题、纯卸问题以及装卸混合问 题。按照车辆载货状况分为满载问题和非满载问题，满载问 题是指货运量多于一辆车的容量，完成所有任务需要多辆运 输车辆。非满载问题是指车的容量大于货运量，一辆车即可 满足货运要求。按照
3、车辆类型分为单车型问题和多车型问题；按照车辆 是否返回车场划分为车辆开放问题和车辆封闭问题，车辆开 放问题是指车辆不返回其出发地，车辆封闭问题是指车辆必 须返回其发出车场。按照优化的目标可分为单目标优化问题和多目标优化 问题；按照有无休息时间要求可分为有休息时间的调度和无 休息时间调度问题。实际中的车辆优化调度问题可能是以上分类中的一种 或几种的综合。车辆优化调度问题是一个有约束的组合优化问题，属于NP 难题( Nondeterministic Polynomial Problem )。随着问 题输入规模的扩大，求解时间呈几何级数上升。求解车辆优化调度的方法可以分为精确算法、启发算法 和智能算
4、法。精确算法主要有分支界定法等；启发式算法主 要有构造算法、两阶段法等；智能算法分为神经网络方法、 遗传算法和模拟退火算法等。精确算法的计算量随着车辆优化问题规模的增大呈指 数增长，如当卸货点的数目超过 20 个时，采用精确算法求 解最短运输路径的时间在几个小时以上。精确算法不适合于 求解大规模的车辆优化调度问题。2 启发式算法启发式方法是从尚未安排的车辆、运输任务或行驶路径 中按照构造算法进行选择，直到所有任务和车辆均被调度为 止。构造的每一步，根据某个判别函数，把当前的线路构形 和另外的构形进行比较并加以改进，以最小代价把一个不在 当前构形上的需求对象插入进构形，最后得到一个较好的可 行构
5、形。常见的构造算法有节约算法、最邻近法、最近插入启发式方法并不追求问题的最优解，而是强调问题解的 满意性，只要决策者认为所得到的解能够较好的满足要求就 可以了。集货或送货非满载车辆调度问题是车辆调度中的一个 基本问题，下面简单介绍采用启发式算法求解的具体步骤：(1) 模型的建立将车场编号为0，车辆编号为k,任务编号为1,2,l , 考虑运输量约束、停车点车辆数目约束、集货和卸货时间约 束等约束，可定义如下的基本模型：i至打的运输成本，它可以根据优化minzZzC ij.X ijkijkIigiy kiq-kLyki=1i二 1 ,.,lkIiXijkykii 二0 ,1，l ; - kLjXi
6、jkykjj =0,1，l ; - kETis iLTii二 1，l式中，Cij表示从点的目标具体体现为运输距离或运输费用或运输时间。Xijk和y为变量，定义为:yki =r 点i的任务由车辆k完成0 否则r 1 车辆k从点i行驶到点jXjk二0否则式中，ET和LT分别为任务i允许的最早开始时间和允许的最迟结束时间；gi为第i点的货运量，q为运输车辆的额定载重量。(2)模型的求解C-W算法由Clarke和Wright提出，该算法简单易用，以改进的C-W节约启发式算法为例来求解车辆调度问题。其 步骤如下： 首先计算各个点i和点j之间线路的费用节约值 s(i,j )，形成集合M并按照从大到小对 s
7、(i,j )进行排序，其中：s(i,j )=Cio+Coj-Cij 。 若M为空，则终止叠代，否则对M中的第一项s(i,j) 考察是否满足下列条件之一，如满足则转下步，否则转。(a) 点i和j均不在已构成的线路上；(b) 点i和j在已构成的线路上，但不与车场相连；(c) 点i和j位于已构成的不同线路上，均不与车场相连，且一个是起点，一个是终点。 考察点i和j连接后的线路上总货运量Q若CK q则转下步，否则转 计算连接点i和j所在的线路后，车辆到达 j点的时间比原路线上车辆到达j点的时间的变化量为： EFj=si+Ti+tij-sj。(a) 若EF = 0,转；(b) 若EFj 0 ,则计算 j
8、,当| EF| j,转，否则转 。式中，刁为线路上j点后面的各任务处均不需要等待的到 达j点时间的最大允许提前量；j为线路上j点后面的各任务不违反时间约束的到达j点时间的最大允许推迟量。其中：j_ 二 min ETr ?j 二 minLTSr ? 连接点i和点j，计算车辆到达各任务时的新时间。令M = M -s(i ,j),转以上是针对单车场的车辆优化调度问题的求解，多车场 问题可以转化为单车场问题来处理，首先确定每个车场完成 的任务，然后再求解。3 人工智能算法3.1 遗传算法遗传算法主要由选择、交叉和变异三个算子组成，分别 模仿自然界进化过程中的自然选择和群体遗传过程中发生 的交配和突变等
9、现象。采用遗传算法求解车辆优化调度问题 时，一般按照以下步骤进行：(1) 确定染色体的编码和初始群体采用自然数对可行线路进行编码，如长度为 l m 的染 色体可写为：(0, i11,i12,i1s, 0,i 21,i 2t ,0,，0, iml,，i mr)其中， i kj 表示第 i kj 项任务，这样的染色体结构可理解为车 辆从车场0出发，经过任务i 11, i 12,，i 1S后回到车场0, 形成子路径1；然后又从车场0出发，经过任务i21,，i2t 后返回车场，形成路径2,如此反复，直到所有的m项任务全部被完成为止。在子路径 1 内交换 i 11 和 i 12的位置表示行 走路径的改变
10、,也使函数目标改变,这样,下面的遗传叠代 可使函数目标最小,也即趋向于最佳或较佳的路径。初始群体的产生采用随机方法,随机产生 l 个城市的全 排列，根据任务的源点和汇点将 0标准插入排列中，形成一 条初始染色体。如此反复，直到满足群体数，群体数一般大 于20个。(2) 确定适应度函数车辆调度的优化目标有多种多样，常见的目标有总运费 最小，总运输时间最短，空载车总运行时间最小，完成任务 所需的车辆最小总运输时间最短，空载车总运行时间最小， 完成任务所需的车辆最小等，以总运费最小为例，其目标函 数为：m nC = min 工二 GjXjji =1 j式中，C为从源点i到汇点j每辆车的单位费用，Xi
11、 为每班从源点i到汇点j的满载车的数量。mn为源点和汇 点的数目。(3) 处理约束为保证车辆调度优化的正确性，约束往往必不可少，常见的约束有汇点处理能力约束，非负约束，车流连续性约束。一般采用惩罚的方法来处理约束，如果一个染色体对应 的解违反了某个约束，根据其违反程度给予一定的惩罚，使 其具有较小的适应度值。这样在不损失群体数目的基础上， 随着叠代的进行，使不可行解的数目在群体中所占比例越来 越小，可行解的数目则逐渐增加，并趋向最优解。(4) 遗传算子 经典的遗传算子包括复制、交叉、变异。复制算子的目 的是保留优良个体，避免基因缺失，提高全局收敛性和效 率。目前常用的复制算子有放回式随机复制又
12、称轮盘赌复 制，无放回式随机复制等十几种。交叉算子的作用是组合出新的个体 ，在染色体空间进行 有效搜索，同时降低对有效模式的破坏概率。染色体采用自 然数编码时，交叉算子一般有部分匹配交叉，顺序交叉，圈 交叉等。染色体采用二进制编码时，常采用的交叉算子有单 点交叉，双点交叉等。交叉算子中采用的交叉率一般在 0.750.95 之间。变异算子是为了克服基因缺失和不成熟收敛 。目前常用 的变异算子有常规位变异，均匀变异和非均匀变异等。变异 算子的变异率一般为 0.0050.01 o除了上述的经典遗传算子外 ，人们又研究了其他一些算 子，称为高级算子，如显性算子、倒位算子、分离和易位算 子、迁移算子等。
13、(5) 确定调度方案 通过上述的遗传操作，产生性能最优的染色体串，根据 初始的编码规定将该串解码成最优调度方案。实用中，人们往往将遗传算法与其他方法如启发式方法 和模拟退火算法杂合，以及将调度专家经验融入模型和遗传操作中，以提高求解的效果。3.2 神经网络算法人们经常采用 Hopfield 网络和自组织特征映射神经网 络来解决车辆的优化调度问题。在 Hopfield 网络中，系统 能够从初始状态，经过一系列的状态转移而逐渐收敛于平衡 状态，此平衡状态是局部极小点。采用神经网络来求解车辆 调度问题时，一般按下列步骤进行：(1) 产生邻接矩阵 将车辆的源点、所经过的各个汇点和停点抽象成网络的 结点
14、，它们之间的有向路径抽象成网络的边，由此构成一个 有向图G=(N,L,D),其中N表示结点数，L表示边数，D为N x N的矩阵，称为邻接矩阵。如果两个结点间存在路径，则 邻接矩阵相应元素的值为路径的长度；如果两个结点间不存 在路径，则邻接矩阵相应元素的值为(2) 约束的处理对于车辆调度中的约束， 将其作为神经网络的一个能量项 来处理，将其施加一个惩罚项后加入到网络的能量方程式 中，这样随着网络的收敛，约束的能量也逐渐趋于稳态，使 约束得到体现。(3) 神经网络计算 设邻接矩阵中的每个元素对应着一个神经元，定义位于位置 (x,i ) 的神经元的输出为 Vxi 。首先确定网络的能量函数，该能量函数包括网络的输出能量函数和各个约束转化的 能量函数E = E5 Ei E? E3 E4式中，吕为距离最短目标，Ei为有效路径约束，Ez为输入输 出路径约束，E3为网络收敛约束，E4为规定的起点终点约束。进而，确定神经元的传递函数和状态转移方程，经过网 络的反复演化，直至收敛。当网络经过演化最终收敛时，可 形成一个由0和1组成的换位阵，阵中的1所在位置即表示 所经过的结点，这些结点间的距离之和即为最短距离。(4)调度方案的形成根据换位阵所形成的最短距离，最终来确定车辆调度的方案
