有时间窗的车辆路径规划模型知识表示研究

摘要

本文针对传统的求解有时间窗的车辆路径问题(VehicleRoutingProblemwithTimeWindows，VRPTW)建模与求解过程对专家的依赖性强的缺陷，研究VRPTW模型的知识表示问题。通过深入分析VRPTW问题的特点，及其数学模型的建模与求解特征，引入了人工智能及知识工程的相关知识表示理论与方法，对VRPTW模型的问题已知知识、建模知识与求解知识进行了整合表示。本文的主要研究工作如下： (1)深入分析VRPTW问题数学模型以及用于求解该问题的高效的启发式求解算法的特征，剖析了模型表示研究领域中的成果，为提出VRPTW模型基于知识的表示方法奠定了基础。 (2)在分析VRPTW问题已知知识，专家建模知识，及模型求解知识的基础上，提出了该问题模型的完整知识结构，阐述了VRPTW模型基于知识的表示方法的原理。 (3)以现有的VRPTW的数据库为基础，结合上述分析出的表示方法的原理，用六大部分——B，R，G,I,S,C实现了VRPTW模型整体知识的表示，将数据、事实、规则、方法以及推理过程作为知识统一处理，消除了传统决策支持系统数据库、模型库、以及知识库等多库处理时带来的接口问题以及处理方法不一致的问题。 (4)以BRGISC模型知识表示方法为基础，实现了中石油大连配送分公司某片区成品油配送VRPTW问题的实例求解。 该模型表示方法使得模型的建立和求解可以不依赖于专家，并且该方法将所有知识统一处理的思想提高了物流配送优化调度系统结构的简洁性和处理方法的一致性，模块化的表示方式使得不同类型的车辆路径问题建模和求解过程中使用的知识在该表示方法下可以很容易得到修改，从而促进了物流配送系统对多种车辆路径问题建模与求解的动态性和自适应能力。

目录

文摘

英文文摘

独创性说明及大连理工大学学位论文版权使用授权书

1.引言

1.1问题的提出

1.2国内外相关研究综述

1.2.1有时间窗的车辆路径问题研究进展

1.2.2模型知识表示国内外研究进展

1.3国内外相关研究小结

1.4本文的主要研究工作

2.VRPTW模型的相关分析及其知识表示方法

2.1 VRPTW问题建模过程分析

2.2 VRPTW模型的求解方法分析

2.3 VRPTW模型的知识构成分析

2.4 VRPTW模型的知识表示方法——BRGISC表示法

2.5本章小结

3.VRPTW模型的BRGISC知识表示的实现

3.1知识表示实现方法

3.1.1基本事实集合(B)

3.1.2约束条件集合(R)

3.1.3初始状态生成器(I)

3.1.4状态操作算子(S)

3.1.5目标状态生成器(G)

3.1.6控制器(C)

3.2知识库与数据库的设计以及实现

3.2.1知识库总体结构

3.2.2知识库与数据库的实现

3.2.3知识的维护

3.3基于BRGISC知识表示的VRPTW问题求解过程的实现

3.3.1推理规则的设计

3.3.2推理过程的实现

3.4本章小结

4.应用研究——中石油大连配送分公司油品配送车辆路径规划实例

4.1实例背景

4.2基于BRGISC模型知识表示方法的实例求解过程及其结果分析

结论

参考文献

附录A 部分程序源代码

攻读硕士学位期间发表学术论文情况及攻读硕士学位期间参与的科研项目

致谢