基于Petri 网的驾校预约系统优化分析

张昊宇

（安徽理工大学 数学与大数据学院，安徽 淮南 232001）

1 引言

随着科技的发展，人们的出行服务对于汽车的需求量不断增加，驾校的用户数量也在不断上涨，据公安部统计，2019 年全国新注册登记机动车3214 万辆，2020 年全国新注册登记机动车3328 万辆。驾校预约系统作为自动化处理平台，可以帮助驾校管理人员规范学员数据，按照预约顺序排列练车名单，提高业务处理效率，也可以帮助学员更简易化地进行线上预约流程。但随着驾校学员数量的快速增长，传统的驾校预约业务流程已无法同时满足大量用户对练车的需求，因此对于业务流程的优化变得愈加重要。

Petri 网是1962 年由德国科学家Carl Adam Petri 在他的博士论文 “Kommunikation mit Automaten”中首先提出来的。它是分布式系统、业务流程的建模和分析工具，被广泛应用到各大领域。特别便于描述系统中进程或部件的顺序、并发、冲突以及同步等关系。同其他系统网模型相比较，对真并发的恰切描述是Petri 网的独特优势。作为一种系统模型，Petri 网不仅可以刻画系统的结构，而且可以描述系统的动态行为（如系统的状态变化等）。Petri 网作为一种最常见的流程建模工具，广泛应用于各种业务流程建模、分析和优化，面对复杂而交互的模型，Petri 网作为一种专业的图形化数学工具，体现了优秀的分析性和扩充性，Petri 网可以很好地处理模型间的行为关系以及正确性验证，以此分析模型间的交互行为[1]。

通过分析Petri 网中活动间的行为轮廓关系，并采用不同的配置信息可以实现对基于Petri 网的业务流程进行优化。Smirnov 等人使用行为轮廓对业务流程模型的描述和优化，使用了阈值对行为进行分析判别抽象模型间行为关系的方法，通过结合模型间的弱序关系，改变和增添模型间的行为轮廓关系，对原始模型进行优化，使优化模型的结构更加完善[2]。Aalst 等人使用配置信息对于业务模型进行正确性验证[3]，Sobociński 等人使用了分布函数对于配置信息的概念介绍[4]。Weidlich 等人提出了一种基于行为轮廓增加变迁的手段对模型进行搜索优化的方法[5]。向小阳等人使用了基于Petri 网的配置信息对智能快递柜系统中的投放和取件流程进行优化，用户通过选择收件方式来改变快递员的投递方式，提高购物体验[6]。

本文采用Petri 对驾校预约系统的业务流程进行建模，通过分析活动间的行为轮廓关系来检验该模型的合理性。该模型包括了从用户注册预约、驾校收到学员名单后开始安排练车、学员收到通知后考虑是否有时间练车、驾照考试等基本流程。通过分析该模型的动态行为，以发现该模型建模的业务流程中存在的不足，如用户等待时间长，用户和约车时间冲突等问题，并通过添加配置信息对原模型进行了优化，实现了驾校预约系统的业务效率的有效提高，很好地解决了当前驾校中普遍存在的问题。

2 基本概念

Petri 网是用于描述分布式系统的一种模型。它既能描述系统的结构，又能模拟系统的运行，描述系统结构的部分称为网，它可以通过对业务模型的优化和配置约束的添加来满足用户的使用需求[1]。

定义1（流程模型） 设∑(A,ai,a0,C,F,T)为一个六元组的流程模型[2]，其中：

（1）T 为一个非空的活动变迁节点集，C 为控制流的节点集，A 和C 互不相交；

（2）ai∈A 为一个最初的活动变迁，a0∈A 为一个最终的活动变迁；

（3）F⊆(A{a0})∪C×(A{a}∪C 为流关系；

（4）T：C→{ang,or,xor}为流程模型控制流的类型。

定义2（行为轮廓） 设一个网系统(N,M0)。其中N=(P,T,F)初始标识是M0；对于任意给定的变迁(t1,t2)∈(T×T)。满足如下关系:

若t1≻t2，且t2≻/t1，则称为严格序关系，记作t1→t2；

若t1≻/t2，且t2≻/t1，则称为排他序关系，记作t1+t2；

若t1≻t2，且t2≻t1，则称为交叉序关系，记作t1‖t2；

若t1≻/t2，且t2≻t1，则称为严格逆序关系，记作t1→－1t2。

将以上几种关系构成网N 的行为轮廓，记为BP={→，→－1，+，‖}[2]。

定义3（可达性） 已知Petri 网PN=(P,T;F,M),如果存在t∈T,使M[t＞M'，则称M' 为从M 直接可达的。如果存在变迁序列t1,t2,…，tk和标识序列M1,M2,…，Mk使得:则称Mk为从M 可达的，从M 可达的一切标识的集合记为R(N)[1]。

定义4（变迁发生规则） 一个四元组PN=(P,T;F,M0)称为Petri 网，并具有下面的变迁发生规则[1]：

（1）变迁t∈T 具有发生权，当且仅当对∀P∈'t:M(P)≥1，记作M[t＞；

（2）在标识M 下能使的变迁t 经发生后，得到一个新的标识M'，记作M[t＞M'，则有：

定义5（配置） 设N=（P，T，F）是一个工作流网，CN∈T→{allow,hide,block} 是网N 的一个配置。则定义:

定义6一个工作流网是合理的当且仅当[1]：

（1）对于任意的标识，都存在一个发生序列M，使得初始库所可以通过M 到达终止库所。

（2） 通过一个初始标识发生而发生的中间标识，如果此时的终止库所里至少有一个token，该状态就是终止状态。终止时，该工作流网终止库所中有且仅有一个标识，并且整个工作流程只有唯一的一个标识。

（3）无死锁，即该Petri 网是活的。

3 基于Petri 网的驾校预约系统初始模型

在目前的驾校练车系统中，虽然对于用户的练车需求由教练根据情况安排，但仍需要人工的审核和电话咨询，在预约过程中，为保证学员练车预约的公平性是非常必要的。但在实际生活中，常常有预约不上练车或预约刚开始名额就已满额，导致部分学员多次预约不上练车的情况。依据某驾校A的预约系统流程，建立Petri 网模型如图1 所示，各变迁对应的活动名称如表1 所示。

图1 驾校练车预约系统Petri 网图

表1 驾校练车预约系统Petri 网中所示变迁含义

驾校练车预约系统业务流程模型如图1 所示，用户在进入系统时选择登陆方式，未注册用户进行账号注册，已注册账号用户直接登录并进行信息验证，验证通过后进入系统，用户进入系统后进行缴费，预约后等待驾校安排练车，驾校在获取已预约的学员名单后，进行练车时间安排，由教练通知学员相应的练车时间，学员在收到练车安排的通知后，根据个人是否有时间进行练车来选择进入此轮练车或等待下一轮练车安排，在教练对学员进行练车评测后，练车合格的用户进入考试阶段，未合格用户进行下一轮练车预约，通过考试的用户成功毕业，未通过考试的用户进行下一次考试预约。

模型中的变迁相互影响，例如用户在登录界面选择登陆方式后，未注册用户t2和已注册用户t3互为排他序关系（记为：t2+t3）；若用户已经注册账号，则用户进行账号输入t5与系统进行信息验证t8按顺序依次发生，互为严格序关系（记为：t5→t8）；未注册用户进行注册后，系统验证注册信息合法性t6与系统内验证注册信息重复性t7互为交叉序关系（记为：t6‖t7）。

通过分析图1 所示的业务流程图，可以发现该系统中存在两个问题：（1）学员缺失自主选择机会，在系统流程中只能通过被动的接收驾校通知的时间来进行个人练车时间的安排，缺乏自主性。（2）在学员收到驾校练车通知后，学员将根据有无时间进行后续流程变迁的选择。若学员此次无时间练车，将重新排队预约下次练车时间。当系统中等待练车的用户数量较多时，将可能会导致部分无时间练车的用户在放弃此次练车机会后，出现下一次预约等待周期较长，或者再次收到不适合自己的练车时间通知等现象，从而使得平台预约效率低，学员产生较多的抱怨甚至长期预约不上合适的练车时间。所以目前的驾校预约系统不能动态根据用户和驾校时间自动安排双方都合适的练车时间。存在不足的业务流程子模块如图1 中的虚线所示。本文对此问题开展了研究，并对当前的驾校预约流程提出了较好的解决方案。

4 基于Petri 网的驾校预约系统优化过程模型

在图1 模型中，当用户高峰期时，排队预约的模型机制很容易使得部分用户始终处于等待阶段，为解决用户高峰期时约车难问题，使预约系统效率得到提高，本文通过增添变迁配置信息的概念，对部分变迁增加配置信息，通过对原有的变迁加入{hide，block，allow}其中的一个值，来对模型进行约束，改变原有的路径。其中配置信息hide（隐藏）变迁表示路径中触发此变迁时会默认进行跳过，且后续路径的变迁正常发生；block（阻塞）变迁表示默认处于阻塞封闭状态，如果没有其他路径可以选择，则该路径后续变迁也不发生；allow（允许）变迁指此变迁既不隐藏也不阻塞，不受约束条件影响。

针对图1 中虚线框部分所出现的第一个问题，在优化模型时，增加了用户自主选择预约时间的途径，不选择预约时间t13设定为hide 变迁，默认用户并不选择预约时间，变迁用户进行自选时间t14对于这些用户也是阻塞的，若用户选择了特定时间段进行预约练车，则进入变迁t14的后续路径，若用户预约的时间段，驾校练车名单有空余，则用户直接进行练车，若驾校该时段练车名单已满，则和默认不选择的用户一并进入等待阶段，通过此种途径对高峰练车时期的用户进行分流，降低练车预约难度。

针对预约练车名额时部分学员始终预约失败所导致的公平性问题，为部分变迁增添配置信息并在系统中为当次流程循环中没有预约上练车名额的用户增加预约优先级。设定t24变迁为block 变迁，此时默认驾校通知的学员有时间进行练车，对于有时间进行练车的用户而言，模型不会执行t24变迁以及后面的流程，若用户无练车时间，则会触发t24变迁，进行后续的流程。对于进入t24变迁后续路径的学员，驾校进行人数统计，安排教练对于此类学员进行预约等级的提升，在下一轮的预约练车名单流程中，这些学员具有更高的预约优先权。例如同一批练车学员进行练车预约，驾校在统计的此批次练车名单中，筛选其中上一轮练车中未有时间练车已提高预约优先级的学员，将此批次学员在此轮练车安排中优先对学员预约的时间进行考虑，若此时间段无空闲名额，则在驾校安排的顺序名单中，将此批次学员提前，以此来解决部分时间段内无空闲时间用户始终无法预约到练车机会的问题。优化后的模型如图2 所示，优化部分使用虚线框标识。新增变迁对应的活动如表2 所示。

图2 基于配置信息的优化模型

表2 基于配置信息的优化模型中新增变迁含义

5 仿真实验与分析

为了验证优化后模型的合理性，本文利用Petri 网分析软件——PIPE 对优化后的模型进行结构分析。PIPE 是一个支持Petri 网模型设计和分析的开源软件，在通过PIPE 软件对优化后的模型进行仿真运行后，测试结果如图3 所示，结果表明优化后的模型能够正确的按照预期的变迁路线进行运行，直到流程结束，具有良好的正确性，在图3 的结果分析中也表明优化后的模型具有良好的有界性和安全性，无死锁问题。

图3 PIPE 模拟运行结果

6 总结

本文基于Petri 网对实际驾校练车预约流程进行建模，通过对模型的动态分析，发现目前的驾校预约流程缺少用户自主选择性与预约公平性方向，通过增加配置变迁信息和子流程模块两种方案，对原有Petri 模型的行为关系进行了优化，有效地提高了预约系统的业务效率，增强了系统对于练车高峰时期的处理能力，能够有效解决用户约车困难的问题并增加了用户自主预约的方式。通过仿真模型表明了优化模型的可行性，是有界、安全并且无死锁的，但实际的实施阶段可能会与流程模型产生差异，今后将通过结合过程挖掘等方面的知识进行进一步的分析。