电气自动化毕业论文基于改进遗传算法的有时间窗车辆调度问题研究.doc

基于改进遗传算法的有时间窗车辆调度问题研究 基于改进遗传算法的有时间窗车辆调度问题研究*葛显龙1a，王旭1a，1b，代应2(1重庆大学a机械工程学院;b贸易与行政学院，重庆400030;2重庆理工大学工商管理学院，重庆400050) 摘要:在分析带有时间窗车辆调度问题的基础上，建立了车辆调度问题的数学模型，并构造了不同时间窗的惩罚函数。设计了针对车辆调度问题基于自然数编码的遗传算法，并改进了传统的交叉运算，避免优秀基因在交叉操作中被破坏，提高了遗传算法的寻优能力。最后，结合算例进行了仿真计算，分析了载重体积约束和时间窗约束对车辆调度的影响，验证了算法的有效性。 关键词:遗传算法;时间窗;车辆调度 0引言 随着信息技术的发展尤其是因特网的出现和普及，电子商务得到了迅速的发展，大大缩短了商品交易活动的时间和空间。信息流、资金流可以在网上瞬间实现，对这些商务活动提供支持的物流提出了更高的要求，物流配送作为新的经济增长点开始引起了人们的注意。车辆调度问题是物流系统的核心环节，因此，对车辆调度问题(vsp)的研究就具有非常重要的意义。 vsp的求解方法基本上可以分为精确算法和启发式算法两大类。由于vsp属于强np问题，运用精确算法求解计算量会随着问题的规模增大而呈指数增加，实际中其应用范围比较有限。实际应用中多采用启发式算法，如启发式算法、禁忌搜索算法、模拟退火算法和遗传算法。其中bergen等人1研究了并行遗传算法求解车辆调度问题;pisinger等人2提出了遗传算法求解多车型约束的车辆调度问题;jozefowiez等人3研究了启发式算法求解多目标的车辆调度问题等。国内对vsp的研究还处于刚刚起步的阶段，李军等人4以c-w为基础的启发式算法对vsp进行了求解;赵燕伟等人5用量子进化算法求解了最短配送路径问题;李兵等人6研究了动态需求的车辆调度问题。另外，陈火根等人7提出了遗传算法与禁忌算法相结合的求解方法;郎茂祥等人8将爬山算法与遗传算法相结合，提出了混合遗传算法;宋伟刚等人9利用节约算法对解决此类问题进行了尝试。但是，车辆调度问题所涉及的种类繁多，启发式算法却没有普适的求解过程。 本文研究了带有时间窗约束的车辆调度问题，建立了有载重体积限制和硬时间窗限制的模型。 1问题描述 车辆调度问题一般描述为:对一系列需求点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如路程最短、费用最小、时间尽量少、使用车辆数尽量少等)。虽然vsp具有多种类型和形式，但vsp形式中的运输特点是基本相同的，即将商品从配送中心按一定的要求送到多个需求点。 本文主要讨论带有时间窗的车辆调度模型，完成第i个需求点的时间表示为ti，开始时间需要在eti，lti内。其中:eti为任务i的允许最早开始时间;lti为任务i的允许最迟开始时间。如果车辆到达i的时间早于eti，车辆需要在i处等待;反之，任务i要延迟进行。 时间窗约束又分为硬时间窗vsp和软时间窗vsp。硬时间窗vsp指每项任务必须在要求的时间范围内完成，若超出这个时间范围，则得到的解为不可行解。软时间窗vsp指如果某项任务不能在要求的时间范围内完成，则给予一定的惩罚，车辆在要求时间之前到达需求点，则车辆在此等待，发生了机会成本损失;车辆在指定时间之后到达需求点，则服务被延迟，须支付一定的罚金。 2建立模型 2.1一般vsp模型一般来说，当约束的问题越多，线路的组织就越难，一台车辆所完成的满足所有约束的任务就越少，这时，车辆实际所能容纳的体积越越小，而所用的车辆数就越多。为了使路线安排具有一定的弹性，可预先估计完成任务所需要的车辆数:m=ni=1qi/q+1(1)其中:表示对括号内的数取整;qi表示需求点i的需求量;q表示车辆的装载体积;01，是对装车的复杂性程度及约束条件限制的估计，一般的情况下，装车越复杂，约束越多，应越小，表示车辆所能容纳的货物量越少。 建立vsp问题的数学模型，首先给出决策变量:xijk=1车辆由需求点i驶向需求点j0其他yik=1需求点i的货运任务由车辆k完成0其他则数学模型如下:min z=ni=1nj=1mk=1cij xijk(2)st:ni=1qi yikq;k=1，2，m(3)mk=1yik=1;i=1，2，n(4)mk=1y0k=m(5)ni=1xijk=yjk;j=1，2，n，k=1，2，m(6)nj=1xijk=yik;i=1，2，n，k=1，2，m(7)xijk(xijk1)=0(8)yik(yik1)=0(9)其中:n表示需求点的个数;0表示车场;cij表示从点i到需求点j的广义成本费用，根据目标的不同可以是距离、费用、时间等不同的含义。 式(2)表示费用极小的目标函数;式(3)表示车辆k承担的任务量之和不大于车辆的载重量;式(4)表示任务i只能由一台车辆完成;式(5)表示由车场发出m辆车;式(6)和(7)表示两个变量之间的关系;式(8)和(9)为0-1变量约束。 2.2带时间窗vsp模型 以si表示车辆到达需求点i的时刻，ti表示车辆在需求点i的等待时间，ti表示完成任务i需要的时间，tij表示车辆由需求点i行驶到j的时间，eti，lti表示任务i的开始时间需要在一定的时间范围内，则有以下关系式:si=0(10)xijk=1si+ti+ti+tij=sj;ij(11)etisilti;i=1，2，n(12)如果配送车辆到达i时的时间早于eti，或晚于lti，则配送车辆要付出一定的惩罚费用。配送车辆到达任务i的时间为si，则惩罚费用为pi=amax(etisi，0)+bmax(silti，0)(13)其中:pi表示惩罚费用;a、b为早到和晚到的惩罚系数。 如果任务i的开始时间要求配送车辆必须在eti，lti内到达，则惩罚费用为pi=mmax(etisi，0)+mmax(silti，0)(14)其中:m为早到和晚到的惩罚系数+。 对于带有软时间窗限制的vsp问题，可将约束式(13)变成目标函数式的一部分，即min z=ni=1nj=1mk=1cij xijk+mmk=1maxni=1(qi yikq，0)+ni=1pi(15)对于带有硬时间窗限制的vsp问题，可将约束式(14)变成目标函数式的一部分，即min z=ni=1nj=1mk=1cij xijk+mmk=1maxni=1(qi yikq，0)+ni=1pi(16)3模型求解3.1改进的遗传算法本文构造的遗传算法是在基本遗传算法的基础上改进的，具体步骤如下:a)编码设计。在此遗传编码上采用自然数编码，模型3 的解向量可编成一条长度为n+m+1的染色体编码，如(0，i1，i2，ie，0，if，ik，0，0，ip，iq，0)，ij表示某个线路上第j个需求点，0表示车场，其数目为m+1个。 b)种群的初始化。随机产生n个需求点的全排列，在首尾处插入0，表示车辆从车场出发，最后又回到车场，如(0，i1，i2，ie，0);然后计算ej=1qijq且e+1j=1qijq，etisilti，否者把0向后移动一个位置。重复上面的步骤，直到将m1个0全部插入染色体内为止。如此反复，直到产生满足种群数目。 c)适应度评价。在此采用的适应度函数与z一致，根据实际情况可对后两项，即车辆载重体积和时间窗的惩罚限制进行取舍，由此可见函数值越小的染色体越优良。 d)选择操作。将所有染色体按照函数值大小进行排序并编号，函数值越小越靠前。假如一个规模为p的种群，函数值最小的染色体编号为0，最大的染色体编号为p1。随机产生一个符合标准正态分布的随机数r，因为99.9%的标准正态分布随机数在3，3。取r*=r3(若r3，则重新生成)。 此时r *在0，1，t=r*(p1)。选取第t号染色体进入新种群，由此选取染色体是越靠近0，概率越大，则选取较优的染色体可能性就越高。 e)交叉操作。vsp问题具有组间无序、组内有序的特性，如果单纯地使用一般的交叉算子，往往会使些优良的子串被破坏，并且在两父个体相同时，无法再产生新的个体。在此采用一种有效的交叉算子，是在传统的顺序交叉的基础上进行了改进。该交叉算子运用编码的特殊结构，即两个0之间的基因码表示两车的配送顺序，所以在选择交叉点时，要选择车场的位置，即0基因码。在交叉时，并不是直接把选中的子串复制过去，而是移位到首位。这样既可以最大限度地保留已成为最优路径的子路径，而且在两个双亲相同的情况下，该算子也会产生新的染色体，在变异的配合下，就会产生新的有效染色体，从而提高算法的寻优能力，降低过早收敛的性能，避免早熟现象的产生。其操作过程如下:(a)子路线交叉复制。选择两个染色体a和b，在1，m间随机产生两个自然数r1和r2(在此假设r1r2)，若r1和r2对应染色体a中的基因码为0;否则，向左或向右移动到最近的0，然后将选中的字串移到临时串temp的首位，其他依次后移。 (b)确定剩下子路线位置。删去染色体b中与选中子串相同的基因码，得到后代需要的其他基因码的顺序;照此顺序，从左到右替代temp中非选中的字串基因码，得到后代a，同理照此方式得到另一后代b。 f)变异操作。随机选择一个染色体，在1，m+p间随机产生两个自然数t1和t2，若t1和t2对应的基因是非零的，交叉其位置变异成新的基因;否则重新产生。 至此一次循环结束，重复上述步骤，根据遗传算法迭代次数或种群的收敛停止循环，输出最终结果。 3.2算法流程 在随机产生的种群中进行世代的进化，按照适应度的高低选择双亲，经过系列算子的操作产生优于父代的子代，用子代代替父代，执行新一轮的进化，直到满足停止条件，产生最优个体，获得最优解。该算法的程序流程如图1所示。 4计算仿真及结果分析 4.1实例模拟现以10个需求点为例，编号为1，2，10，车场及各需求点的节点坐标由maple语言中的rand()函数在0，1000，100的区域内随机产生，各需求点的需求量在0，8内随机产生。m=106，q=12 m3，每个需求点任务完成实际时间ti=20 min，车辆行驶速度v=45 km/h，随机数据如表1所示。 表1 vsp数据 编号0 1 2 3 4坐标/km(55，56)(59，41)(32，94)(58，12)(60，85)需求/t 0 22 23 68 36时间/min14:5015:20 9:009:30 10:3011:30 10:0510:455 6 7 8 9 10(36，71)(14，66)(34，25)(67，40)(75，79)(19，46)12 56 32 18 34 169:209:50 11:0511:45 9:5010:25 14:0014:30 11:0011:25 15:4016:20在此，采用坐标直线距离作为节点的实际距离，把时间的损失转换为距离的损失。令=0.9，则确定的车辆数为m=ni=1qi/q+1=4由此，解得只有载重体积限制的vsp模型，最短配送距离为346.77 km，由三条配送线路来完成所有需求点的需求，分别为:线路1:01830;线路2:052490;线路3:061070，其行驶距离分别为123.59 km，126.07 km，97.09 km，具体线路如图2所示。 求解带有硬时间窗的vsp模型，由上述给出的数据和4.1节的算法，迭代30次，得到最优解为501.69 km，线路1:081100;线路2:025490;线路3:030，线路4:0760，其行驶距离分别为105.74 km，142.18km，88.20 km和125.26 km，具体线路如图3所示。 4.2结果分析与比较 下面对不同限制的vsp模型从行驶线路、行驶距离、车载率及完成任务所用时间进行比较和分析，如表2所示。 表2三种模型求解的数据 模型行驶线路车载率/%行驶距离/km总距离/km带有体积限制线路1:01830 875 12359线路2:052490 867 12607线路3:061070 90 9709346.77带有硬时间限制线路1:081100 467 10574线路2:025490 875 14218线路3:030 567 8820线路4:0760 733 12526501.69由表2中可知，只有体积限制的vsp问题从行驶线路、行驶距离、车载率都能得到很好的优化，行驶总距离也是三种模型最短的;对于带有硬时间窗的vsp问题，其违反时间窗造成的损失很大，在此时只能以牺牲距离来保证时间的要求，所以它的行驶总距离最大。 5结束语 1)本文建立了有时间窗配送车辆调度问题的基于直观描述的数学模型，该模型考虑了较为接近实际的约束条件和目标函数，并具有简单、直观、易于理解、易于设计算法求解及可扩充性强等特点。 2)本文设计改进的遗传算法求解有时间窗配送车辆调度问题，即用自然数顺序编排车辆的行车路线，在交叉操作中避免优秀基因被破坏，与现有文献中的求解算法相比，本文设计的算