基于Hamilton回路的環(huán)游中國(guó)最優(yōu)路線設(shè)計(jì)及Lingo實(shí)現(xiàn)

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

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

中圖分類號(hào)：TP301.6

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

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

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

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

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

2 Lingo程序設(shè)計(jì)

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

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

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

參考文獻(xiàn)：

[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].沈陽(yáng)：東北大學(xué)出版社，2001.

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

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

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