周祺森

摘要：物流与国民经济及生活的诸多领域密切相关，在物流成本方面，运输费用占大约50%，比重最大。因此，物流成了企业创造利润的重要途径。要降低配送成本，缩短并优化车辆路径是关键所在。然而，车辆路径问题（vRP）是物流领域中的一个强NP问题，国内外学者近年来不断提出多种车辆路径优化问题及求解方法以解决愈加复杂的问题。为进一步理清国内外研究现状，就VRP进行总结分析，然后对车辆路径求解方法进行了介绍，特别地对元启发式算法进行了较为详细的综述。

关键词：VRP;元启发式算法;文献综述

中图分类号：U116.2 文献标志码：A

0引言

随着电子商务的快速发展，物流业作为连接生产者与消费者的桥梁，发挥着越来越重要的作用。然而，物流在给人们生活带来极大便利的同时，也给相关企业带来了逐年增高的物流费用。伴随着竞争日益白热化的商业环境，降低物流成本成了物流企业存活和发展所必须重视的环节。在降低物流成本方面，最关键的途径之一是解决车辆路径问题（vehicle routing prob-lem，VRP）。

1VRP综述

车辆路径问题于1959年由丹齐格和拉姆泽提出，最早源于旅行商问题（TsP）的研究。TsP可以简单理解为在给定的m个城市里，从一个城市出发，经过每个城市，并且每个城市只经过一次，最后回到出发点，找出最短回程路径问题。

在TsP的研究基础上，出现了能力约束车辆路径问题（CVRP），CVRP相对于TsP的“一对多”，可以理解为“多对多”，如图1所示。

2VRP元启发式算法综述

基于车辆路径模型，其求解算法基本可分为精确式算法、启发式算法、元启发式算法和机器学习算法，如图2所示。……