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

摘要

蚂蚁演算法于1996年发表至今不过几十年，但在求解效率上与其他发展已久的演算法相较毫不逊色，代表其非常适合求解路径问题，且回顾蚂蚁演算法应用於车辆途程相关文献可以发现以下两个特徵，大多文献提出改良方法大多着重於区域搜寻，其次是在全域费洛蒙公式做调整。rn 本研究主要目的是以蚂蚁记忆系统为基础搭配不同的邻域搜寻法做区域搜寻来应用于车辆途程问题。先以2-opt、根据2-opt增加交换节线的or-opt 及改良交换法的Lin-Kernighan 做途程内交 换，最後选择和已知最佳解误差百分比最少的2-opt做改善，接计算记忆盒中较佳路线之重心，并从运量最少路线开始做区域改善，以其重心为基准对附近路线做途程内2-opt及途程间Swap的交换，如此将能有效降低区域改善的时间，进而提升求解效率。利用国际标竿例题来验证AMS之求解效率，在随机问题C1~C10求解平均误差为0.98%，在丛聚问题C11~C14求解平均误差为0.55%。