含优先级约束的旅行商问题研究

Research on the Travelling Salesman Problem with Precedence Constraints

旅行商问题(TSP)是经典的组合优化问题,其目标是找出一条经过图中所有结点刚好一次的最短路径。实际应用中常常还包含优先级规则,此时称之为含优先级约束的旅行商问题(TSP-PC)。该问题广泛存在于物流服务、交通运输、生产制造等应用场景中,高效的求解方法有助于减小操作成本、提升服务效率。基于此,文中建立了描述该问题的整数线性规划模型,设计了相应的动态规划精确算法。相关的数值实验表明,该算法可以高效地求出不同规模的问题的最优解。

Travelling Salesman Problem(TSP)is a classic combinatorial optimization problem,which focuses on finding a shortest route which visits all the vertices in a graph exactly once.However,the route is often required to satisfy precedence constraints in practical applications.In this occasion,the problem is called Travelling Salesman Problem with Precedence Constraints(TSP-PC).Since it is frequently found in some applications including logisitics,transportation and manufacturing,an efficient methodology can contribute to the reduction of operation cost and the promotion of service.In order to achieve this goal,this paper has described this problem by an integer linear programming model and designed an exact dynamic programming algorithm.As is shown in the numerical experiments,different scales of TSP-PC can be solved to the optimality efficiently by the algorithm.