第 ２８ 卷第 ２ 期 ２０１１ 年 ２ 月　 计 算 机 应 用 研 究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ 基 于 改 进 遗 传 算 法 的 有 时 间 窗 车 辆 调 度 问 题 研 究 Ｖｏｌ畅２８ Ｎｏ畅２ Ｆｅｂ畅２０１１ 倡 １ａ， 王　旭 １ａ，１ｂ， 代　应 ２ 葛显龙 （１．重庆大学 ａ．机械工程学院； ｂ．贸易与行政学院， 重庆 ４０００３０； ２．重庆理工大学 工商管理学院， 重庆 ４０００５０） 摘　要： 在分析带有时间窗车辆调度问题的基础上，建立了车辆调度问题的数学模型，并构造了不同时间窗的 惩罚函数。 设计了针对车辆调度问题基于自然数编码的遗传算法，并改进了传统的交叉运算，避免优秀基因在 交叉操作中被破坏，提高了遗传算法的寻优能力。 最后，结合算例进行了仿真计算，分析了载重体积约束和时间 窗约束对车辆调度的影响，验证了算法的有效性。 关键词： 遗传算法； 时间窗； 车辆调度 中图分类号： Ｆ２７４　　　文献标志码： Ａ　　　文章编号： １００１唱３６９５（２０１１）０２唱０４４５唱０３ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１１．０２．００９ Ａｎａｌｙｓｉｓ ｏｎ ｖｅｈｉｃｌｅ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ ｗｉｔｈ ｔｉｍｅ ｗｉｎｄｏｗ ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ＧＥ Ｘｉａｎ唱ｌｏｎｇ１ａ， ＷＡＮＧ Ｘｕ１ａ，１ｂ， ＤＡＩ Ｙｉｎｇ２ （１a．College of Mechanical Engineering， b．College of Trade ＆ Public Administration， Chongqing University， Chongqing ４０００３０， China； ２． College of Business Administration， Chongqing University of Technology， Chongqing ４０００５０， China） Abstract： Ｉｎ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｖｅｈｉｃｌｅ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ ｗｉｔｈ ｔｉｍｅ ｗｉｎｄｏｗ， ｅｓｔａｂｌｉｓｈｅｄ ｔｈｅ ＶＳＰ ｍａｔｈｅｍａｔｉｃａｌ ｍｏｄｅｌ， ｃｏｎ唱 ｓｔｒｕｃｔｅｄ ａｎｄ ｔｈｅ ｄｉｆｆｅｒｅｎｔ ｔｉｍｅ ｗｉｎｄｏｗ ｐｅｎａｌｔｙ ｆｕｎｃｔｉｏｎ．Ｉｎ ｖｉｅｗ ｏｆ ｒｅｓｏｌｖｉｎｇ ｖｅｈｉｃｌｅｓ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ， ｄｅｓｉｇｎｅｄ ｇｅｎｅｔｉｃ ａｌ唱 ｇｏｒｉｔｈｍ ｏｆ ｔｈｅ ｎａｔｕｒａｌ ｎｕｍｂｅｒ ｃｏｄｅ， ａｎｄ ｉｍｐｒｏｖｅｄ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ｏｖｅｒｌａｐｐｉｎｇ ｏｐｅｒａｔｉｏｎ， ａｖｏｉｄｅｄ ｔｈｅ ｏｕｔｓｔａｎｄｉｎｇ ｇｅｎｅ ｄｅｓｔｒｏ唱 ｙｉｎｇ ｉｎ ｔｈｅ ｉｎｔｅｒｌａｃｅ ｏｐｅｒａｔｉｏｎ， ｅｎｈａｎｃｅｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｂｉｌｉｔｙ．Ｆｉｎａｌｌｙ， ｃｏｍｂｉｎｅｄ ｗｉｔｈ ｔｈｅ ｅｘａｍｐｌｅ ｏｆ ｓｉｍｕｌａ唱 ｔｉｏｎ ｃｏｍｐｕｔａｔｉｏｎ， ａｎａｌｙｚｅｄ ｔｈｅ ｉｎｆｌｕｅｎｃｅ ｈａｄ ｔｈｅ ｃａｒｒｙｉｎｇ ｃａｐａｃｉｔｙ ｖｏｌｕｍｅ ｔｏ ｒｅｓｔｒａｉｎ ａｎｄ ｈａｄ ｔｈｅ ｔｉｍｅ ｗｉｎｄｏｗ ｔｏ ｒｅｓｔｒａｉｎ ｔｏ ｔｈｅ ｖｅｈｉｃｌｅｓ ｄｉｓｐａｔｃｈ， ｃｏｎｆｉｒｍｅｄ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｖａｌｉｄｉｔｙ． Key words： ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ； ｔｉｍｅ ｗｉｎｄｏｗ； ｖｅｈｉｃｌｅ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ（ＶＳＰ） 人 ［９］ ［６］ 等人 用量子进化算法求解了最短配送路径问题；李兵等人 ［５］ 0　引言 研究了动态需求的车辆调度问题。 另外，陈火根等人 ［７］ 提出 了遗传算法与禁忌算法相结合的求解方法；郎茂祥等人 ［８］ 随着信息技术的发展尤其是因特网的出现和普及，电子商 将 爬山算法与遗传算法相结合，提出了混合遗传算法；宋伟刚 务得到了迅速的发展，大大缩短了商品交易活动的时间和空 利用节约算法对解决此类问题进行了尝试。 但是，车 间。 信息流、资金流可以在网上瞬间实现，对这些商务活动提 辆调度问题所涉及的种类繁多，启发式算法却没有普适的求 供支持的物流提出了更高的要求，物流配送作为新的经济增长 解过程。 点开始引起了人们的注意。 车辆调度问题是物流系统的核心 本文研究了带有时间窗约束的车辆调度问题，建立了有载 环节，因此，对车辆调度问题（ＶＳＰ） 的研究就具有非常重要的 重体积限制和硬时间窗限制的模型。 意义。 1　问题描述 ＶＳＰ 的求解方法基本上可以分为精确算法和启发式算法 两大类。 由于 ＶＳＰ 属于强 ＮＰ 问题，运用精确算法求解计算 量会随着问题的规模增大而呈指数增加，实际中其应用范围 车辆调度问题一般描述为：对一系列需求点，组织适当的 比较有限。 实际应用中多采用启发式算法，如启发式算法、 行车路线，使车辆有序地通过它们，在满足一定的约束条件 禁忌搜索算法、模拟退火算法和遗 传算法。 其中 Ｂｅｒｇｅｎ 等 （如货物需求量、发送量、交发货时间、车辆容量限制、行驶里 研究 了 并 行 遗 传 算 法 求 解 车 辆 调 度 问 题；Ｐｉｓｉｎｇｅｒ 等 程限制、时间限制等） 下，达到一定的目标（ 如路程最短、费用 ［１］ 最小、时间尽量少、使用车辆数尽量少等）。 虽然 ＶＳＰ 具有多 提出了遗传算法求解多车型约束的车辆调度问题；Ｊｏｚｅ ［２］ 种类型和形式，但 ＶＳＰ 形式中的运输特点是基本相同的，即将 ｆｏｗｉｅｚ等人 等。 国内对 ＶＳＰ 的研究还处于刚刚起步的阶段，李军等人 商品从配送中心按一定的要求送到多个需求点。 以 Ｃ唱Ｗ 为基础的启发式算法对 ＶＳＰ 进行了求解；赵燕伟等 本文主要讨论带有时间窗的车辆调度模型，完成第 i 个需 　　收稿日期： ２０１０唱０７唱１７； 修回日期： ２０１０唱０８唱２１　　基金项目： 国家“８６３” 计划资助项目（２００６ＡＡ０４Ａ１２３）；重庆市自然科学基金资助项目 （ＣＳＴＣ．２００８ＢＢ２１７３）；国家教育部人文社会科学研究青年基金资助项目（０９ＹＪＣ６３０２４７） 作者简介： 葛显龙（１９８４唱），男，河南信阳人，博士研究生，主要研究方向为供应链管理与现代 物流（ｇｅｘｉａｎｌｏｎｇ＠ｃｑｕ．ｅｄｕ．ｃｎ）；王旭（１９６３唱）， 女，重庆人，教授，博导，主要研究方向为供应链管理与现代物流、项目管理． 研究了启发式算法求解多目标的车辆调度问题 ［４］ 人 人 ［３］ 

计 算 机 应 用 研 究 　 ·６４４· 求点的时间表示为 Ti，开始时间需要在［ETi，LTi］ 内。 其中： ETi 为任务 i 的允许最早开始时间；LTi 为任务 i 的允许最迟开 始时间。 如果车辆到达 i 的时间早于 ETi，车辆需要在 i 处等 待；反之，任务 i 要延迟进行。 时间窗约束又分为硬时间窗 ＶＳＰ 和软时间窗 ＶＳＰ。 硬时 间窗 ＶＳＰ 指每项任务必须在要求的时间范围内完成，若超出 这个时间范围，则得到的解为不可行解。 软时间窗 ＶＳＰ 指如 果某项任务不能在要求的时间范围内完成，则给予一定的惩 罚，车辆在要求时间之前到达需求点，则车辆在此等待，发生了 机会成本损失；车辆在指定时间之后到达需求点，则服务被延 迟，须支付一定的罚金。 2　建立模型 2畅1　一般 VSP 模型 一般来说，当约束的问题越多，线路的组织就越难，一台车 辆所完成的满足所有约束的任务就越少，这时，车辆实际所能 容纳的体积越越小，而所用的车辆数就越多。 为了使路线安排 具有一定的弹性，可预先估计完成任务所需要的车辆数： m ＝［∑n i ＝１qi ／矪Q］ ＋１ （１） 其中：［］表示对括号内的数取整；qi 表示需求点 i 的需求量；Q 表示车辆的装载体积；０ ＜矪＜１，是对装车的复杂性程度及约束 条件限制的估计，一般的情况下，装车越复杂，约束越多，矪 应 越小，表示车辆所能容纳的货物量越少。 建立 ＶＳＰ 问题的数学模型，首先给出决策变量： xijk ＝ １　车辆由需求点 i 驶向需求点 j yik ＝ １　需求点 i 的货运任务由车辆 k 完成 ０　其他 ０　其他 si ＝０ k ＝１ｍａｘ ∑n k ＝１ｍａｘ ∑n i ＝１qiyik －Q，０ ＋∑n i ＝１qi yik －Q，０ ＋∑n 成目标函数式的一部分，即 xijk ＝１痴si ＋ti ＋Ti ＋tij ＝sj；i≠j ETi≤si≤LTi；i ＝１，２，…，n Pi ＝a ×ｍａｘ（ETi －si，０） ＋b ×ｍａｘ（si －LTi，０） Pi ＝M ×ｍａｘ（ETi －si，０） ＋M ×ｍａｘ（si －LTi，０） 第 ２８ 卷 i 的等待时间，Ti 表示完成任务 i 需要的时间，tij 表示车辆由需 求点 i 行驶到 j 的时间，［ETi，LTi］表示任务 i 的开始时间需要 在一定的时间范围内，则有以下关系式： （１０） （１１） （１２） 如果配送车辆到达 i 时的时间早于 ETi，或晚于 LTi，则配 送车辆要付出一定的惩罚费用。 配送车辆到达任务 i 的时间 为 Si，则惩罚费用为 （１３） 其中：Pi 表示惩罚费用；a、b 为早到和晚到的惩罚系数。 如果任务 i 的开始时间要求配送车辆必须在［ETi，LTi］ 内 到达，则惩罚费用为 （１４） 其中：M 为早到和晚到的惩罚系数 ＋∞。 对于带有软时间窗限制的 ＶＳＰ 问题，可将约束式（１３） 变 成目标函数式的一部分，即 ｍｉｎ　Z ＝∑n i ＝１Pi （１５） j ＝１∑m i ＝１∑n k ＝１cijxijk ＋M∑m 对于带有硬时间窗限制的 ＶＳＰ 问题，可将约束式（１４） 变 i ＝１Pi （１６） j ＝１∑m i ＝１∑n ｍｉｎ　Z ＝∑n k ＝１cijxijk ＋M∑m 3　模型求解 3畅1　改进的遗传算法 本文构造的遗传算法是在基本遗传算法的基础上改进的， 具体步骤如下： ａ）编码设计。 在此遗传编码上采用自然数编码，模型的 解向量可编成一条长度为 n ＋m ＋１ 的染色体编码，如（０，i１， i２，…，ie，０，if，…，ik，０，…，０，ip，…，iq，０），ij 表示某个线路上第 j 个需求点，０ 表示车场，其数目为 m ＋１ 个。 ｂ）种群的初始化。 随机产生 n 个需求点的全排列，在首 尾处插入０，表示车辆从车场出发，最后又回到车场，如（０，i１， i２，…，ie，０）；然后计算∑e j ＝１qij≥Q，ETi ＜si ＜LTi，否者 把０ 向后移动一个位置。 重复上面的步骤，直到将 m －１ 个 ０ 全部插入染色体内为止。 如此反复，直到产生满足种群数目。 ｃ）适应度评价。 在此采用的适应度函数与 Z 一致，根据 实际情况可对后两项，即车辆载重体积和时间窗的惩罚限制进 行取舍，由此可见函数值越小的染色体越优良。 ｄ）选择操作。 将所有染色体按照函数值大小进行排序并 编号，函数值越小越靠前。 假如一个规模为 P 的种群，函数值 最小的染色体编号为０，最大的染色体编号为 P －１。 随机产生 一个符合标准正态分布的随机数 r，因为 ９９畅９％的标准正态分 布随机数在［ －３，３］。 取 r倡 ＝ r３ （ 若 r ＞３，则重新生成）。 在［０，１］，t ＝r倡（P －１）。 选取第 t 号染色体进入新种 此时 r倡 群，由此选取染色体是越靠近０，概率越大，则选取较优的染色 体可能性就越高。 ｅ）交叉操作。 ＶＳＰ 问题具有组间无序、组内有序的特性， j ＝１qij≤Q 且∑e ＋１ 则数学模型如下： ∑m k ＝１y０k ＝m ∑n i ＝１xijk ＝yjk；j ＝１，２，…，n，k ＝１，２，…，m ∑n j ＝１xijk ＝yik；i ＝１，２，…，n，k ＝１，２，…，m ｍｉｎ　Z ＝∑n i ＝１∑n j ＝１∑m k ＝１cijxijk ｓ．ｔ．：　∑n i ＝１qiyik≤Q；k ＝１，２，…，m k ＝１yik ＝１；i ＝１，２，…，n ∑m （２） （３） （４） （５） （６） （７） （８） （９） 其中：n 表示需求点的个数；０ 表示车场；cij 表示从点 i 到需求 点 j 的广义成本费用，根据目标的不同可以是距离、费用、时间 等不同的含义。 式（２）表示费用极小的目标函数；式（３） 表示车辆 k 承担 的任务量之和不大于车辆的载重量；式（４） 表示任务 i 只能由 一台车辆完成；式（５）表示由车场发出 m 辆车；式（６） 和（７） 表 示两个变量之间的关系；式（８）和（９）为０唱１ 变量约束。 2畅2　带时间窗 VSP 模型 以 Si 表示车辆到达需求点 i 的时刻，ti 表示车辆在需求点 xijk（xijk －１） ＝０ yik（yik －１） ＝０ 

第 ２ 期 如果单纯地使用一般的交叉算子，往往会使些优良的子串被破 坏，并且在两父个体相同时，无法再产生新的个体。 在此采用 一种有效的交叉算子，是在传统的顺序交叉的基础上进行了改 进。 该交叉算子运用编码的特殊结构，即两个０ 之间的基因码 表示两车的配送顺序，所以在选择交叉点时，要选择车场的位 置，即０ 基因码。 在交叉时，并不是直接把选中的子串复制过 去，而是移位到首位。 这样既可以最大限度地保留已成为最优 路径的子路径，而且在两个双亲相同的情况下，该算子也会产 生新的染色体，在变异的配合下，就会产生新的有效染色体，从 而提高算法的寻优能力，降低过早收敛的性能，避免早熟现象 的产生。 其操作过程如下： （ａ）子路线交叉复制。 选择两个染色体 Ａ 和 Ｂ，在［１，m］ 间随机产生两个自然数 r１ 和 r２（在此假设 r１ ＜r２），若 r１ 和 r２ 对应染色体 Ａ 中的基因码为０；否则，向左或向右移动到最近 的０，然后将选中的字串移到临时串 ｔｅｍｐ 的首位，其他依次 后移。 （ｂ）确定剩下子路线位置。 删去染色体 Ｂ 中与选中子串 相同的基因码，得到后代需要的其他基因码的顺序；照此顺序， 从左到右替代 ｔｅｍｐ 中非选中的字串基因码，得到后代 Ａ′，同 理照此方式得到另一后代 Ｂ′。 ｆ）变异操作。 随机选择一个染色体，在［１，m ＋P］ 间随机 产生两个自然数 t１ 和 t２，若 t１ 和 t２ 对应的基因是非零的，交叉 其位置变异成新的基因；否则重新产生。 至此一次循环结束，重复上述步骤，根据遗传算法迭代次 数或种群的收敛停止循环，输出最终结果。 3畅2　算法流程 在随机产生的种群中进行世代的进化，按照适应度的高低 选择双亲，经过系列算子的操作产生优于父代的子代，用子代 代替父代，执行新一轮的进化，直到满足停止条件，产生最优个 体，获得最优解。 该算法的程序流程如图１ 所示。 4　计算仿真及结果分析 4畅1　实例模拟 现以 １０ 个需求点为例，编号 为 １，２，…，１０， 车 场 及 各 需求点的 节 点 坐 标 由 Ｍａｐｌｅ 语 言 中 的 ｒａｎｄ（） 函 数 在［０， １００］ ×［０，１００］ 的区域内随机产生，各需求点的需求量在 ［０，８］ 内随机产生。 M ＝１０６，Q ＝１２ ｍ３，每个需求点任务完 成实际时间 Ti ＝２０ ｍｉｎ，车辆行驶速度 v ＝４５ ｋｍ／ｈ，随机数 据如表 １ 所示。 葛显龙，等：基于改进遗传算法的有时间窗车辆调度问题研究 ·７４４· 　　　 编号 （５５，５６） ０ ０ — ６ （１４，６６） ５ ．６ １１：０５ ～１１：４５ 表 １　ＶＳＰ 数据 ２ １ （３２，９４） （５９，４１） ．２ ．３ ２ ２ １４：５０ ～１５：２０ ９：００ ～９：３０ ８ ７ （６７，４０） （３４，２５） ．２ ．８ ３ １ ９：５０ ～１０：２５ １４：００ ～１４：３０ ４ （６０，８５） 坐标／ｋｍ ３ ．６ 需求／t １０：０５ ～１０：４５ 时间／ｍｉｎ １０ ５ （１９，４６） （３６，７１） １ ．６ ．２ １ １５：４０ ～１６：２０ ９：２０ ～９：５０ 　　在此，采用坐标直线距离作为节点的实际距离，把时间的 损失转换为距离的损失。 令 矪＝０畅９，则确定的车辆数为 ３ （５８，１２） ６ ．８ １０：３０ ～１１：３０ ９ （７５，７９） ．４ ３ １１：００ ～１１：２５ m ＝［∑n i ＝１qi ／矪Q］ ＋１ ＝４ 由此，解得只有载重体积限制的 ＶＳＰ 模型，最短配送距离 为３４６畅７７ ｋｍ，由三条配送线路来完成所有需求点的需求，分 别为：线路１：０ －１ －８ －３ －０；线路２：０ －５ －２ －４ －９ －０；线路 ３：０ －６ －１０ －７ －０，其行驶距离分别为１２３畅５９ ｋｍ，１２６畅０７ ｋｍ， ９７畅０９ ｋｍ，具体线路如图２ 所示。 求解带有硬时间窗的 ＶＳＰ 模型，由上述给出的数据和４畅１ 节的算 法， 迭 代 ３０ 次， 得 到 最 优 解 为 ５０１畅６９ ｋｍ， 线 路 １： ０ －８ －１ －１０ －０；线路２：０ －２ －５ －４ －９ －０；线路３：０ －３ －０， 线路 ４：０ －７ －６ －０，其行驶距离分别为 １０５畅７４ ｋｍ，１４２畅１８ ｋｍ，８８畅２０ ｋｍ 和１２５畅２６ ｋｍ，具体线路如图３ 所示。 4畅2　结果分析与比较 率及完成任务所用时间进行比较和分析，如表２ 所示。 下面对不同限制的 ＶＳＰ 模型从行驶线路、行驶距离、车载 表 ２　三种模型求解的数据 模型 带有 体积限制 行驶线路 线路 １：０ －１ －８ －３ －０ 线路 ２：０ －５ －２ －４ －９ －０ 线路 ３：０ －６ －１０ －７ －０ 线路 １：０ －８ －１ －１０ －０ 线路 ２：０ －２ －５ －４ －９ －０ 线路 ３：０ －３ －０ 线路 ４：０ －７ －６ －０ ３４６ 车载率／％ 行驶距离／ｋｍ 总距离／ｋｍ ．５ ８７ ．７ ８６ 畅７７ ９０ ４６ ．７ ８７ ．５ ５６ ．７ ．３ ７３ ．５９ ．０７ ．０９ ．７４ ．１８ ．２０ ．２６ １２３ １２６ ９７ １０５ １４２ ８８ １２５ 带有硬 ５０１ 时间限制 畅６９ 　　由表２ 中可知，只有体积限制的 ＶＳＰ 问题从行驶线路、行 驶距离、车载率都能得到很好的优化，行驶总距离也是三种模 型最短的；对于带有硬时间窗的 ＶＳＰ 问题，其违反时间窗造成 的损失很大，在此时只能以牺牲距离来保证时间的要求，所以 它的行驶总距离最大。 5　结束语 １）本文建立了有时间窗配送车辆调度问题的基于直观描 述的数学模型，该模型考虑了较为接近实际的约束条件和目标 函数，并具有简单、直观、易于理解、易于设计算法求解及可扩 充性强等特点。 （ 下转第 ４５０ 页） 

·０５４· 操作性指标 SM ＝１０畅７９９ ４，对应的冗余机械手的形状和 SM 曲 线如图４ 所示。 从图４（ａ） 中可以发现，不仅冗余机械手整体 有着较高的可操作性，而且各个关节角（角度单位统一［ｒａｄ］） 大小也都很均衡，这也说明了以 SM 作为第二指标的优越性。 第 ２８ 卷 计 算 机 应 用 研 究 　 4　结束语 本文在可操作性基础之上，结合 ＰＳＯ 算法，提出了寻优可 操作性指标的方法，即以相关关节点为圆心、关节长度为半径 的圆周上的点坐标为算法粒子进行迭代优化。 根据优化结果 得到的各个关节点坐标就可以确定冗余机械手的形状，而且此 时的冗余机械手有着最优的可操作性。 进一步通过实验仿真， 不仅验证了本文所提出的寻优方法，而且肯定了以 SM 作为第 二指标来确定机械手形状的优越性。 这些不仅为以后进一步 理论上的三维研究提供了一些借鉴，也为实际工程应用提供了 方案。 参考文献： ［１］ ＭＡＣＩＥＪＥＷＳＫＩ Ａ Ａ， ＫＬＥＩＮ Ｃ Ａ．Ｏｂｓｔａｃｌｅ ａｖｏｉｄａｎｃｅ ｆｏｒ ｋｉｎｅｍａｔｉ唱 ｃａｌｌｙ ｒｅｄｕｎｄａｎｔ ｍａｎｉｐｕｌａｔｏｒｓ ｉｎ ｄｙｎａｍｉｃａｌｌｙ ｖａｒｙｉｎｇ ｅｎｖｉｒｏｎｍｅｎｔｓ ［Ｊ］．The International Journal of Robotics Research， １９８５，4 （３）：１０９唱１１７． ［２］ ＮＡＫＡＭＵＲＡ Ｙ， ＨＡＮＡＦＵＳＡ Ｈ， ＹＯＳＨＩＫＡＷＡ Ｔ．Ｔａｓｋ ｐｒｉｏｒｉｔｙ ｂａｓｅｄ ｒｅｄｕｎｄａｎｃｙ ｃｏｎｔｒｏｌ ｏｆ ｒｏｂｏｔ ｍａｎｉｐｕｌａｔｏｒｓ［Ｊ］．The Internatio唱 nal Journal of Robotics Research，１９８７，6（２）：３唱１５． ［３］ ＹＡＳＨＩＫＡＷＡ Ｔ．Ｍａｎｉｐｕａｔｏｒ ｏｆ ｒｏｂｏｔｉｃｃｓ ｍｅｃｈａｎｉｓｍｓ［Ｊ］．The In唱 ternational Journal of Robotics Research，１９８５，4（１）：３唱９． ［４］ ＫＯＥＰＰＥ Ｒ， ＹＯＳＨＩＫＡＷＡ Ｔ．Ｄｙｎａｍｉｃ ｍａｎｉｐｕｌａｂｉｌｉｔｙ ａｎａｌｙｓｉｓ ｏｆ ｃｏｍｐｌｉａｎｔ ｍｏｔｉｏｎ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ＩＥＥＥ／ＲＳＪ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｒｏｂｏｔｓ ａｎｄ Ｓｙｓｔｅｍｓ．Ｇｒｅｎｏｂｌｅ： ［ｓ．ｎ．］，１９９７：１４７２唱 １４７８． ［５］ ＫＥＮＮＥＤＹ Ｊ， ＥＢＥＲＨＡＲＴ Ｒ Ｃ．Ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］ ／／ Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ．１９９５： １９４２唱１９４８． ［６］ 李新春，赵冬斌，易建强．一种全方位移动机械手的可操作度分析 ［Ｊ］．中国机械工程，２００６，17（１４）：１４４２唱１４４７． ［７］ ＳＨＩ Ｙｕ唱ｈｕｉ， ＥＢＥＲＨＡＲＴ Ｒ Ｃ．Ａ ｍｏｄｉｆｉｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚｅｒ ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｃｏｎｇｒｅｓｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ．１９９８： ６３唱７９． 3畅2　轨迹跟踪仿真 给定直角线段 ABC 为四关节冗余机械手手臂末端任务， 仿真过程从 A ～C 点开始等距离０畅１ ｍ 采样一次。 当分别以 手臂末端可操作性指标 SM４ 和整体最优可操作性指标 SM 为优 化目标函数时，在每个采样点位置根据上面已给出的方法分别 依次给出相应的机械手最优形状，整个过程如图５ 所示。 从图５（ａ）中可以看出，由于采样点坐标的原因，在各个采 样点处与手臂末端最优可操作性指标 SM４ 对应的各个关节角 q２ 相比于对应的其他关节角都很小；而从（ｂ）中可以看出，同一采 样点处，与最优 SM 对应的形状比与手臂末端最优 SM４ 对应的形 状要优越得多，此时与各个形状对应的关节角之间都很均匀。 （ 上接第 ４４７ 页） 　　２）本文设计改进的遗传算法求解有时间窗配送车辆调度 问题，即用自然数顺序编排车辆的行车路线，在交叉操作中避 免优秀基因被破坏，与现有文献中的求解算法相比，本文设计 的算法具有解的表示自然直观、算法策略易于理解、计算效率 较高、收敛速度较快的优点。 ３）本文利用设计的算法对随机产生的有时间窗配送车辆 调度问题实例进行了实验计算，计算结果表明，用本文设计的 改进算法求解有时间窗配送车辆调度问题，不仅可以取得很好 的计算结果，而且算法的计算效率较高，收敛速度较快，计算结 果也较稳定。 参考文献： ［１］ ＢＥＲＧＥＮ Ｊ， ＢＡＲＫＡＯＵＩ Ｍ．Ａ ｐａｒａｌｌｅｌ ｈｙｂｒｉｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ ｗｉｔｈ ｔｉｍｅ ｗｉｎｄｏｗ ［Ｊ］．Computers ＆ Operations Research，２００４，31（１２）：２０３７唱２０５３． ＰＩＳＩＮＧＥＲ Ｄ， ＲＯＰＫＥ Ｓ．Ａ ｇｅｎｅｒａｌ ｈｅｕｒｉｓｔｉｃ ｆｏｒ ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ［２］ ｐｒｏｂｌｅｍｓ［ Ｊ］．Computers ＆ Operations，２００７， 34 （８）：２４０３唱 ２４３５． ［３］ ＪＯＺＥＦＯＷＩＥＺ Ｎ， ＳＥＭＥＴ Ｆ， ＴＡＬＢＩ Ｅ Ｇ．Ｍｕｌｔｉ唱ｏｂｊｅｃｔｉｖｅ ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍｓ ［ Ｊ］． European Journal of Operational Re唱 search，２００８，789（２）：２９３唱３０９． ［４］ 李军，郭耀煌．物流配送车辆优化调度理论与方法［Ｍ］．北京：中 国物资出版社，２００１． ［５］ 赵燕伟，彭典军．有能力约束车辆路径问题的量子进化算法［Ｊ］． 系统理论与实践，２００９，29（２）：１５９唱１６６． ［６］ 李兵，郑四发．求解客户需求动态变化的车辆路径规划方法［Ｊ］． 交通运输工程学报，２００７，7（１）：１０６唱１１０． ［７］ 陈火根，丁 红 纲．物 流 配 送 中 心 车 辆 调 度 模 型 与 遗 传 算 法 设 计 ［Ｊ］．浙江大学学报，２００３，37（５）：５１３唱５１６． 研究［Ｊ］．中国管理科学，２００２，10（５）：５１唱５６． 算法［Ｊ］．东北大学学报，２００６，27（１）：６５唱６８． ［９］ 宋伟刚，张宏霞，佟玲．有时间窗约束非满载车辆调度问题的节约 ［８］ 郎茂祥，胡思继．用混合遗传算法求解物流配送路径优化问题的