基于CPS架构的垃圾转运车辆的优化调度系统

周克良，周 桥，胡梁眉

（江西理工大学 电气工程与自动化学院，赣州 341000）

0 引言

CPS（Cyber-Physcial System：信息物理融合系统）是重要、较新的研究领域，是科技发展到一定阶段的产物，顺应信息技术发展趋势[1]。基本理念是通过人机交互接口使网络化空间以实时、可靠、安全的、远程的协作方式对物理世界进行感知和控制[2]，为人类提供智能化服务，最终目标是实现整个系统的完全融合，从而建立可靠、可信、可控安全的系统网络。

垃圾转运可简化为VRP（车辆路线）问题，最早由Dantzig和Ramser提出，经过研究发展，求解方法包括精确算法、启发式算法。垃圾转运涉及到垃圾收集点位置、垃圾量和车辆最大载重量、车辆最大行程等问题[3]。在垃圾转运过程中，需要对涉及到的数据进行收集分析判断。

垃圾转运是垃圾处理中重要的一环，在垃圾转运收集过程中，各个垃圾收集点的垃圾量动态变化[4]。将CPS结合在转运车的调度中，物理层的实体通过对环境的感知, 对相应的信息进行处理[5]，即对垃圾收集点位置、垃圾量和车辆最大载重量、车辆最大行程等数据进行收集分析，对收集到的数据进行简单处理，同时将信息通过网络发送到信息层，信息层组件在获取感知信息后，针对物理环境和网络中用户需求的改变，运用遗传算法自动调整内部关联与模型，然后得到最有效，最方便快捷的有效路径，从而在垃圾转运过程中减少资源的不必要的浪费。车辆在转运过程中，我们可以在系统中监测任务的进度，如果物理环境发生扰动，CPS系统也可以实时的收集数据，对已定的任务进行调节。

1 CPS分析

1.1 CPS运行方式

CPS是一种典型的分布式控制系统。CPS系统中包含海量的受限单元，例如嵌入式控制单元、微型传感单元等，由它们基本组成分布式控制网络[6]。CPS系统需要庞大的计算能力，分布式技术能够承担庞大的计算任务，也可以减少网络负载。

1.2 CPS的基本构架

CPS体系结构是CPS核心的技术，CPS结合计算和物理进程于一体，体现出一系列特定的系统特性。CPS基本架构如图1所示，CPS是物理技术和信息技术的一体化，包括物理层，网络层，协同优化层以及应用层[7]。

物理层指CPS中与现实环境紧密结合的感知测量设备、执行控制设备以及它们组成的具有特定功能或存在于特定区域的无线/有线网络单元；网络通信层负责将感知数据与控制要求的实时准确传递，为系统实时提供可靠服务；协同优化层负责对感知数据的分析与处理融合，其中，监控中心体现实时转运状态，决策控制中心包含一个由实际转运线路映射的仿真模型，体现理想转运状态，将两者对比，确定是否需要对原有转运方案进行调整，并将该决策信息反馈给实际转运设备；应用层支撑各类智能应用与资源和服务的协同优化。

图1 CPS基本架构

2 问题描述及数学建模

2.1 问题描述

在一区域，有一垃圾处理中心，区域分布垃圾收集点，每日采集垃圾量数据，交通状况实时采集并预测，车辆负责将垃圾转运至垃圾处理中心进行预处理，车辆当日最大可运载路程由该车辆油量所定，采集数据，将数据分类上传至CPS系统处理分析，得到将所有垃圾运转到垃圾处理中心的最快速较短的距离，也就是最经济的转运路径。

2.2 建立数学模型

在某一固定区域内有垃圾收集点N个，该区域内有M辆垃圾车负责转运，都在垃圾处理中心等待调度，将垃圾转运到中心进行处理。每辆车的最大载重量为C；每辆车最大行驶距离为lm（m=1，2，…，M）；假定第i个垃圾点产生的垃圾量为Gi吨（i=1，2，3，…，N）；各个垃圾收集点及处理中心任意两点之间行车距离为lij。

假设车辆从垃圾处理中心出发，将垃圾转运收集到处理站进行处理，第m辆收运次数为mf，里程为ml，第t运收路线为第mt条子路径，包含nmt个垃圾收集点，pmt代表第mt条路径中nmf个垃圾站点的集合，其中pmti（t=1，2，…，mt；i=1，2，…，nmt）代表第mt条子路径的第i个垃圾站点，该垃圾车在该站收集的垃圾量为Gpmti，pmtj表示子路径上最后一个垃圾收集站点，该垃圾收集点到垃圾压缩站的距离为lptj。

以垃圾收运成本最低为模型，即最短路径的模型，建立的模型如式(1)所示：

约束条件如式(2)所示：

如式(2)所示，在一条子路径中，车辆运载的垃圾不能超过最大运载量；一辆转运垃圾车转运距离不能超过最大行车距离；垃圾转运车要经过该区域内所有的有垃圾的垃圾收集点；垃圾转运车收集到的垃圾量；一辆车的运输次数不能超过设定值；子路径中的垃圾收集点不能超过总的垃圾点个数。

3 求解算法设计

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型[8]。

本节选用遗传算法思想，设计基于经济效益最高的垃圾转运路线，具体包括：编码与编码设计、种群初始化、适应度函数以及遗传操作[9]。遗传算法流程图如图2所示。

图2 遗传算法基本流程图

3.1 染色体的编码与解码

对于VRP的问题，遗传算法染色体编码采用自然数编码，用0代表垃圾处理中心，1,2，…，i，…，N-1，N代表N个垃圾收集站点。这种染色体结构可以通俗的理解为第一辆车送垃圾处理中心0出发，经过收集点1，2，…，n后回到处理中心0，形成子路径1；第二辆车也从处理中心出发，经过子路径1未访问的收集点如i，…，M后回到处理中心，形成子路径2，以此类推，直到所有的收集点全部被遍历，形成M条子路径，如0 8 10 12 11 0 4 6 7 9 0 5 2 1 0 3 0代表的转运路径为：

处理中心0→收集点8→收集点10→收集点12→收集点11→处理中心0；

处理中心0→收集点4→收集点6→收集点7→收集点9→处理中心0；

处理中心0→收集点5→收集点2→收集点1→处理中心0；

处理中心0→收集点3→处理中心0。

3.2 初始化种群

根据自然数染色体编码方法，对于有N个垃圾收集点，M辆车的问题，在对种群中染色体进行初始化时，随机的产生1到N之间的数来填充基因，保证它们不重复，随机插入M+1个0代表处理中心，如此反复，直到初始种群规模为L。

3.3 适应度函数

遗传算法中，个体适应度越大，表示个体的性能越好，因此需要将目标函数转化为适应度函数[10]，如式(3)所示。

3.4 遗传操作

本文遗传算法采用最佳保留的轮盘赌复制法进行染色体的复制，采用最优保留顺序交叉算子进行染色体的交叉，按照概率进行反转变异[11]。

4 实例分析

4.1 问题描述

赣州章贡区市区有12个垃圾收集点，一个垃圾处理中心和一个车场，暂时位于同一位置，垃圾收集点编号为1～12，处理中心为0。实地测得各收集点和处理中心的位置，通过称重技术获得该区域的垃圾收集点垃圾量，GIS（地理信息）系统标记获取经纬坐标后，简化坐标，垃圾点基本数据如表1所示，采用百度地图的开放平台API获取收集点之间当前时间段交通状况下最段路径如表2所示。市区垃圾收运车辆为中型货车，车辆平均行驶速度为40km/h ，最大载重量为6t。

4.2 基于遗传算法的问题求解

根据以上构建的数学模型，运用遗传算法求解，在MATLAB R2014b上编程得到仿真结果如图所示：

表1 垃圾收集点垃圾量、经纬坐标、简化坐标

表2 任务点之间的距离

续（表2）

如图3所示，总路径通过遗传算法迭代优化计算得到最短路径为49.3（km）。

图3 迭代过程

图4 车辆优化路径仿真图

如图4所示，★代表垃圾处理中心，其他收集点按坐标点标记，在MATLAB R2014b中编写程序画出任务分配路径图。

最优染色体编码为0 1 11 7 9 0 3 2 0 6 5 4 0 12 10 8 0，编码解码表示为车辆的任务分配如表3所示。

表3 车辆最优收运路线

5 结束语

本文将发展迅速的CPS架构运用于垃圾转运车的调度中，利用物理层采集的数据信息通过网络数据库和遗传算法的计算处理，根据垃圾转运外在和内在等主要元素，通过计算和优化使垃圾转运的物理世界与信息世界深度融合，使实时、安全、高效、可靠的智能转运环境能自主调节、自主运用和自主实现，验证了将CPS与垃圾转运是可行且可靠的，证明CPS系统在垃圾处理领域中具有发展前景，能有效提高垃圾转运的经济和时间效率。

[1]刘翔宇.电子信息技术发展现状及发展趋势[J].科技展望,2015,25(36):9-10.

[2]何明,梁文辉,陈国华,等.基于多视图的信息物理融合系统体系结构研究[J].计算机工程与应用,2013,49(12):25-32.

【】【】

[3]刘长玮.城市生活垃圾收运系统优化模型及其应用研究[D].重庆大学,2007.

[4]王勇.基于改进型蚁群算法的餐厨垃圾收运路线优化研究[D].重庆交通大学,2015.

[5]肖枫.大数据时代下CPS的制造系统调度优化[J].科学与信息化,2017,(4):36-38.

[6]韩杰,马斌,黄宽,等.基于蚁群算法的分布式CPS系统任务调度设计[J].测控技术,2015,34(2):121-124.

[7]张明丽.基于CPS架构的垃圾站点无线远程监控系统研究[D].江西理工大学,2015.

[8]金晓慧.基于流形距离和核函数的进化聚类算法研究及其应用[D].西安电子科技大学,2009.

[9]潘烨炀,郭洁,张林颖,等.基于自适应遗传算法的优化布站方法研究[J].国外电子测量技术,2013,32(6):62-64.

[10]郭海双,梁佳雯,张劭昀,等.MATLAB遗传算法工具箱GADS优化及应用[J].电子设计工程,2015,23(10):27-29,32.

[11]朱志勇,刁洪祥.基于改进遗传算法的车辆路径问题研究[J].湘潭大学自然科学学报,2011,33(3).

[12]符俊波,马慧民,张爽,等.有垃圾量变动的生活垃圾收运车辆调度干扰管理研究[J].上海理工大学学报,2017,39(4):368-375.

[13]Yun Wang;Dong Liu;Chen Sun , A Cyber Physical Model Based on a Hybrid System for Flexible Load Control in an Active Distribution Network[J]. Energies.2017(3):1-20.