Intelligent Route Optimization Technology by Case Based GA
Intelligent Route Optimization Technology by Case Based GA
复制标题
基于案例的遗传算法智能路径优化技术
DOI：
10.1109/sitis.2013.64
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Y. Sakurai
中科院分区：
文献类型：
--
作者：
T. Motomura;M. Suzuki;S. Tsuruta;Y. Sakurai
配送路径优化系统大大提高了真实的时间配送效率。为了实现这样的优化，其分销网络需要在交互式响应时间（约3秒）内以专家级精度（低于3%的错误率水平）解决数十到数百个（最多2000个左右）城市的旅行商问题（TSP）。为了满足这些要求，基于实例的遗传算法（CBGA）。这种方法是基于这样一种认识，即大多数解决方案与以前创建的解决方案非常相似。因此，在许多情况下，可以通过以下方式从先前的解决方案中导出解决方案：（1）从先前的TSP解决方案的库中选择最相似的TSP，（2）移除不属于当前TSP的部分的位置，（3）通过突变（即，最近插入（NI））添加当前TSP的缺失位置，以及（4）通过另一GA进一步优化解决方案。这种通过基于案例的推理（CBR）创建解决方案的方式避免了从头开始创建新解决方案的计算成本。
A delivery route optimization system greatly improves the real time delivery efficiency. To realize such an optimization, its distribution network requires solving several tens to hundreds (maximum 2 thousands or so) cities Traveling Salesman Problems (TSP) within interactive response time (around 3 seconds) with expert-level accuracy (below 3% level of error rate). To meet these requirements, a Case Based Genetic Algorithm (CBGA) is proposed. This method is based on the insight, that most solutions are very similar to solutions that have been created before. Thus, in many cases a solution can be derived from former solutions by (1) selecting a most similar TSP from a library of former TSP solutions, (2) removing the locations that are not part of the current TSP, (3) adding the missing locations of the current TSP by mutation, namely Nearest Insertion (NI), and (4) further optimizing the solution by another GA. This way of creating solutions by Case Based Reasoning (CBR) avoids the computational costs to create new solutions from scratch.