螞蟻記憶系統結合鄰域搜尋法應用於車輛途程問題

被引：1

作者：

林大傑

吳啟綸

邵宜邦

机构：

[1] 逢甲大學运输科技管理学系

来源：

交通信息与安全 | 2011年 / 06期

关键词：

螞蟻演算法; 車輛路徑問題; 啟發式演算法; 鄰域搜尋法;

D O I：

暂无

中图分类号：

U491 [交通工程与交通管理];

学科分类号：

082302 ; 082303 ;

摘要：

以螞蟻記憶系統為基礎搭配不同的鄰域搜尋法做區域搜尋來應用於車輛途程問題。先以2-opt、根據2-opt增加交換節線的or-opt及改良交換法的Lin-Kernighan做途程內交換,選擇和已知最佳解誤差百分比最少的2-opt做改善,再計算記憶盒中較佳路線之重心,並從運量最少路線開始做區域改善,以其重心為基準對附近路線做途程內2-opt及途程間Swap的交換,如此將能有效降低區域改善的時間,進而提升求解效率。利用國際標竿例題來驗證AMS之求解效率,在隨機問題C1～C10求解平均誤差為0.98%,在叢聚問題C11～C14求解平均誤差為0.55%。

引用

页码：135 / 138

页数：4

共 5 条

[1]

An improved antcolony optimization for vehicle routing problem. Yu B,Yang Z Z,Yao Baozhen. European Journal of Operational Research . 2009

[2]

A new hybrid ant colony optimiza-tion algorithm for the vehicle routing problem. Zhang X,Tang L. Pat-tern Recognition Letters . 2009

[3] An improved ant system algorithm for the vehicle routing problem [J].

Bullnheimer, B ;

Hartl, RF ;

Strauss, C .

ANNALS OF OPERATIONS RESEARCH, 1999, 89 (0) :319-328

[4]

Ant system:optimization by a colony of cooperating agents. Dorigo M,Maniezzo V,Colorni A. IEEE Transactions on Systems Man and Cybernetics . 1996

[5]

Applying theant system to the vehicle routing problem. Bulleneimer B,,Hartl R F,Strauss C. Proc.of the Second Internat.Conf.on Metaheuris-tics . 2007

← 1 →