摘 要：本文注焦“環(huán)游熱”的現(xiàn)象，改進經(jīng)典的Hamilton圈圖論模型，為旅行者們設(shè)計了一條環(huán)游中國31個省會城市的最優(yōu)線路。模型建立方面，本文在傳統(tǒng)的Hamilton圈模型中巧妙地融入0-1變量，使優(yōu)化模型更加簡單、直觀、高效；模型求解方面，創(chuàng)造性地將Lingo程序和Excel表格交互使用，直觀、便捷地輸出了城市之間的連接關(guān)系和最優(yōu)旅行線路，從而提供了一種Lingo程序處理大數(shù)據(jù)的可視化方法。

關(guān)鍵詞：Hamilton回路；設(shè)計；優(yōu)化

中圖分類號：TP301.6

近幾年來，隨著人民生活水平不斷提高，我國旅游業(yè)的發(fā)展突飛猛進，甚至出現(xiàn)了很多人“辭職”、“休學(xué)”、“休間隔年”來環(huán)游中國的現(xiàn)象。但由于時間和費用仍然是限制旅行計劃的兩大因素，且我國幅員遼闊，交通線路復(fù)雜，因此想要環(huán)游中國，旅游線路的規(guī)劃十分重要。本文假設(shè)一位旅行者想要一次性游覽完中國31個省會城市（因涉及通行證等問題，港澳臺除外），為該旅行者設(shè)計一個最優(yōu)的旅行線路，因為行程的花費和時間主要取決于城市之間距離的遠(yuǎn)近，且不同的人對交通方式的選擇有不同的偏好，所以這里的最優(yōu)旅行路線簡化為求連接31個城市總距離最短的旅行線路。這是一個典型的旅行商問題。旅行商問題（Traveling Salesman Problem，TSP），又稱貨郎擔(dān)問題，最早由Dantzig等人在1954年提出，用于解決一個商品銷售員要去美國主要的49個州的首府城市推銷產(chǎn)品，該銷售員從一個城市出發(fā)，經(jīng)過所有城市后，回到出發(fā)地，如何選擇路線使總行程最短的問題[1]。

主流解決旅行商問題的方法是借助圖論中Hamilton回路：給定無向的完全或不完全圖G（V，E）（V為城市點集；E為邊集，指兩兩城市之間的旅行代價）以及邊代價d（e）（e∈E），尋求G的一個使邊代價之和最小的Hamilton圈。旅行代價可以指時間、距離或者金錢花費等[2]。

本文利用Hamilton回路的思想解決環(huán)游中國最短旅行路線問題。定義一個圖G（V，E），旅行者游覽的31個省會城市抽象為圖G中的31個頂點，構(gòu)成城市點集V；以兩兩城市之間的實際距離為旅行代價。根據(jù)Hamilton回路的定義，目標(biāo)線路經(jīng)過且不重復(fù)經(jīng)過每一個頂點，即每一個頂點只有一條線路進入、一條線路出去，且除起點與終點外，各邊不構(gòu)成圈。于是尋求環(huán)游中國最短旅行路線的問題轉(zhuǎn)化成了求總距離最短的Hamilton圈。

1 Hamilton回路優(yōu)化模型

旅行商問題目前沒有有效的算法求解，屬于NP完全問題。由于在尋找環(huán)游中國最短旅行路線這個問題中，圖G的頂點個數(shù)不算大，于是根據(jù)Hamilton回路的定義建立了一個0-1整數(shù)規(guī)劃優(yōu)化模型[3]，公式（1）為目標(biāo)函數(shù)，公式（2）—（5）為約束條件。

2 Lingo程序設(shè)計

首先，計算31個城市兩兩之間的距離矩陣Dij。通過查詢每個城市的經(jīng)緯度，并用經(jīng)緯度測距公式（公式（6））算出dij，將矩陣Dij存于Excel表格“城市距離.xlsx”的 distance矩陣，以便Lingo快捷、方便地使用數(shù)據(jù)，從而免去將這31×31個龐大的數(shù)據(jù)直接輸入到Lingo程序中的繁瑣與不便。由于數(shù)據(jù)龐大，本文只給出部分distance矩陣截圖，如圖一。

利用Excel表格名稱編輯器，建立一個與距離矩陣Dij格式相同的連接關(guān)系矩陣Xij ，存于Excel表格的line矩陣，用于接收Lingo程序運行后的兩兩城市之間連接關(guān)系變量xij的返回值，以便直觀地判斷回路路徑。模型建立與求解的Lingo程序如下：

通過line矩陣中兩兩城市之間的0-1變量值，得到的最短路徑下31個城市之間連接關(guān)系為：南京→上?！贾荨Ｖ荨喜錆h→長沙→廣州→?？凇蠈帯ッ鳌?貴陽→重慶→成都→拉薩→烏魯木齊→-西寧→蘭州→銀川→西安→鄭州→石家莊→太原→呼和浩特→哈爾濱→長春→沈陽→北京→天津→濟南→合肥→南京（這里假設(shè)出發(fā)點為南京，因為Hamilton圈是一個閉合圈，所以出發(fā)點可以使31個城市中的任意一個），即該路徑為總距離最短的旅行線路，最短總距離為：D=15075km。在地圖上繪制出實際線路圖（如圖四）：

參考文獻：

[1]G Dantzig，R Fulkerson，S Johnson.Solution of a Large-Scale Traveling-Salesman Problem[J].Journal of the operations research society of America，1954（04）：393-410.

[2]聶義勇，貴剛，宋翔.整數(shù)規(guī)劃基礎(chǔ)[M].沈陽：東北大學(xué)出版社，2001.

[3]謝金星，薛毅.優(yōu)化建模與LINDO/LINGO軟件[M].北京：清華大學(xué)出版社，2005：297-302.

作者簡介：蒲星月（1993-），女，四川成都人，本科在讀，研究方向：統(tǒng)計學(xué)、運籌學(xué)。

作者單位：天津商業(yè)大學(xué)，天津 300134