一个简单而有效的进化算法的车辆路径问题,物流工程外文翻译,配送网络优化
文档价格: | 100 金币 立即充值 | 文章语言: | 英语-中文 | 原文出处: | 请在文档内查看 | |||||
译文字数: | 11506 字 (节选翻译) | 译文格式: | Doc.docx (Word) | 更新时间: | 2018-04-27 |
一个简单而有效的进化算法的车辆路径问题,物流工程外文翻译,配送网络优化,遗传算法,零售业
译文(字数:11506):
摘要
车辆路径问题(VRP)的分销网络优化中起着中心作用。由于一些具有 75 个节点的经典实例抵抗最佳精确求解方法,所以大多数研究人员集中于用于解决现实生活问题的元启发式算法。与具有时间窗口的 VRP 相反,没有遗传算法(GA)可以与为 VRP 设计的强大禁忌搜索(TS)方法竞争。本文通过提出一个相对简单而有效的混合 GA 来弥合差距。在平均解法成本方面,该算法在 14 个经典的 Christofides 实例上胜过大多数已发表的 TS 启发式算法, 并成为 Golden 等人生成的 20 个大型实例的最佳解法。
范围和目的
本研究的框架是在车辆路径中遇到的困难的组合优化问题的有效元启发式的发展。令人惊讶的是,在文献中注意到,与具有时间窗口或弧路径问题的节点路径问题相反,没有用于车辆路径问题(VRP,主要生产配送节点路径问题)的有效遗传算法(GA)。早期的尝试基于具有行程分隔符的染色体并且需要修复程序以在每次交叉后获得可行的后代。已知这样的程序削弱了父母对儿童的遗传信息的传播。本文提出一个没有行程分界符的 GA,与本地搜索程序混合。在任何时候,染色体可以转化为最佳 VRP 的解决方案(受染色体序列), 由于一个特殊的分裂程序。这种设计选择避免了修复程序,并允许使用经典交叉比如 OX。当应用于范围从 50 到 483 个客户的两组标准基准实例时,得到的算法是灵活的,相对简单的,并且非常有效。
原文(PDF格式,未统计字数):