遗传算法在车辆调度问题中的应用.pdf

维普资讯 遗传算法在车辆调度问题 中的应用——孙福春 宁 滨 遗传算法在车辆调度问题中的应用 孙福春 宁 滨 (北京交通大学 北京 100044) 摘 要 在消防、救护等场合经常需要 以最短的时间到达 目的地。文章针对这类 问题提出了 一 个调度算法来解决车辆派遣的问题，并在此基础上利用遗传算法给 出车辆行驶 的次优路径 ·给 出了车辆调度相应的数学模型。 关键词 遗传算法(GA)；车辆调度 ；调度算法 中图分类号：U492．22 文献标识码：A Abstract：Infirecontrolandrescue．theshortesttimeisneededtoarrivethedestination．This papergivesadispatchalgorithm tosolvethetaskofdispatchingvehicles．Onthebasisofdispatch algorithm ，the second shorterrouteisalsopresented bymeansofgeneticalgorithm ．Moreover， therelevantmathematicmodelofvehicledispatchisalsogiveninthispaper． Keywords：geneticalgorithm (GA)；vehicledispatch；dispatchalgorithm 法等。尽管局部搜索算法具有通用易实现的优点， 1 相关知识的介绍 但搜索性能完全依赖于邻域函数和初始解 。本文 1)遗传算法 (geneticalgorithm，GA)是一种 使用遗传算法来求解最优路径。 模拟生物遗传学和 自然选择 的机理，通过人工的 2 对车辆调度问题的分析与数学模 方式构造 的一类搜索算法。遗传算法由Holland 型的建立 提出，并由他和他的学生发展完善起来。 2)遗传算法的基本组成。① 编码；② 适应度 在建立数学模型之前给出一些假设条件 。设 函数 ；⑧ 遗传操作 (简单遗传算法的遗传操作主 这个函数是凸函数，这样函数的极值是存在的。该 要有3种 ：选择 (selection)、交叉 (crossover)、变异 模型的输入和输出数据如下 ：Veh为车场总的车 (mutation)；④ 控制参数 。 辆台数，Run(￡)为正在运行 的车辆台数，Back(f) 3)最优路径。求解最优路径问题的方法分为 为已经执行完任务正在返 回车场 的车辆数 目， 精确求解方法和近似求解方法。其中精确求解方 Need(i)为在某一时刻第 i个任务需求 的车辆 台 法又分为篇析方法、穷举方法、分支定界等。近似 数，共有Num (￡)个任务对车辆有需求 ，Undo(f) 求解方法包括基于规则的构造方法、邻域搜索方 表示正准备执行任务 ，Distance()为执行任务的 实际应用 中，本文所述的体系结构还可以方便地 4 郝 琪 ，罗卫平 ．彭炎午 ．等．先进制造 中人机协同的 扩展检测全过程 的视频监控子系统、停车场管理 重要手段—— 自适应人机接 口．中国机械工程，1999 子系统等。 (4)：421～423