基于NSGA-II的渣土车调度系统的研究与设计

母洪铖，苟 刚，姚文钦，黄伶俐

(1.贵州大学 计算机科学与技术学院，贵阳 550025; 2.花溪区人民检察院,贵阳 550025)

0 引言

在实际生产中，一个渣土运输子任务的渣土车调度方案是渣土车数量与运输路径笛卡尔积关系，运输任务增加，调度方案呈指数级增长，在城市交通的限制下，渣土车由工地到消纳场的路径相对固定，对运输成本影响较大的是不同渣土车到不同工地的空车调度距离。渣土车的位置随时发生着变化，调度方案的规模庞大导致成本计算困难。元启发式算法[1-3]在解决全局寻优问题时，能基于问题的数学模型检索出近似最优解。经典的寻优算法有遗传算法[4]、模拟退火算法[5-6]、蚁群算法[7]等。在渣土行业，工地的位置并不固定，有新的托运需求，则产生新的工地，调度的初始状态就产生了改变。遗传算法对初始种群具有依赖性[8]的特点符合渣土运输的这一特性。

遗传算法模仿生物进化和遗传的特性，全局性地搜索解空间。其关键在于个体的编码(可行解的表示方法)；遗传过程中个体的选择、交叉、变异；以及对个体进行评价的适应度函数，最终适应度高的个体集合则是问题的较优解。遗传算法有多种编码方[9]，常见的有二进制编码[10]、实数编码[11]、矩阵编码[12]等，研究使用无需反复编码、解码的实数编码，并可直观地对问题特征进行描述，由于在工地中产生的渣土分较多种类，其运输价格不同，矩阵编码难以表示。遗传算法于1975年提出，1992年由Holland J H[13]发表正式版本，该算法根据实际需求，已被大量研究者和探索者根据实际需求进行了改进[14-17]，满足了不同的生产需求。非支配排序遗传算法(NSGA)[18-19]在解决多目标规划问题上，有着良好的表现，带精英策略的非支配排序算法(NSGA-II)[20-22]相较于前者有更低的计算复杂度，在遗传过程中保证了种群的多样性，同时精英策略的采用保证遗传过程中最佳个体不会丢失。而第三代非支配排序遗传算法(NSGA-III)[23]在解决高维优化问题(优化目标大于3个)时有着更好的优势。

近年来，我国的建筑业施工面积保持着增长的姿态，渣土运输业的发展缺乏信息化与智能化。工地产生的渣土，需要渣土运输车来完成渣土由工地到消纳场的转移，现阶段采用的方案是工地就近选择运输企业或车队为单一承运方，由承运方对其管辖范围内的渣土运输车辆进行调度，完成渣土托运。该方案的优点在于有流程简单、责任人单一，而其缺点在于调度时有很大概率出现以下情况：承运方的部分渣土车较非承运方的渣土车更远，调度成本更高。研究根据实际调度需求，总结出以下3个优化目标：最小化调度车辆数，保证司机每日收入，相同任务量，出车越少，每个司机所得收入越高；最大化完成任务量，在任务量超出平台总运力时，合理调度能完成更多的托运任务，加快建筑进度；最大化总体收益，工地支出固定，渣土车的成本降低，则有更好的效益，同时，低成本调度意味着渣土车在城市中更少地作无效行驶。基于NSGA-II的渣土车调度系统，借北斗终端[24]实现渣土运输的远程监督[25]，算法对调度方案进行了优化，对渣土运输业的信息化建设有着重要意义。

1 平台架构

1.1 总体架构

平台下渣土运输车辆加装北斗智能车载设备和传感器，将反馈得到的实时数据上传至管控平台，从而实现对车辆位置、速度、运输状态的实时监控，后台对工地、消纳场、司机进行综合管理。整体架构如图1所示。

图1 系统架构图

平台由5个层次和两个体系组成：

用户：总经理、管理人员对系统整体有管理权限; 调度员对系统计算出的调度方案进行最终决策; 车队长，对司机进行管理; 系统还包括司机、托运人等用户，他们分别有着不同的权限。

表现层：系统的功能部分由地图维护、车辆监管、车辆调度等组成。工地将需要完成的渣土运输任务发布在系统上，调度部分结合车的坐标位置计算出调度方案。

业务层：针对北斗传入数据的处理和清洗，通过北斗智能车载设备上传的行驶日志数据进行解析，用以查看车辆当前位置并加以利用。

数据层：包括司机、车辆、工地、消纳场、用户、业务等数据。

网络层：使用以太网提供网络服务。

两个体系：运行维护体系和法律法规与标准化体系。连个体系分别保证系统的正常运行和合法合规。

工地是对产生渣土并需要运输的地方的统称，其发布的托运请求信息应包含位置信息、完成时间要求以及运输方量、支付费用等。平台根据车辆位置、运输成本等数据，求解调度方案，最终得到若干个调度方案，不同方案的车辆数、收益以及完成工地任务数量均不相同，运力充足的情况工地发布的任务都能够在规定时间内完成，运力不足时，系统则对完成哪些工地任务进行自动取舍。调度员只需要考虑司机收益、调度整体收益以及完成任务数的优先级来确定最终调度方案，并将调度方案由系统一键转发到对应的渣土车司机手机。

系统根据实际需求完成对数据库的设计，存储用户数据、工地和消纳场定位数据以及运输路线等数据。后台服务使用ThinkPHP框架搭建，添加接收车辆定位数据的通讯扩展，开发数据解析模块将通讯报文中的有效信息存储到数据库中。引入高德地图，对工地、消纳场、渣土车等进行可视化展示，系统内置权限管理、日志查询等功能。

1.2 数据流程

平台上的数据分为两部分，一部分是用户录入，例如用户个人信息、工地托运任务; 另一部分为系统自动录入，这部分数据为渣土车的定位数据。经过处理的数据根据业务需求存入MySQL数据中，并自动备份。系统数据流程如图2所示。

图2 数据流图

2 系统实现

2.1 通讯框架

交通部门要求渣土车、旅游大客车等大型车辆，必须安装北斗导航系统的车载终端[26-27]。系统没有权限直接从终端获取定位数据，终端通过用户数据报协议(UDP,user datagram protocol)或传输控制协议(TCP,transmission control protocol)与车管平台进行信息通讯，当通讯链路系统异常，车载终端采用短消息服务(SMS,short message service)方式通讯。系统则是通过与车管平台建立socket通信获取车辆定位数据。系统通讯流程图如3所示。

图3 通讯流程

2.2 平台框架

渣土车调度系统的搭建基于PHP的开源框架THinkPHP3.2，该框架有较强的模块化概念，方便开发的有序进行。服务器使用的是开源的Apache，能对事务实现较好的处理。数据库是MySQL的5.3版本，有较好的稳定性。前端结合Bootstrap实现页面展示，该前端框架对个组件进行了封装，具有统一的设计风格，提高前端功能的开发效率。

2.3 功能实现

2.3.1 日常管理

日常管理模块中包含工地、消纳场、车辆等注册功能以及收入支出管理功能等日常业务，实现渣土运输的日常生产管理，其中运输路线管理功能记录不同车辆在各工地和消纳场之间的运输费用，为车辆调度成本预算提供数据支撑。各项管理数据在数据库中分表存储，通过控制器(Controller)查询并格式化为Json格式数据，前端通过接口对所需数据进行访问。

2.3.2 车辆管理

车辆管理模块包含车辆实时位置获取、各渣土车的托运记录管理以及历史轨迹复现三大功能。

北斗终端按照JT/T 808-2011《道路运输车辆卫星定位系统 终端通讯协议及数据格式》的规范，通过TCP或UDP实现与车联网位置信息通讯，系统与车联网采用双链路通讯方式，通过车联网所提供的对外接口，搭建socket服务，获得渣土车的定位数据包，服务器对数据包进行解析并存入数据库中，并将渣土车定位点通过地图API进行绘制。系统与车联网的通讯模块制定了重连策略，若长时间内未收到定位数据包，则根据最近丢失时间，主动向上级发出数据包请求，以保证定位的有效性。

渣土车托运记录管理是对调度任务完成情况的核验，系统对渣土车分别在工地、消纳场的停滞时间和工地到消纳场的行驶距离进行记录，并通过预设数据的正常和非正常值范围，对比实际记录数据，对此趟运输记录的“待处理”状态进行修改，不同值范围代表不同状态，状态“采用”表示该趟运输有效且以此计算司机薪酬，否则由记录员查看历史轨迹并对该条记录进行“采用”或“删除”操作。

系统通过渣土车ID和时间区间，后台查询时间段内对应渣土车的位置点信息，前端得到位置点的结果集在地图上进行绘制，并按时间的先后顺序进行连线，得到渣土车在地图上的行驶轨迹，管理员可通过轨迹查询直观地看到渣土车在各时间段的行驶情况。

2.3.3 调度模块

工地通过管理员在系统添加托运请求，系统将任务托运方量按规定方案换算为趟数，并将工地总支出以运输产值单价在列表中展示。系统记录了工地和消纳场的位置、渣土车可运行路线以及渣土车的调度成本等数据，调度时使用最近时间段渣土车的位置信息，通过遗传算法对调度方案进行计算，得到最终调度方案，在详情页展示，并由调度员确认发布调度讯息，调度实现如图4、图5所示。

图4 渣土调度方案选择与发布

图5 调度详情

3 车辆调度方案设计

3.1 问题定义

研究问题的具体描述如下：在渣土车集合N中选出部分渣土车，按照不同的顺序完成工地的任务集合T使得用车数最少、时间最短或者成本最小，这个渣土车的调度序列则是问题的解。系统当前已注册渣土车集合q={q1,q2,q3,...,qj}，j为平台注册渣土总数，工地集合M={M1,M2,M3,...,Mm}，m为平台注册工地总数，消纳场集合N={N1，N2，N3，...，Nn}，工地与消纳场之间的距离集合为D={D(1,1)，D(1,2)，...，D(m,n)}，由于渣土车运输路线相对单一的特殊性，该系统中将工地到消纳场之间的路径存储为确定值，且集合D的元素可为空(工地和消纳场不是一一对应，存在渣土车无法从某些工地到达某些消纳场)，其路径距离通过工地ID与消纳场ID成对查询，各工地运输任务的趟数集合T={T1，T2，...，Tm}。

3.2 编码

对问题的解决方案进行编码是遗传算法的重要初始步骤，也是问题解的表示方式，为了更直观地表示工地及任务量，同时也为避免二进制编码的汉明悬崖问题[9]，此处采用实数编码，种群的个体就是问题的解。每个解序列的长度为n×5+3，n为平台车辆数，5表示一辆车一天运输趟数不超过5次，3是评价函数的个数，分别对应3个优化目标。例如序列(5,0,3,5,0,3,0,3,0,0,f1,f2,f3)中有2个5，表示5号工地的渣土需要2次运输能够完成，3个3表示3号工地的渣土需要3次能够运输完成。在序列中截取长度为5的序列组(5,0,3,5,0)，第一次截取表示编号为1的渣土车当前的调度任务，序列含义为1号渣土车首先完成5号工地的一次托运，0表示没有调度任务安排，然后完成3号工地的一次托运，最后完成5号工地的一次托运，第二次截取的序列组则是2号渣土车的调度次序，每次截取长度为5的序列组，以此类推，序列后的f1，f2，f3表示3个优化目标的评价函数值，也称适应度函数值，分别代表该个体在不同优化目标上的适应度大小，通过前n×5个调度序列计算得到。

3.3 初始化种群

种群是遗传算法中个体的集合，这些个体在渣土车调度应用中表示的是调度方案，种群就是不同调度方案的集合，其数学表示是一个矩阵。在本系统中，种群的生成可分为以下几个步骤：

1)初始化足够长度且元素为‘0’的一维数组，其长度等于系统现有车辆数与每辆车每天最多可运趟数的乘积加3；

2)随机选择一个编号为a的工地，且该工地是第一次被选择，其任务量为n趟，判断一维数组中除保存适应度值的末尾3位，剩下的‘0’的个数是否大于n，若是，则随机修改末尾三位前的‘0’为a，否则，标记a工地为非第一次选择，选择下一个工地继续以上操作；

3)重复步骤2)，当一维数组中的元素全不为‘0’或工地全被标记为非第一次选择时，停止循环，得到一个个体的编码序列；

4)重复以上3个步骤，得到一个新的个体，即一个新的数组，将这个数组与前面得到的数组合并，得到一个列数不变，行数加一的矩阵。种群的大小就是以上4个步骤的重复次数，最终得到初始化矩阵，在该矩阵后面增加三列，每一列分别代表3个目标的适应度函数值。

3.4 适应度函数

适应度函数的作用是对个体的适应度进行计算，适应度是评价个体好与坏的重要指标，也是调度序列好与坏的直接表示。研究针对调度的3个优化目标：

1)最小化车辆数，通过编码序列可知车辆的调度情况，对某一编码序列进行长度为5的截取分片，得到若干定长编码序列和一个长度为3的序列，各长度为5的序列分别对应渣土车的调度情况，分片序列全为0，则对应渣土车没有被调度；若不全为0，则对车辆使用数统计时加1。由此可得到如下车辆使用数的表示

(1)

式中，di表示第i辆渣土车的调度序列，NULL表示调度序列全为0，即序列所对应车辆未被调度。

2)最大化任务完成数，任务数表示所有渣土车的托运总趟数，在编码序列中，除序列后三位，序列中不为0的则表示有一趟运输任务。遍历编码序列的前5n位，编码不为0时，则任务总数加1，托运总趟数的表示如下：

(2)

式中，ti表示编码序列中第i位的值，若为0则没有托运任务，相反托运总趟数加1。

3)最大化收益，工地发布托运任务时对渣土车运输一趟所支付的费用称为运输产值单价，承运方收入是固定的，当成本降低，承运方的收益则对应上升，同时为了方便后期实验结果与实际生产记录作对比，以收益最大化为优化目标。完成托运任务总收益为工地总产值与运输成本的差值，承运方的成本由空车行驶成本和载重行驶成本两部分组成，公式表示如下:

tij=t_cost(p_startij,p_endij)

mij=m_cost(p_endi(j-1)，p_startij)

(3)

式中，n为渣土车总数，4表示渣土车每日运输趟数上限5次，将调度序列用一个n×5的A矩阵表示，即payij为工地Mi到消纳场Nj的运输产值单价，t_cost(p_startij,p_endij)表示渣土车完成任务A(i,j)的载重成本，m_cost(p_end(i-1)j-p_startij)为空车调度成本，若该趟空车调度是当日第一次调度，则m_cost(p_endi(j-1)，p_startij)为渣土车定位到工地Mi的空车调度成本，否则为上一个调度消纳场到工地Mi的空车调度成本。

由式(1)～(3)3个目标函数可转化为以下3个适应度函数：

车辆数适应度函数：

(4)

托运趟数适应度函数：

(5)

收益适应度函数：

(6)

式(6)中，payi为第i个工地的运输产值单价。

3.5 选择、交叉与变异

计算出种群每个个体的适应度，可对比个体的优劣。研究的选择操作采用二锦标赛选择方法，即两两对比，选择适应度更好的个体，由于有一个个体有3个适应度值，当个体的适应度不能满足3个同时优于另一个个体时(非支配排序)，对比个体的聚集距离(个体在直角坐标系上的距离)，选择聚集距离更大的个体，即更加离散的个体。完成选择操作，得到初始种群一半个体数量的种群，将该种群继续做交叉和变异操作。

交叉操作在遗传算法中的作用是产生新的个体，为了保证调度序列的有效性，使用顺序交叉，步骤如下：

1)选择两个个体作为父代1和父代2，在父代1中随机选择一段连续基因，如图6所示。

图6 父代被选中的基因段

图7 子代与父代被选中基因段相同

3)在父代2中依次找出被选中的基因的位置，再将其与基因按顺序放入子代1中，如图8所示。

图8 新的子代的产生

经过以上3个步骤，得到子代1的调度序列为(9,6,9,5,7,0,2,7,5)，该交叉方法的两个父代会产生两个子代，子代2的产生与子代1的形成步骤相同。该方法生成的个体不需要做有效性检测。

遗传算法的选择和交叉操作均基于初始种群，而初始种群并未列出所有可行调度序列，变异操作在遗传算法中的作用是维持种群的多样性，扩大其索解范围，防止陷入局部最优解。变异方法采用两点互换，随机选中父代的两个基因，交换两个基因在序列中的位置得到变异后的子代。变异操作如图9所示。

图9 变异产生新的子代个体

3.6 个体选择策略

在进行二锦标赛选择时，留下的仅是两个个体之间更好的个体，若两个较优个体对比时，相对较差但在群体中较优的个体会被抛弃，这种选择方式得到的种群只是相对较好，而有可能去除了优质个体。研究采用了精英保留策略，该策略将将父代种群和子代种群合并，合并后的种群进行非支配排序[28]，产生若干个分类子集，根据等级由低到高选择出与初始种群大小相同的种群，若存在临界层分类子集，需要对该子集的个体进行拥挤度计算，为了保证群体的分布性和多样性，将聚集距离小的个体认为更优，优先选择，在临界层分类子集选择若干个个体，直到种群大小满足初始要求。选择流程如图10所示。

图10 算法流程图

4 实验结果与分析

4.1 实验步骤和方法

在数据库中通过SQL获取到调度需求、车辆历史定位以及调度成本等数据，并转换为“xls”表文件，在Matlab中完成算法的仿真实验，通过实验结果对调度方案设计的有效性进行验证。将Matlab中的算法代码移植到系统扩展功能上，完成算法在系统中的实际应用。

4.2 实验结果

以2020年6月中某一日为例，完成仿真实验得到的结果如图11所示。

图11 第一层非支配排序结果集

图11中，f1，f2，f3分别对应3个优化目标的适应度函数值，每个点的所对应的个体的编码序列，即为渣土车的调度方案。为更加明显地展示算法在实际系统应用的有效性，实验选择2020年6月整月的历史数据和计算结果进行统计，并以平均量作对比。对比结果如表1所示。

表1 2020年06月不同调度方案结果

表中用车最少和完成任务量最多两个调度方案均取得了较好的应用效果。当该月每天的调度以收益最大为目标时，完成任务量减少了，原因是该月有一天的调度方案是少完成一个工地的托运任务，总收益更多；该方案用车数没有得到有效减少，原因之一是平台所有渣土车的运力超过工地对运力的需求，车辆相对工地较为集中，若以收益最大为目标，系统会就近大量调度渣土车，降低返程托运的空车调度成本。

实验证明，该算法能够有效地完成渣土车调度方案的设计，并得到比以往人工调度更优的结果。系统对渣土运输业相关数据进行了有效管理，方便管理员对历史数据的复验，随着平台规模的扩大，其实用效果将更加明显。

5 结束语

研究对渣土运输车的调度过程进行了建模，结合NSGA-II算法，设计并实现了渣土车调度系统，以贵阳市111辆渣土车、95个工地、235个消纳场、461条路线等数据加以验证，结果表明，该调度系统能够在管理好渣土运输市场各方数据的同时，能够替代调度员对调度方案的设计工作，根据不同目标需求对渣土车进行调度。本系统存在的不足是，对时间约束的处理不是最优，司机虽能完成调度任务，但对于距离较近的托运任务，司机完成系统调度任务后仍有较多可工作时间。后期优化调度的时间约束，可提高系统的预算精准度，调度方案也更接近最优解。若扩大系统的用户量，在更多城市推广，可有效提高渣土运输业的效益。