The virtual partition and flexible batch strategy of DVRP

Abstract:

The virtual partition and flexible batch TSP strategy is proposed, which is based on the cutting and fixed batch TSP strategy. And the competitive analysis of the new strategy shows the reason of the improvement. The new strategy gets improvement mainly on two aspects: on one hand, the virtual partition can maintain the arrival rate of the customer in partition area constant and make the formation time of customer group reduced; on the other hand, the adjustment of the decision time allow the new customers be taken into account in the routing plan, which are emerged between the customer group formation time and the decision time. Then the customer in the routing plan will be more, and the mean distance of the rout plan will be shorter. Finally, a numerical example proved those conclusions.