基于数字孪生的物流配送调度优化

2021-08-20曾艾婧刘永姜陈跃鹏孟小玲温海骏

科学技术与工程 2021年21期

曾艾婧，刘永姜，陈跃鹏，孟小玲，温海骏

(中北大学机械工程学院，太原 030051)

在人工智能、物联网等技术的推动下，产业转型成为工业发展浪潮中生存的趋势，物流行业也已从传统物流发展为智能物流[1-2]。物流配送服务作为物流行业中的基本业务是物流企业面向客户服务的最后一环，具有十分重要的地位[3]。而物流配送成本占据整个物流系统的很大比重，其中物流配送中车辆调度和路径优化将直接影响到物流配送成本的高低。

针对车辆配送调度问题，大多学者主要是对算法的优化进行研究，孙秀巧等[4]探讨了有限巡逻车资源路径、调度优化建模问题，并在改进遗传退火算法的基础上加入动态规划算法对巡逻车进行分配；王泽等[5]考虑电量消耗的车辆调度模型，并将遗传算法与枚举法相结合计算出配送车辆惩罚成本最小时的最优发车时刻。近年来，为了更高效地解决该问题，部分学者将先进信息技术与调度系统融合以得到更加智能有效的解决方案，张雨[6]将多Agent系统与分布式蚁群算法相结合，研究了基于分布式多Agent下的港口作业调度优化方法；周克良等[7]阐述了在信息物理系统(cyber physical systems，CPS)架构下构建一个垃圾转运系统，并将遗传算法作为系统内的算法内核，通过实例分析证明CPS系统架构下的垃圾预转系统的有效性；朱涛等[8]基于大数据驱动提出了智能化公交实时调度和管理技术。

配送过程中各种不确定因素，导致其复杂化不断增加，以至于产生额外的配送成本，为此来越多的学者开始关心如何实现配送过程透明化，相继提出了基于物联网、产业互联等技术的智能物流配送模式[9]，而数字孪生(digital twins，DT)[10]这一概念的提出为物流配送提供了一种全新的解决思路。近年来，数字孪生作为一种新兴的智能技术在制造领域得到了广泛的应用，中外学者分别提出了基于数字孪生的数控机床虚拟交互系统[11]、面向工厂规划的数字孪生技术[12]、基于数字孪生的产品生命周期预测方法[13]、总装配生产线数字孪生技术[14]、数字孪生建筑信息模型[15]、基于数字孪生的航班保障预警系统[16]等，实现了网络物理的融合。

基于此，现引入数字孪生技术来对配送过程进行高效管理，将配送过程由“黑箱”模式转换为配送过程中配送车辆状态、人员状态、道路状态等的实时状态透明化，以实现物资的精准配送。

1 数字孪生驱动下的物流配送调度系统构建

1.1 基于数字孪生的物流配送调度系统模型

为使数字孪生进一步在具体物流配送研究中得到应用，根据文献[17]中的五维DT和建模方法，提出了一个结合具体物流配送过程的数字孪生应用模型，其主要包括物理配送作业面、虚拟配送作业面、物流配送系统服务、物流配送孪生数据和系统连接，如图1所示。

图1 物流配送DT五维模型

同时，物流配送的DT模型可以表示为

DT=(PE、VE、SS、TD、SC)

上述表达式解释如下。

物理配送作业面(physical entity, PE)是在实际物流配送过程中，物流配送中心根据客户需求，在给定的约束条件下，通过对车辆进行合理调配完成指定的配送任务。

虚拟配送作业面(virtual entity, VE)是物理配送作业面在虚拟空间的数字化“镜像”，利用智能软件对真实的物流配送工程进行仿真。

物流配送系统服务(system service, SS)本质上是集成了追踪、评估、优化和控制等算法的数学模型，其根据车载终端提供的真实数据在虚拟空间中进行数据分析，构建以配送总成本最低为优化目标的数学模型，进而依靠数字孪生系统的算法内核实现迭代优化。

物流配送孪生数据(twin data, TD)是将配送过程的真实数据、虚拟配送的模拟数据和服务数据进行融合，并随着实时配送状态的变化而不断更新与优化。在物流配送过程中，TD的一个作用是为VE提供采集到的实时追踪数据，使VE可以精确地对真实物流配送进行仿真模拟；其次是为PE反馈虚拟配送预测数据，从而可以对实际中的物流配送调度进行动态调整。

系统连接(system connection, SC)的作用是将以上4个部分连接成一个整体，使得物流配送数字孪生系统能够进行实时而且有效的数据传递，从而达到真实配送过程与虚拟仿真的交互与协同。

1.2 基于数字孪生的物流配送调度整体框架

数字孪生旨在将物理实体及过程进行数字化表现，通过孪生数据驱动显示物理信息的融合，借助仿真软件模拟物理实体在现实情况下的运作流程，因此提出了物流配送调度系统数字孪生框架，其主要包括物理层、服务层、虚拟层三部分，如图2所示。

图2 物流配送调度系统数字孪生框架

(1)物理层。物理层需要物理实体即配送车辆具备决策和通信能力，并可以采集物流配送设备的位置信息、车辆状况、驾驶行为以及路况等部分的实时信息数据。具体主要是利用GPS系统实时采集车辆位置信息与运输轨迹、利用货运车辆基于SAEJ1939/CAN总线协议的OBDII接口对车辆运行状态进行数据采集，以实现对故障车辆的及时维修，并通过5G技术将配送过程实时相关数据上传至服务层。

(2)服务层。服务层的主要任务是为基于数字孪生的物流配送调度系统提供数据支撑服务，基于对物理层提供的实时参数信息数据与孪生层输出的决策数据的融合和分析，实现物理层与孪生层的交互反馈，从而为整个系统提供智能执行、精确控制和可靠运维等服务。

(3)虚拟层。虚拟层是整个数字孪生驱动的物流配送调度系统框架中最为关键的一层，其是以底层物理层采集的实时数据为基础依靠内核算法进行实时动态调整迭代优化，实现车辆的重调度和路径的优化，最后将最优方案通过5G无线网络输出至车载终端，为实时调度提供决策支撑。

2 问题描述与数学建模

2.1 问题描述

所研究的物流配送调度问题是建立在已知客户点的空间位置和需求量，配送中心的位置以及车辆最大载重量条件下，单个配送中心的基础上，通过采集m辆车对一定区域内的n个客户配送同质货物的实时配送数据，以数字孪生技术为依托模拟配送过程，并将迭代优化得到的最优配送方案反馈至物理模型，以使综合成本最低。另外，该数字孪生模型考虑了配送过程中故障车辆的维修处理问题。并在数学模型中引入了软时间窗，对物资有可能会无法按时被送达的情况进行一定的惩罚。

针对所研究的问题，做出以下假设：

(1)每辆车仅配送于一条路径，且都从配送中心出发，最后返回配送中心。

(2)每个客户都必须被服务并有且只被访问一次。

(3)每辆车所配送的客户需求总量不能超过车辆的载重量。

(4)每辆车服务其路径上的每个客户时，应在客户规定的时间窗内到达配送地点，或早或晚都将面临惩罚。

(5)配送中心货源充足，配送货物为单一品种。

(6)车辆在行驶途中保持匀速行驶，且不考虑道路交通拥挤等状况。

(7)客户的开始服务时间即为车辆到达的时间，且每个客户的服务时间相同。

2.2 数学模型

综合考虑运输成本、车辆使用成本和惩罚成本，具体说明如下。

(1)运输费用。运输成本是指货物运输过程中消耗的燃料消耗成本，运输成本与运输距离成正比，即

(1)

(2)车辆使用成本。

(2)

式(2)中：C2为总车辆使用成本；fk为第k辆车的固定成本。

(3)惩罚成本。将添加一个软时间窗口，这意味着要求车辆尽可能在指定的时间窗口内到达，或早或晚到达都会产生惩罚成本，即

(3)

根据以上分析，建立数学模型为

minC=min(C1+C2+C3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

EETi≤Aik≤ELTi

(11)

(12)

(13)

(14)

式中：Q为配送车辆的最大载重。式(5)表示车辆从配送中心出发进行配送，完成后将返回配送中心；式(6)～式(8)表示每个客户有且只能被一辆车服务一次；式(9)表示每辆车所承载的货物总量不应超过车辆的载重量Q；式(10)表示车辆到达配送点的时间与客户的开始接受服务时间相同；式(11)表示车辆的到达时间必须在客户i规定的服务时间窗内；式(12)是二值变量，值取1时表示车辆k由客户i行驶到客户j；式(13)是二值变量，值取1时表示车辆k对客户i服务；式(14)是二值变量，取值1时表示车辆k完成了客户i的服务。

2.3 算法内核分析

数字孪生驱动下的物流配送调度系统等同于在原有的物流配送调度系统基础上添加了一个虚拟层面的物流配送调度系统，算法内核在物理和虚拟空间之间根据实时反馈的物理信息以及孪生数据对车辆配送安排进行实时动态调整，从而使整个物流配送过程不断地迭代优化。将遗传算法作为内核对物流配送调度问题进行求解，算法的主要流程如图3所示。

图3 遗传算法主要流程

(1)编码。采用实数编码的方式，该方法比较简单，易于表示单配送中心问题的解利用自然数对客户进行编码，将客户点作为基因，编码如图4所示，其中0表示物流配送中心。

图4 实数编码

(2)解码。对上述实数编码进行解码，即表示配送中心安排一辆车先满足客户4的物资需求，再服务客户9，当车辆达到最大载重量时，配送中心将安排别的车辆，对未配送客户进行服务，以此类推，直到满足每个客户的需求。

(3)适应度函数。针对物流配送调度问题，将综合配送成本作为染色体的适应度值，其函数为

Fitness(i)=C

(15)

(4)个体选择。将精英保留策略与轮盘赌法结合对个体进行选择，先利用轮盘赌法，即根据染色体的适应度值进行选择，每个个体被选择的概率为

(16)

(5)交叉。采用部分映射法进行交叉，即先对父代进行常规的两点交叉,再根据交叉区域内各基因值之间的映射关系来修改交叉区域之外的各个基因组的基因值[18]。

(6)变异。根据编码特点，选用两点互换的方式产生变异算子，并在互换后，通过重新判断该个体是否满足约束条件确定互换后的个体是否可行。

2 实验与验证

以某配送中心为例，通过实地调研和数据咨询，收集整理相关信息数据，将该配送中心配送区域内的25个客户作为研究对象，建立基于数字孪生的物流配送调度系统。表1列出了部分配送中心和客户之间的相对距离，配送中心及部分客户坐标点、部分配送点的需求量、早晚时间窗等信息(表2)以及物流配送模型相关参数设定(表3)。

表1 配送中心及客户之间相对距离

表2 客户坐标点、需求量、时间窗和服务时间

表3 物流配送模型相关参数设定

基于数字孪生技术的优化仿真方法为保证更加精准模拟实际配送过程，在传统的物流配送调度模型中加入两个车辆维修站，用以解决运输途中车辆故障等问题，维修站的位置坐标如表4所示。

表4 维修站坐标

根据以上案例，并结合采集的实时相关数据，运用Plant Simulation仿真软件建立的物流配送调度数字孪生体模型如图5所示。遗传算法参数设置如下：染色体长度即客户数目：25，种群中的群体规模：40，最大迭代次数：1 500，交叉率：0.99，变异率：0.1，精英保留策略概率：0.1。

图5 物流配送调度数字孪生体模型

基于数字孪生技术对配送过程进行模拟仿真，并得出满足总成本约束的最优物流配送路径如图6所示，优化迭代过程如图7所示，其配送方案如下：动用4辆车进行配送，最佳运输路径为第1辆车：0-18-8-7-19-11-10-22-0；第2辆车：0-21-2-15-27-23-4-25-24-0；第3辆车：0-6-26-17-16-14-13-0；第4辆车：0-5-12-3-9-20-0，其中第2辆车在服务完客户15后出现故障，在维修站27进行维修后继续完成配送任务，同样第3辆车在完成客户6的配送后出现工作，在维修站26进行维修，并在维修后完成配送任务，配送总成本为30 458元，迭代次数为319。

图6 最优配送路径

图7 优化迭代图

传统物流配送优化仿真方法下得到的满足总成本约束的物流配送路径与优化迭代过程如图8、图9所示，其物流配送方案如下：动用4辆车进行配送，最佳运输路径为第1辆车：0-12-24-3-9-20-10-1-0；第2辆车：0-13-14-16-17-8-6-0；第3辆车：0-2-15-23-25-4-21-5-0；第4辆车：0-22-11-19-7-18-0，配送中成本为33 480元，迭代次数为595。

图8 传统物流配送最优路径

图9 传统物流配送优化迭代图

从实验结果可以看出，针对客户规模为25的配送问题，基于数字孪生优化仿真方法得到的物流配送总成本比在传统优化仿真方法下的物流配送总成本降低了9.92%。将基于数字孪生技术优化方法模拟得到的最优配送方案通过5G无线技术传输至物理层，司机通过车载系统接收到实时反馈信息就可以对配送路线与方案进行合理的调整，实现配送过程的透明化。