基于仿真的遗传算法求解动态旅行商问题

以标准旅行商问题的扩展问题--动态旅行商问题为对象,分析了动态旅行商问题中由于道路流量实时变化所引起的标准旅行商问题的数学建模与优化求解的问题复杂性.通过建立其计算机仿真模型再现动态旅行商问题中众多复杂的非平稳、随机因子.进而提出了基于计算机仿真模型的遗传算法,即根据计算机仿真的结果,应用改造后的遗传算法搜索原问题的优化解.最后,在多智能体仿真平台上实现该优化算法,并以此求解20个城市的动态旅行商问题,计算结果验证了算法的有效性.

A Simulation-Based Genetic Algorithm for Dynamic Traveling Salesman Problem

This paper addresses one of special cases of classical traveling salesman problem (TSP)-the dynamic TSP (DTSP). Based on analysis of the DTSP, the challenges of modeling and solving the DTSP on mathmatical model are recognized to be derived from dynamical traffic flow of road network. Therefore, a computational model is built to represent the complicated DTSP, instead of mathmatical model. In the model, dynamical traffic flow of road network is mimicked by unstationary stochastic function via random variable generators. Based on the computational model, a simulation-based genetic algorithm is proposed to seek the optimal solution of DTSP. Finally, the algorithm is implemented on a multi-agent simulation platform, and a 20-city DTSP is demonstrated to validate and verify the proposal.