车辆路径问题及其智能启发式算法

车辆路径问题（Vehicle Routing Problem, VRP）是运筹学中的热点问题。关于VRP的研究和应用最初来自于公共服务行业，如学生班车路径，银行运钞路径等问题，后来随着电子商务和物流配送业的发展，VRP也成为各商业企业、邮政快递、高速公路配货等行业亟待解决的问题。VRP的原型是旅行商问题，即给定n个城市和两城市之间的距离，求一条访问各城市一次且仅一次的最短路线。VRP问题是多路旅行商问题的扩展，每个城市（客户）有一个需求量，每个旅行商（车辆）有一定的载重量（能力），一条路线上的客户总需求量不能超过行驶该路线的车辆的能力，求从仓库出发并回到仓库的一组总运输费用最少的路线。

解决VRP的方法大致历经了三个时代：简单的启发式方法时代、启发式数学规划方法时代、精确优化算法与智能优化方法并存时代。较为成功的精确优化算法有K树法、拉格朗日放宽法等；而智能方法主要以模拟退火法、禁忌搜索法和遗传算法为代表。VRP是一个NP完全问题，只有在客户数和路段较少时才有可能得到其精确的最优解，而一般情况下，只要找到一个可行的近优解就足够了，因此，VRP的智能启发式算法成为人们的研究的一个重要方向，这一时代的方法多数以100个客户的Solomon VRPTW标准问题集（6类56问题）为算例进行验证，对比算法速度、规模与已知最优解的偏差等，具有可比性。