里特城消防队的最短路问题及其解决方案

里特城（Littletown）是一个农村小镇，它的消防队要为包括许多农场社区在内的大片地区提供服务。在这个地区里有很多条路，从消防站到任何一个社区也有很多条路线，所以时间是消防站到达火灾发生点的主要因素。因此，消防队队长希望事先能够确定从消防站到每一个农场社区的最短路。图6-37 标示了连接消防站和其中一个农场社区的道路系统，图中包含了每条路的英里数。你能够找到从消防站到这个农场社区的最短路线吗？

图6-37

里特城的消防站和某一农场社区间的道路系统，其中 A，B，…，H是交叉口，每条路旁边的数字表示单位为英里的距离。

图6-38 给出了该问题的网络规划，但忽略了布局时路的弯曲情况。消防站和农场社区分别用O 和T 表示。关于这个问题（和任意一个最短路问题一样），可以认为是最小费用流问题的一种特殊类型，在这里，行进的英里数可以解释为网络中流的成本，从消防站到这个农场社区的某一行程可以解释为所选择的网络路径中流量为1的流。所以，使得该流成本最低就等价于使得该路线的行程英里数最少。消防站看成一个供应量为1的供应点，代表此次行程的开始；农场社区看成需求量为1的需求点，代表此次行程的结束，这是因为图3-38中所有其余的节点都是转运点，毎一个节点所产生的净流量都为0。

(www.xing528.com)

图6-38　最短路问题的网络规划模型

根据这一解释，图6-39 是根据上述问题描述给出的电子表格模型。对于每一条被选中的从消防站到农场的路，可变单元格OnRoute（D4：D27）给出的流量为1，表示对应的弧被选为从消防站到这个农场的路，反之，0 则表示没有被选中。目标单元格TotalDistance（D29）给出了该路线以英里为单位的总距离。B 列和C 列将图6-42中所有垂直连接列出了两次，一次为向下的弧，一次为向上的弧，这是因为在所选的路上，两个方向都允许通过。其他的连接只列出了从左到右的弧，因为这是唯一符合从源到目标地要选择最短路要求的方向。K 列显示了每个节点需要产生的净流量。使用该图底部的方程式，将I 列每一个单元格都加上流出量并减去流入量，得到通过该节点的实际净流量。对应的限制条件，即Nodes（H4：H13）=SupplyDemand（K4：K13），在Solver的对话框里进行定义。OnRoute（D4：D27）给出的解是点击Solver 按钮后得到的最优解。

图6-39

利特城消防队最短路问题的电子表格模型，包括目标单元格TotalDistance（D29）和其他输出单元格SupplyDemand（K4：K13）的公式，其中可变单元格OnRoute（D4：D27）的值1表示通过Solver 得到的最优解，从消防站到农场社区的最短路的总距离为19 英里。

虽然我们可以用特殊算法来解决最短路问题，而且也非常有效，但Excel Solver 软件屮没有给出这些算法。用电子表格构建并用Solver 软件来解决像里特城问题这种规模和较之稍微大一点规模的问题是很好的，但是必须注意到规模非常大的问题仍然需要用其他的方法来解决。