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

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

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

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

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