智能运输调度系统模型库构造与管理.pdf

《智能运输调度系统模型库构造与管理.pdf》由会员分享，可在线阅读，更多相关《智能运输调度系统模型库构造与管理.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2000年9月系统工程理论与实践第9期文章编号:100026788(2000)0920083208智能运输调度系统模型库构造与管理蔡延光1,钱积新2,孙优贤2(1.湖北汽车工业学院管理系,湖北 十堰442002;2.浙江大学工业控制技术研究所,浙江 杭州310027)摘要:根据最近的研究和未来展望,从系统设计的角度对VRSP(Vehicle Routing and SchedulingProblem s)的模型按结构进行了分类,给出了模型类的知识表示;详细地讨论了VRSP模型类的父类、子类、多项式派生子类、相似类、多项式派生超子类、等价类;研究了模型类的并、交、补运算,从而深刻地揭示了模型类之

2、间的关系提出了VRSP模型库及其管理系统一个框架设计本文的研究虽然是针对智能运输调度系统进行的,但其思想和方法对一般智能管理系统的设计具有普遍意义关键词:运输调度;智能管理系统;决策支持系统;模型库;模型库管理系统中图分类号:T18.1The Design andM aintenance for theM odelBase of Intelligent V ehicle D ispatch SystemCA I Yan2guang1,Q I AN Ji2xin2,SUN You2xian2(1.Department ofM anagement Engineering,HubeiA utomot

3、ive Industries Institute,Shiyan 442002;2.Institute of Industrial Control Techniques,Zhejiang U niversity,Hangzhou 310027)Abstract:Based on current studies and prospects,a classification scheme is proposedfor the models of vehicle routing and scheduling problem s(VRSP)from the point ofview of system

4、design.The representations of know ledge of model classes are given.This paper reveals profoundly the relations among model classes of VRSP.The fatherclass,son class,polynom ial derivation class,si m ilar class,polynom ial derivationhyperson and equivalent class are discussed respectively.The union,

5、intersection andsupplement of model classes are investigated.Finally,a frame design is presented forthe model base and itsmanagement system of VRSP.The ideas and methods proposedin this paper are meaningful for general intelligent management system design.Keywords:vehicle dispatch;intelligent manage

6、ment system;decision supportingsystem;model base;model base management system1引言在一个存在供求关系的系统中,有若干台车辆(车辆停放在车队),有若干个供应点和需求点 要求给出车辆行车路线(V ehicle Routing Problem s,VRP)设计和出行时间(V ehicle Scheduling Problem s,V SP)安排,在给定的约束条件下,把货物从供应点运送到需求点,使目标函数值取得最优VRP和V SP结合,统称为运输调度问题(V ehicle Routing and Scheduling Pro

7、blem s,VRSP,国内有些研究者称为车辆调度问题)根据有关讨论1,2,结合VRSP的最新进展,可将VRSP归结为如下的一般化网络模型:设G=(V,E,A)是一个连通的混合网络,V是顶点集,E、A分别为(无向)边集和(有向)弧集,E中的边和A中的弧被均被赋权(或称距离或称 时间或为费用)V,E,A 分别为V、E、A的子集求一个满足某收稿日期:1999201225 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.些约束(例如时间约束)并包含V,E,A 的巡回(闭通路),使其总长度(或时间或费用)最小近二

8、十多年来VRSP吸引了许多研究者在理论和应用方面进行了大量而深入的研究,获得了丰硕的成果217,最近的研究进展见文献2及1316的综述文献2,3详细地描述了智能运输调度系统的设计思想和系统结构 其实现智能调度的主要思路是:先通过某种算法(精确算法、近似算法、智能算法)求解问题,然后用推理机构调整任务分配方案;为了提高计算速度,需要充分利用结构相似性、数据相似性和已有的计算经验 这样,就涉及到算法库、算法参数库、算法经验库的设计及维护,和控制策略集的动态刷新;也涉及到模型库的设计、模型的识别、分解、整合(在整体最优的观点指导下进行合成);典型案例的甄别、评价及存储;算法的重用等等算法的研究和应用

9、经验表明,模型与算法是密切相关的 因此本文根据最近的研究和未来展望,从系统设计的角度对VRSP的模型按结构进行了分类,给出了模型类的知识表示;详细地讨论了模型类的父类、子类、多项式派生子类、相似类、多项式派生超子类、等价类;研究了模型类的并、交、补运算,从而深刻地揭示了模型类之间的关系,使智能运输调度系统系统能实现模型类知识的自动构造和自适应;最后,提出了模型库及其管理系统一个框架设计2 模型的结构分类与表示研究VRSP的文献极其丰富,互联网上相关的网站(包括个人网页)有 数百个之多 有关学者提出了模型的各种变种 为了便于智能运输调度系统正确地选择和学习(从而自动构造)模型和算法,按模型的结构

10、进行合适的分类是至关重要的25本文的分类是对VRSP过去研究的总结和对未来的展望根据我们的知识,有些类如模糊、灰色方面的研究几乎是空白,动态方面也鲜有研究 因此,这一分类对VRSP的研究具有一定的指导意义在下述分类中,“待定”的含义是指有无限的资源可供使用,但需确定最优的资源配置2.1模型的结构分类2.1.1车队结构参数1)车队数量:一个;一个以上;待定2)车队位置:固定;待定3)每个车队拥有的车辆数:一辆;一辆以上;待定4)车辆载重量:所有车辆的载重量相等;车辆的载重量不完全相等5)车辆类型:普通车辆;专用车辆;普通、专用车辆混合车队2.1.2供应结构参数1)供应点数量:一个;一个以上;待定

11、2)供应点位置状态:确定的;待定2.1.3需求结构参数1)服务类型:输送型或收集型(两者不可兼有,如配送中心向连锁店输送货物,收集垃圾);输送、收集混合型(如公交车乘客可以下车、上车)2)需求总量:不超过全部车辆总的载重量;可超过全部车辆总的载重量3)需求次数(需求点只需一次或多次运输服务):最多一次;次数不限4)需求位置:边、弧;顶点;混合型(边、弧、顶点)5)需求点或货物对车辆的特殊要求:无要求;某台车辆优先;某类车辆优先6)货物到达目的地的先后顺序:无要求;某一货物必须比另一货物提前到达;某类货物必须比另一货物提前到达;某类货物必须比另一类货物提前到达;某一货物必须与另一货物同时到达;某

12、类货物必须与另一货物同时到达;某类货物必须与另一类货物同时到达7)需求满足程度:全部满足;需求部分满足(不满足有损失,受到惩罚)2.1.4网络结构参数48系统工程理论与实践2000年9月 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.1)有向或无向:无向;有向;混合(既有有向边又有无向边)2)边、弧的权值:固定;随时间不同而变化;随车辆的不同而变化3)权值的关系:无关系;满足三角不等式4)拓扑结构:路径;圈;树;仙人掌图;平面图;简单图;一般结构(多重图,可以包含有重边、环);欧氏空间2.1.5作业类型

13、参数1)混装:不允许混装;允许混装(同一辆车可以装运不同类型的货物)2)分散装运:不允许分散装运 允许分散装运(某个需求点的货物可以分批运达,即使需求量在一辆车的载重量以下)3)中转:不允许中转;允许中转4)车辆完成运输任务后的宿泊地点:必须返回到出发点;返回到任意车队;不需返回到车队2.1.6约束条件1)时间约束:无时间限制;在指定的时间区间内完成运输任务;有时间限制但可以不遵守,不遵守时有惩罚2)距离约束:无距离限制;每辆车的运输距离有限;每辆车的运输距离有限但可以不遵守,不遵守时需另付加班费3)交通流量约束:无流量限制;边、弧限制(每个边、弧上同时行驶的车辆数量有限);顶点限制(顶点上同

14、时进行装、卸货的车辆数量有限);边、弧、顶点限制4)行车路线约束:无相交性限制;顶点不相交(不同车辆的行车路线不能相交);边、弧不相交5)其它要求2.1.7函数及数字的特征1)确定或随机:确定;随机2)精确或模糊:精确;模糊3)数据已知程度:白色;灰色;黑色4)静态或动态:静态;动态2.1.8目标函数结构1)目标数量:单目标;多目标2)目标函数:总的路程最短;最少车辆数;综合费用最小(车辆维护、车队管理费、装卸成本、油料、工资);加班费最小;惩罚最小;其它2.2 模型结构类表示模型结构类及其相关的知识用模型结构类项表示 具体定义如下(其中表示不可兼的或,尖括号表示类,方括号表示值):模型结构类

15、项=模型结构类名称模型结构类编码关键字集模型结构类模型结构类特征的文字描述说明:模型结构类编码与模型结构类是一一对应的,模型结构类不同其编码也不同 关键字集由若干关键字组成,用于查询18 模型结构类特征的文字描述用于人类的阅读理解关键字集=关键字 关键字关键字集模型结构类=车队结构参数供应结构参数 目标函数结构车队结构参数=车队数量车队位置 车辆类型供应结构参数=供应点数量供应点位置状态目标函数结构=目标数量目标函数集车队数量=一个一个以上待定58第9期智能运输调度系统模型库构造与管理 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All r

16、ights reserved.车队位置=固定待定供应点数量=一个一个以上待定供应点位置状态=固定待定目标数量=单目标多目标目标函数集=目标函数 目标函数目标函数集目标函数=总路程最短最小车辆数惩罚最小为了简略起见,在不引起混淆时,以后简称模型结构类为模型类,有时甚至简称为类 除非特别声明,本文所讨论的模型类均为VRSP模型类3模型类的关系与运算为了讨论方便,以C(x1,x2,xk)表示模型类,其中x1,x2,xk是模型类参数xi(i=1,2,k)是变量;xi与2.2节最下层的类是一一对应的,即2.1节中每个阿拉伯数字序对应一个变量(取值范围是其下一行的阿拉伯数字加右圆括号的项目,即2.2节方括

17、号的内容)即x1对应车队数量,取值一个,一个以上,待定x2对应车队位置,取值固定,待定 x6对应供应点数量,取值一个,一个以上,待定因此,对于x1,x2,xk的一组取值,对应着VRSP的一个类本节研究模型类之间的各种关系和运算3.1父类和子类某些值之间具有概念内涵(语义)上的包含关系 如动态包含了静态,从算法的角度看,关于动态问题的算法一般是适合于静态问题的,所以可以认为当其它参数的取值相同时,动态类包含了静态类;同理,平面网络类包含了树形网络类一般地,如果值X在概念内涵(语义)上包含值Y,则称X包含Y,或Y从 属于X 记 作XY或YX类似可定义值的并(=或者)、交(=而且)、补(=非)等概念

18、定义1设C1=C(x11,x12,x1k),C2=C(x21,x22,x2k)是VRSP的两个模型类,如果对一切i=1,2,k,都有x1ix2i,则分别称C2是C1的子模型类(简称子类,以下类推)、C1是C2的父类、C1和C2具有父子关系,记作C1C2或C2C1如果C1C2,且存在i 使x1ix2i,则C1和C2具有真父子关系,记作C1:C2或C2;C1定义1用规则表示如下:IF对一切i=1,2,k都有x1ix2iTHENC1C2从定义可以看出,父子关系具有自反律、传递律(与上述规则一起,构成图1分类规则库的一个子库,本文余下部分有相似的解释)子类继承父类的算法当父类不存在算法而子类存在算法时

19、,可以考虑将父类问题分解为子类问题而求解,通过整合求得原问题的解 父子关系的确定为问题求解提供了一条途径模型间父子关系的自动识别可通过推理机直接引用分类规则和分类事实库(该事实库是图1中分类事实库的一个子库,本文余下部分有相似解释)、分类经验库等实现事实库中存放值之间的包含或从属关系 例如:动态 静态;树 路径对于任何一个模型类,其父类项和子类项定义如下:父类项=父类模型集68系统工程理论与实践2000年9月 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.父类模型集=父类编码 父类编码父类模型集 子类项

20、=子类模型集子类模型集=子类编码 子类编码子类模型集3.2 多项式派生子类定义2 设C1=C(x11,x12,x1k),C2=C(x21,x22,x2k)是VRSP的两个模型类,如果存在一个多项式复杂度的单值算子(变换)f使f(C2)为C1的子类,即C1f(C2),则称C2是C1的多项式派生子类、C1是C2的多项式派生父类、C1和C2具有多项式派生父子关系,记作C1fC2或C2fC1;称f为多项式派生算子,在 不引起混淆时简称为多项式算子例如,若C1是网络结构是多重有向图且需求位置在顶点上的任意类,C2是网络结构是多重无向图且需求位置在顶点上的任意类(C1、C2的其它参数取值相同,下文的举例有

21、相同的解释),定义f=每个无向边变为一对方向相反的平行弧,弧的权值为对应边的权值,则有C1fC2定义2用规则表示如下:IF多项式算子f使C1f(C2)THENC1fC2从定义可以看出,子类是多项式派生子类的特殊形式 前者是f为单位算子多项式派生子类 但是两者在计算复杂性方面有着本质的区别,所以在模型库设计时作为模型类的两个不同属性处理多项式派生父类项=多项式派生父类模型集多项式派生父类模型集=多项式派生父类编码多项式算子 多项式派生父类编码多项式算子多项式派生父类模型集3.3相似类相似性在问题求解、系统设计中扮演着重要的角色19 有三点理由迫使我们考虑模型类的相似性问题:第一,模型类的不完备性

22、 无论考虑得多么周到,模型类是不可能全部列出的,且实践中也会不断地提出新问题 虽然直观看来,增加新模型类可以实现模型类的完备,然而新增的模型类不一定能找到对应的算法第二,已有的模型类不存在现成的算法最后,透过模型类的相似性进行类比学习,例如算法学习、计算经验学习,从而导出问题的新算法定义3 设C1=C(x11,x12,x1k),C2=C(x21,x22,x2k)是VRSP的两个模型类,C1、C2是相等的如果其所有的参数取值是相同的,记作C2=C1定义4C1、C2如定义3,如果存在可逆算子f使f(C2)=C1,则称C1(C2)与C2(C1)是相似的,或者说C2(C1)是C1(C2)的相似类 记作

23、C1fC2(cf=相似度)这里算子f的逆f-1的含义是指f的反向操作,例如如果在f中是减少,则在f-1中是添加;如果在f中是扩大,则在f-1中是缩小等在V RS P中,通过松弛算子是获得相似类的一个重要技术,也是求解VRSP常用技巧例如,C2是必须返回到车队的任意类,C1是不需返回到车队的任意类,定义f=去掉车辆必须返回到车队的约束,则C1fC2模型类的相似性具有自反率、对称律、传递律定义4用规则表示如下:IF可逆算子f使f(C2)=C1THENC1C2(cf=相似度)相似类项=相似模型集相似模型集=相似类编码算子相似度 相似类编码算子相似度 相似模型集3.4类的运算定义5 设C1=C(x11

24、,x12,x1k),C2=C(x21,x22,x2k),C3=C(x31,x32,x3k)是VRSP的模型类,如果78第9期智能运输调度系统模型库构造与管理 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.对于一切i=1,2,k有x3i=x1ix2i,则称C3是C1和C2并,记作C3=C1C2定义6 设C1=C(x11,x12,x1k),C2=C(x21,x22,x2k),C3=C(x31,x32,x3k)是VRSP的模型类,如果对于一切i=1,2,k有x3i=x1ix2i,则称C3是C1和C2交,记作C

25、3=C1C2定义7 设C1=C(x11,x12,x1k),C2=C(x21,x22,x2k)是VRSP的模型类,如果对于一切i=1,2,k有x1i=x2i,则称C2是C1的补类,记作C1=C2由模型类的交、并、补等运算,VRSP模型类得到扩展 实际上本文所有的讨论也适合于VRSP这种扩展类,故图1的VRSP模型库是指这种扩展的模型库3.5等价类定义8 设C1=C(x11,x12,x1k),C2=C(x21,x22,x2k)是VRSP的模型类,记I=i1,i2,it是使x1ix2i的指标的全体,如果当x1i=x2i(一切iI)时x1iiI的概念内涵和x2iiI的概念内涵相同,则称C1、C2是等价

26、的,或者说C1(C2)是C2(C1)的等价类,记作C1C2例如,若C1是车辆数为1且车辆载重量相等的任意类,C2是车辆数为1且车辆载重量不全相等的任意类,则C1C2模型类的等价性具有自反率、对称律、传递律基于存储的考虑,VRSP模型库若存放了某个模型类,则可删掉除该模型类自身外的它的全部的等价类 但是本文并不这样做,提出等价类概念的目的是实现等价类之间的算法互用定义8用规则表示如下:IFx1i=x2i(一切iI)有x1iiI的概念内涵和x2iiI的概念内涵相同THENC1C2等价类项=等价类模型集等价类模型集=等价类编码 等价类编码等价类模型集3.6 多项式派生超子类定义9设C1=C(x11,

27、x12,x1k),C2=C(x21,x22,x2k)是VRSP的两个模型类,如果存在一个多项式复杂度的多值算子(变换)f使f(C2)的全部元素为C1的子类,即对任意C f(C2),C1C,则称C2是C1的多项式派生超子类、C1是C2的多项式派生超父类、C1和C2具有多项式派生超父子关系,记作C1?fC2或C2?fC1 称f为多项式派生多值算子,在不引起混淆时简称为多项式算子例如 设C1是一个车队且车队车辆为一个或一个以上的任意类(C1是两个类的并),C2是一个车队且车队车辆为待定的任意类;定义f=对于每个k,f(C2)的第k个元素为一个车队且车队车辆数为k(k1)的类;则有C1?fC2 通过二

28、分法,如果C1的求解时间为T,则C2可在Tlog2n内确定最优的车辆数,这里n是最大可用的车辆数定义9用规则表示如下:IF多项式多值算子f对任意C f(C2),C1CTHENC1?fC2多项式派生超父类项=多项式派生超父类模型集多项式派生超父类模型集=多项式派生超父类编码多项式算子 多项式派生超父类编码多项式算子多项式派生超父类模型集多项式派生超子类是模型类多项式分解的一种形式,其概念有待于进一步发展下面提出定义9 是其中的一种修正方案定义9 设C1=C1C1=C(x11,x12,x1k)是VRSP一组模型类,C2=C(x21,x22,x2k)是VRSP的模型类,如果存在一个多项式复杂度的多值

29、算子(变换)f使得对任意C f(C2),存在C1C1使C1C,则称C2是C1的多项式派生超子类4模型库设计在VRSP的求解过程中,会涉及到两个模型库,一个是关于VRSP的;一个是关于其它运筹学问题的,88系统工程理论与实践2000年9月 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.如最短路问题、匹配问题、动态规划等模型,VRSP的某些算法有时引用这些运筹学问题的求解技术 限于篇幅,本文只讨论VRSP模型库 智能运输调度系统采用面向对象系统设计技术20,故模型知识表示使用面向对象方法21,22VRSP模

30、型库中存放全部模型类及其相关知识 定义如下:模型库=模型知识项模型知识项=模型结构类项父类项子类项多项式派生父类项 相似类项等价类项多项式派生超父类项算法集算法集=算法编码算法满意度 算法编码算法满意度算法集(所谓算法满意度是对于本模型类,该算法速度、精度等的综合评估值,具体评价方法另文讨论)5模型库管理系统根据第2、3节的讨论,VRSP模型种类成千上万,研究和应用的驱动也必将使模型类不断增加本节给出模型库管理系统的框架设计(图1),包括模型的人工分类、自动分类模块,及分类规则、分类事实和分类经验的维护模块本系统是人机共控、资源共享系统分类经验库存储人类通过直觉、顿悟等难于用显式规则、事实描述

31、的经验 其它库前文各节已经讨论,不再赘述 注意到模型分类受到算法库及其相关库的影响,限于篇幅,不再讨论细节内容图1智能运输调度系统模型库管理子系统6结语本文的研究虽然是针对智能运输调度系统进行的,但其思想和方法对一般智能管理系统的设计具有普遍意义 本文的研究受东风汽车公司有关应用项目的驱动而进行的,主要结果已经编程实现参考文献:1O rloff C S.A fundamental problem in vehicle routingJ.N etworks.1974,4:35642蔡延光.多重运输调度问题之研究D.杭州:浙江大学工业控制技术研究所,1996.3 蔡延光,钱积新,孙优贤.智能运输调

32、度系统的设计与实现J.决策与决策支持系统,1996,6(4):98第9期智能运输调度系统模型库构造与管理 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.108114.4Bodin L,Golden B.Classifaication in vehicle routing and schedulingJ.N etworks,1981,11:97108.5DesrochersM,L enstra J K,Savelsbergh M W P.A classification scheme for vehicl

33、e routing andscheduling problem J.Euro J Opnl Res,1990,46:322332.6蔡延光,钱积新,孙优贤.多重运输调度问题的计算复杂性J.运筹与管理,1997,6(3):15.7蔡延光,钱积新,孙优贤.多重运输调度问题的遗传算法与遗传局部搜索J.系统工程理论与实践,1997,17(12):101107.8蔡延光,钱积新,孙优贤.多重运输调度问题的模拟退火算法J.系统工程理论与实践,1998,18(10):1115.9蔡延光,钱积新,孙优贤.多重运输调度问题基于双表的并行表搜索算法J.系统工程理论与实践,1998,18(11):2026.10蔡延

34、光,钱积新,孙优贤.多重运输调度问题的数学规划算法与界限估计J.系统工程与电子技术,1998,(4):5962.11蔡延光,钱积新,孙优贤.多重运输调度问题的表搜索算法J.运筹与管理,1996,5(4):1825.12蔡延光,钱积新,孙优贤.多目标多重运输调度问题的混合算法J.湖北汽车工业学院学报,1998,12(4):13L aporte G.The vehicle routing problem:an overview of exact and approxi mate algorithm sJ.Euro J Opnl Res,1992,59:345358.14Current J,M ar

35、sh M.M ultiobjective transportation network design androuting problem s:taxonomy and annotationJ.Euro J Opnl Res,1993,65:419.15BallM O,M agnanti T L,M onma C L,N emhauser G L(eds.).N etwork RoutingA.Handbooksin Operations Research andM anagement ScienceJ.Am sterdam:North2Holland,1995.16 Kohl N,M ads

36、en O B G.A n opti m ization algorithm for the vehicle routing problem w ith ti mew indow s based on L agrangian relaxationJ.Opns Res,1997,395406.17林尧瑞,张钹,石纯一.专家系统原理与实践M.北京:清华大学出版社,1988.18李京,孙颍博,刘智深,张道一.模型库管理系统的设计和实现J.软件学报,1998,9(8):611618.19周美立.相似系统工程J.系统工程理论与实践,1997,17(9):3642.20梅姝娥,仲伟俊,徐南荣.面向对象系统设计方法研究J.系统工程理论与实践,1998,18(3):813.21吴今培.智能故障诊断与专家系统M.北京:清华大学出版社,1997.22陈文伟.决策支持系统及其开发M.北京:清华大学出版社,1994.09系统工程理论与实践2000年9月 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.