下载文档原格式
简要说明pki系统中多个ca间建立信任的方法。
-回复PKI（Public Key Infrastructure，公钥基础设施）系统中，信任是确保数字证书的有效性和安全性的关键因素。
在PKI系统中，多个CA （Certification Authority，认证机构）之间建立信任是一项重要的任务。
本文将一步一步回答如何在PKI系统中建立多个CA之间的信任。
第一步：了解PKI系统中的认证机构（CA）PKI系统中的认证机构（CA）是负责验证和签发数字证书的可信机构。
每个CA都有自己的根证书（Root Certificate），该根证书用于验证和签发下级CA的证书。
因此，CA在PKI系统中扮演着至关重要的角色。
多个CA之间建立信任需要确保它们之间的根证书是有效和可信的。
第二步：验证和签发CA的根证书在PKI系统中，首先需要验证和签发每个CA的根证书。
这可以通过以下步骤来完成：1. 验证CA的身份：对于每个CA，其他CA需要验证其身份，确保其符合PKI规范和安全要求。
2. 验证根证书的有效性：其他CA需要验证根证书的有效性，包括根证书的签名是否有效和根证书的完整性是否受到破坏。
3. 签发信任证书：一旦验证通过，其他CA将签发一个信任证书，证明它们对该CA的信任。
该信任证书包含验证通过的根证书信息和对该CA的信任声明。
第三步：更新信任证书和根证书PKI系统中的根证书和信任证书可能会需要定期更新。
更新根证书和信任证书的目的是增加信任的有效期限，以确保PKI系统的连续性和安全性。
以下是更新证书的步骤：1. 根证书的更新：如果根证书过期或被撤销，则需要生成新的根证书。
其他CA通过验证新根证书的有效性来更新对该CA的信任。
2. 信任证书的更新：信任证书也需要定期更新，以确保对其他CA的信任仍然有效。
更新的信任证书将包含新的根证书信息和对该CA的信任声明。
第四步：建立信任链在PKI系统中，信任链是将根证书和信任证书连接在一起的关键。
《基于博弈论的Web服务信任评估模型》篇一一、引言随着互联网技术的飞速发展，Web服务已成为企业间信息交互和业务协同的重要手段。
然而，由于网络环境的复杂性和不确定性，Web服务的安全性、可靠性和信任度问题日益突出。
为了解决这些问题，本文提出了一种基于博弈论的Web服务信任评估模型。
该模型通过引入博弈论的思想，对Web服务的信任关系进行建模和分析，旨在为服务提供者和服务请求者提供可靠的信任评估依据，从而提高Web服务的整体信任度和可靠性。
二、博弈论基础博弈论是研究决策主体的行为在相互影响、相互依存的情况下如何进行决策的理论。
在信任评估模型中，我们可以将服务提供者和服务请求者视为博弈的参与者，通过分析他们的策略选择和收益关系，来评估Web服务的信任度。
三、模型构建1. 模型假设在构建模型时，我们假设Web服务环境中存在多个服务提供者和服务请求者，他们之间的交互行为构成了一个博弈过程。
每个参与者都有自己的利益诉求和策略选择，同时受到其他参与者的策略影响。
2. 模型组成本模型主要由以下几个部分组成：（1）参与者：包括服务提供者和服务请求者。
（2）策略集：每个参与者都有自己的策略集，包括选择信任或不信任对方等。
（3）收益函数：根据参与者的策略选择和博弈结果，计算各参与者的收益。
（4）信任评估指标：根据收益函数和博弈结果，构建信任评估指标体系，对Web服务的信任度进行评估。
四、模型分析1. 博弈过程分析在Web服务环境中，服务提供者和服务请求者之间的博弈过程可以分为几个阶段。
首先，服务请求者需要选择信任或不相信某个服务提供者。
如果选择信任，则进行服务交互；如果选择不相信，则终止交互。
在服务交互过程中，服务提供者会根据服务请求者的行为和反馈来调整自己的策略。
这个博弈过程是一个动态的过程，需要不断地进行策略调整和收益计算。
2. 信任评估指标构建在博弈过程中，我们可以根据参与者的策略选择和收益关系，构建信任评估指标体系。
终端信任评估模型1.引言1.1 概述在当今信息时代，终端设备的安全性和可信度已经成为一个举足轻重的问题。
随着云计算、物联网和大数据技术的快速发展，终端设备的数量和种类不断增加，用户对终端设备的信任成为保障信息安全的重要环节。
终端设备的信任评估是对其安全性和可信度的评估和验证过程。
这一评估过程可以涵盖硬件平台、软件系统、数据处理能力、网络连接等方面，旨在通过评估终端设备的整体信任水平，为用户提供选择和使用终端设备的依据。
终端信任评估模型是用于描述和衡量终端设备信任水平的框架和方法。
通过构建信任评估模型，我们可以对终端设备进行系统性的评估，识别可能存在的安全风险和漏洞，并提供相应的解决方案和建议。
终端信任评估模型通常包括以下几个方面的内容：1. 可信硬件平台评估：对终端设备的物理硬件平台进行评估，包括芯片安全性、加密算法、随机数生成等方面，以确定硬件平台是否可信。
2. 可信软件系统评估：对终端设备的操作系统、应用程序等软件系统进行评估，包括漏洞扫描、代码审计、权限管理等方面，以确定软件系统是否可信。
3. 数据安全与隐私保护评估：对终端设备的数据处理能力和数据传输过程进行评估，包括数据加密、访问控制、隐私保护等方面，以确保数据的安全性和隐私性。
4. 网络连接与通信评估：对终端设备的网络连接和通信能力进行评估，包括网络协议安全性、通信加密机制、传输可靠性等方面，以确保网络连接的安全和稳定。
5. 用户体验与用户信任评估：对终端设备的用户体验和用户信任进行评估，包括用户界面友好性、交互设计、用户隐私意识培养等方面，以提高用户对终端设备的信任度。
通过对上述各方面的评估，终端信任评估模型可以为用户提供一个全面、科学的终端设备选择标准，帮助用户更好地保护自己的信息安全和隐私。
同时，终端信任评估模型也可以为终端设备制造商提供改进产品安全性和可信度的指导和建议，促进整个行业的健康发展。
总之，终端信任评估模型是信息安全领域一项重要的研究内容，它对保障用户信息安全和提升终端设备可信度具有重要意义。
可信层次评估模型
可信层次评估模型是一种用于评估信息系统安全性的模型。
该模型基于不同层次的安全需求，将信息系统划分为不同的层次，分别对每个层次进行评估。
评估结果根据不同层次的安全需求制定相应的安全策略和措施，以保证信息系统的安全性。
可信层次评估模型包括以下层次：物理层、操作系统层、应用程序层、用户层、管理层。
在物理层，评估的重点是硬件设备的安全性和环境的安全性；在操作系统层，评估的重点是操作系统的安全性和配置的安全性；在应用程序层，评估的重点是应用程序的安全性和数据的安全性；在用户层，评估的重点是用户的安全行为和密码的安全性；在管理层，评估的重点是安全管理的完整性和有效性。
可信层次评估模型可用于评估各种类型的信息系统，如网络系统、数据库系统、电子商务系统等，具有灵活性和适用性。
该模型可以帮助企业和机构评估其信息系统的安全性水平，制定相应的安全策略和措施，提高信息系统的安全性和可信度。
- 1 -。
一种基于行为评估的信任模型[摘要]网格是通过网络向用户提供可随时按需利用计算资源和信息资源的环境。
由于这一环境的动态性和不确定性。
给区域间网格实体的合作带来一系列安全问题，其中最难以确定的，是网格实体间的信任关系。
当前的安全机制，已经可以解决信任关系中的身份信任，但实体间的行为信任，却是这些安全机制所不能处理的。
文章把行为信任划分为直接信任和推荐信任，提出了一种基于行为评估的信任模型，采用数学形式化的方法，得到实体的信任度和声誉度，共同衡量网格环境中实体之间的信任关系，以更科学、有效地解决网格环境中的行为信任问题。
[关键词]网格；行为评估；信任；信任度；信任模型[作者简介]农毅，男(1973-)，广西宁明人，桂林电子科技大学管理系讲师，硕士，研究方向：计算机网络，计算机控制；古天龙，男，桂林电子科技大学管理系教授，博士生导师，研究方向：嵌入式系统，形式化技术等，广西桂林，541004．[中图分类号]TP393．08[文献标识码]A[文章编号]1007-7723(2006)11-0108-03一、引言网格就是能够提供对高端计算能力的独立、一致、普遍且廉价的访问的硬件和软件体系结构[1]。
随着网格计算系统的发展，网格环境中的动态性和不确定性，使得信任问题已经成为安全保障的一个重要因素。
当网格实体间进行紧密的合作时，为了能够可靠地共享资源，我们需要确定他们之间的信任关系。
信任可以划分为实体身份的信任和实体行为的信任[2]。
传统的安全机制有加密技术、访问控制等等，它们被用来提供授权和认证，解决了身份信任的问题。
但它们并不能处理行为信任，不能保证提供你所需要的服务(例如不能保证按你所需要的方式进行授权)[3]。
本文提出了一种基于行为评估的信任模型，采用数学的方法把实体间的行为量化，从而科学地评估实体之间的信任关系，帮助网格实体进行信任抉择，从而能够有效地解决网格环境中存在的安全问题。
二、网格中的信任问题(一)行为信任的分类关于声誉和信任的研究已经很多[4][5][6]，它们是相关联的两个概念，都可以用来评价某个实体的信任度。
面向物联网节点的综合信任度评估模型建立
面向物联网节点的信任度评估模型是指通过对物联网节点的行为和性能进行综合评估，以确定节点的可信度和可靠性。
这个模型可以帮助用户对物联网环境中的节点进行选择和
管理，提高系统的安全性和稳定性。
物联网节点的信任度评估模型可以分为两个方面：主观评估和客观评估。
主观评估是
通过用户的主观意见和经验来判断节点的可信度，而客观评估是通过对节点的行为和性能
进行实时监测和分析来评估节点的可靠性。
在主观评估中，用户可以根据他们的经验和观察来评估节点的可信度。
这包括对节点
生产商的信誉度、节点的性能和功能的了解、以及其他用户的评价和反馈等。
这些因素可
以帮助用户对节点做出判断，选择合适的节点。
在客观评估中，可以通过对节点的行为和性能进行实时监测和分析来评估节点的可靠性。
这可以包括对节点的通信质量、数据传输速度、稳定性、功耗等指标的监测和分析。
通过对这些指标的分析，可以判断节点的性能是否达到预期，并对节点的可信度进行评
估。
KMI／PKI及SPK密钥管理体制}O|()川fjl密钥管理技术是信息安全的核技术之一.在美国"信息保险技术框架"中定义了深层防御战略的两个支持构架:密钥管理构架/公凋构架(KMI/PKI)和入侵检测/l向应技术.当前,密钥管理体制主要有三种:一是适用于封闭网的技,以传统的密钥管理中心为代表均KMI机制;二是适用于开放网的KI机制;另一种是适用于规模化专用网的SPK.一,KMI技术KMI(密钥管理中心)经历了从挣态分发到动态分发的发展历程,|前仍然是密钥管理的主要手段.论是静态分发或是动态分发,都于秘密通道(物理通道)进行.1.静态分发静态分发是预配置技术,大致以下几种:1)对点配置:可用单钥实现,旦可用双钥实现.单钥分发是最简而有效的密钥管理技术,单钥为鉴别提供可靠的参数,但不能提供可否认性服务.有数字签名要求时则用双钥实现.2)一对多配置:可用单钥双钥实现,是点对点分发的扩展,只是在中心保留所有各端的密钥,而各端只保留自己的密钥即可.一对多的密钥分配在银行清算,军事指挥的数据库系统中仍为主流技术,也是建立秘密通道的主要方法.3)格状网配置:可以用单密钥实现,也可以用双钥实现.格状网的密钥配置也称端端密钥.其密钥配置量为全网n个终端用户中选2的组和数;KERBEROS曾排过25万用户的密钥.格状网是网络化的信息交换网,因此一般都要求提供数字签名服务,因此多数用双钥实现,即各端保留自己的私钥和所有终端的公钥.如果用户量为25万个,则每一个终端用户要保留25万个公钥. 2.动态分发动态分发是"请求,分发"机制,即与物理分发相对应的电子分发,在KMI下在已在秘密通道的基础上进行,一般用于建立实时通信中的会话密钥,在一定意义上缓解了密钥管理规模化的矛盾.1)基于单钥的单钥分发设一个中,Oc和两个交信双方A(发起者)和B(相应者).在用单密钥实现时,首先用静态分发方式下配置的星状密钥配置,主要解决会话密钥的分发.这种密钥分发方式简单易行.不带鉴别的密钥分发如下:(1)A—C:申请A和B通信的密钥KA—B;C—A:B分别加密发送双方交信用密钥KA—B; EKC—A【KA—B);EKC—B【KA—B);(2)双陟有相同的瘟钥KA—B,可以进行保密通信.带鉴别的动态分发主要有两种模式:拉方式和推方式.(1)拉方式前提:在KMI和A之间,KMI和B之间已有秘密密钥KA和KB.a.A—,C:request//n1;b.C—,A:EKA(KS//request//n1//EKB(KS,IDA));C.A—B:EKB(KS,IDA);d.B—A:EKS(N2);e.A—B:EKS(fN2),其中f是简单函数,是加1等简单变换.这样A,B双方都有相同的密钥KS.(2)推方式前提:在KMI和A之间,KMI和B之间已有秘密密钥KA和KB.a.A—B:A,EKA(EMA);b.B—C:EKA(EMA)C.C—B:EKB(KS,A,EMB),EKA(KS,B,EMA)d.B—A:EKA(KS,B,EMA)2)基于单钥的双钥分发技木论坛rl/,1'fo/Tmq在双钥体制下,公,私钥对都当作秘密变量,也可以将公,私钥分开,只把私钥当作秘密变量,公钥当作公开变量.尽管将公钥当作公开变量,但仍然存在被假冒或篡改的可能,因此需要有一种公钥传递协议,证明其真实性.(1)公钥分发协议基于单密钥的公钥分发,其前提是中心和各终端之间已存在单钥的星状配置.分发协议如下:a.A—C:申请B的公钥,包括A的时间戳.b.C—A:将B的公钥用单密钥加密发送,包括A的时间戳.C.A—B:用B的公钥加密数据,A的标识和nonceNl.d.B—C:申请A的公钥,包括B的时间戳.e.C—B:将B的公钥用单密钥加密发送,包括B的时间戳.f.B—A:用A的公钥加密A的Nl和B的N2.g.A—B:用B的公钥加密N2,返回B.(2)公钥分发途径公钥的分发方式很多,可归结为以下3种:当众宣布,公众目录, 公钥证书交换.Kohnfelder于1978 年提出公钥证书(PubliCkeY certificate),以证书形式进行密钥分发或公布,私钥则通过秘密通道分发,分发机构称CA(certificate agency).二,PKI的兴起1.PKI发展过程在密钥管理中不依赖秘密信道的密钥分发技术一直是一个难题. 20世纪70年代末,Deffie,Hellman 第一次提出了不依赖秘密信道的密钥交换体制D—H密钥交换协议,大大促进了这一领域的进程.但是,在双钥体制中只要有了公,私钥对的概念,私钥的分发必定依赖秘密通道.于是PGP第一次提出密钥由个人生产的思路,避开了私钥的传递, 进而避开了秘密通道.这是伟大的概念的转变,带动了PEM,509CA,PKI的发展.PKI密钥管理解决了不依赖秘密信道的重大密钥管理课题,但这只是概念的转变,并没有多少新技术.PKI是在民间密码摆脱政府控制的斗争中发展的,而且这种斗争一度到了白热化程度.PKI以商业运作的形式壮大起来,以国际标准的形式确定,其技术完全开放,甚至连一向持反对态度的美国国防部, 联邦政府也不得不开发PKI的策略.既然PK1只是用概念的转换来解决了不依赖秘密信道的密钥分发, 由此可能引发很多新问题,如第三方认证的法律地位,信任关系的转移和扩展以及CRL作废证书的保留等.2.DoDPKJ美国国防部1999年3月开始酝酿国防PKI之事,并制订了国防部PKI行程图和DoDX509证书策略, 于1999年l0月和l2月分别公布,声称要保持这一领域的领导地位. PKI是美国国防部密钥管理构架KMI(KeYManage1TIent Infrastructure)的重要子集.PKI先在非密系统中试点,测试,选型.那么,企业界PKI和国防部PKI有哪些不同呢?1)企业界PK1只提供数字签名服务,而国防部PKI提供数字签名和密钥交换(加密)服务;2)国防部PKI增设了密钥托管功能(由ISSO信息系统安全官托管);3)国防部PKI除证书CA外还增设了IDCA;4)CA不是第三方,而是主管方NSA(国防部国家安全局).美国国防部搞PKI的动机,做法,动向是值得研究的.美国国防部想确立或找回这一领域中的领导地位.实际上近30年,美国官方的密钥管理技术越来越明显落后于民间和企业界.这里有主观原因和客观原因.一般军事网比较整齐,业务比较单一,因此对新技术的需求不很迫切.当民问的公钥密码体制问世时,美国国防部采取了限制措施,不鼓励发展.后来证明公钥体制在密钥交换中和不可否认性证明中起到不可替代的作用,但是却受到了专利权的限制,处于欲用而不能用的尴尬境地.因此美军不得不走另一条路,即购买现成的产品.这一点在国防部PKI行程图和安全策略中以及在信息保险技术框架中明显体现出来.3.KMI和PKl的关系信息自保技术框架》是NSA编写的,但培训对象并不是国防部, 而是企业界和政府部门.此书基本上遵从了国防部PKI行程图》和国防部PKI策略,但有意把KMI和PKI,ID卡和CA证书,主管方KDC和第三方CA混淆在一起.在书中简单地将传统的单密钥统统纳入KMI,而把双公钥统统纳入PKI 中,但也承认KMI中不少单密钥已被双密钥所替代.为了说明的方便, 这样划分是可以理解的.密钥管理没有一个万能的技术,因为网络不同,业务性质不同,对密钥管理模式提出不同的要求. KMI和PKI也一样,有自己的优点, 也有缺点,也有自己适合的环境,也有不适合的环境.能满足业务需求而又最简捷的密钥管理才是最好的密钥管理技术.理论上完美的不一定适用,实用技术都有缺点,因为安全系统是实用系统,是利弊权衡的产物.下面分析两种密钥管理体制的优缺点和适用范围:1)从作用特性角度看:KMI具有很好的封闭性,而PKI则具有很好的扩展性.KMI的密钥管理可随时造成各种封闭环境,可作为网络隔离的基本逻辑手段,而PKI适用于各种开放业务,却不适应于封闭的专用业务和保密性业务.2)从服务功能角度看:KMI提供加密和签名功能,PK1只提供数字签名服务.PKI提供加密服务时应提供秘密恢复功能,否则无法用于公证.PKI提供数字签名服务时, 只能提供个人章服务,不能提供专用章服务.3)从信任逻辑角度看:KMI是集中式的主管方的管理模式,而PKI是靠第三方的管理模式,基于主管方的KMI,为身份鉴别提供直接信任和一级推理信任,但密钥更换不灵活;基于第三方的PK1只能提供一级以下推理信任,密钥更换非常灵活.4)从负责性角度看:KMI是单位负责制,而PKI是个人负责的技术体制;KMI适用于保密网,专用网等,PKI则适用于安全责任完全由个人或单方承担,其安全责任不涉及它方利益的场合.5)从应用角度看:互联网中的专用网,主要处理内部事务,同时要求与外界联系.因此,KMI主内, PKI主外的密钥管理构思是比较合理的.如果一个专用网是与外部没有联系的封闭网,那KMI就足够.如果一个专用网可以与外部联系, 那么要同时具备两种密钥管理体制, 至少KMI要支持PKI.如果是开放网业务,则可以用PKI处理,也可以人为设定边界的特大虚拟专用网的SPK技术(种子化公钥)处理,如一个国家范围内构成大的专网.三,SDK技术根据美国国防部的KMI和PKI发展动向看,这两者的差别越来越小.KMI往PKI方向发展,而PKI越来越带有KMI的性质.PKI解决了密钥的规模化,但仍没有解决不依赖秘密通道的问题,身份认证过程(注册)还是用面对面的物理通道来解决.存在秘密通道和物理通道,本来可以减少很多不必要的麻烦,但PKI没有这样做,将很多麻烦留给后面的应用中,这是很大的逻辑上的矛盾.研究表明任何有信任要求的安全系统都是有边界的(封闭性),而且是有中心的.一旦承认有边界,有中心,存在秘密通道,那么规模化的密钥管理就可以用简化的方法实现,即可以省掉如CRL,运行协议, LDAP等部件.目前提出来的种子化公钥(SPK=Seededpublickey)或种子化双钥(SDK=seededdoublekey)体制有三种.公钥和双钥的算法体制相同,在公钥体制中,密钥的一方要保密,而另一方则公布;在双钥体制中则将两个密钥都作为秘密变量.在PKI体制中,只能用前者,不能用后者.在SPK体制中两者都可以实现.1.多重公钥(双钥)(LPK/LDK)多重公钥(双钥)(Lappedpubic ordoublekey)用RSA公钥算法实现.1990年提出并实现,如:以2K个公钥种子,实现100万用户的公钥分发.多重公钥(双钥)有两个缺点:/b(hm/r1/:Ol71111技7ft论坛一是将种子私钥以原码形式分发给署名用户;二是层次越多,运算时间越长.2.组合公钥(双钥)(CPK/CDK)组合公钥(双钥)(Combined publicordoublekey)用离散对数DLP或椭圆曲线密码ECC实现. 因为这两个算法非常类似,算法和协议互相可以模拟,所以只以ECC 来说明.ECC组合公钥(双钥)算法:2000年提出,2001年实现demo,以1K个公钥种子,实现1078用户的公钥.1K个公钥种子可以在网上公布(CPK时),让各用户下载使用;也可以记录在简单媒体中,与私钥和ID卡或CA证书一同发给用户, 将私钥和"公钥"一同加密(CDK 时),分发给用户使用,因此,公钥的分发变得非常简单而方便.组合公钥克服了多重公钥的两个缺点,私钥是经组合以后的变量,不暴露种子,公钥的运算几乎不占时间.由此可见种子公钥体制,尤其是椭圆曲线组合公钥(双钥)是电子商务和电子政务中比较理想的密钥管理解决方案.(总参第五十八所)0。
两层物资配送中心车辆调度问题研究 耿 雪1,2，段会川1,2 (1. 山东师范大学信息科学与工程学院，济南 250014；2. 山东省分布式计算机软件新技术重点实验室，济南 250014) 摘 要：在分析物流配送物资问题的基础上，提出一种基于两层物流配送中心的物资配送方法。供应方在配送物资时需经过两层配送中心到达需求方，否则将予以惩罚。在建立供应方、两层物流配送中心及需求方四层物流网络模型的基础上，采用Dijkstra算法求出从各供应点到各需求点的最短运输距离并将其转化在供需平衡表中，采用表上作业法和节约里程法相结合的算法求解四层物流网络模型。结合算例计算验证，该算法在保证运输总费用最少的同时可有效地减少配送过程中车辆调度的次数。 关键词：表上作业法；物资配送；物流网络模型；Dijkstra算法；节约里程算法；最小元素法
Research on Vehicle Schedule Problem of Two-layer Mterial Distribution Center
GENG Xue1,2, DUAN Hui-chuan1,2 (1. School of Information Science and Engineering, Shandong Normal University, Jinan 250014, China; 2. Shandong Provincial Key Laboratory for Distributed Computer Software Novel Technology, Jinan 250014, China)
【Abstract】By analyzing the problem of logistics, this paper proposes a way of dispatching material on the basis of two-layer distribution center. When dispatching the materials, the side of supplier has to pass through two layers of distribution center to reach the side of demander, otherwise it will be punished. On the basis of establishing the model of four-layer logistics network, which includes the sides of supplier and demander, also two layers of distribution center, this paper uses the Dijkstra algorithm to obtain the shortest transport distance between the point of supplier point and the point of demander, and conversion into the balance chart of supply and demand, then it makes use of algorithm which combines the Tabular method and save-mileage method to solve the model of four-layer logistics network. Experimental results show that the algorithm can guarantee the least total cost of transportation. At the same time, it can effectively reduce the number of vehicle schedule in the process of delivery. 【Key words】Tabular method; material distribution; logistics network model; Dijkstra algorithm; saving mileage algorithm; minimum element method DOI: 10.3969/j.issn.1000-3428.2012.05.088
计 算 机 工 程 Computer Engineering 第38卷 第5期
Vol.38 No.5
2012年3月
March 2012
·开发研究与设计技术· 文章编号：1000—3428(2012)05—0285—03
文献标识码：A
中图分类号：TB114.1
1 概述 在物资配送过程中，面对强大的竞争压力，作为企业第三利润源的物流业在社会生产过程中的地位越来越重要。随着物流配送物资过程的复杂性，出现了多层物流配送中心的运输物流网络问题，车辆路径优化(Vehicle Routing Problem, VRP)是基于复杂物流网络运输问题研究的关键之处[1]。国外
学者对其进行的研究起步较早，常用启发式算法进行求解，如节约启发式、遗传算法等，国内学者对其进行的研究起步较晚，以C-W为基础的启发式算法对VRP进行了求解；也
运用遗传算法就VRP问题进行求解等。 运输问题[2]是线性规划的一类特殊问题，它可以解决物资的合理配送。因此，可以尝试将问题转化在近似供需平衡表中，运用表上作业法进行求解。运输问题存在着产销平衡、供大于求和供不应求的情况。对于产销不平衡的情况，可以通过增加虚拟产地(虚拟销地)转化为产销平衡的问题进行求解。本文基于产销平衡的运输问题，结合改进的表上作业法和节约里程算法，研究基于四层物流网络中如何将物资进行最优化调度。
2 物资配送模型的建立 2.1 物资配送模型 由于城市规模都比较大，物流配送车辆又受到交通拥挤的影响，如果每个供应点都只通过一级配送中心供应物资，
不仅造成很多较远的需求点难以及时得到物资，同时又造成了配送中心的紧张局势，导致整个服务水平降低，因此出现了多层物流配送中心。车辆运输物资的过程如图1所示[3]。
供应点1供应点2. . .供应点m供应点1供应点2. . .供应点n
物流中心
配送
配送配送配送 图1 物资配送模型 根据本文研究的内容，可将物资配送模型转换为四层物流网络模型，如图2所示。
图2 四层物流网络模型 作者简介：耿 雪(1987－)，女，硕士研究生，主研方向：优化调度，物流管理；段会川，教授 收稿日期：2011-08-24 E-mail：gengxuesdnu@163.com 286 计 算 机 工 程 2012年3月5日 该模型可以描述为供应方Ai的物资经过两层配送中心到达需求方Bj。设某产品有m个供应商A1,A2,…,Am，可供应物资a1,a2,…,am；另有n个需求方B1,B2,…,Bn，需求物资b1,b2,…,bn。用gij表示从供应点i到需求方j的供应量，用xij表示从供应点i到需求点j的路径和，若从Ai到Bj的单位运价为cij，这样就把问题转化为：在此网络求可行的调配方案，使得保证总的运价最小。 根据对物资配送问题的描述，为了更直观地说明在配送过程中要解决的问题，首先给出供需平衡表[4]，如图3所示。然后建立如下数学模型，如式(1)~式(3)所示，式(4)~式(6)表示需要满足的约束条件： 11min(2)ijijmnijCcXx==××=+∑∑ (1) min(1())()ijikkssjkjxLLLXLX=++−×+× (2) 01X⎧=⎨⎩物资经过二级配送中心到达需求方物资从一级配送中心直接到需求方 (3) 11qnskjsjMQ==∑∑≤ (4) 11mnijijab===∑∑ (5) 110,,ijnmijiijjjigggab====∑∑≥ (6) 其中，Lik表示从Ai到一级配送中心的距离；Lks表示从一级配送中心到二级配送中心的距离；Lkj表示从一级配送中心到需求点的距离；Lsj表示从二级配送中心到需求点的距离；xij表示从供应点i到需求点j的路径和；Mk表示车辆在第k条路径上的一次运载量；Q表示车辆的载重量。 在上述模型中，式(1)为目标函数，即要求配送总里程最短。任一供应方需经过2次配送中心到达需求方，供应方Ai的物资如果只经过一层配送中心到达需求方Bj，则相应的会有2个单位的费用惩罚；式(2)表示了从Ai经过二级配送中心到达Bj的距离之和；式(4)表示了第s个二级配送中心在第k条路径上的运载量不超过车辆的载重量；式(5)、式(6)保证了产销平衡。 B1 B2 … Bn 供应量 A1 C11 C12 … C1n a1 A2 C21 C22 … C2n a2 … … … … … … Am Cm1 Cm2 … Cmn am 需求量 b1 b2 … bn 图3 供需平衡表 2.2 相关算法描述 2.2.1 Dijkstra算法 最短路径搜索算法旨在寻找图中两节点之间的最短路径。常用的路径算法有：Dijkstra算法，A star算法，SPFA算法，Bellman-Ford算法，Floyd-Warshall算法，Johnson算法。可以采用Dijkstra算法求得从某个源点到其余各顶点的最短路径[5]。 2.2.2 表上作业法 表上作业法[6]是求解运输问题的一种行之有效的方法，其求解工作在平衡运输表上进行。它是一种迭代法，迭代步骤如下： 步骤1 用最小元素法或西北角法找出一个初始解。 步骤2 运用闭回路法或位势法对所求的初始解进行最优性判别。若这个解不是最优解，就在运输表上对它进行调整改进，得出一个新解；再判别，再改进；直至得到运输问题的最优解。 2.2.3 节约里程算法 节约里程算法[7]的核心思想是依次将运输问题中的2个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。 如图4所示，物资从A、B分别运往DC，然后返回A、B，那么路程为2×(La+Lb)，车辆调度次数为4。若Lab<(La+ Lb)，则Lab+Lb+La<2×(La+Lb)，所以车辆可以从A-B-DC-A，这样不
仅可以节约路程，而且可以减少车辆调度次数[8]。
图4 节约里程算法样例 3 D-T-S算法 针对2.1节中建立的四层物流配送网络模型，提出了一种新的算法，将Dijkstra算法、表上作业法和节约里程算法相结合求解四层网络配送问题。步骤如下： 步骤1 运用Dijkstra算法求出从各供应点经过两层配送中心到达各需求点的最短路径，并将其转化在供需平衡表中。 步骤2 运用最小元素法求得运输问题的初始解，在物流配送物资过程中，在每一次配送过程中都保证单位运价最小化，从而经过若干步后可以完成物资配送过程。 步骤3 用闭回路法进行检验，构造每一个空格的闭回路，计算出各非基变量(对应空格)的检验数。若检验数大于或等于0，则可得问题的最优解；否则，需找出绝对值最大的负检验数格进行调整，经过调整后得到问题的最优解。 步骤4 在保证车辆运载能力的情况下，运用节约里程算法对运输问题中从二级配送中心到需求方的2个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。具体过程如图5所示。
