车辆路由问题中序列扩展法的一种改进算法

Algorithm Improvement of Sequential Expansion Method About Vehicle Routing Problem

序列扩展法是对"车辆路由问题"(VRP)进行求解的一种可行的启发式算法,但在网点分布不均匀、约束条件比较极端的情况下,应用序列扩展法难以获得满意解。本文以市内邮路规划为例对序列扩展法作了介绍,并提出了一种序列扩展法的改进算法,通过比较两种算法的结果,说明改进的算法能获得比常规序列扩展法更优的解。

Sequential expansion method is a feasible heuristic algorithm to solve ＂vehicle routing problem＂ （VRP）, but in the cases of uneven distribution network and extreme constrains, it is hard to acquire satisfied solution for applying the sequential expansion method. In this paper, sequential expansion method is introduced by an example of postal routes planning in the city, and put forward a improved algorithm of sequential expansion method, by comparing , explained that the improved algorithm can obtain better solution than sequential expansion method.