excel求解规划旅行路线问题

 

excel求解规划旅行路线问题

 

它的路线需要经过网络中的所有节点，并且最终形成回路。对于每个节点来说，都要被访问到而且只访问一次，同时对于某个节点来说，访问者的来源必定是唯一的。某送奶工每天从配送出发需要送奶至6个不同位置的小区，然后将6个地方收集来的空瓶再送回配送点，通过长时间的观察记录，送奶工将6个小区之间骑行所需的平均时间整理如下图所示，其中配送点就设立在A小区附近，因此可以将A小区视作出发点。现在送奶工想要知道，如何规划一天的送奶路线，可以使得花费在路上的时间最少。此问题即为一个典型的旅行商问题，可以用Excel规划求解工具来解答，方法如下：

1）根据题目需求，在原有题目条件的下方建立规划求解所需的公式模型，如下图所示，其中C12：H17单元格区域用于记录实际的路径选择情况，可以用数字0表示路径未选择，用数字1表示选择从某地出发前往另一地。此区域将作为规划求解的可变单元格区域。但需要注意的是：其中A小区至A小区、B小区至B小区等类似的路径在实际中是不存在的，因此在规划求解时需要保证C12、D13…H17等单元格的取值不可为1。1列用于统计抵达各地点的来源的数目。根据旅行商问题的特性，每个地点的访问来源地是唯一的，在I12单元格内输入公式“=SUM（C12：H12）”，然后向下复制填充至I17单元格。第18行用于统计各出发地前往目的地的数目，根据旅行商问题的特性，每个出发地的目标地点也是唯一确定的，在C18单元格内输入公式“=SUM（C12：C17）”，然后向下复制填充至H18单元格。J列用于统计访问路线确定的情况下各条线路所需的时间，可以在J12单元格内输入公式“=SUMPRODOCT(C3:H3,C12:H12)”, 然后向下复制填充至J17单元格。J18单元格用于累计J12：J17单元格中的时间，即走完整条送奶路线总的时间，可以在单元格中输入公式“=SUM(J12:J17)”，此单元格将作为规划求解的目标单元格；

2）为了提高规划求解结果的可读性，可以预先将C2：H17单元格区域的数字格式自定义为“0”。
3）选中J18单元格，单击菜单[工具]—[规划求解]打开“规划求解参数”对话框，在“设置目标单元格”文本框中选择J18单元格，选中“最小值”单选按钮，在“可变单元格”文本框中选择C12：H17单元格区域；
4）单击“添加”按钮打开“添加约束”对话框进行约束条件的添加，本例中所包含的约束条件如下：条件1：C12：H17为二进制数、条件2：I12：I17=1、条件3：C18：H18=1。在条件1中将可变单元格C12：H17的约束条件设置为二进制数，可使其取值在0-1之间变化。要将目标约束为二进制数，可以在“添加约束”对话框中间的条件下拉列表不选择“bin”。各个条件添加完成单击“添加约束”对话框中的“确定”按钮返回“规划求解”对话框，如果如下图所示。

5）C12、D13…H17这6个单元格的取值需要限定为0，可以在上面的“规划求解参数”对话框中继续添加约束条件。还有一种更简单的方法是将原条件区域中的C3、D4…H8这6个对角单元格的值改为远远大于其他路线时间的数值，使得规划求解过程中不可能选取到A-A、B-B这样的路径。例如在本例中可以在这6个对角单元格中填入“999”，如下图所示。

6）单击“规划求解参数”对话框中的“求解”按钮开始求解运算过程，并显示找到一个结果，单击“规划求解结果”对话框中的“确定”按钮可以保存此结果，如下图所示：

当前规划求解找到一条最短的路线方案，考察这条路线的具体走法，如果能够形成一个独立的封闭回路，即从A小区出发能够访问到其他5个小区最后再返回A小区，说明此路线即为满足题目要求的最佳路线方案，否则需要根据情况继续规划求解过程以求取满足条件的答案。通过上图中的解答可以发现，当前解法路线包含两个独立的回路（反向同样成立）：

显然存在上述两条回路的情况下无法满足从A点出发遍历完所有节点再返回A点的要求，因此需要进一步地查找合理的解答，同时通过当前解答也可以知道，此问题的最终合理路线方案的开销时间应该大于等于目前的结果49。
要将当前的求解结果最终调整为单独的一条回路，需要拆分目前两条回路中的一条。可以从其中的较短的一条回路“”入手，采用人为设置障碍的方法，使得“”的路线不可选或“”的路线不可选，相当于宣布“此路不能”，从而打断原有的回路，让规划求解找到更合理的最佳路线。由此这个规划求解问题分成了下面的两个分支，即分别寻求B至D不通和D至B不通情况下的最短路线方案。
分支1：D至B路径不通。
要设置人为障碍使得D至B的路径不通，可以在题目条件区域中将F4单元格的数值设置为相当大的一个数，如999，也可以直接添加约束条件限制F13单元格的取值。
7）单击菜单[工具]—[规划求解]打开“规划求解参数”对话框，在原有规划求解参数的基础上继续添加约束条件，条件4：F13=0，如下图所示；

8）单击“求解”按钮开始求解运算过程，并显示找到一个结果，单击“规划求解结果”对话框中的“确定”按钮可以保存此结果，如下图114所示：

从当前找到的分支结果来看，全局路线形成了一条完整的封闭回路（反向同样成立）：

路径满足题目要求，同时此路线方案的时间开销总计为55，然后记录下此结果留待对比。
分支2：B至D路径不通。
要设置人为障碍使得B至D的路径不通，同样可以通过修改题目条件或增加约束条件，需要注意的是，在改变题目条件或增加约束条件之前，同时需要恢复之前所设置的D至B路径不通的条件，最后得到的结果如下图所示：

从现在找到的分支结果来看，全局路线仍然分成两条独立的回路。

同时当前的路线方案时间开销总计为59，如果继续在此基础上寻求单一回路的方案，其时间总开销必定比59更大，更大于第1个分支的结果55，因此第2个分支的路线方案结果必不会优于第1个分支的路线方案。
由此可以判断，最佳路线为以下路线或者其相反方向。