“从第一原理建模旅行推销员问题”

目录

1. 动机和目的

2. 理解数据

3. 从问题描述定义概念模型

4. 从概念模型构建数学模型

• 4.1. 将数据放入集合和参数中
• 4.2. 在变量中编码决策
• 4.3. 定义目标
• 4.4. 创建约束条件

1. 动机和目的

本文从第1篇文章继续。你不需要阅读它来理解我们将在这里做什么，但让我给你一个快速回顾（如果你已经阅读了前一篇文章，随时跳到第2部分）。简而言之，我们概述了游客在规划旅行时面临的常见问题，并致力于构建一个系统，可以帮助我们更有效地规划旅行，加快决策速度，甚至完全自动化任何给定旅行的行程安排。我们观察到，以这种方式陈述问题太复杂了，所以我们对它进行了分解，并得出了其基本版本，并将其称为最小有价值问题。最后，我们得出结论，它采取了旅行推销员问题（TSP）的形式，其中寓言中的推销员必须访问的“城市”，在我们的版本中，对应于游客希望访问的城市中的“兴趣点”。

因此，作为一个起点，我们必须首先对TSP进行建模并解决它，一旦完成，我们将站在牢固的基础上，继续朝着更复杂和通用的解决方案迈进，解决我们的旅行规划问题。我们选择这种方法，因为这个文章系列还教授运营研究（OR）中建模的敏捷方法，因此你在这里找到的许多教训、技巧和诀窍都适用于你在OR中可能面临的任何问题。

回到我们的事业，我们有了TSP的问题描述：

• 目标：尽量走最少的距离
• 要求：每个兴趣点只参观一次，并返回到最初出发点（在我们的情况下是酒店）。

由于我们知道这个问题并不是我们真正面临的问题，而只是对其的简单近似，我们希望建立一个问题的模型，因为模型可以不断完善、扩充和调整；我们知道我们需要这样做才能找到解决我们真正问题的方法。因此，我们的目标是建立一个模型，而不是直接找到解决方案或者设计某种启发式算法为您找到某种解决方案。一旦你学会了如何推导出这样的模型，你就能很好地理解并阅读下一篇文章，在那里我们将用Python实现这个模型。

2. 理解数据

如果你还记得我们最后一篇文章中提到的，TSP的基本输入只是一个要在一天内访问的站点列表。在这个样例中，我们使用的是巴黎，所以我选择了以下八个著名的、必去的地方：

• Sacre Coeur
• Louvre博物馆
• Montmartre山
• Port de Suffren
• 凯旋门
• 香榭丽舍大道
• 巴黎圣母院
• 埃菲尔铁塔

由于问题是找到一条最短距离的旅程，我们实际上需要的是距离数据，这取决于站点及其相对地理位置。如何从地理位置计算距离数据将在第四节中介绍，因为现在涉及到距离计算会让你分散注意力，无法集中在模型构建上。

因此，现在，请考虑你被给定了所有可能配对之间的距离。当我们在下一节用Python实现模型时，它们将以CSV文件的形式给出。数据如下：

我们将这个表格称为距离矩阵。请注意，虽然酒店不是特别照片级的，但它也被包含在矩阵中，因为它是需要在最终旅程中的另一个站点。对于这个MVP，我们保持简单，使用了对称距离矩阵，也就是说，从𝐴到𝐵的距离与从𝐵到𝐴的距离是一样的，对于任意的𝐴和𝐵。在更高级的设置中，这不一定会以相关的方式发生，从而使这种近似无效。

3. 从问题描述中确定一个概念模型

现在我们处于下面流程图中所表示的阶段：

概念模型的目的是用文字陈述问题，但以一种标准化的格式，以便后续阶段（数学模型构建）中“句子”和“数学对象”的映射变得清晰。我们可以这样设定我们的概念模型：

（了解）

数据（数据集和参数）：

• 要访问的网站列表
• 任意一对网站之间的距离

（我们需要决定）

决策：以什么顺序访问这些网站

（以一种方式）

目标：最小化总路程

（使得）

约束条件：：

• 访问所有网站
• 每个网站只能访问一次
• 访问的最后一个网站是我们起始的网站（进行闭合旅行）

👁️ 遵循良好的实践，在实践中，良好的结果将随之而来

你可能认为这个概念模型看起来非常琐碎，与我们开始时的“简单”问题陈述并没有太大区别。你是对的。对于这样的小问题，这可能是一个重复的步骤。但对于更大的问题，这个阶段是必不可少的，试图在没有概念模型的情况下建立数学模型通常会导致混乱（不明确或模糊的要求、糟糕的描述、有缺陷的代码、不可行的模型等）。因此，现在建立纪律并经历这个阶段非常重要，即使在我们的简单案例中边际价值非常低。注重良好习惯，良好结果会随之而来。

4. 从概念模型构建数学模型

我们刚刚达到了下面绿色部分的“第3阶段”。也就是“数学模型阶段”，可能是最具挑战性的阶段，这是自然语言变成数学的地方。

在这个阶段，甚至不允许有丝毫的模糊不清。

一个定义良好的数学模型价值百次澄清

在我们的工作流中的这个阶段，我们为TSP建立一个纯粹的模型，在接下来的阶段（在“sprint 3”中介绍）中，我们将借助Python根据前面解释的CSV数据集构建一个模型实例。

📝 理论复习：抽象模型 vs. 模型实例

数学模型（在OR中）由“组件”组成。这些是所有元素（方程、数据等）的集合，共同表示一定结构的问题。不管这些组件在任何给定示例中的具体数值如何，真正定义一个模型的是其结构，即这些组件如何相互关联。

模型实例是一个“抽象模型”的具体“实现”，具有具体数据。因此，通常我们先定义抽象模型，然后用特定场景的数据填充它们，从而生成模型实例。优化这些模型实例可以获得具体结果。

在下面的小节中，我将简要介绍构成模型的各个组件及其目的，同时进行定义。如果你不是初学者并且已经了解模型组件的功能，可以跳过这些解释，直接转到数学定义部分。

4.1. 将数据放入集合和参数

我们需要的所有数据都驻留在图2.1中显示的数据帧中。我们可以仅将数据保存在那里，在创建模型的约束和目标时从该数据帧中抓取所有数字。实际上，许多人这样做，但这是一个不好的习惯，随着模型的规模增长，它无法很好地扩展。随着模型复杂性的增加，这种方法需要越来越多的胶水代码（用于处理数据帧操作），如果数据保存在其他更适合构建优化模型的数据结构中，则可以避免这种情况。这些数据结构就是模型的集合和参数。

💡 不同的数据结构满足不同需求

如果你曾经纳闷“为什么要创建集合和参数，既然我们已经在表格中拥有所需数据？”，简短的回答是：这样做可以使模型构建更加简单、更加通用，而且减少错误。

“集合”用于存储问题的主要“实体”或“元素”，而“参数”则用于存储这些实体的数值属性，或者它们之间的关系的数值属性。在我们的例子中，网站是主要“实体”，因此它们将被存储在一个集合中，而站点之间的距离则是它们关系的“数值属性”，因此将被存储为参数。在“实施层面”上，进行这种分类也非常有用，因为每个组件都有不同的功能，这将使模型构建更加容易：

• 集合的功能是方便地存储和操作索引。这些索引是表示问题不同“实体”的ID或名称，它们被用来以方便的方式索引参数，以创建约束和目标。

• 参数的功能是方便地存储和操作“实体”数值属性，这些数值就是实际出现在约束和目标中的数字。

从我们的概念模型中，我们有：

• 要访问的网站列表，我们定义为集合 𝕊：

短语“以 𝑖, 𝑗 为索引”被放置在集合定义旁边，以表明每当模型中使用索引 𝑖 或 𝑗 时，它们代表 𝕊 的成员。这样，当我们有多个集合时，同时使用多个索引，就更容易记住每个索引的含义。

• 任意一对网站之间的距离，我们定义为索引参数 𝐷ᵢⱼ：

这个参数被称为“索引”，只是为了表示它不是一个标量参数（即一个单一数字），而是一个二维矩阵的数字。要从这个索引参数中获取一个数字，你需要指定两个索引 𝑖 和 𝑗，这两个索引又来自于集合 𝕊。

𝕊 和 𝐷ᵢⱼ 是概念模型中唯一的“数据组件”。但这并不限制我们在构建模型时提出其他有用的集合或参数。

作为示例，请注意 𝐷ᵢⱼ 的索引 𝑖 和 𝑗 是𝕊 的成员，但不能重合。如果它们重合，距离将是零，这是一个平凡的数据。此外，我们永远不会再次从一个地方到另一个地方，所以考虑（𝑖, 𝑖）对是没有意义的。因此，限制对（𝑖, 𝑗）可以采取的组合，可以使建模变得更容易（且错误更少）。为此，我们现在创建另一个从 𝕊 派生的集合 𝔸，其中包含所有不同站点之间的所有对（𝑖, 𝑗）。“弧（arc）”连接站点 𝑖 和站点 𝑗，因此使用了符号 𝔸。

📝 一条弧只是两个“节点”之间的“有向链接”。可以将弧(𝑖, 𝑗)看作是一个从𝑖开始到𝑗结束的向量。当两个节点之间的“链接”不是有向的（即方向无关紧要）时，使用“边”这个词，因为一直说“无向弧”会太啰嗦。图论中的人们也喜欢高效。

一个有趣的性质是𝔸是定义𝐷ᵢⱼ的定义域，并且在Python中实现模型时，明确定义这样的域可以使其在其他模型组件中重复使用，这也很方便。

• 不同站点之间可能的弧集合：

4.2. 在变量中进行编码决策

由于我们正在构建一个能告诉我们应该采取哪些行动的模型，而且在模型优化之前，这些预定的行动对我们来说是未知的，所以我们必须将所有可能采取的行动编码成变量。

那么我们如何定义这样的潜在行动呢？从我们的概念模型来看，我们需要做出的通用“决策”是“访问站点的顺序”。这个“顺序”指的是在进行旅游时我们可以遵循的所有可能路径中的一条。关键思想是，路径由连接单个节点（即站点）的一系列弧组成。因此，决定走一个特定的路径实际上就是决定穿越一系列特定的弧。我们希望将关于是否穿越连接两个站点的特定弧的“原子决策”编码为变量。

“是否从站点A到站点B”显然是一个二进制决策：我要走，还是不走。由于这种性质，决策变量需要是二进制的（即只取0或1作为值），并且仅对有效的弧进行定义（这就是派生的𝔸现在很方便的原因）。用数学术语来说：

每个可能的弧（𝑖, 𝑗）都有一个独特的决策变量，但当模型被优化时，我们只对取值为1的变量感兴趣，因为它们指示了应该穿越哪些弧。例如，如果变量𝛿ᵢⱼ，其中𝑖=酒店，𝑗=卢浮宫的值为1，这意味着我们应该作为旅游的一部分从酒店去卢浮宫。

4.3. 定义目标

假设我们有4个点，𝑎, 𝑏, 𝑐, 𝑑，并且我们按照路径𝑎 → 𝑏 → 𝑐进行旅游，其中点𝑑没有被访问。它的总距离是其弧距离的总和：𝐷ᵃᵇ + 𝐷ᵇᶜ。但是，如果我们不事先知道将要遵循的路径，我们如何表示这条未知路径的总距离呢？

💡 正是因为最优路径是未知的，我们需要一个涵盖所有可能路径的表达式，但当模型优化时，它将退化为“最佳路径”的距离。

通过利用任何遍历弧 (i, j) 将具有 𝛿ᵢⱼ = 1 的事实，以及任何未遍历弧 (i′, j′) 将具有 𝛿ᵢᑊⱼᑊ = 0，我们可以创建一个表达式，一旦变量被决定，就会缩小为遍历路径的总距离。方法是“将所有可能性相加”，即通过对所有可能的弧距离 Dᵢⱼ 进行加权求和，其中权重为它们的二进制“弧变量” 𝛿ᵢⱼ，并让这些变量采取的 0 和 1 决定哪些距离保留（Dᵢⱼ × 1 = Dᵢⱼ），哪些消失（Dᵢⱼ × 0 = 0），在总距离的表达式中。这个“可能性的总和”代表最终旅行将要走的总距离，所以我们的目标（称为 𝑍）是将其最小化。

在数学上，可以表示为：

注意，由于使用了𝔸，右侧的求和变得更简单易读（和实现）。

此外，注意这个目标构成了我们的好的定义。由于我们希望将其最小化，较低的数值比较高的数值更好，所以显然，最小值是最佳值。决策变量𝛿ᵢⱼ的值对应于这个目标的“最佳”值，它们将通过优化过程来找到。

4.4. 创建约束条件

根据我们的概念模型，我们有：

1. 所有站点都被访问。
2. 每个站点只被访问一次
3. 最后访问的站点是我们开始的站点（我们进行闭环游览）

我们意识到要求（1）已经“包含”在要求（2）中，因为如果每个站点只被访问一次，那就意味着每个站点都被访问了，因此所有站点都被访问了。所以我们不再需要单独对要求（1）进行约束，并集中在如何将要求（2）建模为约束上。

说“每个站点只被访问一次”等同于说“每个站点只被进入和退出一次”。而那个短语，又等同于这两个短语一起出现：“每个站点只被进入一次” 和 “每个站点只被退出一次”。让我们将这些“短语”分别建模为约束：

• 每个站点只被进入一次：

从右到左阅读整个表达式是有用的。如果你首先看看约束在哪些指数上定义，理解左侧约束定义的含义会更容易。我会大声读出这个约束：

对于属于所有站点集合 𝕊 的每个站点 𝑗，所有潜在弧的求和 𝛿ᵢⱼ 到达 𝑗 必须等于 1，意味着只能有一个 进入的 弧发生于 𝑗。或者更通俗地说：每个站点只能从一个其他站点访问。

• 每个站点仅一次退出:

我会将这个约束理解为：

对于属于所有站点𝕊的每个站点𝑖，从𝑖出发的所有潜在弧𝛿ᵢⱼ之和必须等于1，这意味着只能发生一个外向弧在𝑖上。或者，更口语化一些：每个站点只能前往一个其他站点。

我们只剩下要求(3)。它规定了最优路径必须以其起始站点结束，或者等效地说，路径必须是一个闭环。以下是我们在第一眼看到时可能有的一种推理思路：“因为我们已经创建了约束来强制每个站点进入和退出一次，这意味着结果路径必须是闭合的，因为任何站点都不可能是一个“汇点”（即一个站点具有一个入弧但没有出弧）或者是一个“源点”（即一个站点具有一个出弧但没有入弧） 。因此，前两个约束，可能会迫使最终轨迹成为一个闭环”。

这种推理逻辑正确吗？让我们采取实验的方法。让我们假设这种推理是正确的，然后尝试解决当前的模型。当我们查看解决方案时，我们会看到它是否正确或是否有问题。 如果结果是错误的（或以任何方式不合理），我们始终可以返回并修正我们的逻辑（在现实项目中经常发生的事情）。我们的“下一个迭代”将涵盖实施、求解和“实验验证”，其中将创建、求解、检查和根据我们获得的结果进行重新建模的Python模型。

因此，我们在此（暂时）结束“数学模型制定”的阶段。下一站：在使用Python实现、求解和可视化旅行商问题。

将会有更多“迭代”的文章发布，所以如果你渴望成为我在这个旅程中的伴侣，请保持关注并在第3节的“项目时序表”中查看此系列中的第一篇文章，以导航到您感兴趣的迭代并关注正在进行的工作。

此外，随时关注我，通过评论问我问题，给我反馈，或在LinkedIn上联系我。

感谢阅读，我们在下一篇见！ 📈😊

参考资料：

• Wikipedia。旅行商问题