蚁群优化算法在图书配送路径规划中的应用研究

宇婷

摘  要： 针对图书物流配送中的多目标优化问题，提出一种基于蚁群优化算法的图书配送路径规划模型，使配送成本最小化。首先对图书物流配送路径规划模型进行分析，并选择作业成本法对成本目标进行优化;然后采用单亲遗传混合蚁群算法对建立的模型进行求解，解决全局优化问题和求解效率问题。以某图书配送中心为例进行优化仿真测试，验证了模型的有效性。相比传统的人工方案，采用的图书物流配送路径规划模型及单亲遗传混合蚁群算法的配送方案有效降低了物流配送作业的成本。

关键词： 图书配送; 路径规划; 蚁群算法; 遗传算法; 模型求解; 成本降低

中图分类号： TN98?34; TP393                    文献标识码： A                      文章编号： 1004?373X（2019）15?0113?03

Application of ant colony optimization algorithm in book distribution path planning

YU Ting

（Zhengzhou University of Industry Technology， Zhengzhou 450000， China）

Abstract： Aiming at the problem of multi?objective optimization in book logistics distribution， a book distribution path planning model based on ant colony optimization algorithm is proposed to minimize the distribution cost. The book logistics distribution route planning model is analyzed， and the activity cost method is selected to optimize the cost target. The single?parent genetic hybrid ant colony optimization algorithm is used to solve the established model， which can solve the global optimization problem and solution efficiency. The optimization simulation test was carried out by taking a book distribution center as the example to verify the validity of the model. In comparison with the traditional manual scheme， the distribution scheme of book logistics distribution path planning model and single?parent genetic hybrid ant colony optimization algorithm can reduce the logistics distribution cost effectively.

Keywords： book distribution; path planning; ant colony algorithm; genetic algorithm; model solution; cost reduction

0  引  言

随着经济的快速发展，我国的GDP已经连续保持高速增长，人们的生活在物质方面得到了长足的进步， 生活富足。与此同时，人们的娱乐和文化需求日益增长。图书作为一种传统的知识载体，在人类历史上扮演着十分重要的作用，是人类智慧的结晶。图书能够在很大程度上满足人们精神文化需求，提高知识水平，提升文明素养，因此，近几年来图书出版与发行业能够维持稳定的增长趋势[1]。但是，随着用户需求和图书数量的不断增多，图书物流配送问题成为近期研究的热点[2?3]。

如何在保障配送效率和准确率的前提下，尽可能地降低图书配送的作业成本是图书物流管理系统的关键。随着计算机、应用数学和网络交通等学科的交叉研究，作为NP问题的车辆路径是解决图书物流管理系统关键的有效手段[4]。近期，启发式算法求解车辆路径问题成为研究的新途径。文献[5]采用蚁群算法对周期性车辆路径问题进行求解，并提出采用两种改进措施（多维信息素的运用和基于扫描法的局部优化方法）来提高算法的性能，表现出显著的性能提升。算法测试结果验证了提出方法的可行性。相比传统的遗传算法，提出的蚁群优化遗传算法表现出较好的性能。针对最小最大车辆路径求解问题，文献[6]提出一种动态自适应蚁群优化算法。该算法采用动态最大最小蚂蚁系统策略调整最优解，每次迭代更新将作为当前信息素矩阵最大值的函数，并通过灰色模型预测和信息素矩阵的边界控制来增强蚁群算法参数的自适应性能。

与其他相关的蚁群算法相比，单亲遗传混合蚁群算法收敛速度更快，具有更好的优化性能和应用效果。因此，本文提出一種基于蚁群优化算法的图书配送路径规划模型，使配送成本最小化。仿真测试结果验证了提出方法的可行性。实验结果表明，基于单亲遗传混合蚁群算法的图书物流配送路径规划模型表现出较好的性能。

1  图书物流配送路径规划模型

1.1  优化目标选择

物流配送车辆调度过程需要根据货物和车辆信息在配送区域划分后进行车辆的具体安排。其中，配送区域划分涉及配送中心分布和需求点分布。用户需求一般包括订货信息和退货信息，并需要事先进行分类汇总。在车辆安排完成后，需要根据交通状况、客户的具体位置和送货时间来选择配送路线，这时涉及模型的两个关键指标：交货时间信息和运输成本费用，这也是选择算法的优化目标。在选择完成后，根据配送路线和配送顺序进行车辆装配并完成配送，通常会对车辆的位置进行周期采集跟踪。

通过上述分析，可以将配送作业的优化目标分为：车辆利用率高;准时送达;配送距离最短;配送成本最低;每吨货物运送1 km所需要的运费最少。

由于图书物流配送的行业特征，对配送的效率要求不是很高，最大的需求点是降低成本，因此本文将降低配送成本作为配送作业的优化目标。

1.2  基于作业成本法的模型优化

图书物流中心配送模型研究已经较为成熟，因此本文重点采用作业成本法对现有图书物流配送的车辆路径规划问题的数学模型进行优化。

通过图书配送成本项分析，采用作业成本法计算优化目标后，车辆路径规划问题的数学模型的形式如下：

2  单亲遗传混合蚁群算法

求解多目标优化的车辆路径问题时，与基本蚁群算法相比，单亲遗传混合蚁群算法具有计算效率高、收敛性好等优点，尤其单点单亲遗传混合蚁群算法不仅具有较好的计算性能，而且具有较高的稳定性。因此，本文引入单亲遗传混合蚁群算法对构建的模型进行求解。

2.1  蚁群算法求解路径规划问题

设蚁巢的蚂蚁数为[R]，需要优化的元素集合为[D]，[Dφi]表示其第[i][（1≤i≤n）]个元素。为实现初始种群求解问题，在本文中需要优化的所有参数的数量为[n]。假设这些元素[φi]存在[K]种数值，则[ζj（Dφi）（0）]为初始条件下第[j]个元素的信息素。

重复执行以上过程直到允许的最大迭代次数，或者所有蚂蚁均获得唯一个元素，即得到了优化后的初始种群相关参数。

2.2  单亲遗传混合蚁群算法的实现

传统蚁群?遗传算法在通过蚁群算法生成初始种群之后，需要继续执行遗传操作。遗传操作的主要内容为：选择算子、交叉算子和变异算子[6]。传统遗传过程的交叉算子操作会存在计算复杂度较大和早熟收敛现象，文献[7]将单亲遗传算法和基本蚁群算法相结合，使其优势互补，并利用单亲遗传算法的特点，构建出两种求解该问题的单亲遗传混合蚁群算法。因此针对构建的成本优化图书物流配送路径规划模型引入单亲遗传混合蚁群算法，以便提高收敛速度并获取更优解，单亲遗传混合蚁群算法的流程如图1所示。

图1  单亲遗传混合蚁群算法流程

3  实验结果与分析

为了验证提出的图书物流配送路径规划问题模型及单亲遗传混合蚁群算法的可行性，以2018年10月—12月某省会城市图书物流中心为例，进行某辖区内图书销售网点配送优化和仿真。该辖区内图书销售网点共9个，配送的货物种类为一般印刷图书。中心同类型配送车辆共6辆。车辆固定成本因子为102元 /（辆·次）。

3.1  算法性能分析

经过100次仿真运算，设置最大迭代次数均为200。优化前的配送路径如图2所示。经过单亲遗传蚁群算法计算合理的配送顺序后，优化后的拣选路径如图3所示。

图2  优化前的配送路径（9网点）

图3  优化后的配送路径（9网点）

3.2  配送方案比较

最后，将提出模型计算出的配送方案与人工经验设计的配送方案[8]进行对比分析，如表1所示。

表1  配送方案比较

从表1可以看出，相比现有人工设计的配送方案，本文图书物流配送路径规划问题模型即单亲遗传混合蚁群算法的配送方案配送成本降低了22.1%，配送距离减少了15.9%。这说明单亲遗传混合蚁群算法在一定程度上克服了收敛“早熟”，得到了全局最优解。

4  结  语

本文提出一种基于蚁群优化算法的图书配送路径规划模型，使配送成本最小化。结合某图书物流中心的配送實例进行案例分析，验证了模型的有效性。同时，通过算法的比较分析，证明单亲遗传混合蚁群算法具有较好的全局最优和快速收敛性能。但是，算法的复杂性有一定的提高，后续将对并行计算和算法步骤简化开展进一步研究。

参考文献

[1] MILLIOT J. The book publishing industry [J]. JRC?IPTS， 2014， 2（6）： 319?339.

[2] WOLL T， RACCAH D. Publishing for profit： successful bottom?line management for book publishers [J]. Library management， 2014， 13（8）： 16?17.

[3] WANG C， GUAN Z， SHAO X， et al. Simulation?based optimization of logistics distribution system for an assembly line with path constraints [J]. International journal of production research， 2014， 52（12）： 3538?3551.

[4] NIU Y F， LAM W H K， GAO Z. An efficient algorithm for evaluating logistics network reliability subject to distribution cost [J]. Transportation research Part E， 2014， 67（C）： 175?189.

[5] 蔡婉君，王晨宇，于滨，等.改进蚁群算法优化周期性车辆路径问题[J].运筹与管理，2014（5）：70?77.

CAI Yijun， WANG Chenyu， YU Bin， et al. Improved ant colony algorithm for optimizing periodic vehicle routing problem [J]. Operations research and management science， 2014（5）： 70?77.

[6] 葛斌，韩江洪，魏臻，等.最小最大车辆路径问题的动态自适应蚁群优化算法[J].模式识别与人工智能，2015，28（10）：930?938.

GE Bin， HAN Jianghong， WEI Zhen， et al. Dynamic adaptive ant colony optimization algorithm for minimum and maximum vehicle routing problem [J]. Pattern recognition & artificial intelligence， 2015， 28（10）： 930?938.

[7] 刘云，张惠珍.多目标带时间窗的车辆路径问题的单亲遗传混合蚁群算法[J].公路交通科技，2016，33（6）：95?100.

LIU Yun， ZHANG Huizhen. Single?parent genetic hybrid ant colony algorithm for vehicle routing problem with multiple time windows [J]. Journal of highway and transportation research and development， 2016， 33（6）： 95?100.

[8] REN Y， HU L， MA Y. Logistics distribution route optimization method for peach products transport [C]// 2015 International Conference on Measuring Technology & Mechatronics Automation. Nanchang： IEEE， 2015： 1?8.