华东交通大学学报
華東交通大學學報
화동교통대학학보
JOURNAL OF EAST CHINA JIAOTONG UNIVERSITY
2012年
5期
29-33
,共5页
组合优化%旅行商问题%NP-Hard%简化模型
組閤優化%旅行商問題%NP-Hard%簡化模型
조합우화%여행상문제%NP-Hard%간화모형
目前关于旅行商问题的启发式算法主要分为两类:环路构造算法和环路改进算法.通过对两类近似算法的深入研究,提出了一种新的方法――简化模型法来求解旅行商问题.该方法通过排序和选择操作得到原网络图的简化模型,对简化模型中的路径进行重构得到旅行商问题的解.通过测试TSPLIB中的实例,表明用简化模型法求解旅行商问题解的质量高、收敛快,时耗小,该算法是实用的.
目前關于旅行商問題的啟髮式算法主要分為兩類:環路構造算法和環路改進算法.通過對兩類近似算法的深入研究,提齣瞭一種新的方法――簡化模型法來求解旅行商問題.該方法通過排序和選擇操作得到原網絡圖的簡化模型,對簡化模型中的路徑進行重構得到旅行商問題的解.通過測試TSPLIB中的實例,錶明用簡化模型法求解旅行商問題解的質量高、收斂快,時耗小,該算法是實用的.
목전관우여행상문제적계발식산법주요분위량류:배로구조산법화배로개진산법.통과대량류근사산법적심입연구,제출료일충신적방법――간화모형법래구해여행상문제.해방법통과배서화선택조작득도원망락도적간화모형,대간화모형중적로경진행중구득도여행상문제적해.통과측시TSPLIB중적실례,표명용간화모형법구해여행상문제해적질량고、수렴쾌,시모소,해산법시실용적.
