Excel求解旅行商問題及實現(xiàn)

劉芊

摘要：旅行商問題歷來是大家感興趣的一個難題，對其求解也有各種算法。Excel中規(guī)劃求解也是有效解決問題的方案之一，通過介紹其基本原理，求解思路和在旅行商問題中的具體實現(xiàn)步驟，希望能對讀者學習Excel的高級應用有很好的借鑒作用。

關鍵詞：旅行商問題；規(guī)劃求解；加載宏

1 引言

旅行商問題（TSP），是假設一個旅行商出于業(yè)務需要，要到N個城市去，那么如何找出一條最佳的路徑使其能既經(jīng)過每個城市，又路徑最短。旅行商問題在實際工作中有很多具體應用，如貨物配送、家用管網(wǎng)規(guī)劃、網(wǎng)絡路由選擇等。該類問題與普通的求最短路徑的根本區(qū)別是：既要經(jīng)過已知的所有節(jié)點，又要從起點到終點形成封閉回路，在滿足這兩個前提下路徑最短。對于較大規(guī)模的該類問題，需要通過智能算法（蝙蝠、蟻群等）求解，對于一定規(guī)模的旅行商問題可采用Excel的規(guī)劃求解來解決。

2 方法概述

規(guī)劃求解是Excel的“可使用加載宏”的一種，它能夠?qū)Υ嬖诙鄠€變量的線性或非線性問題求解，以求出最優(yōu)值。通過規(guī)劃求解，可以幫助用戶得到最優(yōu)的設計方案。其工作原理是可以設計多個可調(diào)整的單元格，給出這些單元格需遵守的約束條件，同時給出目標單元格的公式，通過改變可變單元格的值，求出目標單元格的最大值、最小值或指定值。

3解決方案：

以下圖為例，共有A、B、C、D、E、F六個城市，它們之間的路徑及距離如圖1所示

3.1 打開Excel 2010，建立一個工作簿，名為“旅行商問題”

3.2 在C4：C19單元格，用“9999”來替換“-”，如圖所示，該步驟是給不存在的路徑用一個很大的數(shù)來表示，防止以后選擇該路徑。

3.3 建立解決模型，如下圖所示。

在以上模型中，我們用“來源唯一性”限制出發(fā)地，用“目標唯一性”限制抵達地，以確保都任何時候只能走一條路徑，不能同時存在多條路徑。

打開Excel 2010的“加載宏”選擇，選擇其中的“規(guī)劃求解加載項”前的復選框，然后“確定”，操作后我們再打開“數(shù)據(jù)”選項卡，就能看到“規(guī)劃求解”。

給單元格輸入公式，其中，I14 單元格 =sum（c14：h14），填充I15：I1

C20 單元格=sum（c14：c19），填充D20：H20

J14 單元格 =sumproduct（c4：h4，c14：h14），填充J15：J19

J20 單元格 =sum（j14：j19）

C14：H19 的“單元格格式”我們可以設置為“數(shù)字”，選擇“自定義”中的“0”，我們用該區(qū)域表示實際路徑的選擇情況，選擇即為“1”，不選即為“0”，然后對應出發(fā)地、抵達地，形成一條回路。這個區(qū)域是可變區(qū)域，代表了不同路徑的組合可能，J20是規(guī)劃求解的目標單元格，即總路徑，在這里，根據(jù)題意我們給J20選“最小值”。

3.4 觀察求解結(jié)果，可以看到，選擇的路徑是：C-A-C，B-D-B，E-F-E，它們不能形成封閉回路，所以不符合要求，為解決這個問題，我們需要加上限制條件，防止返回情況發(fā)生，也就是E14和C16不能同時為“1”，F(xiàn)15和D17不能同時為“1”，H18和G19不能同時為“1”

在下面可選C23：C25輸入這些“添加條件”，C22單元格錄入“添加條件”，C23至 C25錄入公式。

C23單元格 =E14+C16

C24單元格 =F15+D17

C25單元格 =H18+G19

3.5 繼續(xù)規(guī)劃求解，可以在“規(guī)劃求解參數(shù)”對話框中增加約束條件，設置C23：C25<=1

3.6 得出新的規(guī)劃求解結(jié)果，如下圖所示。

3.7 經(jīng)觀察，這次求得路徑為B-A-C-B，D-F-E-D，仍讓沒有形成閉合回路，那就要同上增加新的約束條件，C26單元格=D14+E15，C27單元格=F19+G17，

3.8 然后重新設計“規(guī)劃參數(shù)”，如下圖所示。

3.9 得出最優(yōu)的規(guī)劃求解結(jié)果，如下圖所示。

3.10 觀察下，這次形成的路徑是B-D-F-E-C-A-B，為封閉路徑，符合要求，那么旅行商路徑即為B-D-F-E-C-A-B，反向路徑B-A-C-E-F-D-B 也是旅行商的解，路徑長同為250。

4 結(jié)束語

用Excel2010求解旅行商問題及實現(xiàn)如上分析，具體節(jié)點數(shù)不同，數(shù)據(jù)不同，求解過程會有差異，但總體思路是一致的，根據(jù)具體路線，有繁有簡，實現(xiàn)的步驟也會略有差異。

參考文獻：

[1]金曉龍. Excel高級應用實例教程，2012第一版：144-150