混合人工蜂群算法求解煤炭物流中的CVRP问题

庞柒 阮平南 关志强

摘要：煤炭物流中生产物资的运输问题属于典型的车辆路径问题（CVRP， Capacitated Vehicle Routing Problem）。文章采用改进的人工蜂群算法对该问题进行求解。首先按照相对中心位置（物资供应中心）的角度大小，对各个位置的矿区进行排序，然后产生合法初始解；通过算子操作产生邻域解，采用蚁群信息素更新方式，在邻域内进行更为细致的迭代搜索。通过国际测试算例仿真，改进的人工蜂群算法可以找到近似最优解，证明算法的有效性，对于解决实际运输问题具有应用价值。

关键词：煤炭物流；车辆路径问题；混合人工蜂群算法

一、 引言

煤炭是我国生产和消费的主要能源，而煤炭物流是保证煤矿企业安全生产的前提条件，合理的煤炭物流不仅能够保证煤矿企业的正常生产，而且可以为煤矿企业节约可观的物流成本，因此煤炭物流中CVRP（Capacitated Vehicle Routing Problem）问题的优化显得十分重要。所谓煤炭物流中的CVRP问题，即是在煤矿企业生产物资供应中心（可能是一个或多个物资供应中心）向附近多个煤矿矿区运输维持其生产所需要的各种物资，并且达到最低运输成本的目标。

VRP问题是典型的NP问题，作为组合问题，VRP问题可以看作是背包（Bin Packing Problem，BPP）和TSP二者的综合问题。对于大型TSP问题求解已经不容易，再融合BPP问题后，CVRP的求解就更加困难。在求解方法上，传统的求解方法有G.Clarke和J.W.Wright提出的节约算法，B.E.Gillet和L.R.Miller提出的扫描算法。随着研究进展以及各类启发式智能算法的兴起，不同学者针对此问题，分别采用遗传算法、模拟退火算法、蚁群优化算法、粒子群优化算法等。

人工蜂群算法（Artificial Bee Colony algorithm，ABC）是近年兴起的模拟蜜蜂觅食行为的优化算法，Dervis Karaboga在其文章中对人工蜂群算法的正反馈、负反馈、波动性以及相互作用的特性进行了细致的阐述。在组合优化、函数寻优、以及神经网络权值优化等问题中，人工蜂群算法均得到了很好应用。M.Dorigo等人于1992年提出蚁群算法（Ant Colony Optimization，ACO），蚁群算法群体搜索能力较强，易于与其他优化算法结合；但存在搜索时间长容易陷入局部极值的缺点，而人工蜂群算法在种群内个体分工协作上优势明显，因此本文在此基础上提出算法，首先采用人工蜂群算法进行初步搜索以期望获得较好的邻域解，然后采用蚁群优化算法进行更细致搜索，最终得到近似最优解的策略。

文章结构安排如下：第一部分对煤炭物流中CVRP问题数学模型进行描述分析；第二部分对混合人工蜂群算法设计进行详细阐述，包括编码形式、初始解产生、邻域计算方式以及局部更新策略；第三部分是仿真实验与结果分析，最后是结论部分。

二、 CVRP问题数学模型

假设某煤矿企业有一个物资供应中心，该物资供应中心拥有m辆同质的运输车，每辆车的最大运输能力为Q，共有n个需要服务的矿区，每个矿区Ai（i=1，2，…，n）对物资的需求为qi，dij代表第Ai个矿区与第Aj个矿区之间的距离或者运输费用，对CVRP建立如下的数学模型，如公式（1）-（7）所示。

公式（1）为目标函数，公式（2）-（7）为约束条件。公式（2）表示矿区Ai和矿区Aj之间是否有连接，即为1表示二者由某一辆车共同服务，否则为0；公式（3）表示矿区Ai是否由车辆k服务，为1即表示由车辆k为其运输物资，否则为0；公式（4）表示车辆k所服务矿区的物资需求量之和不超过车辆最大载重量；公式（5）表示路径约束；公式（6）-（7）表示一个矿区仅由一辆运输车服务，且从物资供应中心出发后仍回到物资供应中心。

三、 混合人工蜂群算法

1. 人工蜂群算法。Dervis Karaboga和Bahriye Basturk根据蜜蜂群体觅食行为，提出人工蜂群算法（Artificial bee colony algorithm，ABC）。人工蜂群算法以食物源、采蜜蜂（Employed Foragers）和待工蜂（Unemployed Foragers）作为基本要素；以向食物源招募（Recruit）蜜蜂和放弃（Abandon）某个食物源作为两种基本的行为模式。

食物源与巢穴的距离、丰富度、集中度以及容易程度有关，代表问题解的优劣好坏程度。采蜜峰（Employed Foragers）是当前正在进行“开采”工作的蜜蜂，它们可能与某一特定食物源有关，掌握某一食物源的信息，并且在一定程度上共享食物源信息。待工蜂（Unemployed Foragers）分为侦查蜂和围观蜂，侦查蜂负责搜索巢穴附近新的食物源，围观蜂在巢穴内等待新的食物源信息，当采蜜峰共享的食物源信息后，围观蜂开始工作。

待工蜂在可能作为围观蜂在巢穴中等待信息共享，也可能作为侦查蜂到巢穴附近去寻找食物源；当作为侦查蜂找到新的食物源后，其角色变为采蜜峰，采蜜回到巢穴并卸载食物后，它可能因为食物源即将枯竭而放弃该食物源，也可能共享信息招募其它蜜蜂，或者没有招募行为继续独自去“开采”该食物源。

2. 混合人工蜂群算法设计

（1）解的编码形式。假设n个矿区分别采用阿拉伯数字表示，“1”作为标记，表示物资供应中心。解的表示形式如表1所示。解的涵义即表示用3辆车为7个矿区服务，第一辆车的行驶路线依次为1-3-7-2-1；第二辆车行驶路线依次为1-5-6-1；第三辆车行驶路线依次为1-4-8-1，且各个车辆运输的物资满足其服务矿区的物资需求又不超过车的承载能力。

（2）初始解的产生。一般采用群智能优化算法解决问题时，问题的初始解往往采用随机生成的方式，但是由于CVRP问题约束条件的限制，采用随机产生初始解的方式会产生大量非法解存在，导致无效迭代，造成时间浪费；因此采用构造符合条件的初始解方式。假设矿区及物资供应中心的坐标分别记作（xi，yi）和（x0，y0）。按照公式（9）计算各个矿区相对于原点的坐标，然后根据公式（10）计算各个矿区的角度，然后根据角度大小排序。将排序后的各个矿区，按照承载能力Q，进行装载直至不能再装载物资为止。

（3）邻域解的计算。在得到初始解之后，为保持解的多样性，采用两种方法产生邻域解，（1）使用插入、交换和反向操作算子，由于是按照约束条件产生合法解，因此不同路线之间不再使用交换算子；（2）使用交互向量。交互向量可以使得初始解在不同路线间发生变化，即服务矿区会产生由不同车辆服务的变化效果。假设三个初始解a，b，c，交互向量v=[1，1，1]，交互向量的作用之后可能产生的解为a*，b*，c*。交互向量根据矿区需求量和位置角度设计产生。

四、 实验仿真与分析

本文选取国际标准测试数据进行实验，数据来源于网站。算法首先根据问题规模设置种群规模及参数，然后根据生产满足约束条件的初始解，根据交叉向量信息进行采蜜峰的搜索，然后根据共享信息进入了围观蜂搜索阶段，侦查蜂对搜索到的解进行评价后以一定概率放弃并生成新的解，直至满足条件为止。混合人工蜂群算法迭代的流程图如图（1）所示。

表2为采用国际标准测试案例中E集合中不同规模案例的测试结果。算法中蜂群最小规模设为20，最大规模设为问题规模二倍，迭代步数设为150步，算法迭代次数为10次。采用局部搜索策略时，蚁群搜索机制的参数分别设为ρ=0.1。从表2中可以看出对于，不同规模的的问题，本文提出的算法均得到近似最优解，且车辆平均满载率较高，除E_n23_3外，各个案例车辆满载率均在90%左右。表3为对应各个算例的实际路线安排表。图2为大规模测试用例E-n101-k8各个车辆运行路线图，图3为该算例下算法迭代后收敛效果图，从图中可以看出，运行距离从930逐渐下降到850，在80步之后逐渐稳定。

五、 结论

通过国际测试用例仿真，验证了混合人工蜂群算法在求解煤炭物流中CVRP的有效性，可以快速计算出近似最优解，证明了算法的实际应用价值。同时，通过算法设计以及仿真过程可以得出以下结论：

1. 在对煤炭物流中CVRP问题研究基础上，采用改进的人工蜂群算法对该类问题进行求解，并取得近似最优解的效果，可将算法用于实际煤炭物流路线优化。

2. 根据问题约束特点以及算法自身特点，采用了以“1”作为标记的编码方式，该编码方式简单易懂，迭代方便。

3. 改进人工蜂群算法中，初始解产生按照极角方式，避免非法解参与运算；邻域解采用交叉向量作为“指引”，避免大范围的无效搜索；局部搜索采用蚁群搜索机制，增强局部搜索能力。

参考文献：

1. 汪文生，曾志猛，王娟.多级煤炭物流网络优化选择模型的构建与应用.煤炭学报，2011，26（6）：1060-1064.

2. WANG Wen-sheng， ZENG Zhi-meng， WANG Juan. Construction and application of multi-level coal logistics network optimization model. JOURNAL OF CHINA COAL SOCIETY，2011，26（6）：1060-1064.

3. T.K.Ralphsy， L.Kopmanz， W.R. Pulleyblankx， L.E. Trotter， Jr. On the Capacitated Vehicle Routing Problem. Mathematical Programming，2003，94（2）：343-359.

4. G.Clarke， J W Wright.Scheduling of Vehic- les from a Central Depot to a Number of Delivery Points. Operations Research，1964，12（4）：568-581.

5. 姜大立，杨西龙，杜文，周贤伟.车辆路径问题的遗传算法研究. 系统工程理论与实践，1996，（6）：40-44.

6. 张丽萍， 柴跃廷.车辆路径问题的改进遗传算法.系统工程理论与实践，2002，（8）：79-84.

7. 谢秉磊，安实，郭耀煌.随机车辆路径问题的多回路优化策略.系统工程理论与实践，2007，（2）：167-171.

8. 袁健，刘晋，卢厚清.随机需求情形VRP 的退火网络解法.系统工程理论与实践，2002，（3）：109-113.

9. 张涛，田文馨，张玥杰，刘士新.带车辆行程约束的VRPSPD问题的改进蚁群算法.系统工程理论与实践，2008，（1）：132-140.

10. 刘志硕， 申金升， 关伟.车辆路径问题的混合蚁群算法设计与实现. 管理科学学报，2007，10（3）：15-21.

11. 李琳，刘士新，唐加福.改进的蚁群算法求解带时间窗的车辆路径问题.控制与决策，2010，25（9）：1379-1383.

12. 李宁，邹彤，孙德宝.车辆路径问题的粒子群算法研究.系统工程学报，2004，19（6）：596-600.

13. 王素欣，高利，崔晓光等. 多需求点车辆调度模型及其群体智能混合求解.自动化学报，2008，34（1）：102-104.

作者简介：阮平南，北京工业大学经管学院教授、博士生导师；庞柒，北京工业大学经管学院管理科学与工程专业博士生；关志强，北京工业大学电控学院硕士生。

收稿日期：2013-11-20。