论文部分内容阅读
摘 要：建立了一种应急蔬菜配送问题的模型，考虑到在对该类问题规划线路时种群规模对遗传算法选择最优解的影响，将改进扫描法的思想融合到遗传算法中，形成一种新型的混合遗传算法。结合改进的扫描法后的遗传算法在种群选择上加以有效控制，减少了遗传算法陷入局部最优解的概率，同时提高了算法的时效性。
关键词：应急蔬菜配送；遗传算法；改进扫描法；混合遗传算法
中图分类号：F252.14 文献标识码：A
Abstract： Set up an emergency vegetable distribution model， considering the problems in planning line population size influence the selection of optimal solution of genetic algorithm， convergence will be improved scanning method to the genetic algorithm， a novel hybrid genetic algorithm. Combined with genetic algorithm improved after scanning method to effectively control the population selection， reduce the probability of the genetic algorithm into a local optimal solution， and improve the validity of the improved algorithm.
Key words： emergency vegetable distribution； genetic algorithm； improved scanning method； hybrid genetic algorithm
我国每年的蔬菜产量很高，并且呈逐年递增的趋势。同时也是一个蔬菜需求量巨大的国家，随着居民生活水平的提高，人们对蔬菜的要求已经从曾经的数量型转变为质量型。但在追求蔬菜质量的同时，物价的飞涨也增加了百姓的生活压力。为此，相关部门也加快步伐，通过采取各种措施来抑制蔬菜价格的上涨。以乌鲁木齐市为例，政府通过搭建社区蔬菜副食品直销店（简称：社区菜店）的方式来管控蔬菜的质量和价格，以此来解决老百姓买菜难、买菜贵的问题。
在对社区菜店规划配送路线时，一般会抽象成车辆路径问题来考虑。在解决车辆路径问题时，选用合理有效的算法是非常关键的。林国玺（2006）[1]采用混合智能算法来解决现实中的CVRPTW的问题，提出将模拟退火算法中的Metropolis接受准则引入到遗传算法的群体更新策略中，并将其应用于物流管理中的带容量约束和时间窗的车辆路径问题（CVRPTW）。郎茂才等（2009）[2]在配送车辆优化调度模型与算法中讨论了多车场多目标的配送问题。张静等（2013）[3]在对物流配送路径优化问题中使用遗传算法进行研究。
1 问题描述与算法设计
以乌市社区菜店为例，指定某家配送中心负责周边区域的65家社区菜店的蔬菜配送工作，该配送中心拥有载重量为2t的货车10辆，1t的货车4辆。每家社区菜店都有配送时间的要求，时间窗限制阀值最小为2小时，需要配送车辆进行非满载蔬菜配送运输。在某些情况（如：订单遗漏某些菜品、订单打印时出现错误、工作人员在清点菜品时出现失误、突发状况导致暂存蔬菜损坏无法出售等）发生的时候，为了维持每日居民对蔬菜的需求量，就需要实施应急蔬菜的配送工作。在这里提出应急配送指数f=■（α代表该种菜品的需求指数，c■代表该种菜品的单位利润，m代表该种菜品的需求量，s代表运输菜品所走的路程长度，c■代表单位运输成本，c■代表单位距离车辆磨损费）来判断是否需要实施配送服务，同时还要考虑配送中心是否有额外的车辆可以安排配送。对于n家菜店都需要应急配送的情况下，用s■=s/n来代替应急配送指数公式中的s；若s■>s则不必替换，实施点对点运输。
2 RSG-遗传算法设计
RSG-遗传算法是一种结合改进扫描法思想的混合遗传算法。算法的整体设计分为RSG（Radar Scan Grouping）扫描部分和遗传寻优两个部分。对于RSG扫描的设计，其基本思想是由中心点（配送中心）开始向任意方向划一条射线（扫描线），沿顺时针或逆时针的方向旋转该扫描线与任意货物需求点相交。如果需要在某分组里增加该需求点，则反馈该点，并累计货运量，计算是否会超过安排车辆的运载能力，若无则继续旋转扫描线，直到与下一个货物需求点相交；再次累计货运量，计算安排运输车辆的已装载程度。如果超过车辆的运输能力，便不考虑最后的货物需求点，或按照其他设定的终止条件，直到达到车辆最大运载能力为止，该分组确定。随后沿着扫描线的方向，从不包含在上一组的货物需求点开始，继续旋转扫描线以寻找新的货物需求点，继续该过程直到所有的货物需求点都被合理的划分成组。
RSG流程图如下图1所示：
对遗传寻优部分的设计采用RSG的结果来划定遗传种群。然后通过随机生成的方法产生初始种群、使用轮赌盘复制法保留染色体并进行复制和最优保留顺序交叉算子进行染色体交叉的基础上，采用反转变异算子进行变异操作，加速有效收敛，然后根据终止条件——染色体连续最佳保持到β代得到问题的最优解。
步骤如下：
（1）初始数据输入。根据改进扫描法的分组结果，将初始数据例如起点坐标、终点坐标、配送车辆载重量、社区菜店坐标、各家菜店的需求量、需求时间和遗传控制参数输入程序中；
（2）初始化运输距离数组，并初始化染色体；
（3）进行选择、交叉、变异操作；
（4）根据终止条件判断是否停止计算，如满足条件，停止计算，输出最优解，否则转（3）。
3 优化结果分析
在表2中，采用RSG-遗传算法得到了优化后的配送线路。A代表配送中心，数字编号表示各家菜店。根据车辆需要行驶的路线长度和平均行驶速度（50km/h），可知每组运输车辆都可以在1.5h内完成蔬菜的配送工作，并返回配送中心，满足时间窗的最小阀值。同时，优化算法中使用的载重量为2t的汽车10辆，1t的汽车2辆，没有超出配送中心的实际配送能力。因此，程序运行的实验结果合理有效。
从图2可以看出，采用RSG-遗传算法在收敛速度上有显著的提升，在较短时间内收敛到最优值，减少了遗传算法的计算时间。
4 结 论
通过实例验证RSG-遗传算法可以有效地控制种群规模，提取出优质的遗传种群，有效降低了发生局部最优解的概率，相比传统的遗传算法更加高效。虽然应急配送出现的概率很小，但是从理论研究的角度把它提出来，期望对其他相关问题的研究有一定的参考价值。
参考文献：
[1] 林国玺，宣慧玉. 混合智能算法在CVRPTW中的应用[J]. 工业工程，2006（1）：107-111.
[2] 郎茂祥. 基于遗传算法的物流配送路径优化问题研究[J]. 中国公路学报，2002（3）：76-79.
[3] 张静，卫文学，刘倩. 基于遗传算法的物流配送路径优化算法[J]. 中国科技信息，2013（1）：98-99.
关键词：应急蔬菜配送；遗传算法；改进扫描法；混合遗传算法
中图分类号：F252.14 文献标识码：A
Abstract： Set up an emergency vegetable distribution model， considering the problems in planning line population size influence the selection of optimal solution of genetic algorithm， convergence will be improved scanning method to the genetic algorithm， a novel hybrid genetic algorithm. Combined with genetic algorithm improved after scanning method to effectively control the population selection， reduce the probability of the genetic algorithm into a local optimal solution， and improve the validity of the improved algorithm.
Key words： emergency vegetable distribution； genetic algorithm； improved scanning method； hybrid genetic algorithm
我国每年的蔬菜产量很高，并且呈逐年递增的趋势。同时也是一个蔬菜需求量巨大的国家，随着居民生活水平的提高，人们对蔬菜的要求已经从曾经的数量型转变为质量型。但在追求蔬菜质量的同时，物价的飞涨也增加了百姓的生活压力。为此，相关部门也加快步伐，通过采取各种措施来抑制蔬菜价格的上涨。以乌鲁木齐市为例，政府通过搭建社区蔬菜副食品直销店（简称：社区菜店）的方式来管控蔬菜的质量和价格，以此来解决老百姓买菜难、买菜贵的问题。
在对社区菜店规划配送路线时，一般会抽象成车辆路径问题来考虑。在解决车辆路径问题时，选用合理有效的算法是非常关键的。林国玺（2006）[1]采用混合智能算法来解决现实中的CVRPTW的问题，提出将模拟退火算法中的Metropolis接受准则引入到遗传算法的群体更新策略中，并将其应用于物流管理中的带容量约束和时间窗的车辆路径问题（CVRPTW）。郎茂才等（2009）[2]在配送车辆优化调度模型与算法中讨论了多车场多目标的配送问题。张静等（2013）[3]在对物流配送路径优化问题中使用遗传算法进行研究。
1 问题描述与算法设计
以乌市社区菜店为例，指定某家配送中心负责周边区域的65家社区菜店的蔬菜配送工作，该配送中心拥有载重量为2t的货车10辆，1t的货车4辆。每家社区菜店都有配送时间的要求，时间窗限制阀值最小为2小时，需要配送车辆进行非满载蔬菜配送运输。在某些情况（如：订单遗漏某些菜品、订单打印时出现错误、工作人员在清点菜品时出现失误、突发状况导致暂存蔬菜损坏无法出售等）发生的时候，为了维持每日居民对蔬菜的需求量，就需要实施应急蔬菜的配送工作。在这里提出应急配送指数f=■（α代表该种菜品的需求指数，c■代表该种菜品的单位利润，m代表该种菜品的需求量，s代表运输菜品所走的路程长度，c■代表单位运输成本，c■代表单位距离车辆磨损费）来判断是否需要实施配送服务，同时还要考虑配送中心是否有额外的车辆可以安排配送。对于n家菜店都需要应急配送的情况下，用s■=s/n来代替应急配送指数公式中的s；若s■>s则不必替换，实施点对点运输。
2 RSG-遗传算法设计
RSG-遗传算法是一种结合改进扫描法思想的混合遗传算法。算法的整体设计分为RSG（Radar Scan Grouping）扫描部分和遗传寻优两个部分。对于RSG扫描的设计，其基本思想是由中心点（配送中心）开始向任意方向划一条射线（扫描线），沿顺时针或逆时针的方向旋转该扫描线与任意货物需求点相交。如果需要在某分组里增加该需求点，则反馈该点，并累计货运量，计算是否会超过安排车辆的运载能力，若无则继续旋转扫描线，直到与下一个货物需求点相交；再次累计货运量，计算安排运输车辆的已装载程度。如果超过车辆的运输能力，便不考虑最后的货物需求点，或按照其他设定的终止条件，直到达到车辆最大运载能力为止，该分组确定。随后沿着扫描线的方向，从不包含在上一组的货物需求点开始，继续旋转扫描线以寻找新的货物需求点，继续该过程直到所有的货物需求点都被合理的划分成组。
RSG流程图如下图1所示：
对遗传寻优部分的设计采用RSG的结果来划定遗传种群。然后通过随机生成的方法产生初始种群、使用轮赌盘复制法保留染色体并进行复制和最优保留顺序交叉算子进行染色体交叉的基础上，采用反转变异算子进行变异操作，加速有效收敛，然后根据终止条件——染色体连续最佳保持到β代得到问题的最优解。
步骤如下：
（1）初始数据输入。根据改进扫描法的分组结果，将初始数据例如起点坐标、终点坐标、配送车辆载重量、社区菜店坐标、各家菜店的需求量、需求时间和遗传控制参数输入程序中；
（2）初始化运输距离数组，并初始化染色体；
（3）进行选择、交叉、变异操作；
（4）根据终止条件判断是否停止计算，如满足条件，停止计算，输出最优解，否则转（3）。
3 优化结果分析
在表2中，采用RSG-遗传算法得到了优化后的配送线路。A代表配送中心，数字编号表示各家菜店。根据车辆需要行驶的路线长度和平均行驶速度（50km/h），可知每组运输车辆都可以在1.5h内完成蔬菜的配送工作，并返回配送中心，满足时间窗的最小阀值。同时，优化算法中使用的载重量为2t的汽车10辆，1t的汽车2辆，没有超出配送中心的实际配送能力。因此，程序运行的实验结果合理有效。
从图2可以看出，采用RSG-遗传算法在收敛速度上有显著的提升，在较短时间内收敛到最优值，减少了遗传算法的计算时间。
4 结 论
通过实例验证RSG-遗传算法可以有效地控制种群规模，提取出优质的遗传种群，有效降低了发生局部最优解的概率，相比传统的遗传算法更加高效。虽然应急配送出现的概率很小，但是从理论研究的角度把它提出来，期望对其他相关问题的研究有一定的参考价值。
参考文献：
[1] 林国玺，宣慧玉. 混合智能算法在CVRPTW中的应用[J]. 工业工程，2006（1）：107-111.
[2] 郎茂祥. 基于遗传算法的物流配送路径优化问题研究[J]. 中国公路学报，2002（3）：76-79.
[3] 张静，卫文学，刘倩. 基于遗传算法的物流配送路径优化算法[J]. 中国科技信息，2013（1）：98-99.