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

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

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

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

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