基于中国邮递员问题的城区烟草配送线路优化模型与算法

The Optimization Model and Algorithm of Tobacco Distribution Routing in Urban Area Based on the Chinese Postman Problem

文中利用中国邮递员问题研究城区烟草配送问题,首先分析城区烟草配送的特点,提出多人中国邮递员问题。然后给出最优匹配模型和生成城区烟草配送的欧拉图的方法,设计欧拉环游的有向回路分割算法。最后给出算例,通过计算说明算法的可行性。

The tobacco distribution routing problem in urban area is studied based on the Chinese postman problem in this paper.Firstly the characteristic of tobacco distribution in urban area is analyzed,and China postman problem with more than one people is put forward.Then the optimal matching model and generation method of the Euler graph of tobacco distribution in urban area are given.And the directed circuits partitioning algorithm of Euler tour is given.At last,an example is given,and the feasibility of the algorithm is proved through the example.