旅行商问题（TSP，Traveling Salesman Problem）：假设某人要拜访N个城市，他必须选择所要走的路径，每个城市只能拜访一次，最后回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
TSP问题有许多不同的变体，每一种变体都根据不同的现实情况对原问题进行调整。下面将详细解释每种问题，并建立相应的数学模型。
1. 标准TSP
在标准TSP中，城市之间的距离或成本是任意的。即给定城市的集合 ，旅行商的目标是找到一个最短的回路，使得每个城市只访问一次并返回起点。
数学模型:
是从城市 到城市 的成本或距离（可以是任意值）。 决策变量 表示是否选择从城市 到城市 的路线（ 1 表示选择， 0 表示不选择）。
目标是最小化总距离或成本:
满足以下约束条件:
每个城市恰好进一次:
每个城市恰好出一次:
消除子回路 (Subtour Elimination Constraints, SECs)，以防止旅行商在回路中被困在一小部分城市:
2. 度量TSP (Metric TSP)
度量TSP是一种特殊的TSP问题，其中城市之间的距离或成本满足三角不等式，即：
三角不等式保证了最短路径几何距离的规律，例如欧几里得距离。数学模型: 和通用TSP一样，度量TSP的模型保持不变，唯一的区别是距离 满足三角不等式约束条件。
3. 对称TSP (Symmetric TSP, STSP)
在对称TSP中，城市 到城市 的距离与城市 到城市 的距离相同，即 。例如，城市之间的行驶成本是对称的。
数学模型：和通用TSP的模型类似，只是约束 ，即所有的路线都是双向的，且成本一致。
4. 非对称TSP (Asymmetric TSP, ATSP)
在非对称TSP中，城市 到城市 的距离可能与城市 到城市 的距离不同，即 。这种情况通常出现在单向路网或风向影响的航行路线中。
数学模型：与通用TSP相同，只是 。
5. 多次访问TSP (TSP with Multiple Visits, TSPM)
在多次访问TSP中，允许旅行商多次访问同一城市。通常这种问题用于多需求场景，比如需要重复访问一些节点。
数学模型:
决策变量 ，表示从城市 到城市 的访问次数，可以大于 1 。 其他约束条件保持不变，但不再需要"每个城市恰好访问一次"的条件，允许多次访问。
目标函数和约束条件与通用TSP相似，唯一的变化是决策变量允许多次访问。
6. 多销售员TSP (Multiple Traveling Salesmen Problem, mTSP)
多销售员TSP允许多名销售员同时访问城市。目标是最小化所有销售员的总成本或最小化最长销售员路径。
数学模型:
设 名销售员。 决策变量 表示销售员 是否从城市 到城市 。 目标函数为最小化所有销售员的总路径长度：
每个城市恰好被所有销售员访问一次:
每个销售员的路径构成一个循环回路。
7. 开放巡回TSP (Open Traveling Salesman Problem, OTSP)
开放巡回TSP中，销售员不需要从起始点结束旅程。换句话说，旅行商不需要回到原点。数学模型:
保持通用TSP模型中的约束，去掉回到起点的约束，即路径可以从任意城市出发并结束在任意城市：
8. 时间依赖TSP (Time-Dependent TSP, TD-TSP)
在时间依赖TSP中，旅行的成本不仅取决于距离，还取决于时间。不同时间段的交通状况可能不同，导致不同的旅行成本。
数学模型:
是从城市 到城市 在时间 的旅行成本。 目标是最小化总旅行时间：
其中 是从 到 的出发时间，由之前路径的结束时间决定。
9. 广义TSP (Generalized TSP, GTSP)
广义TSP中，城市被划分为多个簇，销售员必须从毎个簇中选择一个城市访问。此问题适用于多区域选择的情况，如物流公司必须在每个城市区域选择一个站点进行送货。
数学模型:
设 为簇的集合， 为簇 中的城市集合。 目标函数为最小化总旅行距离:
每个簇 至少访问一个城市:
10. 带时间窗的TSP (TSP with Time Windows, TSPTW)
在TSPTW中，每个城市必须在指定的时间窗口内访问。这种问题常见于物流配送场景，客户要求货物在特定时间段送达。
数学模型:
设 是城市 的时间窗口，表示必须在时间 和 之间访问城市 。 决策变量 表示访问城市 的时间。 目标函数为最小化总旅行时间:
约束条件是访问城市 的时间必须在指定的时间窗口内:
