动态车辆路径问题的隐分区灵活分批策略

The virtual partition and flexible batch strategy of DVRP

摘要:

在一般分区分批旅行商策略的基础上，提出了隐分区灵活分批旅行商策略，并进行了有效性分析。新策略主要从2个方面做了改进：①通过设置虚拟分区，保持了分区顾客的到达率不变，使顾客群的形成时间减少；②对决策时间进行了调整，允许在顾客群形成时间与决策时间之内出现的新顾客进入决策，使进入计划的顾客更多，从而使路径平均距离更短。最后，实例仿真验证了策略的优越性。

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.