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

以螞蟻記憾系统為基礎搭配不同的鄰域搜尋法做區域搜尋來應用於車輛途程問题.先以2-opt、根撩2-opt增加交换節線的or-opt及改良交換法的Lin-Kernighan做途程内交换,選挥和已知最佳解誤差百分比最少的2-opt做改善,再計算記憾盒中較佳路综之重心,並從運量最少路線開始做區域改善,以其重心為基準封附近路線做...     

蚂蚁记忆系统应用於车辆途程问题

蚂蚁演算法发表不过短短十几年,在各类型组合问题求解上皆有不错的表现,因此本研究主要目的是以蚂蚁记忆系统为基础做改良并延伸至车辆途程问题。本研究透过图像检视发现即便有候选名单的限制节点选择范围,但在不断选择节点下,仍会偏离其建构之路径,所以研究方向主要在节点选择路径公式多增加该路径第一选择节点之角度,以减少逐渐扩散之可能性。在效率提昇方面,当路线建构完成後,计算出各路线之重心,并从运量最少路线开始做区域改善,以其重心为基准对附近路线做2-opt及Swap的交换,如此将能有效降低区域改善的时间,进而提升求解效率。利用国际标竿例题来验证AMS之求解效率,在随机问题C1-C10求解平均误差为0．98％,在丛聚问题C11-C14求解平均误差为0．55％。