论文摘要：车辆路径问题的蚂蚁算法研究

随着物流业向全球化、信息化及一体化发展，配送在整个物流系统中的作用变得越来越重要。运输系统是配送系统中最重要的一个子系统，运输费用占整体物流费用的50%左右，所以降低物流成本首先要从降低物流配送的运输成本开始。选取恰当的车辆路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本。因此，自从1959年Dantzig和Ramser提出车辆路径问题(Vehicle Routing Problem, VRP)以来，VRP便成为近年来物流领域中的研究热点。车辆路径问题是物流配送领域的重要问题，蚁群算法是一种新的启发式算法。本文研究的就是把改进后的蚂蚁算法用于特殊的车辆路径问题一有时间窗的车辆路径问题（Vehicle Routing Problem With Time Window，VRPTW）的求解。本文的主要研究工作如下：（1）以第三方物流配送中心的角度，通过对VRPTW模型的分析，构建合理的VRPTW数学模型；（2）通过对目前蚁群算法的分析及TSPLIB典型实验的测试，概括总结出各种算法的优劣，对蚂蚁算法中MMAS算法作出进一步的改进，为快速、有效地求解VRPTW开辟了途径，这是本文的核心部分；（3）本文通过深入分析蚂蚁算法的优化机制，针对时间窗车辆路径问题，提出了改进的信息素浓度更新规则，并综合运用了推广的2—opt方法进行邻域搜索。对基准VRPTW问题的MATLAB求解表明，能得到满意的结果。本文通过对蚂蚁算法的分析，在MATLAB环境下实现该算法，采用一系列Benchmark Problems对算法进行测试，实验结果表明改进的MMAS算法在求解VRPTW上是有效的。