摘要通過(guò)對(duì)某運(yùn)輸公司為10個(gè)客戶配送貨物問(wèn)題的研究，把根據(jù)給定的路線距離矩陣制定合理的行駛路線問(wèn)題轉(zhuǎn)化為圖論中的最短路徑問(wèn)題。建立了求解每對(duì)頂點(diǎn)之間的最短路徑模型，采用Floyd算法，并編寫了相應(yīng)的程序，求出了任意一個(gè)客戶到客戶10的最短路線，具體路線見(jiàn)表一。采用圖論中的旅行商(TSP)問(wèn)題求解一個(gè)貨車從提貨點(diǎn)出發(fā)給10個(gè)客戶配送完貨物后再回到提貨點(diǎn)的盡可能短的行駛路線，并用近似算法去尋求近似最優(yōu)解，總的行走路程為230公里。

關(guān)鍵詞圖論Floyd算法最短路徑TSP

中圖分類號(hào):F50文獻(xiàn)標(biāo)識(shí)碼:A