陈梦圆 余函

摘 要：最优解方案是在生活和工作中经常出现的问题策略，其往往寻求系统中最高收入最低成本的设置点。本文以运输业常见的车辆调度问题作为案例场景，建立VRP模型。使用蚁群算法进行求解，寻找到用时最短人数最少的方案。

关键词：蚁群算法；车辆调度；数学建模；VRP模型

一、引言

当今社会，快递行业已成为人们日常生活中离不开的一部分，快递行业的蓬勃发展为生活带来了诸多便利。一般地，所有快递到达某地后，统一存放在公司总部，然后安排业务员将快件一一送达。对公司而言，既希望能尽快送完当日快件，又希望送货费用最省。但越多的业务员意味着成本会越高，因此需要制定合理方案，提前安排好路线，保证任务的尽快完成，又能让业务员人数最少。

本文建立送货线路的VRP模型和最优人数的0-1规划模型，使用蚁群算法进行求解并将求解方案与现实方案进行对比来说明蚁群算法在车辆调度问题中的应用。

二、送货线路的VRP模型

车辆调度问题VRP（Vehicle Routing Problem），可表示为：给定一个中心点（即公司总部）、一个车辆（即业务员）集合、一个客户（即送货点）集合，每辆 车和客户都有自己的属性（载重量，货物需求量），要求所装载的货物不能超过车 辆的总量（即载重量）。起初所有车辆都在中心仓库，中心仓库和各客户点的位置 坐标及货物需求量已知，中心仓库派送若干车辆。每辆车都必须从起点出发，完成 若干客户点的运送任务再回到起点。[1]

先假设每个业务员只送货一次，即只往返一趟，求得总路程最短的各个线路。业务员送货运行线路均为平行于坐标轴的折线，为便于计算，先将折线化为直线，即视业务员通过任意两个相邻送货点之间行驶的线路均为直线。

业务员从公司总部出发，到各送货点送货，最终返回总部。用点 0 表示总部，并命名为源点，点1，2，...，l表示m个业务员需要到达的送货点。

设任意两个送货点坐标分别为，因业务员送货运行线路均为平行于坐标轴的折线，故这两点间的距离为：

完成每天快件派送所需业务员的最少人数：

业务员每天送货，既要受限于一次性的快件携带量，又要受限于每日工作时间上限，属于多约束的非线性规划问题，是组合优化领域中的典型的NP难问题[2]。一般的求解方法不仅计算周期长，甚至难以得到结果，精确算法的计算量随着问题规模的增大而大幅增长。

三、蚁群算法的实际应用

蚁群系统（Ant System或Ant Colony System）是由意大利学者Dorigo、Maniezzo等人于20世纪90年代首先提出来的。他们在研究蚂蚁觅食的过程中，发现单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现，蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。[2]

蚁群算法的本质是一种随机搜索算法，是通过对候选解组成的群体的进化来搜索全局最优解。[3]

使用改进的蚁群算法，能够通过多次迭代找到总路程最短时的线路条数，并给出具体线路，不用人为划分线路条数。

初始时刻，各条路径上的信息素量相等：

将蚂蚁随机或均匀分布在各送货点上。

禁忌表tabuk用来标记已被访问过的送货点，保证不重复訪问。每只蚂蚁通过 访问各送货点而形成一个解，在访问过程中，将访问记录保存在禁忌表中。

在货运点i的每只蚂蚁依据概率公式（1-16），在未访问过的货运点中选择下一 个要访问的货运点j。循环进行此步，直到访问完所有货运点。

概率公式为：

计算每只蚂蚁行走的总线路长度，并保存最优方案。

进行信息素调整，每只蚂蚁完成对所有货运点的遍历后，更新残留信息素。

其中，Q表示信息素强度，它在一定程度上影响算法的收敛速度；Lk表示第K只蚂蚁在本次循环中所走线路的总长度。

判断系统是否满足停止条件，不满足则又重新安排蚂蚁，再次进行运算，直至得到最优策略。

基本蚁群算法的结构流程图：

四、总结

将蚁群算法应用于解决优化问题的基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。[4]

社会的高速发展对时间的要求越来越严苛，追求高速度的同时又想要低成本，使用蚁群算法协调车辆能够达到智能化的最优搜索方案。

参考文献

[1]宋燕子，基于模拟退火算法的启发式算法在VRP中的应用[D].华中师范大学，2013.1

[2]康与云，元功能链驱动的机电产品矩阵式创新设计方法.山东人民出版社，2015.11

[3]于凤青，物流配送车辆优化调度问题研究[D].沈阳工业大学，2007：28-31

[4]郁磊、史峰、王辉、胡斐，MATLAB智能算法30个案例分析（第2版）北京航空航天大学出版社，2015.9

（作者单位：重庆邮电大学 计算机科学与技术学院）