你真的掌握了TSP的精髓吗？

本文共计1009个文字，预计阅读时间需要5分钟。

+ 整数规划 模型 2022年5月26日 + TSP问题 + 一个快递员，他每天负责110个客户的家门口送一单报纸，他希望走最短的总路程来完成配送任务，这正是TSP问题最原始的场景。用理论描述即是……

​整数规划-模型

2022年2月26日

TSP问题

有一个邮递员，他每天负责向100个客户的家门口送一份报纸，他希望走最短的总路程来完成配送任务，这是TSP问题最原始的场景。用理论描述就是：找一个路径最小的哈密顿回路（Hamiltonian cycle） 。

哈密顿回路：也称为一笔画问题，就是从一个点出发不重复的走完所有的点，最后在回到出发点。我们现在希望为邮递员找到这个最短的哈密顿回路。

求解

关于求解TSP问题的方法，有很多，但是他们之间的效率也是千差万别，比如我们本篇推文介绍基于整数规划的一类求解思路这也是最主流的效果最好的，可以拓展到非常大的规模的一类解法，可以说是正统解法，当然还有其他解法，比如动态规划等，这里先挖一个坑，有时间小编一定把动态规划的思路的代码一同奉上。

模型

这里我们提供两个模型，分别是对称TSP和非对称TSP，假设我们我们将报亭标号为1，且客户的数量加上报亭一共为n；cij表示从i到j的距离。