牛奶配送问题的两阶段平衡TSP优化算法研究

Study on optimal algorithm of 2-period balanced TSP for milk delivery problem

牛奶配送问题中包含访问次数不同的节点,该问题可以当做两阶段旅行商问题进行求解。为有效地求解节点个数处于平衡条件下的牛奶配送问题的两阶段旅行商问题,提出了一种启发式优化求解方法,有助提高目标问题的求解效率和性能。针对节点数量平衡性和节点访问次数不同的特点,提出一种基于节点划分的动态规划优化。通过对实例进行计算和比较,结果验证了所提方法的有效性和优越性。

Milk delivery problem is a problem which contains different visiting time node, it can be regarded as a 2-period TSP. In order to solve 2-period traveling salesman problem for milk delivery problem under balancing condition effectively, a heuristic optimal algorithm is proposed, which can improve efficiency and performance on solving target objection. Considering the node characteristics both number balance and different visiting time, a dynamic programming optimal method based on node division is proposed. By calculating and comparing on examples, the result shows the effectiveness and superiority of this proposed algorithm.