毕业设计（论文）-城区物流快递送货的路径选择研究.doc

ANYANG INSTITUTE OF TECHNOLOGY 本本 科科 毕毕 业业 论论 文文 城区物流快递送货的路径选择研究 The Research of path Choice for City Logistics Express 系 院 名称 计算机科学与信息工程学院 专业班级 11 届计算机科学与技术嵌入方向 学生姓名 学生学号 200703020038 指导教师姓名 指导教师职称 副 教 授 2012 年 5 月 毕业设计 论文 原创性声明和使用授权说明毕业设计 论文 原创性声明和使用授权说明 原创性声明原创性声明 本人郑重承诺 所呈交的毕业设计 论文 是我个人在指导教师的指导下 进行的研究工作及取得的成果 尽我所知 除文中特别加以标注和致谢的地方 外 不包含其他人或组织已经发表或公布过的研究成果 也不包含我为获得安 阳工学院及其它教育机构的学位或学历而使用过的材料 对本研究提供过帮 助和做出过贡献的个人或集体 均已在文中作了明确的说明并表示了谢意 作 者 签 名 日 期 指导教师签名 日 期 使用授权说明使用授权说明 本人完全了解安阳工学院关于收集 保存 使用毕业设计 论文 的规定 即 按照学校要求提交毕业设计 论文 的印刷本和电子版本 学校有权保存毕 业设计 论文 的印刷本和电子版 并提供目录检索与阅览服务 学校可以采用 影印 缩印 数字化或其它复制手段保存论文 在不以赢利为目的前提下 学 校可以公布论文的部分或全部内容 作者签名 日 期 城区物流快递送货的路径选择研究 专业班级 11 届计算机科学与技术嵌入方向 学生姓名 指导教师 侯贵法 职 称 副教授 摘要 物流快递是现代电子商务的支撑基础 我们越来越依赖于物流的同时 也伴随着 很多问题 比如能不能尽快送到目的地 怎样才能最快送到等 物流快递送货的路径选 择即对于给定的一组订单 先送什么后送什么的路径规划 对于小规模的送货可用最短 路径和动态规划等方法实现 但是随着问题规模的扩大 组合优化问题常常会呈现组合 爆炸的特征 此类问题无法使用常规方法来求解 属于 NP Hard 问题 车辆路径问题就 是典型的组合优化问题 蚁群算法 ACO 是受自然界中蚂蚁搜索食物行为启发而提出的 一种智能优化算法 研究发现 蚁群算法可以较好地求解 VRP Vehicle Routing Problem 车辆路径优化 等组合优化问题 蚁群算法发现较好解的能力很强 具有分布 式计算 鲁棒性强 易于与其他方法结合等优点 具有十分广阔的应用前景 然而 蚁 群算法存在求解速度慢 在规模扩大后带来收敛慢等问题 对车辆路径问题解决上 现 有的蚁群算法存在难以回归原点等问题 这些问题也是我们面临的巨大挑战 本文采用的是面向对象的 VC 语言 依据蚁群算法解决配送路线的优化问题 文章从 以下几个方面展开 首先充分概括了当前的蚁群算法在车辆路径问题上的研究 详细分 析了基本蚁群算法的原理 然后详细阐述了 VRP 问题并引用了其数学模型 并介绍了蚁 群算法解决 VRP 问题的方法以及现状面临的挑战 并将遗传算法的复制 交叉 变异等 遗传算子引入蚁群算法 同时改进信息素的更新方式 客户点选择策略 以提高算法的 收敛速度和全局搜索能力 关键词 物流配送 车辆路径问题 蚁群算法 The Research of path Choice for City Logistics Express Abstract Logistics express is the basis of modern e business we are increasingly dependent on logistics We are increasingly dependent on the logistics with many problems associating with it at the same time For example if it is sent to the destination as soon as possible how can it be the fastest The delivery route choice of logistics express is a path planning of what should be put foreword and what afterward for a group of given orders It is can be realized by using the method of the shortest path and dynamic programming for the small scale delivery But with the expansion of the scale combinatorial optimization problem often feature a combination of the explosion such problems can not use conventional methods to solve The problem belongs to NP Hard Ant colony algorithm ACO is created by the natural world which is to imitate the process of ants searching for food The study found that ant colony algorithm finds better solutions of strong distributed computing robust easy to combination etc These performances make it have very broad application prospects However the ant colony algorithm has disadvantages like slow convergence in the expansion nodes and so on What s more the an colony algorithm in the vehicle routing problem cannot make traveler return to repository center properly These problems are also huge challenges that we are facing In this paper the system is based on VC technology full analyses of the current ant colony algorithm are listed on the issue Then we analyze the basic ant colony algorithm in detail and then elaborated on the issue VRP and its mathematical model The increasing scale nodes of the combinatorial optimization problems lead to deal with problem more difficult Several genetic operators such as crossover and mutation are inducted into the ant colony algorithm and pheromone updating strategy is ameliorated to improve the efficiency Key words logistic distribution Vehicle Routing Problem ant colony algorithm ACA I 目录 引言引言 1 第第 1 1 章章 绪绪 论论 2 1 1 课题研究的背景和意义 2 1 1 1 课题研究的背景 2 1 1 2 课题研究的意义 2 1 2 研究现状 2 1 3 课题的研究内容 3 1 3 1 基本蚁群算法研究 3 1 3 2 蚁群算法解决车辆路径问题 3 第第 2 2 章章 VRPVRP 问题的蚁群优化算法分析问题的蚁群优化算法分析 4 2 1 蚁群算法应用于 VRP 问题 4 2 1 2 物流配送问题的描述 5 2 1 3 利用蚁群算法解决车辆路径问题 5 2 1 4 实际应用 6 2 1 5 确定可行解采用策略 7 2 2 传统算法存在的问题 8 2 3 相关理论简介 9 2 3 1 蚁群算法基本原理 9 2 3 2 车辆路径问题 9 2 3 3 遗传算法 10 2 3 4 蚁群算法信息素 11 第第 3 3 章章 基于改进的蚁群算法解决车辆路径问题基于改进的蚁群算法解决车辆路径问题 13 3 1 蚁群算法的改进 13 3 1 1 改进算法提出的背景 13 3 1 2 处理策略 13 3 2 可行解问题 16 II 3 3 程序的设计 19 3 3 1 Ant 模块 19 3 3 2 Common 模块 21 3 3 3 蚁群和遗传算法相结合 24 第第 4 4 章章 系统测试分析系统测试分析 26 4 1 单元测试 26 4 1 1 测试 1 26 4 1 2 测试 2 27 第第 5 5 章章 结论结论 29 5 1 总结 29 5 2 展望 29 致谢致谢 30 参考文献参考文献 31 1 引言引言 物流是以物品从供应地向接收地实体流动的过程 它是一个全新的系统概念 和金 融结算一起构成了现代电子商务的两大支撑基础 随着经济的发展和经济体制改革的进 一步深化 物流业正成为我国市场经济中竞争最为激烈的行业之一 其在现代经济发展 中的地位和作用 比任何时期都更加重要 现阶段 物流业已贯穿于我国生产 分配 流通 和消费的各个领域 社会对物流需求的数量 质量正在不断提高 物流配送作为物流体系中最为重要的一环 对整个物流体系的效率起着关键的作用 先进高效的物流配送系统能为企业创造出更高的经济效益 是企业增强自身竞争力的重 要手段 当今物流配送的一个重要的研究领域就是系统优化 车辆调度是物流配送管理最重要的部门 随着社会的发展以及消费者对服务质量要 求的不断提高 高效的车辆调度 以提高物流效率 降低物流成本 提高服务质量对于 促进经济健康稳定的发展具有重要意义 所谓的车辆路径问题 就是车辆和路径的恰当 选取 运输规划的合理制定问题 解决此问题 可用加快对客户需求的响应速度 提高 服务质量 增强客户对物流环节的满意度 降低服务商运作成本 车辆调度问题 vehicle route problem VRP 是物流的一个重要研究方向 是一个典型的车辆调度 问题 也是一个比较重要的组合优化问题 优化技术原本是近代数学的一个分支 优化是指寻求数学上的最优解 而优化技术 则是以数学为基础寻求最优解的技术 在管理科学中 优化是指在给定条件下如何做出 最佳的决策去完成给定的任务 最好地达到预期的目标 对于车辆路径这种组合优化问题 通常随着问题规模的扩大 问题空间呈现组合爆 炸特征 因此 无法用常规方法求解 属于 NP Hard 问题 研究声明 蚁群算法发现较 好解的能力很强 具有分布式计算 鲁棒性强 易于与其他方法结合等优点 具有十分 广阔的应用前景 也具有很重要的研究价值 通过研究车辆路径问题 确定最佳的运输 路线 在提高车辆满载率的同时 使车辆运输距离达到最小化 完善配送系统 使配送 环节的总成本降低 提高配送的效率 2 第第 1 1 章章 绪绪 论论 1 1 课题研究的背景和意义 1 1 1 课题研究的背景 物流业正在成为我国市场经济中竞争最为激烈的行业之一 在我国国民经济和社会 发展 十一五 计划中 已将 物流配送 作为重点支持和发展的服务产业 智能物流 配送管理系统是完成货物配送的功能性系统 也是车辆配送中心系统中一个非常重要的 组成部分 而高效的车辆调度 可以提高物流的效率 降低物流成本 提高物流服务质 量 加快对客户需求的响应速度 增强客户对物流的满意度 1 1 2 课题研究的意义 物流配送路径优化和蚁群算法原型所解决的问题相比有共同点 都是寻找遍历所 有客户点的最短路径的问题 也有其特性 有更多更复杂的约束条件和优化目标 本 文针对这种特点 研究一种基于蚁群算法的优化路径算法 通过引入遗传算子 在局部 搜索过程中能够避免算法早熟 停滞 同时改进信息素的更新方式 客户点选择策略 增强蚁群算法的正反馈作用 从而提高收敛速度和全局搜索能力 使得其在物流配送路 径优化问题中有较好的实际效果 1 2 研究现状 蚁群算法是由 M Dorigo 和他的同事首先提出来 很好地解决了一些复杂的组合优化 问题 如旅行商问题 TSP 和背包问题等等 目前已经有很多种基于蚁群算法或其改进 算法 应用于各种不同的离散优化问题 这些研究涉及到了车辆路径问题 VRP 网络 中路由通信问题 等等 蚂蚁们跟踪信息素路径的行为确实导致了最短路径的发现 即当食物源和巢穴之间 存在多条路径时 一群蚂蚁通过跟踪由个体留下的信息的确找到了优化的路径 这具有 实际研究意义 初步的研究结果表明 蚁群算法在求解复杂优化问题方面有着很大的优 越性 虽然目前对蚁群算法的研究刚刚起步 一些思想还处于萌芽时期 其严格的理论 基础尚未确立 收敛性的证明也不够成熟 国内外的相关研究仍停留在实验探索阶段 但是从当前的应用效果来看 这种模仿自然生物的新型寻优算法无疑具有非常光明的前 景 3 1991 年 意大利学者 M Dorigo 等提出了第一个蚁群算法 蚂蚁系统并成功应用于求 解 TSP 问题 实验结果证明蚁群算法具有较强的鲁棒性和发现较好的解的能力但与此同 时也存在着一些缺陷 如收敛速度慢 易出现停滞现象等 该算法的问世引起了学者们 的普遍关注 针对算法的缺点提出了一些改进的蚁群算法 最近国内外对蚁群算法的研 究日趋火热 相信随着更深入的研究 蚁群算法必定会得到更好的发展 1 3 课题的研究内容 物流配送管理系统是完成货物配送的功能性系统 也是车辆配送中心系统中一个非 常重要的组成部分 正是通过配送管理系统 配送中心才得以最终完成货物从生产商到 用户的转移 实现商品的使用效用 另外 配送中心配送系统还通过对货物的集中 合 理配送有效的节约了运力 降低了整个社会的物流总成本 物流配送管理系统 主要是 配送车辆优化调度 包括集货线路优化 货物配装及配送车辆路径优化 其中的配送车 辆路径优化 是物流系统优化中关键的一环 对配送车辆路线进行优化 可以提高经济 效益 实现物流科学化 为解决配送车辆路径优化问题 做了如下工作 1 3 1 基本蚁群算法研究 首先介绍基本蚁群算法的原理以及相应模型的创立 给出了基本蚁群算法的实现步 骤 着重介绍了如何利用蚁群算法解决车辆路径问题 蚁群算法具有采用分布式并行计 算机制 易于与其他方法结合 具有较强的鲁棒性等优点 但也存在搜索时间长 容易 陷入局部最优是其最突出的缺点 蚁群算法并不完美 为此本文做出改进措施 通过这 种改进 加速了蚁群算法的收敛效果 改进的算法易于实现 1 3 2 蚁群算法解决车辆路径问题 通过对相关文献的分析和总结 从物流配送中车辆路径问题 VRP 的基本理论出发 阐述了 VRP 问题 深入分析了 VRP 问题的数学模型 通过利用已有的蚁群算法解决 VRP 问题 随后分析了基本蚁群算法解决 VRP 问题的不足 结合遗传算法的优点 将复制 交叉 变异这些遗传因子引入蚁群算法中 以提高算法收敛速度和全局搜索能力 4 第第 2 2 章章 VRPVRP 问题的蚁群优化算法分析问题的蚁群优化算法分析 2 1 蚁群算法应用于 VRP 问题 2 1 1 蚁群算法介绍 蚁群算法是一种由于受自然界生物的行为启发而产生的 自然 算法 它是从对蚁 群行为的研究中产生的 蚁群的觅食行为实际上是一种分布式的协同优化机制 蚁群中 的蚂蚁以 信息素 pheromone 为媒介的间接的异步的联系方式是蚁群算法的最大的 特点 单只蚂蚁虽然能够找到从蚁穴到食物源的一条路径 但是找到最短路径的可能性 极小 只有当多只蚂蚁组成蚁群时 其集体行为才凸显出蚂蚁的智能发展最短路径的能 力 这也是蚁群算法的基础思想 通过蚂蚁间的相互合作来搜寻最短路径 在寻找最短路径的过程中 蚁群会在它们经过的地方留下一些化学物质 我们称之 为 信息 这些物质能被同一蚁群中后来的蚂蚁感受到 并作为一种信号影响后到者 的行动 具体表现在后到的蚂蚁选择这些物质的路径的可能性 比选择没有这些物质的 路径的可能性大得多 而后到者留下的信息会对原有的信息素进行加强 并且如此循环 下去 这样 被越多的蚂蚁选择的路径 在后到蚂蚁的选择中被选择的可能性就越大 因为残留的信息浓度较大的缘故 由于在一定的时间内 越短的路径会被越多的蚂蚁 访问 因而积累的信息量也就越多 在下一个时间内被其他的蚂蚁选中的可能性也就越 大 这个过程会一直持续到所有的蚂蚁都走最短的哪一条路径为止 因此 蚁群算法中 另一个重要的机制是自催化机制 也就是正反馈机制 这种正反馈机制将指引蚁群找到 高质量的问题解 除了正反馈机制外 蚁群算法还有信息素挥发机制 路径上的信息素 随着时间不断挥发将驱使蚂蚁探索解空间中新的路径从而避免求解过程中过早的收敛于 局部最优解 蚁群算法大概可以概括为 1 蚂蚁通过的路线会留下信息素 经常通过的路径会造成信息素正反馈 反馈机制 能够扩大解的质量对个体选择路径的影响 使得算法能够快速发现较好的解或最优解 2 在分岔口 信息素浓度大的路线有更大概率被蚂蚁选择 也即蚂蚁仅仅通过信息 素相互交流 3 路径越短的路线 选择的概率越大 这属于人工干涉的人工蚁群算法 在实际中 可以加速找到最短路径 5 4 信息素会随着时间而挥发 使得蚂蚁有更多的几率选择到不常走的路径 2 1 2 物流配送问题的描述 一般配送路径问题可描述如下 有 L 个客户点 已知每个客户点的需求量及位置 至多用 K 辆汽车从配送中心到达这 批需求点 并且在完成配送任务后 返回物流中心 每辆汽车载重量一定 要求安排车 辆行驶路线使得运输距离最短 且满足以下几个约束条件 1 每条线路上的客户点需求量之和不超过汽车载重量 2 每条配送路径的总长度不超过汽车一次配送的最大行驶距离 3 每个客户点的需求必须且只能由一辆汽车来完成 其目的是使总成本 如距离 时间等 为最小 2 1 3 利用蚁群算法解决车辆路径问题 车辆路径问题 简单的来说就是在一定约束下遍历所有节点 我们用人工蚂蚁代替 车辆对客户点进行配送 蚂蚁在 i 客户点选择服务的下一个客户点 j 时 主要考虑两个 因素 一是 i j 两顾客点之间的关系的亲密程度 称为可见度 记为 另外考虑的 ij 是由已完成的循环所得路径方案体现出来的有 i 到 j 的可行性 即信息素浓度 在 t ij 时刻蚂蚁 k 由客户点 i 转移到客户点 j 的概率 P t k ij allowk ikik ijij t t if j 公式 2 1 k allowed 式中变量的意义如下 表示从 i 节点到 j 节点路线的信息素浓度 浓度越大蚂蚁选择走这条路的可能 ij 性就越大 这就体现了蚁群算法正反馈的特点 与节点 i 到节点 j 路线长度有关 这是蚁群算法中人为加上去的一个变量 在 ij 自然界中的蚂蚁并不知道路线长短 为了更好地达到目标 加上了这个变量 它一般是 路径长度的倒数 也即 1 d 但实际情况中 它实际上起的作用是更好地将距离短 ijij 的路线选择的概率变大 也即只要是距离的减函数即可 反应蚂蚁在搜索路径中积累的信息量的相对重要程度 过小 收敛速度慢 6 而且算法很容易陷入局部最优解 如果 过大 相当于信息素的重要性增大 这样也会 很容易陷入局部最优而过早的收敛 在搜索路线的过程中 一些信息也可以左右蚂蚁的选择 比较典型的就是每条路 线的长度 也即长度信息的加权因子 对算法性能也有很大影响 过大 收敛速 度快 过小 则蚁群算法则进入了随即搜索状态 allow 0 1 n 1 表示蚂蚁 k 尚未服务的客户点 k 当下一个要服务的客户点会使运载总量超出汽车载重量 或者使运距超过一次最大 行驶距离时 就返回到配送中心 人工蚂蚁代表下一辆车出发 继续配送 当一次循环 结束后 蚂蚁遍历了所有客户点 完成一次配送 当所有蚂蚁完成一次循环后 根据各 蚂蚁遍历的好坏 目标函数值 计算信息素增量 更新相关路径上的信息素 更新规则 ijijij tnt 公式 2 2 m k k ijij 1 2 1 4 实际应用 实际应用中 和 并不是相对独立的 彼此间相互影响 这也在很大程度上变成 了难以解决的问题 很难确定究竟如何选择参数 由以前研究的结论中 1 0 2 0 4 0 6 0 0 1 0 5 是蚁群算法中参数的最优设置 其中 是信息素挥发因 子 在蚁群算法中 每只蚂蚁的回路仅仅是可行解的一个部分 我们将一些蚂蚁的回路 组合起来 如果这些回路包括了所有的节点 我们称这个回路的集合为可行解 然而很 可能在完成后一个可行解都得不到或者很难确定可行解 将复制 交叉 变异这些遗传算子引入蚁群算法中 以提高算法的收敛速度 1 编码 遗传算法中的交叉和变异操作是建立在基因编码上的 因此在引入交叉和变异操作 之前 我们首先对物流配送模型进行编码 假设有 L 个客户点 K 辆配送车辆 本文采用的编码方式是将这 L 个客户点分别用到 1 到这 L 个自然数标识 第一辆车从配送中心出发时用 0 标识 其他车辆则分别用 7 L 1 L 2 L K 1 表示 由于同一辆车可以多次配送 所以 2 次以上配送的车辆 出发时 依次用 L K L K 1 表示 新的一辆车从配送点出发 或者编码结束 就 表示前一辆的路线结束 返回配送中心 这样就将一次配送表示为一组由 0 和自然数组 成的编码 例如 有 6 个客户点 我们分别用 1 至 6 表示 3 辆车负责 那么编码 0 1 2 3 7 4 5 8 6 表示三辆车的配送路线分别是 车辆 1 0 1 2 3 0 车辆 3 0 4 5 0 车辆 1 第二次配送 0 6 0 2 交叉 交叉操作是遗传算法中增加种群多样性 防止算法早熟 停滞的操作 在蚁群算法 中引入交叉操作 可以有效地扩大搜索空间 避免算法陷入局部最优解 在蚁群算法每一代搜索完成之后 我们将其中的最优解和次优解进行编码交叉操作 交叉规则如下 假设两组编码分别是 S1 和 S2 首先随机生成交叉段的长度和交叉段起始位置 找出 S1 和 S2 中的交叉段 假设 S1 P P P S2 Q Q Q P 和 Q 分别是 12312322 S1 和 S2 的交叉段 将 Q 插入 S1 中 位于 P 前面 这样形成新的编码 S3 P Q 2212 P P 23 在 S3 中 删除 P P P 中与 Q 重复的编码 形成交叉编码 S3 1232 同样的方法用在 S2 上 生成新的编码 S4 比较 S1 S2 S3 S4 的结果 选出最优的两组编码并保存 3 变异 变异操作也是增加种群多样性的一种进化手段 适度的变异 既能保持种群内个体 的多样化 又能提高算法的效率 在蚁群算法中 我们在完成交叉操作后 对种群中最优个体进行变异操作 操作方 法为 随机生成变异次数 N 随机生成两个不同的自然数 n n 1 第一位不变 保证编码以物流中心为起点 12 在最优个体的编码 S 中 将第 n 位和第 n 位的编码对调 12 重复 N 次 生成新的编码 S 8 比较 S 和的结果 保存较优解 S 2 1 5 确定可行解采用策略 根据已研究出来的结论可得到以下策略 1 大蚂蚁数策略 增加蚂蚁数量 扩大范围 增加可行解产生的可能性 2 蚂蚁初始状态均匀分布 在每次迭代前 蚂蚁随机均匀分布于各个节点 从而发 现可行解的机会增大 3 近似解策略 当一些情况下无法得到可行解时 或者很难得到可行解时 选择一 些非可行解作为近似 然后按照一些近似化策略得到一些可行解 采用这种策略一般可 以得到可行解 但是结果是否好则很难确定 关于可行解的一些策略虽然有理论研究价值 但在实际情况下 很难利用大量时间 去测试回路间是否有可行解 回路是否能够构成可行解 2 2 传统算法存在的问题 传统的蚁群算法研究与实际应用结合不足 在实际中 如何让蚁群算法可以进行企 业级的应用 通过蚁群算法来为多客户进行服务 同时对算法的安全性 快速性 可行 性 有效性提出了挑战 单独运行蚁群算法时 可能对于其速度等因素并不考虑太多 许多研究仅仅停留在 理论层面 但当用户数量 仓库规模变大时 蚁群算法的速度问题将受到越来越多的重 视 传统蚁群算法对 TSP 问题求解时得到算法复杂度为 O NC n m 2 表 2 1 基本蚁群算法时间复杂度 步骤内容时间复杂度 1 初始化参数 O n m 2 2 设置蚂蚁禁忌表 O m 3 每只蚂蚁单独构造解 O n m 2 4 解的评价和轨迹更新量的计算 O n m 2 5 信息素轨迹浓度的更新 O n 2 6 判断是否算法终止 O nm 7 输出结果 O 1 其中 NC 表示迭代次数 n 表示节点数 m 表示蚂蚁数量 当 n 增大时 将影响对服 9 务器的性能 如何在有限的迭代次数中得到接近最优解成了巨大的挑战 在可行解的搜 索方面 传统的蚁群算法将得到大量的无用解 耗费大量的资源 传统算法的应用性研究并不多 没有针对特殊问题的整体解决方案 也即没有将理 论很好地渗人现代物流项目中 这里包含很多原因 其中一个重要原因是没有与具体实 际相结合 研究的东西很多偏向理论 导致物流企业无法直接感触到算法对物流领域带 来的巨大影响 随着一系列新的技术的提出和成熟 蚁群算法渐渐可以和其融合起来 在实际项目中体现出巨大的潜力 2 3 相关理论简介 2 3 1 蚁群算法基本原理 蚂蚁在寻找食物过程中 单个蚂蚁很难找到食物到蚁穴的最短路径 但一个蚁群往 往可以很轻易地找到最优解 寻其原因 单个蚂蚁在爬行时留下了具有挥发性的信息素 蚂蚁根据信息素的大小选择路径 随着时间流逝 信息素会不断减小 那些相对较短的 路线 蚂蚁通过的频率较高 信息素也较高 这将导致越来越多的蚂蚁选择较短路径 这样正反馈就产生了 蚂蚁也最终找到一条最优路线到达目的地 2 3 2 车辆路径问题 在物流配送领域中 有一类问题是非常常见的 存在一批客户 各个客户的位置和 货物需求是已知的供应商具有若干可供派送的车辆 运载能力是一定的 每辆车都从起 点出发 这个起点我们通常称为配送中心 从这个起点出发完成若干客户点的配送任务 后再回到配送中心 现在 要求的是用最小的车辆总行程类完成货物的派送 这个问题被 称为车辆路径问题 vehicle routing problem 也即 VRP 车辆路径问题是物流的一个重要研究方向 在物流系统中起很大的作用 也是一个 比较重要的组合优化问题 其研究的是如何使用最短路径遍历一个加权路径网络 这也 相似于旅行商问题 但是相对于旅行商问题 车辆路径问题有更多的约束 这将增大算 法的难度 对车辆路径问题的描述如下 一个城市里存在一个配送中心 存在多个仓库 仓库 中有货物 且货物是有重量的 且货物种类不同 现有 n 辆车 每辆车的载重是 Q 现在 利用这 n 辆车通过所有仓库 从仓库里取得货物 并将货物送回配送中心 怎样才能取 得最短路径使得所有车辆的运行轨迹之和最短 车辆路径问题属于 NP Hard 问题 求解 VRP 的计算量会随着仓库的增加而急剧增加 通常我们在物流方面的应用仅仅是找到次优 10 解 也即近似最优解 车辆路径问题的数学描述 通常使用有向加权图 G V A d 来表示 VRP 问题 其 中 V v0 v1 vn 表示节点 v0 表示配送中心 也是每辆车的起点和终点 A Vi Vj i j 表示连接两节点的弧 在实际问题中由于存在单行道的问题 Vi Vj 并不等于 Vj Vi 也即图所对应的矩阵并不是对称的 每个仓库节点都有一定的需求 q 其中 q 必须为一个大于 0 的数 Q 为车的载重量 ii 对于路线 Rk 路线上面经过的所有的节点的需求之和应该小于 Q 也即对第 j 条线路应 有 q 1 第一位不变 保证编码以物流中心为起点 12 在最优个体的编码 S 中 将第 n 位和第 n 位的编码对调 12 重复 N 次 生成新的编码 S 比较 S 和的结果 保存较优解 S 5 其他改进策略 在引入遗传算法对蚁群算法进行改进后 算法的收敛速度和全局搜索能力得到了提 高 我们下面还将从信息素的更新方式 客户点选择策略进行改进 以提高蚁群算法的 自适应性 信息素传递参数的选取 按照基本蚁群算法 是一个常量 如果 过大 则会使未搜索过的路径被选择的 概率相对减小 影响全局搜索能力 而如果 过小 又会影响算法的收敛速度 因此我 15 们在改进算法中将对 作适当调整 在算法初期 我们希望算法能尽快找到较优解 因 此 要比较大 增大信息浓度的影响 加快算法收敛速度 而当算法停滞不前时 我们 要减小 从而减小信息素对蚁群的影响 增大蚁群对解空间的搜索 以脱离局部最优 解的束缚 1 t MAX r r min t min others t 公式 3 1 3 1 式中 r 表示连续没有进化的循环的次数 r 是一个常量 0 1 是一个 max 常量 控制 衰减速度 是 的最小值 防止 过小影响收敛速度 当r 达到预先 min 设置的一个数值r 时 我们就减小 r 重新计数 如此反复 直至 达到预设最小 max 值 为止 min 确定性搜索和探索性搜索的选择 加速收敛就是要在已得到的较优解的基础上 尽量快的进化 以得到更优解 由于 蚁群算法是一种启发式算法 不断地 探索 是蚁群算法进化的必要手段 而正是这种 探索 限制了蚁群算法收敛速度 例如 当算法得到一个较优解 而且该解有可能进 一步优化 但由于 探索 范围很大 使得蚂蚁选择该路径的概率相对减小 从而使得 路径上的信息量浓度逐渐衰减 该路径也逐渐被 遗忘 了 为了解决这一问题 我们 引入一个新的常量 q0 0 1 蚂蚁k 在每次选择路径之前 先随机产生一个q 0 1 蚂蚁k 选择路径s 将根据下式 当q q0时 依照概率得到j 当q q0 时 j argmax 公式3 2 k allowedj tt ijij 公式3 2中 当q q0 时 是基本蚁群算法中的探索性搜索 当q q0 时 是从已得的 结果中 找出概率最大的路径作为选择 是对已得成果的 利用 为确定性搜索 确 定性搜索弥补了探索性搜索在收敛速度上受限制的缺陷 通过适当调整q0 能够使得确定 性搜索和探索性搜索合理搭配 加快蚁群算法的收敛速度 我们还要对q0 的取值进行讨 论 当q q0 时 算法是采用确定性搜索 此时蚂蚁以概率q0 选择距离最短的路径 当 q q0时 算法是采用探索性搜索 此时蚂蚁以概率l q0 随机选择路径 在算法迭代的 初期q0 选取较大的初始值 以较大的概率进行确定性搜索 这样可以加快寻找局部较优 16 路径的速度 在算法的中期q0 选取较小的值 增大探索性搜索的概率 从而扩大搜索空 间 在算法的后期 恢复q0 的初始值 加快收敛的速度 3 2 可行解问题 在第二章中看到许多解决方法 但实际上 在真正的开发中 如何写出一个好的函 数来解决可行解问题是很困难的 如果一开始把蚂蚁随意洒在节点上让其任意爬最后才 来整理可行解空间 这是对资源的浪费 而且只有在蚂蚁数量很多时才可能有可行解被 发现 而且可行解的发现过程牵涉到回路间的相交问题 因此其本身就是一个很复杂的 过程 在工程中 蚁群算法的应用是一个很考验效率的问题 如果任其乱爬 转换为计算 机资源 实际上就是对 CPU 和内存的浪费 因此 我们可不可以在蚂蚁爬完的时候可行 解就自动出来呢 答案是肯定的 我们可以完全回避可行解问题 将可行解化到整个过 程中 首先 将所有蚂蚁都放在配送中心 这相对于蚂蚁均匀分布在节点而首先回到配送 中心是一个改变 蚂蚁均从配送中心出发 经过一系列节点后回到配送中心 此时的禁 忌表有所变化 已经走过的节点从禁忌表中除去 下一只蚂蚁出发 它可以走的节点为 第一只蚂蚁走剩下的节点 这样一只只蚂蚁从原点出发 当所有节点都遍历一遍时 所 有出发的蚂蚁所组成的回路自然就形成了一组可行解 更新信息素方面 可以根据排序蚁群算法进行 每次产生一个新的可行解时 对比 原来的精英蚂蚁所形成的可行解集合 如果发现比其中某些可行解要更优 则替换之 并在路上留下较强信息素 表示此路径有可能比较优越 下图为蚁群算法解决 VRP 问题的整体流程图 在图 3 1 中 具体阐述了整个算法的 框架 其中 tabu 表示蚂蚁 k 尚未服务的客户点 k 17 开始 G 0 初始化信息 C 设置进 化代数 G MAX 对每只蚂蚁 初始化车辆序列 随机产生 q 1 0 G G MAX 确定性搜索探索性搜索 更新 tabu q q 0 对最优解进行复制 交叉 变异 返回物流中心 选择下一辆 结束 Y N Y N tabu 满了吗 tabu 0 更新最佳路径 清空 tabu G G 1 更新 q0 若连续 未进化代数 r r max min MAX 得到最优路径 输出结果 Y N N Y N 图 3 1 用蚁群算法解决 VRP 问题的整体流程图 18 还有一个重要的步骤 就是如何实现蚂蚁的路径选择 这也是蚁群算法的核心所在 图 3 2 为我们显示出每只蚂蚁构造路径的流程 开始 此蚂蚁结束 是否在配送中心 下步不可是配 送中心 下步允许是配送 中心 利用轮盘赌求得下 步路线 处理禁忌表 是否走完全部节点 并返回配送中心 计算每条线路的概 率 YN Y N 图 3 2 每只蚂蚁构造路径的流程 为了在蚂蚁寻找路线的过程中就确定可行解 我们一开始把所有蚂蚁放在配送中心 的位置 蚂蚁出发后寻找下一个仓库节点 如果在配送中心则下步允许到配送中心 通 过计算每条路线的概率后 由计算机随机生成一个概率值 利用轮盘赌的方法找到一个 19 路线 使用公式计算出是否回到配送中心 这时确定蚂蚁的下一步路线 处理禁忌表 当所有节点均被遍历并且蚂蚁回到配送中心后 这只蚂蚁的行程结束 在它的所有步骤 中 我们并不更新信息素 因为这个蚂蚁的路线可能是很差的 只针对那些精英蚂蚁采 用更新信息素的策略 3 3 程序的设计 程序的几个模块 3 3 1 Ant 模块 算法实现类 定义蚂蚁类 保存车辆的发车顺序 车辆数组 生成随机数 蚂蚁去 过和没去过的城市等 include common h class CAnt public CAnt void CAnt void public int m CarOrderAry N MAX CAR COUNT ANT VEHICLE m CarAry N MAX CAR COUNT double m dbQ int m AllowedCity N MAX CITY COUNT 1 int m nCityCount int m nCurCity int m nCurCarIndex int m nPath N MAX PATH int m nPathCount double m dbPathLength bool m blSearchFail private int ChooseNextCity void Move public void Init void Search void CalPathLen include StdAfx h 20 include ant h CAnt CAnt void memset m nPath 0 sizeof m nPath m nPathCount 0 CAnt CAnt void void CAnt Init for int i 0 i CAR COUNT i m CarOrderAry i i void CAnt Search int nBackCount 0 while m nCityCount CAR COUNT m blSearchFail true break else nBackCount 0 if m nPathCount N MAX PATH m blSearchFail true break 21 if m blSearchFail false CalPathLen 3 3 2 Common 模块 公共头文件 定义变量和公用函数 包括城市结构体 车辆结构体 蚂蚁车辆结构 体 蚁群算法参数等 pragma once struct CITY double dbX double dbY double dbW double dbTB double dbTE double dbTS struct VEHICLE double dbMaxLength double dbMaxWeight double dbSpeed struct ANT VEHICLE double dbMovedLength double dbMovedWeight double dbMovedTime 22 int nSendCount const int N MAX CITY COUNT 200 const int N MAX ANT COUNT 100 const int N MAX CAR COUNT 100 const int N MAX IT COUNT 10000 const int N MAX PATH 1000 const double DBQ 100 0 const double DB MAX 10e9 const double Pbest 0 05 const int R MAX 5 const double Q Min 0 2 const double Q Max 0 8 const double Q POWER 1 0 extern int CAR COUNT extern int CITY COUNT extern double ALPHA extern double BETA extern int ANT COUNT extern int IT COUNT extern double ROU MAX extern double ROU MIN extern double ROU REDU extern double g distance N MAX CITY COUNT 1 N MAX CITY COUNT 1 extern double g Pheromone N MAX CITY COUNT 1 N MAX CITY COUNT 1 extern double g distance BETA N MAX CITY COUNT 1 N MAX CITY COUNT 1 extern double g Prob N MAX CITY COUNT 1 N MAX CITY COUNT 1 extern VEHICLE g CarAry N MAX CAR COUNT extern CITY g CityAry N MAX CITY COUNT 1 23 extern CProgressCtrl g pc extern bool g blLenInt extern int g nHTW extern double g dbPathLenAry N MAX IT COUNT extern double g dbPathAvgLenAry N MAX IT COUNT extern int rnd int nLow int nUpper extern double rnd double dbLow double dbUpper extern double ROUND double dbX extern double MAX double dbA double dbB extern double MIN double dbA double dbB extern int MAX int A int B extern int MIN int A int B template T Create2DArray int M int N T pAry new T M for int i 0 i M i pAry i new T N return pAry template void Free2DArray T pAry int M if pAry NULL return for int i 0 i M i delete pAry i delete pAry pAry NULL 24 3 3 3 蚁群和遗传算法相结合 包括信息素 蚂蚁分组 遗传算法的复制 交叉 变异等操作 pragma once include common h include Ant h class CTSP public CTSP void CTSP void private double m pdbTempAry CString GetFieldValue CString strIniFile CString strSection CString strKey private double m dbMaxQ double m dbMinQ double m dbRatio double GetGreedSearchLen public CAnt m cAntAry N MAX ANT COUNT CAnt m global best ant CAnt m iteration best ant CAnt m vary ant CAnt m temp ant double m dbRou double m dbMinLength int m nBestPath N MAX PATH int m nBestPathCount int m nStep int m nVaryStep int m nVaryCount bool m blVary public void Init void Search void SaveBestAnt void UpdatePheromone int nFlag void Propagate bool Vary bool Vary 2 bool Vary 3 bool CheckVaryAnt CAnt ant public 25 int GetCarNo int nNode void CalCityDistance void SetParameterDefault void LoadDataFromIniFile CString strIniFile 26 第第 4 4 章章 系统测试分析系统测试分析 系统详细设计完成后 往往要对系统进行测试 以便检验系统的性能和功能 这是 一个严格的过程 必须认真进行 系统测试主要解决各模块之间的数据