双层车辆路径问题的混合启发式算法

摘要

针对与城市物流密切相关的双层车辆路径问题(2E-VRP),提出了一种用来求解的混合启发式算法.该算法利用贪心算法的快速性、蚁群算法的搜索多样性以及邻域搜索算法较强的局部寻优能力来提高求解质量,加速算法的收敛性.把该算法应用于22个测试算例和3个大规模的算例,并与同类研究进行了比较.实验结果表明,混合启发式算法不仅能保证较高的精确性,而且具有很高的效率；与精确性最高的同类算法相比,虽然在解的质量方面稍逊,但在求解速度方面表现出了明显的优势.实验结果还显示了构建双层城市物流系统的潜在收益,中转站的设置能够在一定条件下显著提高城市物流效率.%Aiming at the two-echelon vehicle routing problem (2E-VRP) closely related to city logistics, the paper put forward a kind of hybrid heuristic algorithm to solve 2E-VRP. In order to improve the solution quality and accelerate the convergence of algorithm, the algorithm took advantage of the rapidness of greedy algorithm, the search diversity of ant colony algorithm and the strong local optimization ability of local search algorithm. It applied the algorithm to 22 benchmark examples and 3 large-scale examples, and compared the results with similar studies. The experimental results show that the hybrid heuristic algorithm can not only guarantee a high accuracy, but also have high efficiency. Compare with the similar algorithm of the highest accuracy, although the hybrid heuristic algorithm performs somewhat less well in solution quality, but shows great advantage as far as the solving speed is concerned. The experimental results also show potential benefit of constructing the two-echelon city logistics system, and that setting satellites in certain conditions can significantly improve the city logistics efficiency.