罗义学

(1.北京科技大学机械工程学院，北京100083；2.南宁市公安局交通警察支队，广西南宁530022)

0 引 言

送货时间是衡量物流配送水平的一个非常重要标准。物流配送的目标是准时、准确和快速，因此路径优化是物流配送的关键环节。其作用是高效地计算出配送车辆到目的地的最佳路径，实现对配送车辆出行路径的优化，引导车辆沿最优路径到达目的地。物流配送路径优化，对物流企业提高服务水平、降低物流成本、提高竞争力和增加经济效益具有十分重要的理论和现实意义。

物流配送路径优化的关键是最优路径(SP)算法，Dijkstra算法是解决最优路径问题中的经典算法[2]。在实际物流配送网络，各个路段的行驶时间及交叉口延误共同组成的交通阻抗将直接影响配送车辆的路径选择[3]。调查表明车辆在交叉口的时间延迟占整个出行时间的20%-40%[4]。因此在配送网络中距离最短路径并不一定是最优路径，车辆受交叉口时间延误的影响，最优路径可能是距离相对较长而用时最短的一条路径[5]。对于物流配送网络来说，配送车辆在交叉口处的时间延误与其在路段上的行驶时间相比同样重要。因此建立一种考虑实际交通阻抗的物流配送路径优化算法，使求解的最优路线符合实际交通情况，具有重要的理论和现实意义。

Petri网是一种图形化的建模工具，它不仅可以刻画系统结构，而且可以描述系统的动态行为，它能精确地描述事件之间的顺序、并发、同步等关系，适合于描述离散事件的动态过程[6-7,9]。Petri网模型是目前离散事件动态系统建模中最活跃的技术之一。物流配送路径选择是典型的离散事件系统，所以选择Petri网对物流配送路径选择进行模拟比较合适。

1 基于智能Petri网的物流配送路径优化算法

物流配送网络是相对复杂且处在动态变化中的系统，因此需要在基本Petri网的基础上进行扩展，建立一种可以描述物流配送网络的智能Petri网，并通过制定一些简单的运行规则来建立最优路径的选择方法。本文给出的物流配送路径优化算法主要由物流配送网络智能Petri网和路径优化运行规则两部分组成。

1.1 物流配送网络的智能Petri网描述

智能Petri网(intelligent Petri net)是在基本Petri网基础上的拓展，是可以描述系统组织结构和系统状态动态变化的一种系统模型[7]。它由库所Pi(用圆圈表示)、变迁ti(用矩形方块表示)以及连接库所、变迁的线段和库所中的托肯(用小黑点表示)构成。如图1所示给出的智能Petri网由5个库所(Pi(i=1,2,…,5)、4 个变迁 ti(i=1,2,3,4)及 8 条连线构成。

图1 智能Petri网

对智能Petri网进行赋时，即当某一变迁的发生条件满足时，延迟一段时间后从相应的输入库所中移走相应的托肯。智能Petri网中的库所Pi标上的时间值tpi称为库所时间，对应的库所称为时间库所。定义：①托肯运行方向集T：当托肯处在某库所时，通过变迁与该库所直接连接的库所组成的集合。②托肯经过库所集S：托肯达到目标库所经过的库所的集合。如：T3={P1,P2,P3,P4,P5}，S1={P1}，S5={P5}。

1.2 物流配送网络的智能petri网

物流配送网络由交叉口和路段组成。根据图论可以将物流配送网络抽象为节点、边的元素集和他们相互关系描述的一张图G，G=G(V,E,W)，其中V表示节点vi的集合；E为有向弧eij的集合；W为权值Wij的集合，表示配送车辆在路段上行驶的时间。物流配送网络的图模型如图2所示，配送车辆在路段上的行程时间标注于图中弧段的旁边。

图2 物流配送网络的图模型

物流配送网络的智能Petri网描述：库所Pi代表配送网络的节点Vi；当节点Vi与Vj之间有连线时，表示库所Pi与Pj之间存在变迁tij，若无连线时表示库所之间不存在变迁。配送车辆用托肯表示，配送车辆在路段上行驶的时间用库所Pi与Pj间的变迁tij消耗值表示。物流配送网络的智能Petri网模型如图3所示。

求配送车辆所在的节点Vi到目标客户所在节点Vj的最优路径问题，即转化为时间库所Pi经过变迁到达时间库所Pj的最小消耗。初始条件为托肯在库所Pi，满足的约束为托肯经过变迁所用的时间消耗最小，托肯按照变迁的规则，使托肯逐步到达目标库所Pj，求得托肯经过库所集Sj，即求得最优路径。

相对于物流配送网络图模型，物流配送网络智能Petri网模型可以实现配送过程的动态模拟。

图3 物流配送网络的智能Petri网模型

1.3 智能Petri网路径选择运行规则

在描述物流配送网络的智能petri网建立以后，需要对物流配送路径的选择进行定义，以实现物流配送路径选择的优化。以图2为例，配送车辆位于节点Vi，目标客户位于节点Vj，配送车辆在路段上的行驶时间为定值，车辆在各交叉口的右转、直行和左转平均延误的时间不同。求配送车辆所在节点Vi到目标客户所在节点 Vj的最优路径问题可以转化为智能Petri网路中(如图3所示)托肯在时间库Pi经过变迁到达时间库所Pj的最小时间消耗。

因此最优路径的算法可以描述为，初始条件为托肯在库所Pi，满足的约束为托肯经过变迁所用的时间消耗最小。以图3为例，本论文定义最优路径选择规则如下：

规则1：当托肯在库所P时，托肯的运行方向由可行方向集T'决定。T'区别于运行方向集T。当托肯在库所Pi时，变迁tik发生后，托肯到达库所Pk，此时托肯的可行方向集为Tk'=Tk-{Pi}。

规则2：赋予时间库所中的托肯两种状态：“进入库所中延时”状态和“延时完成”状态。当托肯进入时间库所P，托肯处于“进入库所中延时”(用空心黑点来表示)状态，库所时间开始消耗，当库所时间耗时完成，托肯的状态变为“延时完成”(用实心黑点来表示)时，则实施某个变迁t，托肯将进入输出库所。

规则3：托肯在库所Pi“延时完成”后的运行方向由可行方向集Ti'决定；沿可行方向集Ti'分别实施变迁t，在变迁经过“路途耗时完成”后，在对应库所集Ti'中的输出库所元素中放入一个托肯，并使托肯处于“进入库所中延时”状态。输入库所Pi中的“延时完成”状态的托肯被移出。

HLFs细胞(编号GNHu28)从中科院细胞库购买。试剂有DMEM培养液、0.25%胰蛋白酶、胎牛血清(美国 Gbico)，Tβ4(美国 RegeneRx)，DAPI、鼠抗人a-SMA抗体(美国Sigma)，兔抗人GAPDH、HI心标记的羊抗兔、羊抗鼠IgG抗体(美国CST)，TRITC标记的羊抗鼠 IgG(鼎国生物)，重组人TGF-β1(美国 R＆D)，BCA 蛋白浓度检测试剂盒(美国pierce)，CCK-8试剂盒(日本同仁)。

规则4：当一个库所Pi存在一个托肯且该托肯处于“延时完成”状态或者库所Pi曾经存在过托肯，而另外一个库所Pj中的托肯经过变迁t的输出库所为Pi，则变迁t不再实施，将库所Pj的中托肯移出网络。即每一个库所只能接受唯一一个变迁的“延时完成”托肯。

规则5：当一个库所Pi存在一个托肯且该托肯处于“进入库所中延时”状态或者库所Pi曾经存在过托肯，而另外一个库所Pj的中托肯经过变迁t的输出库所为Pi，则实施变迁，托肯进入输出库所Pi，与其它托肯一起处于“进入库所中延时”状态，Pi中最先处于“延时完成”状态的托肯开始按照可行方向集Ti'运行，库所Pi中的其余托肯移出网络。

规则6：当目标库所Pj中拥有托肯时，则计算终止，到达目标库所的托肯经过的库所集S，即为最优路径。

2 实例分析

本文采用文献[8]中的算例，并与改进的Dijkstra算法求解进行对比，以此来论证算法的可行性、有效性。基于智能petri网的物流配送路径优化算法流程如图4所示。

图4 基于智能petri网的物流配送路径优化算法流程

算例：如图5所示物流配送网络图，配送车辆位于节点V1，目标客户位于节点V9。配送车辆在路段上的行驶时间标注于图中弧段的旁边。配送车辆在各交叉口的右转、直行和左转平均延误时间分别为0、2、3(时间单位：min)，计算配送车辆从V1到达目标客户V9的最优路径。

图5 算例的物流配送网络

基于经典的Dijkstra算法求得在不考虑交叉口延误时的最优路径，如图6中粗实线所示：最优路径有3条V1V4V7V8V9，V1V4V5V8V9，和V1V4V5V6V9。然后根据文献[8]的改进的Dijkstra算法求得在考虑交又口延误时的最优路径，如图7中粗实线所示：最优路径为V1V4V5V8V9。

图6 不考虑交又口延误时的最优路径

图7 考虑交又口延误时的最优路径(改进的Dijkstra算法)

(1)将算例的物流配送网络转化为智能Petri网模型，托肯运行的方向用箭头表示。在第0时刻，库所P1的库所时间tp1=0，T1'={p2,p4}。P2和 P4中均没有托肯，实施变迁 t1和 t2。(如图8(a)所示)。

(2)在第13时刻，变迁t8的输入库所P5中的托肯处于“延时完成”状态，实施变迁t8。由于P2、P5中都有托肯，且处于“延时完成”状态，不实施变迁t4。变迁t9的输入库所P5中的托肯仍然处于“进入库所中延时”状态。变迁t6在第12时刻“路途耗时完成”，托肯进入库所P7中处于“延时完成”状态，实施变迁t10。变迁t3，t10没有“路途耗时完成”，则继续耗时。(如图8(b)所示)。

(3)在第22时刻，由变迁t9进入输出库所P8的托肯在P8中首先达到“延时完成”状态，因此由变迁t10进入输出库所P8的托肯被移出网络。实施变迁t12，且t12没有“路途耗时完成”，则继续耗时。此时，P6中的托肯“延时完成”，实施变迁t11，变迁t11没有“路途耗时完成”，则继续耗时。由于P6中已经有托肯，且处于“延时完成”状态，不实施变迁t7，并将P3托肯移出网络。(如图 8(c)所示)。

(4)在第25时刻，变迁t12“路途耗时完成”，托肯进入P9，且托肯处于“延时完成”状态。因为P9就是目标库所，运行完毕。托肯经过的库所集合为S={P1,P4,P8,P9}，即最短路径为V1V4V5V8V9。(如图 8(d)所示)。

图8 不同时刻智能Petri网

可见，应用基于智能PETRI网的物流配送路径优化算法得出的最优路径与改进的 Dijkstra算法得出的最优路径是一致的。运用该算法，可以得到配送车辆从出发点到城市中任何一个节点的最优路径。比如车辆从V1到达目标客户V6的最优路径为V1V4V5V6，耗用的时间为19个单位时间。

3 结束语

本文利用智能 Petri网在描述离散事件动态过程上的优点，考虑配送车辆受交叉口时间延误的影响，建立了物流配送网络的智能Petri网，并通过定义运行规则，给出了基于智能Petri网的物流配送路径优化算法与计算流程。经算例与改进的Dijkstra算法相比，论文提出的算法不需要对物流网络图作任何修改，同时还可实现配送过程的动态模拟。实际上物流路径的选择过程是十分高智能、复杂的，本文给出的路径选择的规则，虽然较全面的考虑了路径选择的一些特性，但仍然需要在实际应用过程中不断修正和改进。后续研究可以将该算法应用到物流仿真技术之中。

[1]赵建有.道路交通运输系统工程[M].北京:人民交通出版社,2004:199-201.

[2]王勇,池洁.物流配送路线及配送时间的优化分析[J].重庆交通大学学报(自然科学版),2008,27(4):647-650.

[3]邵春福.交通规划原理 [M].北京:中国铁道出版社,2004:174-183.

[4]何鹏,李文锋.基于随机Petri网的物流配送流程建模与分析[J].武汉理工大学学报·信息与管理工程版,2010,32(3):434-436.

[5]朱文兴,贾磊,丁绪东,等.城市交通网络中的路径优化研究[J].山东大学学报(工学版),2005,35(1):74-77.

[6]张梅青,周叶.Petri网理论在物流管理中的应用研究综述[J].物流技术,2010(7):13-16.

[7]杨世强,张海峰,李德信.基于Petri网的FMS物流系统建模与仿真[J].计算机工程与应用,2008,44(22):226-228.

[8]樊月珍,江发潮,毛恩荣.车辆行驶最优路径优化算法设计[J].计算机工程与设计,2007,28(23):5758-5761.

[9]石春玲,杜玉越.基于逻辑Petri网的物流配送系统建模[J].系统仿真学报,2007,19(1):114-117.