模糊条件下市区集送货的计算机辅助调度

论文摘要

针对目前研究中存在的集送货代价描述不准确,不确定信息假设不合理,集送货动态调度方法效率较低等问题,建立评价调度方案优劣的代价函数,拟合模糊信息的隶属度曲线,设计高效的随机合理化禁忌算法、同步优化算法等,为建立高效实用的市区集送货计算机辅助调度系统打下基础。论文首先建立集送货问题的数学系统,并提出扇面Dijkstra算法完成复杂路网模型下最短路径集合的快速求解。通过模糊综合判断方法计算车厢整理代价,同时综合考虑油耗代价、折旧代价、司机代价和正常装卸代价,建立评价调度方案优劣的集送货代价函数。同时,以典型路段的交通数据和实际物流企业的业务数据为基础,拟合模糊车速和模糊发货体积的隶属度函数,在此基础上引入调度人员的主观评价指标描述集送货问题的多模糊约束条件。其次对具有模糊车速和模糊发货体积的集送货问题进行描述,提出随机合理化禁忌算法。在对线路的可行性进行分析的基础上,设计备选方案的随机合理化动态衍生方法,详细阐述基于均衡原理和代价最小原理的双特赦准则以及自适应的禁忌长度选取策略,并给出初始可行方案的快速生成方法。然后针对集送货执行过程中出现新的发货客户这一突发情况,确定动态调度的开始时刻,并引入“虚拟客户”概念将动态问题静态化。在此基础上提出将同步优化算法与顺路插入算法紧密结合,并通过模糊综合判断方法进行智能选取的求解策略,同时设计车辆位置的分段模糊递推法消除由于执行时间的不确定性带来的车辆位置变化对优化结果的影响。分析由于集送货任务变化导致调度方案无法按照原计划继续执行的情况,提出将变化客户和变化线路分开处理的两阶段应急调度算法。最后详细介绍集送货计算机辅助调度系统,并利用系统对集送货代价函数、静态调度算法和动态调度算法进行实用性验证。通过近半年时间的运行,集送货计算机辅助调度系统在稳定性、安全性、实时性等方面均能满足设计要求。

论文目录

• 摘要
• Abstract
• 主要符号对照表
• 第1章 绪论
• 1.1 车辆路径问题研究概述
• 1.1.1 车辆路径问题分类
• 1.1.2 数学模型
• 1.2 启发式求解现状
• 1.2.1 经典启发式方法
• 1.2.2 通用启发式方法
• 1.3 带回取货的车辆路径问题
• 1.4 模糊条件下的车辆路径问题
• 1.5 车辆路径问题的动态调度
• 1.6 计算机辅助调度系统研究现状
• 1.7 研究计划
• 第2章 模糊条件下市区集送货过程与客户间最短路径
• 2.1 市区集送货过程分析
• 2.1.1 集送货信息的数学化
• 2.1.2 集送货调度过程描述
• 2.2 多客户间的最短路径
• 2.2.1 Dijkstra 算法的搜索区域
• 2.2.2 扇面搜索区域
• 2.2.3 扇面 Dijkstra 算法
• 2.2.4 多客户间最短路径计算实例
• 第3章 市区集送货代价函数与调度目标函数
• 3.1 带模糊约束的调度目标函数
• 3.2 集送货代价函数
• 3.2.1 集送货代价的构成
• 3.2.2 单车集送货代价的数学模型
• 3.3 模糊的装卸代价模型
• 3.3.1 单客户装卸代价
• 3.3.2 整理集的确定
• 3.4 多模糊约束条件
• 3.4.1 客户服务时间约束
• 3.4.2 车辆配载约束
• 第4章 多模糊约束下的市区集送货静态调度
• 4.1 集送货静态调度框架
• 4.2 线路可行性分析
• 4.2.1 可行性分析函数的定义
• 4.2.2 可行性检查顺序
• 4.3 备选方案的随机合理化动态衍生
• 4.3.1 备选方案集合的动态调整
• 4.3.2 随机性衍生方法
• 4.3.3 合理化衍生方法
• 4.4 备选方案的禁忌择优
• 4.4.1 双层的禁忌表结构
• 4.4.2 自适应的禁忌长度选取策略
• 4.4.3 基于均衡原理和代价最小原理的双特赦准则
• 4.5 基本方案的初值和终止规则
• 4.5.1 初始可行方案的快速构造
• 4.5.2 多层次的衍生终止规则
• 4.6 集送货静态调度实例
• 4.6.1 随机合理化禁忌算法求解
• 4.6.2 调度方案的对比分析
• 4.6.3 客户数目对计算时间的影响
• 第5章 针对新增发货客户的集送货动态调度
• 5.1 集送货动态调度流程
• 5.2 确定动态调度开始的时刻
• 5.3 执行时间不确定导致车辆位置变化
• 5.3.1 方案开始执行的时间
• 5.3.2 车辆位置的预估
• 5.4 同步优化算法
• 5.4.1 虚拟客户的设置
• 5.4.2 同步优化求解思想
• 5.4.3 提高效率的关键步骤
• 5.4.4 同步优化算法验证
• 5.5 顺路插入算法
• 5.5.1 顺路原则及求解流程
• 5.5.2 调整范围的模糊选择
• 5.5.3 最短路径集合的补充
• 5.5.4 插入剩余客户的处理方法
• 5.5.5 顺路插入算法验证
• 5.6 求解算法的模糊选择
• 5.6.1 隶属度函数及模糊综合判断
• 5.6.2 算法模糊选择策略的验证
• 第6章 集送货任务变化时的应急调度
• 6.1 变化原因及常用处理方法
• 6.1.1 集送货任务变化的主要原因
• 6.1.2 人工调度常用的处理方法
• 6.2 变化客户的处理
• 6.2.1 当日客户和明日客户
• 6.2.2 变化客户的分类处理
• 6.3 变化线路的应急调度
• 6.3.1 任务变化对线路的影响
• 6.3.2 应急调度算法
• 6.4 应急调度算法验证
• 第7章 集送货计算机辅助调度系统与现场实验
• 7.1 集送货计算机辅助调度系统
• 7.1.1 系统特点
• 7.1.2 网络结构
• 7.1.3 主要功能
• 7.1.4 交互界面
• 7.1.5 调度数据的获取
• 7.1.6 调度方案的多方式动态发布
• 7.2 部署测试与现场实验
• 7.2.1 集送货现场实验
• 7.2.2 对现有工作方式的有效改进
• 第8章 结论
• 参考文献
• 致谢
• 个人简历、在学期间发表的学术论文及研究成果