在分析带有时间窗车辆调度问题的基础上，建立了车辆调度问题的数学模型，并构造了不同时间窗的惩罚函数。设计了针对车辆调度问题基于自然数编码的遗传算法，并改进了传统的交叉运算，避免优秀基因在交叉操作中被破坏，提高了遗传算法的寻优能力。最后，结合算例进行了仿真计算，分析了载重体积约束和时间窗约束对车辆调度的影响，验证了算法的有效性。
第2期 葛显龙,等:基于改进遗传算法的有时间窗车辆调度问题研究 447 如果单纯地使用一般的交义算子,往往会使些优良的子串被破 表1VSP数据 坏,并且在两父个体相同时,无法再产生新的个体。在此采用 种有效的交叉算子,是在传统的顺序交叉的基础上进行了改 坐标/km(55,56)(59,41)(32,94)(58,12 (60,85 需求 3.6 进。该交叉算子运用编码的特殊结构,即两个0之间的基因码 时间/min 1450-15:209:00-9:3010:30-11:3010:05-10 表示两车的配送顺序,所以在选择交叉点时,要选择车场的位 置,即0基因码。在交叉时,并不是直接把选中的子串复制过 )(14,66)(34,25)(67,40)(75,79 (19,46) 去,而是移位到首位。这样既可以最大限度地保留已成为最优 路径的子路径,而且在两个双亲相同的情况下,该算子也会产 9:0-9:01105-1:459:0-10:25140-14:3010-1:2515:40-16:20 在此,采用坐标直线距离作为节点的实际距离,把时问的 生新的染色体,在变异的配合下,就会产生新的有效染色体,从 而提高算法的寻优能力,降低过早收敛的性能,避免早熟现象损失转换为距离的损失。令=0.9,则确定的车辆数为 的产生。其操作过程如下 m=[∑q/0Q]+1=4 (a)子路线交叉复制。选择两个染色体A和B,在[1,m] 由此,解得只有载重体积限制的VP模型,最短配送距离 间随机产生两个自然数n和n(在此假设n1<r2),若n1和n2为346.77km,由三条配送线路来完成所有需求点的需求,分 对应染色体A中的基因码为0;否则,向左或向右移动到最近别为线路1:0-1-8-3-0线路2:0-5-2-4-9-0;线路 的0,然后将选中的字串移到临时串temp的首位,其他依次3:0-6-10-7-0,其行驶距离分别为123.59km,126.07km, 后移。 97.09km,具体线路如图2所示。 (b)确定剩下子路线位置。删去染色体B中与选中子串 求解带有硬时间窗的VsP模型,由上述给出的数据和4.1 相同的基因码,得到后代需要的其他基因码的顺序;照此噘序,节的算法,迭代30次,得到最优解为501.69km,线路1: 从左到右替代temp中非选中的字串基因码,得到后代A,同0-8-1-10-0;线路2:0-2-5-4-9-0;线路3:0-3-0, 理照此方式得到另一后代B。 线路4:0-7-6-0,其行驶距离分别为105.74km,142.18 f)变异操作。随机选择一个染色体,在1,m+P]间随机km,88.20km和125.26km,具体线路如图3所示。 产生两个白然数t1和t2,若t1和t对应的基因是非零的,交叉 90 其位置变异成新的基因;否则重新产生。 至此一次循环结束,重复上述步骤,根据遗传算法迭代次 数或种群的牧敛停止循环,输岀最终结果。 0000000 50 3.2算法流程 0 在随机产生的种群中进行世代的进化,按照适应度的高低 203040506070 203040506070 选择双亲,经过系列算子的操作产生优于父代的子代,用子代 图2带有载重量限制的 图3带有硬时间窗口的 Milk-run路线图 Milk-run线路口 代替父代执行新一轮的进化自到满足停止条件,产生最优个42结果分析与比较 体,获得最优解。该算法的程序流程如图1所示。 下而对不同限制的ⅤSP模型从行驶线路、行驶距离、车载 设置算法参数 率及完成任务所用时间进行比较和分析,如表2所示。 机产生初始种群 表2三和模型求解的数据 计算和群中染色体的适应度和总里程 车载率/%行驶距离/km总距离/km 根据适应度选择双亲 带有线路1:0-1-8-3-0 123.59 进行交叉操作 线路2:0-5-2 4-9-0 86.7 体积限制 线路3:0-6-10-7-0 97.0y 进行变异操作 线路1:0-8-1-10-0 105.74 判断是否满足 带有硬线路2:0-2-5-4-9-0 87.5 142.18 501.69 停止条件 间限制线路3:0-3-0 56.7 88.20 是 线路4:0760 73.3 125.26 算法结束并输出结果 由表2中可知,只有体积限制的VsP问题从行驶线路、行 图1算法流程图 驶距离、车载率都能得到很好的优化,行驶总距离也是一种模 4计算仿真及结果分析 型最短的;对丁带有硬时间窗的ⅤsP问题,其违反时间窗造成 的损失很大,在此时只能以牺牲距离来保证时间的要求,所以 4.1实例模拟 它的行驶总距离最大。 现以10个需求点为例,编号为1,2,…,10,车场及各 5结束语 需求点的节点坐标由Male语言中的rand()函数在0, 100」×0,100」的区域内随机产生,各需求点的需求量在 1)本文建立了有时间窗配送车辆调度问题的基于直观描 0,8]内随机产生。M=10°,Q=12m3,每个需求点任务完述的数学模型,该模型考虑了较为接近实际的约束条件和目标 成实际时间T=20min,车辆行驶速度υ=45km/h,随机数函数,并具有简单、直观、易于理解、易于设计算法求解及可扩 据如表1所示。 充性强等特点。 (下转第450页) 450 计算机应用研究 第28卷 操作性指标S1=10.7994,对应的冗余机械手的形状和S曲 线如图4所示。从图4(a)中可以发现,不仅冗余机械手整体 4结束语 有着较高的可操作性,而且各个关节角(角度单位统一[rad] 本文在可操作性基础之上,结合PSO算法,提出了寻优可 大小乜都很均衡,这也说明了以S作为第二指标的优越性 操作性指标的方法,即以相关关节点为圆心、关节长度为半径 手臂末端最优可操作性指标 E=(0.5,0.5) 的圆周上的点坐标为算法粒子进行迭代优化。根据优化结果 10.798}6 得到的各个关节点坐标就可以确定冗余机械手的形状,前且此 m .32249.25210 0.3mC(0.159,0 电10.794 时的冗余机械手有着最优的可操作性。进一步通过实验仿真 42=0.134 359,0.359)10.792 02mB(0.05,0.194 10.79 不仅验证了本文所提出的寻优方法,而且肯定了以SM作为第 0.1m 二指标来确定机械手形状的优越性。这些不仅为以后进一步 =0.422 10.786 10.784 0.1mA0m0.1m0.2m0.3m0.4m0.5m 理论上的三维研究提供了一些借鉴,也为实际工程应用提供了 10.782 0.1m 方案。 进化代数 参考文献 图4E坐标为(0.5,0.5)时对应整体最优 可操作性的冗余机械手形状和Sx曲线图 [1 MACIEJE WSKI AA, KLEIN C. A. Obstacle avoidance for kinemati 3.2轨迹跟踪仿真 ally redundant manipulators in dynamically varying environments L 1. The International Journal of Robotics Research. 1985,4 给定直角线段ABC为四关节冗余机械手手臂末端任务, (3):109-117 仿真过程从A~C点开始等距离0.1m采样一次。当分别以 [2 NAKAMURA Y, HANAFUSA H, YOSHIKAWA T. Task priority 手臂末端可操作性指标Sμ和整体最伉可操作性指标S〃为优 based redundancy control of robot manipulators. The Internatio 化目标函数时,在每个采样点位置根据上面已给出的方法分别 nal Journal of Robotics Research, 1987, 6(2): 3-15 依次给出相应的机械手最优形状,整个过程如图5所示。 [3] YASHIKAWA T. Manipuator Df robaticcs mechanisms [J]. The In B(0.5,0.5) ylm] A(0.1,6.5) 0. 卫A(0.1,d.5 B(0.50.5 ternational Journal of Robotics Research, 1985, 4(1): 3-9 [4] KOEPPE R, YOSHIKAWA T. Dynamir: manipulability analysis nf 04m compliant motion[c//Proe of IEEE/RSJ International Conference 0.3m 0.2mi un Intelligent Rubols and Syslelms. Grenoble: [sll.1,1997:1472 0.2m C(0.5,0.1) C(0.50.1) x lm] [5 KENNEDY J, EBERHART R C. Particle swarm optimization/ -0.1mOm.lm02m0.3m0.4m0.5m 0.1m0m0.1m0.2m03m0.4m0.5m 0.1m 0. Im Proc of IEeE International Conference on Neural Networks. 1995 1942-1948 图5跟踪直角ABC轨迹仿真 从图5(a)中可以看出,由于采样点坐标的原因,在各个采 [6]李新春,赵冬旅,易建强.一种全方倞移动械手的可操作度分斫 J].中国机械工程,2006,17(14):1442-1447 样点处与手臂末端最优可操作性指标Sm对应的各个关节角q2 [7] SHI Yu-hui, FBE.RHART R C. A modified partic le swarm optimizer 相比于对应的其他关节角都很小;而从(b)中可以看出,同一采 [C//Proc of IEEE Congress on Evolutionary Computation. 1998 样点处,与最优Sx对应的形状比与手脣末端最优Sm对应的形 63-79 状要优越得多,此时与各个形状对应的关节角之间都很均匀。 (上接第447页) 2)本文设计改进的遗传算法求解有时间窗配送车辆调度 problems[ J]. Computers Operations, 2007, 34(8): 2403 问题,即用自然数顺序编排车辆的行车路线,在交叉操作中避 2435 免优秀基因被破坏,与现有文献中的求解算法相比,本文设计3110 ZEFOWIE2N, SEMET F, TALBIE C. Multi-abjective vehicle 的算汏具有解的表示自然直观、算法策略易于理解、计算效率 routing problems[ J. European Journal of Operational Re search,2008,789(2):293-309 较高、收敛速度较快的优点。 [4]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中 3)本文利用设计的算法对随机产生的有时间窗配送车辆 国物资出版社,2001 调度间题实例进行了实验计算,计算结果表明,用本文设计的[51赵燕伟,彭典军.有能力约束车辆路径问题的量子进化算法[ 改进算法求解有时间窗配送车辆调度问题,不仅可以取得很好 系统理论与实践,209,29(2):159-166 的计算结果,而且算法的计算效率较高,收敛速度较快,计算结[6]李兵,郑四发.求解客户需求动态变化的车辆路径规划方法[J] 果也较稳定 交通运输工程学报,2007,7(1):;106-110 参考文献 [冂」陈火根,丁红纲.物流配送中心车辆调度模型与遗传算法设计 J」.浙江大学学报,2003,37(5):513-516 [I BERGEN J, BARKAQUI M. A parallel hybrid genetic algorithm for L8」郎茂祥,胡思继.用混合遗传算法求解物流配送路径优化问题的 the vehicle routing problem with time window [J]. Computers 研究[J].中国管理科学,2002,10(5):51-56 Operations Research, 2004, 31(12): 2037-2053. [9]宋伟刈,张宏霞,佟玲,有时间窗约柬非满戟车调度问题的节约 [2 PISINGER D, ROPKE S. A general heuristic for vehicle routin 算法[J].东北大学学报,206,27(1):65-68