基于案例推理的不确定信息车辆路径问题研究

摘要

近年来，随着电子商务的快速发展，物流企业的重要性越来越突出。目前我国的物流运输费用占总费用的50％以上，对能有效改善运输成本的车辆路径问题(VRP)的研究显得尤为重要。在物流配送过程中普遍存在诸如突发车辆故障、道路堵塞、客户需求变化等不确定事件，使得原配送路线不经济或不可行。如何快速实时地调整原配送方案，使得突发情况下，配送方案仍旧达到最优，是现阶段VRP研究面临的重要问题。
　　 为了解决以上问题，本文将人工智能和知识工程领域的理论引入不确定信息VRP问题的求解，按照“VRP问题的知识表示→构建案例库→案例检索→案例知识重用”这一思路，从基于案例推理的知识重用角度解决突发状况下的VRP问题，以提高VRP问题求解系统的智能化和实时性。
　　 本文首先在对VRP问题和知识表示进行理论梳理的基础上，提出了一种VRP问题的树状知识表示法。设计了VRP问题知识表示支持系统的体系结构，通过编辑启发式输入窗口，辅助非物流专业人员进行物流信息的输入。采用prolog语言对VRP问题的知识描述树进行表述，生成了VRP问题的知识化信息模型，为后续VRP问题建模求解时调用。
　　 构建了基于VRP问题树状知识表示结构的案例库。提出了一种基于案例属性重用度的权重确定方法(ReusabilityofAttributes，简称RA法)，实现了突发情况下，案例属性权重的实时计算和动态更新。在此基础上，提出了一种多层加权的相似度计算方法(MultilayerWeightedk-NearestNeighbor，简称MWK法)，考虑了VRP问题属性之间的多层隶属关系，改进了传统算法中不考虑属性之间相关性的缺陷。用MATLAB编程实现了这两个算法。
　　 最后以某大型连锁超市为应用背景，运用VRP问题树状知识表示方法、RA法和MWK法，对该超市配送过程中产生的突发问题进行了分析和计算。实验结果表明，将本文提出的方法综合应用，在计算效率、结果的查全率和分辨率上均有改善。
　　 本文的研究是人工智能、知识工程以及运筹组合优化学科的交叉与渗透，为从基于案例推理的知识重用角度解决不确定信息VRP问题，为提高问题求解的实时性和智能化提供了研究思路和解决方法。

目录

声明

摘要

图表目录

1 引言

1．1 问题的提出

1．2 国内外研究现状

1．2．1 不确定信息车辆路径问题的研究现状

1．2．2 知识表示的研究现状

1．2．3 案例推理中相似度计算的研究现状

1．2．4 研究中存在的问题及研究趋势

1．3 本文的研究内容与框架

2 车辆路径问题的基本理论

2．1 车辆路径问题的一般描述

2．1．1 车辆路径问题的定义

2．1．2 车辆路径问题的构成要素

2．2 车辆路径问题的分类

2．3 车辆路径问题的数学模型和算法

2．3．1 车辆路径问题的数学模型

2．3．2 车辆路径问题的优化算法

2．4 本章小结

3 车辆路径问题的知识表示方法及其支持系统

3．1 车辆路径问题的信息分析

3．1．1 车辆路径问题的特点

3．1．2 车辆路径问题信息结构分析

3．2 车辆路径问题的树状知识表示方法

3．2．1 知识表示方法的相关研究

3．2．2 知识表示方法的要求

3．2．3 树状知识表示法

3．2．4 车辆路径问题的树状知识表示

3．3 车辆路径问题的知识表示支持系统

3．3．1 车辆路径问题知识表示支持系统总体结构

3．3．2 车辆路径问题领域知识库

3．3．3 车辆路径问题启发式输入窗口

3．3．4 车辆路径问题的知识化信息模型

3．4 本章小结

4 基于案例推理的车辆路径问题

4．1 案例推理的基本原理和流程

4．2 案例的表示

4．2．1 案例的基本结构信息

4．2．2 案例的属性信息

4．3 案例库的构建

4．3．1 案例库的表结构

4．3．2 案例基本信息表

4．3．3 硬时间窗表

4．3．4 软时间窗表

4．3．5 属性表

4．4 案例的检索

4．4．1 相似度计算的相关研宄

4．4．2 基于属性重用度的权重确定方法

4．4．3 基于多层加权的案例相似度计算方法

4．4．4 案例检索的实现

4．5 案例的调整和重用

4．6 本章小结

5 应用实例研究

5．1 问题描述及抽象

5．2 树状知识表示

5．3 相似案例检索及结果分析

5．4 本章小结

6 结论

6．1 主要工作

6．2 创新点

6．3 前景展望

致谢

参考文献

附录