行程问题的九个公式行程问题（TravellingSalesmanProblem，简称TSP）在理解和解决许多实际问题（例如路由规划、车辆调度与最优路径搜索）方面都发挥着重要作用。
其主要研究内容是：在一定网络结构中，以某一源点为起点，按指定的顺序依次访问该网络中的其他结点，并且最终到达源点，构成一个闭环路径，该闭环路径的路径权值最小。
TSP的数学模型被称为旅行商问题，它的解表示最优路线以及最小距离，是人们研究图论一大难题。
研究行程问题需要使用一些特定的公式，下文将介绍求解TSP过程中使用到的九个公式。
第一个公式是显示型，即给定一个旅行商路径，可以算出它的路径权值：d(Pi, Pj)= d(i,j)+d(j,k)+... d(pk-1,pk)。
其中，d(i,j)表示从结点i到结点j的距离，Pk-1和Pk分别表示结点k-1和结点k的路径顺序。
第二个公式是移动型，即某一结点被插入到一条路径中时，其权值的增加量：d(i, j)+d(j, k)-d(i, k) 。
其中，d(i,j)表示从结点i到结点j的距离，d(i,k)表示从结点i到结点k的距离。
第三个公式是换位型，即某一结点在路径上两个相邻位置之间“移动”时，其权值变化：d(i, j)+d(k, l)-d(i, k)-d(j, l) 。
其中，d(i,j)和d(k,l)分别表示权值变化前的两条路径的长度，d(i,k)和d(j,l)表示权值变化后的两条路径的长度。
第四个公式是回头路检查型，即确定某结点是否能被加入某个方案的路径时：D(i,j)= d(i,j)+d(j, k)+... d(pk-1,pk)+d(pk,i)。
其中，d(i,j)表示从结点i到结点j的距离，Pk-1和Pk分别表示结点k-1和结点k的路径顺序，d(pk,i)表示最后一次访问结点k 时从k回到i的距离。
第五个公式是分支限界型，即确定当前搜索节点的最小路径权值时：D(i,j)= C(i,j)+f(i,j) 。
