用Excel强势求解TSP

哈喽，很久不见，转眼又到了5月了，小编最近总是在忙东忙西，不过还好，小编就在昨天找到了在大学中最重要的人，好开心。

今天小编给大家带来的Excel模型就是用Excel来求解帮助我们做决策，该模型最为典型的就是“货郎担问题”，“中国邮递员问题”。

中国邮递员问题：

1962年中国数学家管梅谷先生提出中国邮递员问题(简称CPP)，是著名图论问题之一。一个邮递员从邮局出发，要走完他所管辖的每一条街道，可重复走一条街道，然后返回邮局。任选择一条尽可能短的路线。

货郎担问题（TSP）：

货郎担问题也叫旅行商问题，即TSP问题(Traveling Salesman Problem)，是数学领域中著名问题之一。其一般提法为:有n个城市，用1，2，…，n表示，城i,j之间的距离为dij，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短?

旅行商问题的提法为:假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

该类型的问题虽产生的年代久远，但放到今天其仍然可以广泛应用于某些特定的领域，如销售人员销售路径问题，仓库内拣货路径的优化和盘点路线的选择。

【案例回放】求解四个城市面上旅行推销员问题,其距离矩阵如表5-3所示,当推销员从城市1出发,经过每个城市一次且仅一次,最后回到1城市,问应该按照怎样的路线走,才能使得总的行程最短?

求解步骤如下：

这里用到了index返回查询函数，且出发点的1和终点的1是手动打上去的

1.这里涉及到的index返回从不同点到不同点的距离

2.“到”下面的单元格是手动打上1，2，3，4,最后一个是要返回到原点所以是1，“从”下面的字除了第一个1是打上去的，其它都是引用到那边的数据。

3.对总距离求和，最短路径用最小值，下面进行规划求解，注意其约束条件。

4.最后求解结果和路径选择

▼

冰点文库：

链接：https://pan.baidu.com/s/17TCl45LXztmR3CHOMYXYJA

密码：z2fm

豆丁当当：

链接：https://pan.baidu.com/s/1odnAhqJ7wgWvHrQvOXKoAA

密码：78go