蚁群算法在车辆优化调度中的应用研究

摘要：本文阐述了车辆优化调度问题（VRP）和蚁群算法（ACO）基本理论的基础上对蚁群算法在一般车辆优化调度问题中的应用做了深入的改进研究，给出了算法的实现步骤。通过算例分析，对模型和算法的正确性、高效性和适应性进行了验证。实验结果表明，ACO可以快速、有效求得VRP的优化解，是求解VRP的一个较好方案。

关键词：蚁群算法；车辆优化调度；组合优化

一、引言

车辆优化调度问题（Vehicle Routing Problems，简称VRP）是由Dantziga和Ramser于1959年首次提出的在物流运输等行业中具有广泛应用的一类组合优化问题，如邮局的邮件递送业务、工业产品的运输、运输公司的任务安排、乘务员计划安培等。对于物流中心和第三方物流企业的货物配送，货运车辆的调度是工作的重点，正确合理的调度可以有效减少车辆的空架率，实现合理路径运输，从而有效减少运输成本、节约运输时间，提高经济效益。

二、车辆优化调度问题

（一）车辆优化调度问题的定义

车辆优化调度问题一般定义为：对一系列发货点和（或）收获点，组织适当的行车路线，使车辆有序的通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最小、时间尽量少、使用车辆数尽量少等）。车辆优化调度问题是一类有约束的组合优化问题，属于完全NP-hard问题。随着问题输入规模的扩大，求解时间呈几何级数上升。因此，VRP一直是物流研究中的热点问题，对物流企业费用的节约具有重要的理论和现实意义。

（二）车辆优化调度问题的分类

总体上看，车辆优化调度问题一般可根据时间特性和空间特性分为车辆路径规划问题和车辆调度问题。仅根据空间位置安排车辆的线路时称为车辆路径规划问题VRP（Vehicle Routing Problem）；考虑时间要求安排运输线路时称为车辆调度问题VRPTW（Vehicle Routing Problem with Time windows）。车辆优化调度问题可根据不同性质具体分为以下几类：（1）按照运输任务分为纯装问题、纯卸问题以及装卸混合问题。（2）按照车辆载货状况分为满载问题和非满载问题。（3）按照车辆类型分为单车型问题和多车型问题。（4）按照车辆是否返回车场划分为车辆开放问题。（5）按照优化的目标可分为单目标优化问题和多目标优化问题。（6）按照有无休息时间要求可分为有休息时间调度和无休息时间调度问题。实际中的车辆优化调度问题可能是以上分类中的一种或几种的综合。以下仅研究单个发货点对多个收货点的车辆优化调度问题。

三、蚁群算法

（一）蚁群算法的基本思想

蚂蚁具有找到蚁巢与食物之间的最短路径的能力。蚂蚁的这种能力是靠其所经过的路径上留下的一种随时间推移会逐渐消逝的挥发性分泌物（俗称信息素）来实现的。当蚂蚁在一条路上前进时，会留下挥发性信息素，后来的蚂蚁选择该路径的概率与当时这条路径上该信息素的强度成正比。对于一条路径，选择它的蚂蚁越多，则在该路径上所留下的信息素强度就越大。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈。正是通过这种正反馈，蚂蚁最终可以寻找出最短的路径。

四、蚁群算法在车辆优化调度问题中的应用

（一）单个发货点对多个收货点的车辆调度问题模型的建立

（二）蚁群算法的求解步骤

（三）算例及分析