基于遗传算法的车辆路径问题研究(编辑修改稿)

基于遗传算法的车辆路径问题研究(编辑修改稿)内容摘要：

所有的需求点建构成一条路线，再根据车辆的容量将这一路线分割成许多适合的单独路线。 1990 年以来，人工智能方法在解决组合优化问题上显示出强大功能，在各个领域得到充分应用，很多学者也将 人工智能 引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法。 禁忌搜索法 （ TS）基本上是属于一种人工智能型（ AI）的局部搜寻方法， Willard 首先将此算法用来求解 VRP ，随后亦有许多位学者也发表了求解 VRP 的 TS 算法。 西南交通大学 的袁庆达等设计了考虑时间窗口和不同车辆类型的禁忌算法，这种算法主要采用 GENIUS 方法产生初始解，然后禁忌算法对初始解优化。 模拟退火方法具有收敛速度快，全局搜索的特点， Osman 对 VRP 的模拟退火算法进行了研究，他提出的模拟退火方法主要适合于解决路线分组。 遗传算法 具有求解组合优化问题的良好特性， Holland 首先采用遗传算法（ GA）编码解决 VRPTW 问题。 现在多数学者采用混合策略，分别采用两种人工智能方法进行路线分组和路线优化。 Ombuk 提出了用 遗传算法 进行路线分组，然后用禁忌搜索方法进行路线优化的混合算法。 Bent 和 Van Hentenryck 则首先用 模拟退火算法 将车辆路线的数量最小化，然后用大邻域搜索法（ largneighborhood search）将运输费用降到最低。 10 总结几种人工智能方法可以看出， TS 算法所得到的解最接近最优解，但其运算时间也最长，是 GA 算法的 2～ 3 倍， SA 算法的近 20 倍；由于 GA 算法也能较好的逼近最优 解，同时使运算时间大大缩短，所以 GA 算法能兼顾运算时间和效率两方面，是具有较好的发展前途的方法； SA 算法求解速度非常快，也能提供一定程度上的优化方案在求解较小规模问题上具有较好效果。 11 4 遗传算法介绍 遗传算法简称 GA(Geic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。 它是根据生物进化思想而启发得出的一种全局优化算法。 遗传算法的概念最早是由 Bagley 在 1967 年提出的；而开始遗传算法的理论和方法的系统性研究的是 1975 年，这一开创性工作是由 Michigan 大学的 . Holland 所实行。 当时，其主要目的是说明自然和人工系统的自适应过程。 遗传算法是受生物进化学说和遗传学说启发而发展起来的，基于适者生存思想的一种较通用的问题求解方法。 利用遗传算法进行寻优时，编码、选择、交叉、变异是四个重要步骤。 遗传算法作为一种全局优化搜索方法，具有简单、通用普适性强，适用于并行处理和应用范围广等优点。 遗传算法在优化领域表现出了其强大的能力，遗传算法仿照生物进化和遗传的规律，利用复制、交换和突变等操作，使优胜者繁殖，劣败 者消失，一代代重复同样的操作，最终找出最优解。 具有如下特点： (1) 遗传算法运算的是解集的编码，而不是解集本身； (2) 遗传算法的搜索始于解的一个种群，而不是单个解； (3) 遗传算法只使用报酬信息（适值函数），不使用导数或其他辅助知识； (4) 遗传算法采用概率的，而不是确定的状态转移规则。 遗传算法特别适用于传统搜索方法难以解决的复杂的和非线性的问题，可广泛用于组合优化、自适应控制、规划设计和人工生命等领域。 作为一种随机优化技术在解优化问题中显示了优于传统优化算法的性能，遗传算法的一个显著优 势是不需要目标函数明确的数学方程和导数表达式，同时又是一种全局寻优算法，不会象某些传统算法易于陷入局部最优解。 遗传算法是具有 “ 生成 +检测 ”(generate andtest)的迭代过程的搜索算法。 遗传算法中包含了如下 5 个基本要素： 1)参数编码； 2)初始群体的设定； 3)适应度函数的设计； 4)遗传操作设计； 12 5） 控制参数设定 (主要是指群体大小和使用遗传操作的概率等 )。 这 5 个要素构成了遗传算法的核心内容。 遗传算法的基本思想 遗传算法是受生物进化学说和遗传学说启发而发展起来的，基于 适者生存思想的一种较通用的问题求解方法。 利用遗传算法进行寻优时，编码、选择、交叉、变异是四个重要步骤。 遗传算法作为一种全局优化搜索方法，具有简单、通用普适性强，适用于并行处理和应用范围广等优点。 遗传算法在优化领域表现出了其强大的能力，遗传算法仿照生物进化和遗传的规律，利用复制、交换和突变等操作，使优胜者繁殖，劣败者消失，一代代重复同样的操作，最终找出最优解。 具有如下特点： (1) 遗传算法运算的是解集的编码，而不是解集本身； (2) 遗传算法的搜索始于解的一个种群，而不是单个解； (3) 遗传算法只使用报酬 信息（适值函数），不使用导数或其他辅助知识； (4) 遗传算法采用概率的，而不是确定的状态转移规则。 遗传算法流程图 13 图 2 遗传算法流程图 14 5 模型建立求解及实例应用 车辆调度模型 根据上述对问题的描述 ， 可以采用混合整数规划方法对车辆调度进行建模 设 N为最小成本 ， 则目标函数为 满足约束条件 1： 式中： K为所有车辆的集合， ； G为所有客户的集合， ， ， 其中 {0}代表配送中心 ； 为由车辆 k服务的客户的集合； 为车辆到达客户 i的时间； 为惩罚函数，车辆在时间 到达客户 i时所对应的惩罚成本； 为车辆从客户 i到客户 j的所有运输成本； 为车辆从客户 i到客户 j的行车时间； 为客户 i的需求量 ； Q为车辆 k的最大装载量； 为车辆在客户 i处的停留的时间。 另外 ， 变量 和 的值为 0 或 1。 若车辆 k 为客户 i 服务 ， 则 1， 否则为 0， 即 ： 此变量表示车辆分配方案 ， 可用布尔矩阵表示 ； 若车辆 k 经由客户 i 到客户 j， 则 为 1， 否则为 0， 即 ：， 表示车辆路线安排。 约束条件 2： 保证每个客户均被服务 ， 而且每辆车都从配送中心出发 ； 约束条件 3： 表示每辆车负责的客户点的货物需求量总和不超过该车辆的最大装载量 ； 15 约束条件 5： 表示对任一由 k服务的客户点 j必定有另一 (而且只有一个 )由 k服务的客户点 (包括配送中心 )I,车辆 k从客户点 i到达客户点 j,而对由 k服务的客户点 i同样存在由 k服务的另一客户点 ,车辆 k是从该客户点到达客户点 i的 ,依次类推 ； 约束条件 6： 保证每辆车的行车路线的总耗时不超过一个事先定下的数值 ； 约束条件 7： 对某个客户点 ， 车辆到达时间限制 在某一时间段内。 根据实际情况 ， 本文采用软限制时间窗 ， 其惩罚函数 如图 2所示。 其中 ，为客户所要求的送货时区 ， 为时间窗 ， 超过该范围客户将拒绝收货 ， 因此设定一个极大的惩罚成本 以避免此情况的发生。 图 3 惩罚函数 带时间窗的物流配送问题优化问题 带时间窗 VRP（ VRP with Time Windows， VRPTW）是带装载能力约束的CVRP(Capacitated VRP， CVRP)的扩展。 在该类问题中，有车辆装载能力约束，且每个客户 i 都有一个与之相联系的时间区间 [ai ,bi]， 称为时间窗。 客户的服务必须在相应的时间窗内开始，车辆必须在客户点停留的时间长度为 si。 按客户对物流中心违反时间窗约束规定时的接受程度，可分为硬时间窗、软时间窗和混合型时间窗。 硬时间窗 (Hard Time Windows)：指配送车辆必须在特定时间区段，将货物送达顾客手中，不论是迟到或早到都完全不予接受；软时间窗 (Soft Time Windows)：允许服务的开始时间有所偏离时间窗，则必须按照违反时间的长短。