使用Excel计算最优路径
使用Excel计算最优路径
假设陆家嘴地区的快递员要从国金中心出发，跑完以下5个大楼后再回到国金中心：国金中心, 金茂大厦, 上海中心, 环球金融中心, 正大广场。那么是不是存在一个最优的路径，在完成目标的同时让总里程最低呢?这就是经典的TSP问题 (traveling salesperson problem) 。我们今天就来看怎么使用Excel计算最优路径。
我们在下面的双向表格中列出了5个大楼之间的相互距离（为简化演示，采用的是直线距离），比如最近的距离是上海中心和金茂大厦的200米，最远的距离是正大广场和环球金融中心的860米。将D3:H7区域命名为“距离”，方便后续写公公式。在C10:C14随机输入一个初始顺序，这里我输入的是1，5，2，3，4。意思是第一段旅程是从1号目标国金中心出发到5号目标正大广场；第二段旅程是从5号目标正大广场出发到2号目标金茂大厦。。。以此类推。在E10输入=VLOOKUP(C10,$B$3:$C$7,2,0)，根据序号把大楼名称匹配出来，填充到E14。
在D10输入=@INDEX(距离,C14,C10)，此公式取的是"距离"（也即D3:H7）里的第4行，第1列。取到的是环球金融中心到国金中心的距离590，这个其实是配送员从最后一站返回起始站的距离。在D11输入 =@INDEX(距离,C10,C11)，此公式取的是"距离"（也即D3:H7）里的第1行，第5列，取到的是国金中心到正大广场的距离260，这个是配送员的第一段旅程的距离。公式向下填充到D14。在D15输入 =SUM(D10:D14) 计算总距离，这里我们可以看到此随机设定的方案总距离是1870米。
设置目标为D15, 也就是总距离，我们要找最优路径也就是总距离要最小。可变单元格设置为C10:C14, 也就是让Excel更改推荐顺序。约束条件选择C10:C14后再选dif，这样就是告诉Excel重新排列顺序，但是不能有重复。
设定好后让规划求解运行，根据电脑配置和模型复杂度，通常可能需要20几秒。最终Excel提示找到如下最优解（可能有多种最优解）：如上图，规划求解跑出来的这个方案总距离是1680，相较我们之前随机设置的方案有明显改善。如何理解这一方案：顺序1在第14行，意思是 从1号目标(国金)出发，先到2号目标(金茂)，再到4号目标(环球)，再到3号目标(上海中心)，再到5号目标（正大），最终返回1号目标。最优路径计算同样适用于员工多城市出差的最优成本规划，PCB打孔的最优路径规划等等场景。
本文来自网友投稿或网络内容，如有侵犯您的权益请联系我们删除，联系邮箱：wyl860211@qq.com 。
