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

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

Application of Ant Memory System to Vehicle Routing Problem

Ant System（AS） is a meta-heuristic algorithm based on the behavior of ants.As it performs well in solving various NP-Hard problems,several modified versions have been developed,including Ant Memory System（AMS）.AMS is developed by the author and very good results have been obtained when it is applied in TSP（Travelling Salesman Problems）.The design of memory boxes in AMS is able to avoid accepting local optimum found in the solving process.This study plans to find out the effectiveness of the AMS in solving VRP.AMS is modified for VRP and some local search mechanisms such as 2-opt are adopted to develop a new approach.International benchmark problems will be used to test the efficiency of the modified algorithm.Meanwhile,a tool has been developed to observe the iteration in the solving process,which will give significant insight into improving AMS.