中國城市TSP問題求解系統(tǒng)的設(shè)計、實現(xiàn)與應(yīng)用.pdf

1、TSP (旅行商）問題既是組合優(yōu)化問題又是經(jīng)典的NP難問題，在計算機科學中具有十分重要的意義。以實際的城市開展TSP問題的求解具有很好的實用價值。文獻和資料調(diào)研表明，已經(jīng)有美國、瑞典、德國等一些有代表性國家的城市TSP問題求解結(jié)果發(fā)布，但是目前還尚未見關(guān)于中國城市TSP問題的系統(tǒng)化求解探索。
　　本文對TSP問題進行了較為全面的調(diào)研和綜述，對求解TSP問題較為前沿的啟發(fā)式算法Lin-Kernighan和Concorde(CPLEX

2、)進行了介紹，基于此算法設(shè)計和實現(xiàn)了一個中國城市TSP問題求解系統(tǒng)。系統(tǒng)實現(xiàn)了數(shù)據(jù)獲取、路徑計算、數(shù)據(jù)展示、自定義旅游、TSP路徑展示、用戶管理、微信管理等七個功能模塊，系統(tǒng)能夠展示全國省會城市、全國地級市、各省地級市、各省縣級市的TSP求解過程、求解結(jié)果及百度地圖顯示。自定義旅游功能能夠根據(jù)用戶自選的城市或地點進行TSP路徑求解，包括駕車時間最短和駕車路徑最短兩種路徑定義。微信管理功能能夠讓用戶通過關(guān)鍵詞得到對應(yīng)TSP路徑二維碼。系統(tǒng)

3、提供了大量的城市數(shù)據(jù)，方便用戶查詢城市之間的距離和城市信息，具有通用性和實用性的特點。
　　中國城市TSP問題求解系統(tǒng)開發(fā)采用瀑布流模型，使用百度API進行城市之間的路徑計算，前端頁面采用BootStrap進行響應(yīng)式設(shè)計，運用JavaScript的面向?qū)ο笏枷?，使用MyEclipse+Tomcat作為開發(fā)環(huán)境和模擬服務(wù)器。
　　系統(tǒng)首先分析中國城市TSP問題求解系統(tǒng)的開發(fā)背景與實際意義。其次介紹系統(tǒng)的需求分析、總體設(shè)計、詳細

4、設(shè)計、數(shù)據(jù)庫設(shè)計。在需求分析階段，從用戶角度，通過各模塊的用例圖和用例規(guī)約描述表對系統(tǒng)進行詳細的功能需求分析，從系統(tǒng)開發(fā)角度，根據(jù)系統(tǒng)的特性對系統(tǒng)進行非功能需求分析；系統(tǒng)總體設(shè)計過程中將系統(tǒng)的體系結(jié)構(gòu)抽象為界面層、功能層及數(shù)據(jù)層，并通過網(wǎng)絡(luò)拓撲圖和結(jié)構(gòu)功能圖對系統(tǒng)的總體設(shè)計進行物理結(jié)構(gòu)和功能結(jié)構(gòu)展示；詳細設(shè)計階段，通過類圖和時序圖對系統(tǒng)模塊進行詳細設(shè)計，并設(shè)計出實體類和聯(lián)系；系統(tǒng)數(shù)據(jù)庫采用關(guān)系型數(shù)據(jù)庫，針對13實體類和15個聯(lián)系利用第三