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

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

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

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

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