基于蚁群算法的图书物流中心配送路径规划.pdf

第 26 卷第 4 期湖 北 工 业 大 学 学 报2011 年 08 月 Vol 26 No 4 Journal of Hubei University of TechnologyAug 2011 收稿日期 2011 03 16 作者简介 计三有 1963 男 湖北汉川人 武汉理工大学教授 研究方向为机械设计及理论 物流技术及设备 物流 管理 文章编号 1003 4684 2011 04 0019 02 基于蚁群算法的图书物流中心配送路径规划 计三有 王 星 武汉理工大学物流工程学院 湖北 武汉 430063 摘 要 以图书物流中心车辆路径规划问题为研究对象 结合图书配送多品种小批量的特点 以配送路线最短为 目标 在考虑车辆容量限制的条件下 建立基于零担运输策略的图书物流中心车辆路径规划模型 针对传统路径规 划问题研究的不足 运用 GPS 导航系统重新定义了配送距离 用蚁群算法对所建模型进行求解与仿真 并结合实际 案例给出优化结果 验证了模型及算法的有效性 关键词 车辆路径规划 图书配送 蚁群算法 中图分类号 U116 2 文献标识码 A 车辆 路径 问题 Vehicle Routing Problem VRP 最早由 G Dantzig 和 J Ramser 于 1959 年提 出 1 VRP 问题已经被证明是 NP Hard 问题 针对 它的求解算法主要有精确算法和智能算法两类 由 于精确算法在有限的时间内并不是总能得到合适的 解 因此 在实际应用中 智能算法要更有效 本文采 用一种新型的智能算法 蚁群算法 Ant Colony Optimization ACO 进行求解 1 图书物流车辆路径规划模型 图书因其商品的特殊性质 客户的需求一般体 现为高频率 小批量的特点 在这种情况下 单个客 户的需求量通常较小 多个客户需求量之和才能达 到一部车辆的有效装载容量 若仍采用不同客户需 求分车配送的方式 则大大降低了资源利用率 2 3 1 1 模型描述及优化 为简化建模过程 优化模型结构 特对物流车辆 路径规划模型做如下设定 1 配送中心的图书储备 量能满足所有需求点的需求 不存在缺货情况 2 车 辆顺序地为需求点提供配送服务 只有卸货不带取 货 3 每个客户需求点只被一辆车服务一次 4 配送 车辆由配送中心出发 服务结束后返回配送中心 1 2 车辆路径规划模型 根据模型描述及相关假设 基于零担运输策略 的图书物流车辆规划模型建立如下 min N j 0 N i 0 K k 1 xijkdij 1 N j 1 x0jk 1 k K 2 N i 1 xi0k 1 k K 3 K k 1 N i 0 xijk 1 j 1 2 N 4 K k 1 N j 0 xijk 1 i 1 2 N 5 N i 0 qi N j 0 xijk Ck k 1 2 K 6 其中 N 为客户需求点总数 k 代表车辆编号 且 k 1 2 K dij为需求点i 与j 之间的距离 其 中 i j 且i j 1 2 N qi为客户点i 的需 求量 Ck为车辆k 的最大装载量 xijk 为判断系数 且 xijk 1当车辆由客户点 i 到j 时 i j i j 1 2 N 0其他 式 1 为优化目标表达式 使配送路径的总里程数尽 可能小 式 2 3 表示每一辆参与配送的车辆都从 配送中心出发 并最终回到配送中心 式 4 5 表 示每个需求点被且仅被一辆车服务一次 式 6 表示 容量约束 保证每辆车的实际装载量都不超过其容 量 2 最短距离的改进 目前在 VRP 问题的研究中 任意两个客户点 间的最短距离 通常采用两点间的直线距离 这样的 简化与实际路程并不吻合 5 城市交通路况比较复杂 两点之间的距离并非 是直线距离 而是行车路线中各段路程的代数和 有 的时候实际距离与直线距离相差非常大 针对该问题 本文结合实例在计算任意两个客 户点之间的最短距离时采取通过 GPS 导航系统取 得的路程数据为基础 进行优化计算 3 蚁群算法 蚁群算法最早是由 Marco Dorigo 于 1992 年在 他的博士论文中提出 是一种模仿蚂蚁觅食过程的 模拟进化算法 6 为模拟蚂蚁选择路径及路径上信息素的更新过 程 定义如下符号 m 为蚂蚁数量 dij为城市i j 之 间的距离 ij是路段 i j 的能见度 反映由城市 i 转移到城市j 的启发程度 ij 1 dij ij为t 时刻在 ij 路径上信息素的残留量 则蚂蚁从城市 i 转移到 城市j 的概率 p k ij ijt ijt s tempk ijt ijt j tempk 0 otherwise 式中 和 为两个参数 分别表示已积累的信息和 启发信 息 在 蚂蚁 选 择路 径 时的 相 对 重 要性 tempk k 1 2 m 是为满足容量约束的配送点 的集合 表示在 t 时刻蚂蚁k 可选的待访问点 信息素更新规则如下式所示 ij t 1 1 ij t ij t 其中 是为了避免累积的信息素淹没启发信息引 入的挥发系数 0 1 ij t 表示本次循环中 i j 路段的信息素增量 7 8 4 配送实例分析 本配送实例中 相关配送点数据存入 matlab 工 作空间 在算法优化过程中调用 根据模型建立蚁群算法程序 参数设置为 蚂蚁 数 m 15 信息素比重 1 启发信息比重 4 挥发系数 0 1 进化次数 n gen 100 用 mat lab7 0 编程求解 程序运行结果如图 1 所示 最终线路 线路一 1 22 16 13 17 19 14 1 线路二 1 8 2 3 18 4 9 1 线路三 1 10 5 6 12 7 1 线路四 1 21 20 15 11 1 运输总距离为 178 9 km 经统计 计算 该次配送 的实际运 输距离为 207 0 km 与之相比 经过优化的配送路径能减少 13 的配送里程 图 1 程序运行结果 5 结论 结合图书配送的特点 在配送车辆装载容量有 限情况下 建立以配送总里程最短为目标的图书物 流配送路径规划模型 开发了符合模型描述的蚁群 算法程序 针对实例的仿真研究表明 优化结果能降 低配送里程 提高配送效率 减少配送决策时间 参 考 文 献 1 Dantzig G Ramser J The trunk dispatching problem J Management Science 1959 6 80 91 2 张美娟 图书物流新发展 图书物流配送 J 出版发行 研究 2000 6 43 44 3 胡 勇 郁阳刚 关于图书物流配送的研究 J 商场现 代化 2007 35 108 4 龚延成 郭晓汾 尤晓铃 等 基于遗传算法的物流配送 车辆调度间题研究 J 数学的实践与认识 2004 34 6 93 97 5 陈 昊 宁红云 基于集合运算的最短路径搜索算法 J 计算机工程 2007 33 20 199 203 6 Colorni A Dorigo M M aniezzo V et al Distributed op timization by ant colonies C Proceedings of the 1st European Conference on Artificial Life 1991 134 142 7 王 颖 谢剑英 一种自适应蚁群算法及其仿真研究 J 系统仿真学报 2002 14 1 31 33 8 Bell E MeMullen R Ant colony optimization tech niques for the vehicle routing problem J Advanced Engincedng Informaties 2004 18 41 44 下转第 28 页 20 湖 北 工 业 大 学 学 报2011 年第 4 期 Research on the Blind Source Separation of Gearbox vibration and Its Application in Gear Fault Diagnosis JIANG Yu1 LI Zhi xiong2 1 School of Inf ormation and Engineering Huangshan University H uangshan 245021 China 2 School of Energy and Power Engineering Wuhan University of T echnology Wuhan 430063 China Abstract In this paper a condition monitoring and faults identification technique for rotating machineries based on independent component analysis ICA and support vector machine SVM is described In the diagnosis process the ICA was initially employed to separate characteristic vibration signal and interfer ence vibration signal from the parallel time series obtained from multi channel accelerometers mounted on different positions of the gearbox T hen the ICA features could be obtained from the characteristic signal Finally the SVM was implemented in the pattern recognition process to identify the conditions of the gears of interest The experimental results suggest that the sensitive fault features can be extracted efficiently after the ICA processing and the proposed diagnostic system is effective for the gear multi fault diagnosis including the gear crack failure pitting failure gear tooth broken etc In addition the proposed method can achieve better performance than that without ICA separation processing with regard to the classifica tion rate Keywords Gearbox fault diagnosis ICA SVM 责任编校 张 众 上接第 20 页 Vehicle Routing Planning Based on the Ant Colony Algorithm for Book Distribution JI San you WANG Xing Wuhan University of T echnology Logistics College Wuhan 430063 China Abstract T aking the vehicle routing problem of book distribution center as the research object and consid ering the characteristics of the book distribution and the limited capacity of the distribution vehicles a ve hicle path planning model based on less than truck load transport strategy is established in this paper In view of the deficiency of traditional research on vehicle routing problem the distribution distance is rede fined by GPS vehicle navigation system An ant