基于多代理的两阶段实时车辆调度系统研究

论文摘要

车辆运输及调度在供应链中占有重要的地位。随着市场竞争的加剧和顾客需求的多样化,企业不可能在所有信息己知的情况下制定调度计划,即使制定了计划也因外界因素的多变而很难实施。因此实时车辆调度(Vehicle Routing Problem, VRP)的研究受到越来越多研究者的重视,但是目前的研究在许多方面还不够深入,在如何处理实时事件和设计简单有效的算法等方面仍存在着大量值得进一步研究的问题。解决实时VRP的关键问题在于如何及时、充分掌握信息,以及做出实时的响应。前者随着IT技术的发展已经得到解决,后者则需要设计简单有效的算法,按照一定的优化策略,在保证求解质量的情况下快速更改原有的静态计划。为了实现这一目标,多Agent系统作为一种新兴的解决方法被引入了实时VRP研究中来,该系统可以满足配送系统中车辆地理上分布、信息动态变化、顾客订单随时变更等众多变化,因而得到了越来越广泛的应用。本文对带有时间窗限制的实时VRP进行了研究,设计了基于多代理协商机制的系统求解模型,描述了模型的体系结构和功能,明确将静态计划和实时订单分开来处理,提出了基于多代理的两阶段算法:第一阶段是静态计划制定。本文从多代理协商和改进遗传算法两个方面进行了研究。通过Solomon算例的实验结果表明改进遗传算法具有适用范围广、计算时间少、计算精度高等优点;第二阶段是仿真运行阶段,车辆Agent会依次服务顾客,仿真系统基于合同网协议的协商机制来实现实时事件的处理。本文重点研究了多代理应用中基于合同网协议的协商算法,指出了传统合同网协议的不足,从多个方法和策略提出改进的合同网协商算法,并且通过实验证明了在求解结果无明显下降的情况下,能够大幅减少协商次数以及协商时间。为了验证原型框架的可靠性和有效性,不同于传统实时VRP的验证算例,本文提出一种新的测试实时VRP的算例,用来验证系统框架对静态订单的求解能力,以及对实时订单的快速反应能力。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.2 研究意义
• 1.2.1 学术意义
• 1.2.2 企业应用
• 1.3 本文的研究内容
• 1.3.1 多代理应用于实时VRP 系统研究
• 1.3.2 本文研究内容
• 1.4 本文的内容安排
• 第2章 文献综述
• 2.1 VRP 及实时VRP 研究综述
• 2.1.1 传统确定性VRP 研究综述
• 2.1.2 早期实时 VRP 研究
• 2.1.3 近期实时 VRP 研究
• 2.1.4 国内VRP 研究
• 2.2 多代理系统应用于VRP 问题研究
• 2.2.1 主要研究内容
• 2.2.2 研究中存在问题
• 2.3 小结
• 第3章 基于多代理的两阶段框架
• 3.1 Agent 的定义及分类
• 3.2 多代理系统
• 3.2.1 多代理的定义
• 3.2.2 多代理的体系结构
• 3.2.3 多代理中 Agent 之间的协商
• 3.2.4 多代理中 Agent 之间的通信
• 3.3 实时VRP 系统框架
• 3.3.1 系统模型设计
• 3.3.2 系统框架
• 3.3.3 两阶段求解算法
• 3.4 本章小节
• 第4章 生成静态计划的改进遗传算法
• 4.1 VRPTW 问题
• 4.1.1 VRPTW 问题的定义
• 4.1.2 VRPTW 问题的研究
• 4.2 改进遗传算法用于静态计划生成
• 4.2.1 染色体的表达方式
• 4.2.2 初始化种群操作
• 4.2.3 选择操作
• 4.2.4 交叉操作
• 4.2.5 变异操作
• 4.3 改进遗传算法验证实验
• 4.3.1 Solomon 算例的描述
• 4.3.2 求解结果
• 4.3.3 参数分析
• 4.4 本章小结
• 第5章 多代理系统的协商和通信研究
• 5.1 多代理系统的协商
• 5.1.1 多代理中任务分配问题的提出与分析
• 5.1.2 传统合同网协议
• 5.1.3 改进合同网协议
• 5.2 改进合同网协议用于VRPTW 问题求解
• 5.2.1 订单发布策略研究
• 5.2.2 车辆 Agent 的选择策略
• 5.2.3 多个订单批次发布策略研究
• 5.3 多代理系统的通信
• 5.3.1 Agent 之间通信概述
• 5.3.2 基于KQML 的通信语言
• 5.3.3 基于改进合同网协议的Agent 之间通信
• 5.3.4 基于KQML 的合同网协议通信实例
• 5.4 本章小结
• 第6章 原型系统的开发及测试
• 6.1 关键技术
• 6.1.1 JADE 多代理框架
• 6.1.2 SQL Server 数据库服务器
• 6.2 系统运行分析
• 6.2.1 静态计划制定策略
• 6.2.2 实时处理策略
• 6.3 基于动态度的实时仿真实验
• 6.3.1 评价指标及实验设计
• 6.3.2 实验结果分析
• 6.4 本章小结
• 第7章 结论
• 7.1 全文总结及创新点
• 7.2 今后工作展望
• 参考文献
• 致谢
• 附录A RC101 改进算例数据
• 个人简历、在学期间发表的学术论文与研究成果