路由设计（routing design），理学-计算机科学技术-计算机科学理论-算法-近似算法，在近似算法中，路由设计问题是和路径选择有关的一类组合优化问题的统称。常见的路由设计问题包括车辆路由（vehicle routing）问题、不相交路径问题、组播路由问题等。车辆路由问题中包括著名的旅行商问题（Traveling Salesman Problem，TSP）、中国邮递员问题、电话叫车（Dial-a-Ride）问题、路径覆盖问题、树覆盖问题、圈覆盖问题[1]等。TSP问题是NP困难的。1976年，Christofides对度量空间中的TSP问题（即，无向完全图上的TSP问题）给出了1.5-近似算法，40多年过去了，该近似比仍是度量空间TSP问题的最好近似比。如何改进这个近似比是近似算法中长期以来著名的未解决问题之一。有向完全图上的TSP问题又称非对称TSP问题，是TSP问题众多变化中著名的一个。