The balanced heuristics for vehicle routing problem with capacity restriction for instances.

New heuristics is proposed for approximate solution of Vehicle Routing Problem (VRP) with capacity restriction and metric distances between vertices. VRP is the task of finding a set of cyclic tours, each vertex-customer must be included in one of these tours and all of them must contain special common vertex - depo. The strategy includes two phases: the clustering of vertex in groups and solution of Travelling-Salesman problem (TSP) inside of groups. The proposed strategy performs clustering by multiple dichotomic dividing vertex set onto groups with keeping balancing criterion. Clustering takes time nearly O(n) and TSP solution with Lin-Kernighan iterative heuristics takes time not exceeding O (n).According to computing experiment the quality of suggested strategy on some examples is insignificantly less than the quality of one of the best approaches to VRP solution - Osman's strategy . By increasing of number of vertices up to 150 and more with proportional increasing number of vertices in each tour new heuristics demonstrates better quality than Osman's strategy with required time less than Osman's by an order. More successive results can be obtained by combining these two heuristics'.Strategies were tested on benchmarks suggested by Christofides, Mingozzi and Tothb and on examples of randomly generated samples with number of vertices from 50 to 200.Due to good time requirement new heuristics can be used for tasks with up to 1000 vertices and more, what is impossible for Osman's strategy.

Keywords

Authors

References