需求可拆分车辆路径问题的聚类求解算法

针对传统的车辆路径问题通常假设客户的需求不能拆分,即客户的需求由一辆车满足,而实际上通过需求的拆分可使需要的车辆数更少,从而降低配送成本的问题,分析了需求可拆分的车辆路径问题的解的特征,证明了客户需求不宜拆分应满足的条件,设计了符合解的特征的聚类算法,并对其求解.通过实验仿真,将所提出的聚类算法与蚁群算法和禁忌搜索算法进行比较,所得结果表明了所提出的算法可以更有效地求得需求可拆分车辆路径问题的优化解,是解决需求可拆分车辆路径问题的有效方法.

Clustering algorithm for split delivery vehicle routing problem

In the traditional vehicle routing problems,customer demands are usually assumed that they can not be split.That is to say,a customer can only be severed by a vehicle.In fact,split delivery requires fewer vehicles,which reduces transportation costs.This paper analyzes the solution’s characteristics of split delivery vehicle routing problem,and also proves the situations that customers’ demands can not be split.A clustering algorithm meeting the solution’s characteristics is designed to solve this problem.Compared with ant colony algorithm and tabu search algorithm,the proposed algorithm is demonstrated to obtain optimal solution more effectively through the simulation,and it is an effective method to solve split delivery vehicle routing problem.