约束条件遗传算法的餐厨废弃物收运路线研究

肖艳兵，芮小平

（1.山东正元地球物理信息技术有限公司，山东 济南 250000；2.山东明嘉勘察测绘有限公司，山东 淄博255000；3.中国科学院大学资源与环境学院，北京 100049）

约束条件遗传算法的餐厨废弃物收运路线研究

肖艳兵1,2，芮小平3

（1.山东正元地球物理信息技术有限公司，山东 济南 250000；2.山东明嘉勘察测绘有限公司，山东 淄博255000；3.中国科学院大学资源与环境学院，北京 100049）

以西宁市交通网络数据库为基础，结合GIS技术，分析西宁市餐厨废弃物的时空分布规律，并在此基础上，根据收运车辆、餐厨废弃物产生点以及产生量之间的关系，采用遗传算法研究最佳派送路线，并通过系统进行实现。

车辆路径问题；遗传算法；西宁市

传统餐厨废弃物的收运调控过程主要凭借主观经验确定，忽略了动态变化，从而造成收运过程运能配置不合理。根据动态变化的餐厨废弃物产生量以及废弃物的分布位置，结合空间数据库建立餐厨废弃物收运车辆和收运路线动态分配模型，保证用最少的餐厨收运车辆和最佳的收运路线进行收运，具有重要的现实意义。

车辆收运路线的分配属于车辆路径问题（Vehicle Route Problem, VRP）。现有对车辆路径问题的求解方法主要有精确优化算法和启发式算法。精确优化算法主要有分支定界法[1]、Dijkstra[2-3]、A*算法和线性规划算法等方法在内的线性规划方法和非线性规划方法来求最优解[4-5]。启发式算法主要有模拟退火算法[6]、禁忌搜索算法[7-8]、蚁群算法以及遗传算法等[9-14]。精确求解主要应用于路网规模较小的情况。当城市路网规模很大时，使用精确优化算法进行最优路径求解需要较长的运行时间。一般在为收运车辆分配收运路线时，并不需要绝对的最短路径，只要大致较短即可，因此可以使用启发式算法求解。

目前人们使用遗传算法研究的大都基于城市点或配送点，主要以点之间的坐标作为运算依据，并没有结合实际道路网络应用到具体某个区域中。本文以西宁市交通网络数据库为基础结合GIS技术，分析西宁市餐厨废弃物的时空分布规律，并在此基础上，根据收运车辆、餐厨废弃物产生点以及产生量之间的关系，采用遗传算法研究最佳派送路线。

1 问题描述

餐厨废弃物收运要求对有饭店存在的每条街，都至少通过一次，再集中到餐厨废弃物收购中心。每辆车装运的废弃物是有限的，而且废弃物的量又是随时变化的，如何用最少的车辆最大限度地收取所有废弃物是多目标调配算法要解决的主要问题。由于城市内路网规模相对较小，餐厨废弃物收运车辆相对灵活，对餐厨废弃物波动比较敏感。所以应更强调于满足以下原则：

1）严格遵循城市道路运输方案的有关法规政策。

2）尽可能用最少的车辆最大限度地收运餐厨废弃物。

3）尽可能提高收运效率，如在一定区域选取最优路径，每车每次重复路线最少，收运所有该地区的餐厨废弃物。

4）尽可能使空车行驶的总里程少，空车行驶的时间少等。

5）由于餐厨垃圾收运过程中产生异味，因此收运线路要尽量绕开居民区。

2 基于遗传算法的多目标路径规划

2.1 基本思路

根据西宁市餐厨废弃物产生的时空规律，可以根据青海洁神现有的收运车辆吨位确定分配收运车辆的最少数量，最少车辆可用如下方法判断计算：

首先判断最大吨位车辆能够装运的总量是否大于餐厨废弃物总量，如果大于餐厨废弃物总量，则车辆数为餐厨废弃物总量/最大吨位上取整。如果小于餐厨废弃物总量，则进一步判断第二吨位的车辆能够装运的总量是否大于餐厨废弃物总量-最大吨位装运总量，如果大于该数，则车辆数为最大吨位车辆数+（（餐厨废弃物总量-最大吨位装运总量）/第二吨位）上取整。如果小于则进一步根据上面的方法判断第三吨位需要的车俩。

动态收运路线设计的核心在于确定每条线路的收运路线，所有的收运车辆都是从收运中心出发，收运完后又回到收运中心，因此该问题属于典型车辆配送问题（VRP）。

2.2 遗传算法收运路线数学模型

首先对每个餐饮店进行编码，随机生成N个个体，生成初始化种群，然后根据适应度函数计算每个个体的适应度，通过选择算子选择适应度高的一个或者多个个体直接传入下一代种群中，再通过复制、交叉、变异对个体进行筛选，组成新的种群，反复循环计算，种群中的个体适应度会不断的提高，达到设置的条件时终止进化。多目标车辆路径问题进行求解时的约束条件有：

式中，i为收运点；m为满足条件时最大收运点；Q为车辆最大运量；D为车辆最大行驶距离；T为车辆最大行驶时间；L为收运点数量；nk为每辆车包含的收运点的数量；dm,0为满足条件时的站点到回收中心距离。

式（1）保证每条收运线路上的收运点的垃圾量之和不会超过此条路径上的配送车辆的最大载重量；式（2）保证每辆车辆在收运路线上的行驶距离不会超过该车辆的最大行驶距离；式（3）保证每辆车辆行驶的时间不会超过该车辆最大行驶时间，式（4）保证了每个收运点都能被车辆收运到。当Q(x)＞Q或D(x)＞D或T(x)＞T时，调用下一辆车辆进行路线计算。

2.3 遗传算法的参数及优化

遗传算法主要包括种群规模及种群初始化、选择算子、交叉算子和变异算子等几个参数。

2.3.1 种群规模

种群规模的大小将直接影响算法执行的效率和最终的优化结果。一般情况下，种群规模太小，不能提供足够的采样点，当计算结束时，可能得不到问题的可行解；当种群规模太大时，尽管可以防止早熟收敛现象的发生，但是计算量会非常大，影响算法的执行效率。

为方便起见，本文的染色体编码将使用餐馆的编号，每个餐馆有单独的编号，将所有餐馆编号采用随机组合的方式生成N个染色体组成初始种群。

2.3.2 选择算子

常见的选择算子包括最佳个体保存法、期望值方法、适应度比例法、联赛选择法、排序选择法、排挤方法等。本文使用的是最佳个体保存法，即通过选择适应度最高的个体进入下一代。适应度函数为：

使用最佳个体保存法，可以使适应度最高的个体直接进入到下一代中，而不必进行交叉复制，保证在进化的过程中保留该代的最优解，在个体交叉和变异的时候，不会被交叉和变异破坏该最优解。

2.3.3 交叉算子

常见的交叉算子包括一点交叉法、二点交叉法、多点交叉法、一致交叉法等。根据研究问题的特点，本文使用的是两点交叉法，即随机在父代染色体中生成两个交叉点，然后交换两个交叉点之间的部分染色体，生成两个新的个体。如A和B两条收运路线：

子代A从父代A中取交叉点前267，然后取父代B中两个交叉点之间的8 697基因插入父代A4 513之前，然后去掉重复基因得到2、6、7、8、9、4、5、1、3。

2.3.4 变异算子

常见的变异算子包括基本变异法、自适应变异法、逆转算子法等。本文使用的算子是基本变异法，即对个体随机挑选一个基因，通过变异概率Pm进行基因变动。方法如下[15]：随机产生一个1～n之间的数k，决定对回路中的第k个城市代码Wk作变异操作，又产生一个1～n之间的数w替代Wk，将Wk加到尾部，得到此串有n+1个数码，因为数w在串中重复了，必须删除与数w相重复的数以得到合法的染色体。

3 算法实例应用

通过餐厨废弃物的空间分布规律可知，居民较聚集、道路通达的地方以及老城区都是餐厨垃圾收运量较大的地区，因此本文选取西宁市市区262家餐馆作为研究对象，暂时不考虑偏远郊区；通过时间分布规律可知，平均每天的餐厨废弃物的产生量约为100 t，假设每家餐馆每天产出餐厨垃圾均0．381 7 t，初步配置20辆车辆进行收运，车辆载重及最大行驶距离如表1。其中序号表示收运车辆的车辆编号；载重代表每辆车最大载重；运距代表每辆车最大行驶距离。

表1 车辆参数表

本算法选定的全部参数如下：车辆数x=20（最大收运线路）；最大迭代次数T=30 000；交叉概率Pc=0.9；变异概率Pm=（1-Pc）*0.9=0.09，种群规模Scale=100。算法实现基于Visual Studio2010平台，采用C#编程语言结合ArcGIS Engine组件库以及MySQL数据库进行系统实现，经过程序运算得出最优路径如表2所示。其中，序号代表收运车辆的车辆编号；收运方案代表车辆收运的路线并显示出收运的餐馆的顺序；收运方案中的编号“0”代表车辆配送中心和车辆回收中心；本文中车辆配送中心和车辆回收中心是同一个单位，因此都用编号“0”表示，收运方案中的其他编号分别代表一个餐馆，载重和运距分别为车辆分配路线后车辆收运餐厨废弃物的实际收运量和实际行驶距离。

由程序运算结果可知，最优路径出现在25 023代，最优路线数为18条即使用前18辆车进行餐厨垃圾收运，所有车辆从派车中心出发，收运完餐厨垃圾返回回收中心，详细路线如图1所示。

图1 收运线路结果图

表2 最优收运方案

4 结 语

本文对于经典车辆路径问题采用标准遗传算法，并基于西宁市餐厨废弃物时空分布规律将遗传算法应用于实际的道路网络中，而不仅仅只是以点对点之间的坐标作为计算依据，并通过系统设计实现了路线分配。本文虽然将遗传算法应用到实际的道路网络中，但标准遗传算法本身具有容易早熟收敛，陷入局部最优解，因此还需要对标准遗传算法进行改进或者结合其他算法以解决这方面问题。

[1] 李诗珍,曹平方,李诗珍．基于分枝界定的VRP模型精确算法研究及应用[J]．包装工程,2014(17)： 97-101

[2] YANG MY,COILLIE F V,LUC H,et al． Nature Conservation Versus Scenic Quality：A GIS Approach Towards Optimized Tourist Tracks in a Protected Area of Northwest Yunnan,China[J]．Journal of Mountain Science, 2014(1)： 142-155

[3] 江成玉,杨林,刘勇．煤与瓦斯突出后最佳避灾路线的研究[J]．煤炭技术,2014(12)： 213-215

[4] 李志建,郑新奇,王淑晴,等．改进A*算法及其在GIS路径搜索中的应用[J]．系统仿真学报, 2009(10)： 3 116-3 119

[5] 赵真明,孟正大．基于加权A*算法的服务型机器人路径规划[J]．华中科技大学学报（自然科学版）, 2008(S1)： 196-198[6] 胡大伟,朱志强,胡勇．车辆路径问题的模拟退火算法[J]．中国公路学报,2006(4)：123-126

[7] 余丽,陆锋,杨林．交通网络旅行商路径优化的遗传禁忌搜索算法[J]．测绘学报,2014(11)：1 197-1 203

[8] 贺一,刘光远．禁忌搜索算法求解旅行商问题研究[J]．西南师范大学学报（自然科学版）, 2002(3)： 341-345

[9] 段海滨,马冠军,王道波,等．一种求解连续空间优化问题的改进蚁群算法[J]．系统仿真学报, 2007(5)： 974-977

[10] 段海滨,王道波,朱家强,等．蚁群算法理论及应用研究的进展[J]．控制与决策,2004(12)：1 321-1 326

[11] 张丽萍,柴跃廷．遗传算法的现状及发展动向[J]．信息与控制,2001(6)：531-536

[12] YANG S,TINÔS R．A Hybrid Immigrants Scheme for Genetic Algorithms in Dynamic Environments[J]． International Journal of Automation and Computing,2007(3)：243-254

[13] 李晓娟,沈斐敏．城市供水管网抗震加固优化研究[J]．中国安全科学学报,2014(12)：51-56

[14] 蔡菲,崔健,丁宁,等． 基于GIS和改进遗传算法的最优路径规划[J]．工程勘察, 2009(10)： 62-65

[15] 蔡自兴,徐光祐．人工智能及其应用[M]．清华大学出版社, 1996

P208

B文章编号：1672-4623（2017）06-0064-03

10.3969/j.issn.1672-4623.2017.06.019

肖艳兵，工程师，研究方向为地理信息系统开发与应用。

2016-03-25。

项目来源：国家科技支撑计划资助项目（2012BAC25B01）。