（管理科学与工程专业论文）车辆路径问题的知识表示支持系统研究.pdf

大连理丁大学硕士学位论文 摘要 本文针对目前车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 求解方法缺乏动态自 适应能力这一缺陷，从面向问题的角度出发，研究车辆路径问题的形式化和知识表示。 通过深入分析车辆路径问题及其特点，引入人工智能及知识工程相关理论和方法，提出 了基于知识的车辆路径问题的形式化方法及车辆路径问题的树状知识表示方法，并以此 为基础，设计并实现了车辆路径问题的知识表示支持系统，为模型自动生成和问题求解 创造条件。本文所做的主要研究工作包括： ( 1 ) 在对车辆路径问题信息分析和描述的基础上，根据车辆路径问题信息结构模 型，运用人工智能和知识工程相关理论和方法，提出了车辆路径问题的树状知识表示方 法。 ( 2 ) 以车辆路径问题的树状表示法为基础，在深入剖析车辆路径问题的特点的基 础上，引入相关的问题形式化理论，提出了基于知识的车辆路径问题的形式化原理，研 究了形式化过程中问题辨识、问题结构化和问题知识表示所做的工作以及为整个形式化 工作提供智力支持的领域知识库的结构。 ( 3 ) 从系统的总体设计、数据库的设计、知识库的设计等方面对车辆路径问题的 知识表示支持系统加以设计，并根据上述设计内容实现了车辆路径问题的知识表示支持 系统，取得了良好的效果。 本文提出的基于知识的车辆路径问题的形式化以及树状知识表示法，具有一定的理 论意义和实际价值。基于知识的车辆路径问题的形式化原理对同类问题的研究具有借鉴 作用。同时，系统的实现提高了车辆路径问题的智能化处理水平，为用户提供了一个良 好的信息输入环境，帮助非专业人员完成实际车辆路径问题的输入以及基于知识的表 示，为车辆路径问题的模型自动生成和求解提供了基础，有利于促进v r p 问题的研究。 关键词：车辆路径问题( v r p ) ；知识表示：形式化；知识表示支持系统 胡田田：车辆路径问题的知识表示支持系统研究 r e s e a r c ho nk n o w l e d g er e p r e s e n t a t i o ns u p p o r ts y s t e mf o rv e h i c l e r o u t i n gp r o b l e m s a b s t r a c t a i m i n gt oo v e r c o m et h ed e f i c i e n c yt h a te x i s t i n gs o l v i n gm e t h o d so fv r p a r el a c ko f d y n a m i cs e l f - a d a p t a t i o n t h ef o r m a l i z a t i o na n dk n o w l e d g er e p r e s e n t a t i o nf o rv r p a r es t u d i e d f r o mp r o b l e m - o r i e n t e da s p e c t o nt h eb a s i so fd e e p l ya n a l y z i n gt h ev r pa n di t sp r o p e r t i e s ，a n e wf o r m a l i z a t i o nm e t h o db a s e do nk n o w l e d g ea n dat r e e l i k ek n o w l e d g er e p r e s e n t a t i o nf o ri t a r ep r o p o s e db ya p p l y i n gt h et h e o r i e sa n dm e t h o d so fa r t i f i c i a li n t e l l i g e n c ea n dk n o w l e d g e e n g i n e e r i n g a n db a s e do nt h ea b o v er e s e a r c h ，ak n o w l e d g er e p r e s e n t a t i o ns u p p o r ts y s t e mf o r v r ph a sb e e ns e tu p i ti sv e r yb e n e f i c i a lt om a k i n gm o d e la u t o m a t i c a l l ya n ds o l v i n gp r o b l e m t h em a i nr e s e a r c h e si nt h i sp a p e ra r ea sf o l l o w s ： ( 1 ) o nt h eb a s i so ft h ea n a l y s i sa n dd e s c r i p t i o no ft h ev r p ，t h ei n f o r m a t i o ns t r u c t u r e m o d e lo ft h ev r p ，at r e e - l i k ek n o w l e d g er e p r e s e n t a t i o nf o rt h ev r pi sp r e s e n t e db ya p p l y i n g t h et h e o r i e sm a dm e t h o d so f a r t i f i c i a li n t e l l i g e n c ea n dk n o w l e d g ee n g i n e e r i n g ( 2 ) b yd e e p l ya n a l y z i n gt h ev i u pa n di t sp r o p e r t i e s ，a p p l y i n gt h et h e o r i e so ft h e f o r m a l i z a t i o n ，t h ef o r m a l i z a t i o np r i n c i p l eb a s e do nk n o w l e d g ei sp r o p o s e db a s e do nt h e t r e e - l i k ek n o w l e d g er e p r e s e n t a t i o nf o rt h ev r pi nt h i sp a p e r t h es t u d yo ft h ef o r m a l i z a t i o n p r i n c i p l ec o n t a i n st h et a s k so ft h r e ep h a s e s ( p r o b l e mi d e n t i f i c a t i o n ，p r o b l e ms t r u c t u r i n ga n d k n o w l e d g er e p r e s e n t a t i o nf o rp r o b l e m ) ，a n dt h es t r u c t u r eo fd o m a i nk n o w l e d g eb a s ew h i c h p r o v i d e st h ei n t e l l i g e n ts u s t a i nf o rt h ef o r m a l i z a t i o n ( 3 ) i nt h i sp a p e r ，t h ek n o w l e d g er e p r e s e n t a t i o ns u p p o r ts y s t e mf o rv r p i sd e s i g n e df r o m t h ef o l l o w i n gf e a t u r e si n c l u d i n gt h ew h o l ed e s i g n ，d a t a b a s es y s t e m ，k n o w l e d g eb a s es y s t e m e t c b a s e do nt h e s et h ek n o w l e d g er e p r e s e n t a t i o ns u p p o r ts y s t e mf o rv r pi sb u i l t i th a sc e r t a i ns i g n i f i c a n c ea sw e l la p p l i c a t i o nv a l u et h a tt h ef o r m a l i z a t i o np r i n c i p l eb a s e d o nk n o w l e d g ea n dt h et r e e - l i k ek n o w l e d g er e p r e s e n t a t i o nf o rt h ev r pp u tf o r w a r di n t h i s p a p e r m e a n w h i l e ，t h ef o r m a l i z a t i o np r i n c i p l eb a s e do nk n o w l e d g eh a ss o m er e f e r e n c et ot h e s t u d yo fs i m i l a rp r o b l e m s f u r t h e r m o r e ，t h er e a l i z a t i o no ft h es y s t e mh a si m p r o v e dt h e i n t e l l i g e n c ef o rp r o c e s s i n gt h ev r p o f f e r e dag o o di n t e r f a c ef o ru s e ra n da s s i s t e dt h eu s e rt o a c c o m p l i s ht h ei n p u ta n dt h ek n o w l e d g er e p r e s e n t a t i o nf o r t h ep r o b l e m i th a sg r e a t f a c i l i t a t i o nt om a k i n gm o d e la u t o m a t i c a l l ya n ds o l v i n gp r o b l e m ，a n dp r o m o t e st h er e s e a r c h e s o f t h ev 1 t 2 查垄望三查堂堡主兰垡笙苎 k e yw o r d s ：v e h i c l e r o u t i n gp r o b l e m ；k n o w l e d g e r e p r e s e n t a t i o n ；f o r m a l i z a t i o n ； k n o w l e d g er e p r e s e n t a t i o ns u p p o r ts y s t e m 大连理工大学硕十学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名： 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 大连理工大学硕士学位论文 1 引言 1 1 问题的提出 当前，现代物流已被公认为是企业在降低物质消耗、提高劳动生产率以外创造利润 的第三个重要源泉，也是企业降低生产经营成本，提高产品市场竞争力的重要途径。物 流配送是物流系统中的一个重要环节，它是指按客户( 包括零售商店、用户等) 的订货要 求( 包括在货物种类、数量和时间等方面的要求) ，在物流中心( 也称物流基地、物流据 点，包括配送中心、仓库、车站、港口等) 进行分货、配货工作，并将配好的货物及时 送交收货人的物流活动。物流配送过程主要包括以下作业环节：从生产工厂进货或运达 并集结的集货作业；根据各个客户的不同需求，在物流中心将所需要的货物挑选出来的 分货和配货作业；考虑配送货物的重量和体积，充分利用车辆的载重和容积的货物配装 作业；合理确定车辆配送路线并及时送货的作业。可见，物流配送是一种集集货、分货、 配货、配装、送货等多种功能为一体的物资流通方式。 由于配送是对顾客服务的最后一环，因此，配送的地位十分突出，如何实现快速而 准确的配送是企业在经营方面必须解决的重要课题。目前我国的物流配送基本上还停留 在“只送不配”的水平上，造成物流配送效率低下，车辆空驶严重，物流配送成本很高， 服务质量却很低。鉴于此，研究运用科学方法合理组织物流配送，以提高企业的服务质 量、减少库存、降低经营成本、增加经济效益是十分必要的。 物流配送车辆路径问题，是物流配送优化中关键的一环，也是电子商务活动不可缺 少的内容。物流配送车辆路径问题于1 9 5 9 年由d a n t z i g 和r a m s e r 提出后，很快便引起 运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家 以及运输计划制定者的极大重视，并一直是运筹学与组合优化领域的前沿与热点问题。 在现实生产和生活中，邮政投递问题、飞机、铁路车辆、水运船舶及公共汽车的调度问 题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为物流配送 车辆调度问题。 目前的车辆路径规划多采用“人工离线构造模型”加“计算机辅助求解”的方式， 它一方面无法适应订单与车辆信息瞬息万变的客观情况，另一方面难以满足电子商务环 境下的订单批量大、反应时间短的要求，使得整个电子商务活动难以发挥出它应有的优 势和作用。为解决这一问题，必须为目前的离线处理系统注入处理动态优化问题的机制 和能力，实现由计算机自动实现v r p 问题信息的形式化一自动构建v r p 模型一自动求解 模型获得最优行车路径一运用晟优行车路径实时调控车辆的过程。其中，v r p 问题的形 胡田田：车辆路径问题的知识表示支持系统研究 式化及形式化的结果在计算机中的表示是首要和关键的一环，它处理的好坏直接影响到 后续的建模及其求解的效率和精度。 图1 1 本文的研究工作 f i g 1 1t h ew o r ko f t h ep a p e r 本文正是以这一思路为基础，将人工智能和知识表示理论应用于实际的车辆路径问 题，深入分析车辆路径问题的特点，提出了基于知识的车辆路径问题的形式化方法以及 车辆路径问题的树状表示法，并以此为基础，设计并实现了车辆路径问题的知识表示支 持系统，为模型自动生成和问题求解奠定了基础。整个v r p 问题的求解思路及本文的研 究如图1 1 所示。本研究是人工智能与运筹学理论与方法的交叉和渗透，它有利于促进 并深化运筹学的知识化、智能化的应用研究，是智能运筹学应用研究的一大尝试。应该 说，课题的研究具有较强的理论和实践意义。 1 2 国内外相关研究综述 车辆路径问题的知识表示支持系统研究要实现实际问题的形式化自动建模一 一自动求解这一过程中的第一环节，即实现如何将实际问题形成一个形式化的问题信息 机内表示的过程，这其中涉及两方面问题，一是如何将v r p 问题形式化，二是将形式 化的结果采用何种知识表示方法在计算机中进行表示。因此本文从车辆路径问题 ( v r p ) 、问题形式化和问题的知识表示这三方面对国内外相关的研究现状进行综述。 大连理工大学硕士学位论文 1 2 1 物流配送车辆路径问题的综述 1 2 1 1 物流配送车辆路径问题的描述及其分类 物流配送车辆路径问题可以描述为：对于一系列装货点和( 或) 卸货点，组织适当 的行车路线，使车辆有序地通过它们，在满足一定的约束条件( 如货物需求量、发送量、 交发货时间、车辆容量限制、行驶里程限制、时间限制等) 下，达到一定的目标( 如路 程最短、费用最小、时间尽量少、使用车辆尽量少等) l l 】。 物流配送车辆路径问题自1 9 5 9 年被提出以后，许多学者从不同角度，按不同标准 对其进行了多种分类。按已知信息的特征可分为确定性v r p 和不确定性v r p ，其中不确定 性v r p 可进一步分为随机v r p ( s v r p ) 和模糊v r p ( f v r p ) ；根据v r p 中各项任务是否有 时间限制来区分，有一般车辆路径问题和带时间窗的车辆路径问题( v 砌，t w ) ，其中时间 窗又可分为硬时间窗和软时间窗，硬时间窗( h t w ) 是指任务必须在给定的时间范围内完 成，否则得到的解视为不可行解，软时间窗( s t w ) 指如果任务不能在给定的时间范围内 完成，则同时给予一定的惩罚：按照配送车辆的数量、种类方面的区别，有车辆数有限、 无限、单一车型和多种车型；按车辆载货状况分，有满载问题、非满载问题以及满载和 非满载混合问题；按配送任务特征分，有纯装货问题或纯卸货问题及装卸混合问题( 即 集货、送货一体化问题) ；按照优化目标数，有单目标问题和多目标问题。由于情况的 不同，车辆路径问题的模型构造及算法有很大差别。 1 2 1 2 物流配送车辆路径问题的模型及其算法 v r p 问题是旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 的延伸，由此，解决 t s p 的模型网络模型和数学模型就自然而然地延伸使用到v r p 上，采用通用的求 解网络模型和数学模型的算法求出的是问题的精确解。后来，随着物流系统的发展，实 际的v r p 变得越来越复杂，而且人们也注意到了v r p 是n p 难题，如果单纯使用以前 的图模型或数学模型的算法很难求出问题的精确解，而且单纯的追求精确解意义不大。 这就使得人们逐渐意识到在解决v r p 的时候不能够忽略问题领域知识，应该从问题出发， 结合问题领域知识构造知识化模型，以使求解过程能够得到问题领域的启发性知识，使 求得的解更有效。 ( 1 ) 网络模型及其算法 物流配送车辆路径问题可以构造成网络图，图中的顶点表示物流中心、客户、停车 场等，边代表这些物理节点之间的道路，边被赋予权值表示配送的距离、时间或费用等。 胡田田：车辆路径问题的知识表示支持系统研究 网络模型的经典解法很多，有动态规划、最小生成树、d i j k s t r a 算法、逐次逼近算法、 f l o y d 算法等等。这些算法求出的都是最短路，虽然对t s p 很实用，也可用于对单车辆 的路径规划，但是对既要指派车辆又要规划路径的v r p 来说，仅仅求出最短路显然并 不能真正达到要求。 ( 2 ) 数学模型及其算法 物流配送车辆路径规划数学模型是一个混合整数线性规划模型，这种传统的数学模 型的求解基本上采用的都是精确算法。代表性的研究成果主要有：f i s h e r 【2 l 提出的k 树 法、m p a d b e r g 等p 1 的分枝剪枝法、c h r i s t o f i e d s 4 1 用动态规划放宽空间变量解决v r p 、 f u m e r o 等【5 】的修正拉格朗日松弛及子梯度优化方法、l o r e n al u i z 等 6 1 对列生成方法的 改进等。精确算法可求出问题的最优解，但随着问题规模的增长，计算量呈指数增长， 因此精确算法不适合求解大规模的车辆路径问题。考虑到v r p 问题是一个n p - - h a r d 问 题，只有在需求点数和路段数较少时才有可能寻求其精确解，而在实际应用中，面临的 v r p 问题往往很难求出其精确解，寻找问题的满意解是必要和现实的，因此此类v r p 的解决就需依赖于知识化模型及与其对应的启发式算法。 ( 3 ) 知识化模型及启发式算法 作为对现实问题的一种逻辑抽象方法，知识化模型比图模型和数学模型增加了问题 的求解知识。该类模型没有固定的形式结构，它是在启发式算法建立过程中，逐渐将问 题知识剥离分析出来，并将这些知识并入到算法的求解过程中，以使算法能够在求解的 时候得到问题领域知识的启发，因此，所有与启发式算法同步建立起来的模型都是知识 化模型。多年来，国内外学者从启发式算法的角度对v r p 问题的求解方法进行了大量 而深入的研究。下文从国内和国外两方面对v r p 启发式算法的研究成果进行概述。 国外对车辆路径问题启发式算法的研究可以分为两个阶段：第一个阶段是从1 9 6 0 年到1 9 9 0 年，产生了各种简单启发式算法，包括构造算法，两阶段法，改进算法等； 第二阶段是从1 9 9 0 年至今，随着人工智能方法在解决组合优化问题上显示出的强大功 能，很多学者也将人工智能引入车辆路径问题的求解中，并构造了大量的基于人工智能 的启发式算法，其中包括禁忌搜索算法、模拟退火算法、遗传算法、蚁群算法及混和算 法等。 ( 1 ) 简单启发式算法 常见的经典的简单启发式算法有以下几种： c l a r k e - - w r i g h t 算法。c l a r k e - - w r i g h t 算法最早是由c l a r k e 和w r ! i g h t 7 1 提出的， 用来解决车辆数固定的路径规划问题。该算法通过列出各点对之间的节约量，按节约量 4 大连理工大学硕十学位论文 从大到小构造路径具有运算速度快的优点，但存在未组织点零乱、边缘点难以组合的 问题，只适合求解小型、简单的v r p 。 s w e e p 算法。s w e e p 算法是由w r e n 、g i l l e t t 眵增人提出的，基本思想是从车场发 出的射线“扫过”整个区域，使不超过容量限制的需求点组成一个区域，再对区域内的 各点应用t s p 的优化算法安排行车路线。s w e e p 算法实际上是一种先分组后安排路线的 算法。 两阶段法。f i s h e r - j a i k u m a r 9 1 分派算法是典型的先分组后安排路线的两阶段算法。 该算法将v s p 问题划分为广义分派问题和旅行商问题，首先将任务分派给不同的车辆， 这可以通过解一般分派问题得到，每辆车内部实际上是一个t s p 问题，应用t s p 问题 的启发式算法来得到每辆车的行车路线，但该算法中没有涉及如何去处理距离约束。 k 一交换法。k 一交换法最早是在1 9 6 5 年由l i n l lo 】提出的，它是解决v r p 问题的 局域寻优技术，即对初始可行线路的k 条边进行交换，在初始可行解的邻域内逐步改进 线路，直到在邻域内不能改进为止。k 一交换法速度很快，但它只是对于初始解的改进， 需要其他方法的协作。 ( 2 ) 人工智能启发式算法 禁忌搜索算法( t s ) 。禁忌搜索算法是一种迭代搜索算法，g e n d r e a u i 1 等人最 早将禁忌搜索算法应用于v r p 问题，t a i l l a r d 1 2 1 通过按角度和路径重心对原问题的空间 进行分割，再用禁忌搜索结合模拟退火对子问题求解，实现了对问题求解的并行化，此 外，r o c h a t 、t a i l l a r d 【1 3 还提出了适应性记忆的概念，改进了禁忌搜索算法。禁忌搜索 算法具有强的“爬山”能力( 相对于全局最小值问题) ，但它对于初始解具有较强的依赖 性。 模拟退火( s a ) 法。其思想最早由m e t r o p o l i s l 9 5 3 年提出，o s m a n 1 4 1 对v r p 的模 拟退火算法进行了研究，他提出的模拟退火方法主要适合于解决路线分组。该算法通过 模拟冶金作业的退火过程来搜索解空间。退火算法具有收敛速度快，全局搜索的特点。 然而该方法所得解的好坏与初始状态、温度函数等都有一定的联系，降温较快的效果不 一定很好，效果好的，其降温过程又极其缓慢。 遗传算法( g a ) 。遗传算法是由h o l l a n d 等于7 0 年代发展起来的，j l a w r e n c e t ”1 最先将该方法用于v r p 问题的研究，并有效求解带有时间窗的v r p 问题。遗传算法开 创了在解空间中从多出发点搜索问题最优解的先河。但它在进化搜索过程中，每代总是 要维持一个较大的群体规模，从而使计算次数呈非多项式时间增加，限制了g a 的使用。 同时遗传算法存在“早熟”问题和爬山能力差的弱点。 胡田田：车辆路径问题的知识表示支持系统研究 蚁群算法。蚁群算法是一种新型的模拟进化算法，该算法是由意大利学者 m d o r i g o 16 】等人在2 0 世纪9 0 年代初首先提出，并将其成功地应用到求解v r p 问题中 1 7 1 。蚁群算法具有群体合作、正反馈选择、并行计算等三大特点。因此，该算法具有很 强的发现较好解的能力。但是这种算法也存在一些缺陷，如搜索时间较长，容易出现停 滞现象( s t a g n a t i o nb e h a v i o r ) 等。 混合算法。针对各种算法的优缺点，许多学者提出了各种混和算法，特别是基 于遗传算法和禁忌搜索算法的混合策略。例如，o m b u k i 【l8 j 提出了用遗传算法进行路线 分组，然后用禁忌搜索方法进行路线优化的混合算法。 国内对于v r p 问题的研究起步比较晚，大部分研究集中在2 0 世纪9 0 年代以后， 而且大多数研究工作都是在现有算法基础上对其进行的改进。下面从简单启发式算法、 禁忌搜索算法、遗传算法三个方面对其中具有代表性的研究成果和方法进行论述。 ( 1 ) 简单启发式算法。西南交通大学的李军【l9 】针对有时间窗的车辆路径问题，以 t s p 问题的c w 算法为基础，构造了连接点对时对路线点的最大允许提前时间或最大 允许延迟时间的检查约束，以及等待惩罚和延迟惩罚的处理方法，设计了解决有时间窗 的车辆路径问题的启发式算法。此外，李军i s 0 1 还借助f i s h e r 和j a i k u m a r 分派算法的思想， 将模型分解成一个分派问题和一个t s p 问题，对运输问题的表上作业法进行修正来进行 任务分派，设计了直接处理多车场、在分派中安排路线( 满足时间约束才能得到分派) 的启发式算法，来解决有时间窗的车辆路径问题，该算法较适用于任务数较多的情况。 ( 2 ) 禁忌搜索算法。北方交通大学的郎茂祥等1 2 l j 针对现有文献中有向边排列的解 的表示方法存在的解的表示不太直观使得算法策略复杂不易理解、解中元素较多搜索效 率低、不可行解多收敛速度慢等缺点，根据车辆路径问题的特点，提出了一种新的解的表 示方法客户直接排列的解的表示方法，并基于这种解的表示方法构造了求解车辆路 径闽题的一种新的禁忌搜索算法。西南交通大学的袁庆达等1 2 z j 设计了考虑时间窗口和不 同车辆类型的禁忌算法，这种算法主要采用g e n i u s 方法产生初始解，然后禁忌算法对 初始解优化。 ( 3 ) 遗传算法。李大卫、王莉、王梦光等口3 j 采用比较直观的编码方法，同样使用 自然数编码，但起点客户不出现在染色体中，根据各客户的优先关系确定车辆路径数， 并提出基于优先关系的交叉算子m x 3 。张涛、王梦光【“j 等是通过遗传算法来保证搜索 的全局性，用3 - o p t 算法来加强局部搜索能力，得到针对v r p 的混合算法。同时张涛、 王梦光等【2 5 】还针对禁忌搜索和遗传算法各自的优缺点，提出了一种遗传算法与禁忌搜索 算法的混合策略，把禁忌搜索算法独有的记忆思想引入到遗传算法的搜索过程中，构造 了新的重组算子，并把禁忌搜索算法作为遗传算法的变异算子。 6 大连理工大学硕士学位论文 纵观近年来国内外学者对于物流配送车辆调度问题的研究，可以分为建模和模型求 解两部分：针对具体的实际问题建立模型，构造算法对其进行求解。根据实际问题建立 模型的建模过程主要依靠熟悉领域知识的专业人员凭借其专业知识用手工来完成，在模 型求解方面，目前大部分学者都将目标集中在v r p 问题的算法研究上，提出了很多高 效的求解算法，但算法都是依赖模型的，模型的微小变化，都有可能引起其求解程序的 重大修改、扩充甚至重建。因此，现有的对v r p 问题的研究远不能满足电子商务环境 下进行实时动态调度的需求，对“问题模型求解程序”连锁反应的变化无能为 力。 1 2 2 问题形式化研究综述 物流配送车辆路径问题是复杂管理决策问题，要实现问题在计算机内的知识表示， 必须首先通过问题形式化这一过程。建立物流配送车辆路径问题的知识表示支持系统即 为了完成其问题的形式化工作。在管理科学领域，问题形式化是指确定个人、群体或组 织问题域中所包含的变量及变量之间关系的过程【2 6 l 。问题形式化是问题求解的一个重要 阶段，目的是正确理解并准确描述组织面临的真正问题。一般来讲，问题形式化过程主 要包括：问题识别、问题定义和问题结构化划分3 个阶段。通常问题形式化过程是一个 反复的过程，这3 个阶段的反复利用才能将实际问题良好地形式化。 1 2 2 1 决策问题的复杂性 决策问题的不良结构是导致决策问题复杂性的直接原因。k e e n 和m o r t o n 在s i m o n 的决策分类框架结构化决策、半结构化决策和非结构化决策的基础上，把决策问题 相应地分类为结构化决策问题、半结构化决策问题和非结构化决策问题。对于问题结构 不良的原因，s m i t h 27 j 对其进行了总结，他划分了4 类问题结构概念化：( 1 ) 目标状态 概念化。这一观点认为，问题目标的不确定是问题之所以弱结构或非结构的主要原因。 ( 2 ) 问题空间概念化。s m i t h l 2 7 认为问题结构与问题的可表示性有关，弱结构问题不能 像良结构问题一样得到精确的表示，主要是因为问题的可能状态及状态间的变换是未知 的。( 3 ) 知识概念化。m a s o n 和m i t r o 讲2 8 1 等人认为问题的非结构性主要是由于求解主 体对问题的相关状态及状态转换的不熟悉，非结构问题的求解主体缺乏良结构问题求解 主体所拥有知识。( 4 ) 过程概念化。c o m a n l 2 9 1 认为问题之所以非结构，是由于求解主体 缺乏有效的求解。s m i t h l 2 7 1 总结这些观点后，提出了决策问题结构度的概念，认为决策 问题结构度是问题求解主体拥有求解问题的定性与定量知识充分性的度量。 胡田田：车辆路径问题的知识表示支持系统研究 根据上述决策问题结构化的观点，决策问题形式化可以理解为一个不良结构问题， 通过对问题结构、问题及子问题的目标、问题反映客观事物的状态、问题求解涉及的知 识和方法这四方面的逐步明确，最终转化为结构化问题的过程【3 0 1 。 1 2 2 2 复杂问题形式化方法 问题的形式化最终目的是要提高复杂决策问题的结构化程度。问题形式化是问题求 解的准备阶段，形式化的结果作为问题求解的基础，决定着问题求解能否顺利地进行。 采用何种形式化方法对问题进行形式化就成了目前问题形式化研究中的关键问题。 目前在国外问题形式化方法的研究中，有模型形式化、问题分解、问题启发式分解、 案例推理等方法。模型形式化方法 3 1 , 3 2 1 将问题结构化看成模型化的一部分或前奏，对问 题进行形式化表示，操纵或求解这种表示，将其结果用于原问题。该方法对模型的操纵 和求解较方便，通常能够提供一个具有较强洞察力的问题定义。但模型形式化方法使求 解方案的选择变得狭窄，除己识别的几个标准问题结构( 如排队问题) ，模型化方法没有 提供详细叙述问题元素及关系的能力。在s m i t h 的文献【3 3 】中介绍了问题分解和问题启发 式分解等问题形式化方法。问题分解试图将不可求解的大问题分解为可求解的小问题， 减少了问题的复杂性，但分解后的小问题必须是结构化的。问题启发式分解方法是将问 题分解为结构化的、可结构化的、非结构化的子问题，对非结构化的子问题，通过对问 题的概念属性的识别，为有效的求解策略的识别提供进一步的方向，它的优点是将结构 化的子问题与有关的求解策略对应起来，缺点是非结构化问题的问题属性的引入，并为 对非结构化子问题的求解策略的识别带来方便。案例推理是通过先前的类似问题处理经 验来实现整个问题的形式化。o w e n 3 4 】根据先前的案例经验来进行问题求解，k o l o d n e r 3 5 通过事例推理的方法来改进决策支持的效果等。案例推理需要丰富的先前的经验知识， 但经验并不可靠，对于复杂的管理问题，前后只要有一个因素不同，问题的解都可能会 大相径庭。 在国内，问题的形式化研究起步较晚，系统深入研究此问题的学者也不是很多，比 较有代表性的有：文 3 6 开发的决策问题识别环境，利用归约分解方法帮助用户进一步 明确问题的结构；文 3 7 研究表明d s s 对决策求解的支持体现在两个方面，一是自动 完成结构化部分的求解；二是改变半结构化和非结构化部分的边界，减少非结构化部分， 即改善复杂决策问题结构化程度；文 3 0 在对决策问题复杂性原因研究的基础上，为复 杂决策问题形式化下了准确的定义，并提出复杂决策问题形式化方法的逻辑框架，该框 架由3 部分组成，即复杂决策问题表示层、复杂决策问题结构化层和定量分析模型综合 大连理工大学硕士学位论文 层。针对各层次所要解决的关键问题如复杂决策问题的表示，领域知识网的组织以及复 杂决策问题形式化结果等，并提出了相应的解决方法。 上述研究成果极大地推动了问题形式化的研究，问题的形式化极大地提高了问题的 结构化程度和求解方法的可重用程度。然而，经过目前方法的复杂问题形式化结果仍然 难以求解，同时这些研究成果多停留在理论层面，少有成功的应用案例，复杂问题的形 式化方法难以兼顾通用性与实用性。问题的形式化过程依旧是复杂问题求解的瓶颈。 1 2 3 问题的知识表示综述 所谓知识表示就是对知识的一种描述、或者说一种约定，是一种计算机可以接受的、 用于描述知识的数据结构p ”。按照上述定义，问题的知识表示就是以实际问题为知识对 象，将实际问题的有关知识( 数据或符号化知识) 在知识系统的全局数据库g d b 和规 则库r b 等结构上所进行的映射，通俗地说就是用知识表示理论与方法对实际问题知识 所进行的描述【3 。目前针对v r p 问题的知识表示方法还少有优秀的理论成果出现，查 阅国内外学术期刊有关文献。针对故障诊断、管理决策、自然语言理解、语音识别等这 些具体的问题提出了很多知识表示方法。下面对这些知识表示方法进行综述，以期找到 一种适合车辆路径问题的知识表示方法。 传统知识表示方法有状态表示法、问题归约法、谓词逻辑法、规则、语义网络法、 框架表示、剧本表示、过程表示等，这些知识表示方法针对各自领域问题不同的特点， 各有所长，适用于不同的问题。状态空间图适合于具有方案搜索性质的问题，但它只能 表示比较简单的问题。问题归约法把初始问题分解成子问题集合，最后归约成一个平凡 的可以直接求解的本原问题集合，因此适合于能够对问题进行分解的问题，同样它也只 适合于比较简单的问题。谓词逻辑表示法非常善于处理逻辑性较强的问题但对于层次的 表达力就较弱。基于规则的知识表示方法能够表达一些不确定或不完备甚至是复杂结构 的知识，但对于类似工艺知识等涉及大量数值型和字符型经验的知识，却因知识量大和 表达效率低等缺点而不适用。语义网络表示法、框架表示法和脚本表示法都是结构化的 知识表示方法，但都无法表达具有因果关系的过程性知识，同时它们各自又有各自适用 的问题：语义网络可以用来表示具有实体一关系模型特点的问题，它把事物的属性和事 物之间的联系用语义网络的结构形式显式地表示出来，从而实现信息共享和减少信息冗 余：框架表示法适用于表达具有层次结构的问题，相关的属性和规则可以形成框架层次 结构：剧本表示法是框架的一种特殊形式，但它特别适用于描述顺序性的问题。过程表 示法将有关某一问题领域的知识连同如何使用这些知识的方法均隐式地表达为一个求 胡田田：车辆路径问题的知识表示支持系统研究 解过程，因此过程表示法适用于表达问题求解过程易于表达的问题，但难以表示非过程 性知识。 传统的知识表示方法在知识工程的发展过程中起到了非常大的作用，但随着需要处 理的知识和数据的大量增加，研究者发现传统的知识表示方法已不能满足要求。基于这 种情况，2 0 世纪8 0 年代以来，随着人工智能和知识工程的不断发展，国内外学者在上 述知识表示的基础上拓展了知识表示，根据特定的问题和领域提出了许多新的知识表示 方法，例如面向对象的知识表示方法【4 2 1 ，基于p e t r ii 4 3 , 4 4 1 、神经网络1 4 5 1 、树状表示 法1 4 6 , 4 7 ，基于x m l 的知识表示方法【4 8 - 9 1 等等。 ( 1 ) 面向对象的知识表示1 4 0 4 2 1 面向对象的知识表示方法以领域对象为中心，以对象为基本单元表示知识，将多种 单一的知识表示方法( 如规则、框架等) 按照面向对象的程序设计原则组成一种混合的 知识表达形式，将对象的属性、动态行为、领域知识和处理方法等有关知识“封装”在 表达对象的结构中。面向对象的知识表示方法将对象的概念和对象的性质结合在一起， 符合专家对领域对象的认知模式。面向对象表示法具有模块性、继承性、封装性、多态 性等特点，这种表示方式减少了信息冗余，减少了错误，便于系统维护，适合大型知识 系统的开发。 ( 2 ) 基于p e t r i 网的知识表示 p e t r i 网的概念是由德国学者c a p e t r i 在1 9 6 2 年首先提出的，用于构造系统模型 及进行动态特性分析，后来逐渐用作表示知识的方法。p e t r i 网易于表达过程性和结构性 知识，具有直观、易于理解和使用的优点，因此国内外学者不断提出不同的基于p e t r i 网的知识表示，并且发展了基于模糊p e t r i 网的知识表示【4 副和基于模糊彩色p e t r i 网的知 识表示【4 4 j 。它的缺点是比较抽象，不易理解，专业性太强。 ( 3 ) 基于神经网络的知识表示 神经网络的知识表示采用与传统知识表示方法完全不同的思想。传统的知识表示都 可以看成是知识的一种显式表示，而神经网络的知识表示可看成是知识的一种隐式表 示。神经网络的知识表示是把某一问题领域的若干知识彼此关联地表示在一个神经网络 中。美国f l o r i d a 大学的f u 教授【4 5 1 对神经网络的知识表示方法进行深入研究，先后提出 了基于知识的概念神经网络( k n o w l e d g eb a s e dc o n c e p t u a ln e u r a ln e t w o r k s ，k b c n n ) 、从 神经网络中提取规则的k t 算法、规则知识的神经网络表示方法等等。基于神经网络的 知识表示方法具有如下优点：具有统一的内部知识表示形式，通过学习过程即可获得 网络的相关参数；便于实现知识的自动获取；便于实现并行联想推理和自适应推理； 1 0 火连理工大学硕士学位论文 能够表示事物的复杂关系。但因为它的知识表示和知识推理方式都是隐含的，使碍知 识难以理解，同时也无法评价其推理过程的正确性。 ( 4 ) 树状表示法 胡祥培等【4 6 1 人根据运筹学规划论问题的特点，利用人工智能与知识工程的知识表示 理论，提出了一种基于知识的描述运筹学规划问题的树状表示法。其原理如下：根据实 际问题的信息结构特征，将实际应用问题的信息划分为若干个信息侧面，每一个信息侧 面又可划分为若干个信息单元，如此细分下去，可以把实际问题的信息归结成为一 种层次化的树状结构图。由于运筹学问题的信息具有这种层次化的树状结构特征，采用 一种层次化、结构化的问题描述树来表示运筹学实际问题。这一表示法具有良好的问题 可辨识性和问题描述结构的可扩性，具有较高的信息搜索与处理效率、辩识与推理效率。 并具有描述表格数据、决策树图形及数据、数学函数的基本能力。 清华大学的李德英、张跃等f 4 7 j 针对锅炉系统的故障诊断问题及其特点，在故障诊断 技术已有研究成果的基础上，提出了面向对象基于框架、规则、模型与过程集成的广义 故障树知识表示方法。这种方法是在锅炉系统故障树的基础上，以诊断对象为中心，应用 面向对象技术将多种单一的知识表示方法( 如框架、规则、模型、过程) 集成一种混合表 示形式，把诊断对象的结构、功能、属性、行为特征、诊断推理知识有机地结合起来， 形成一个具有模块化、表达广泛概念能力和知识重用能力的多层次结构模型。这种知识 表示方法集各种表示方法之优点，以满足锅炉系统的故障诊断的特点。该方法广泛被应 用于故障诊断。 ( 5 ) 基于x m l 的知识表示方法【4 8 9 j 基于x m l 的知识表示方法_ x k r ( x m l b a s e dk n o w l e d g er e p r e s e n t a t i o n ) 把产 生式、框架、语义网络、过程表示法等多种传统的表示方法融合到一起，用x m l 作为 统一的形式描述语言。由于x m l 本身包含语义并能够无限扩充，因此x k r 可以描述 不同背景不同类型的知识，实现知识融合，并进一步构建出分布式知识库。x k r 的表 示能力比b n f 更强，它不仅可以描述知识结构与属性，还可以描述知识或者属性之间 的联系。 上述问题的知识表示方法各有侧重和优缺点，至今未形成较为完善的问题知识表示 理论体系。问题的知识表示方法选择的好坏直接影响到后续的自动建模和自动求解，因 此对于问题的知识表示必须从智能问题求解的角