Chain partitioning as a key element for building vehicle routing problem heuristics

Chain partitioning is the process of partitioning a tree into chains. The edges and vertices of the tree have weights. In a vehicle routing context the weights of edges might represent distances between customers and the weights of the vertices might represent the demand of the customers. Based on the distances a minimum spanning tree can be built and, when partitioned into chains with total vertex weight per chain less than a certain value, each chain represents a route with total demand less than the vehicle capacity. This one–step process can be embedded in a local search procedure or a meta–heuristic with the advantage that a neighbour always represents a feasible solution.