第18卷第5期系统管V0I．18No．52009年10月JournalofSystems0Ct．2009文章编号：1005—2542(2009)05—0591—05基于仿真的遗传算法求解动态旅行商问题李锋，魏莹(1．华南理工大学工商管理学院，广州510640；2．新鲁汶大学运筹学与计量经济学中心，比利时)【摘要】以标准旅行商问题的扩展问题——动态旅行商问题为对象，分析了动态旅行商问题中由于道路流量实时变化所引起的标准旅行商问题的数学建模与优化求解的问题复杂性。通过建立其计算机仿真模型再现动态旅行商问题中众多复杂的非平稳、随机因子。进而提出了基于计算机仿真模型的遗传算法，即根据计算机仿真的结果，应用改造后的遗传算法搜索原问题的优化解。最后，在多智能体仿真平台上实现该优化算法，并以此求解20个城市的动态旅行商问题，计算结果验证了算法的有效性。关键词：动态旅行商问题；遗传算法；仿真理＆中图分类号：TP18文献标识码：AMa学eeASimulation。-BasedGeneticAlgorithmforDynamic报TravelingSalesmanProblemLIFeng。WE，Ying。(1．SchoolofBusinessAdministration，SouthChinaUniversityofTechnology，Guangzhou510640，China；2．CenterforOperationsResearchandEconometrics，UniversiteCatholiquedeLouvain，Belgium)[Abstract]Thispaperaddressesoneofspecialcasesofclassicaltravelingsalesmanproblem(TSP)一thedy—namicTSP(DTSP)．BasedonanalysisoftheDTSP，thechallengesofmodelingandsolvingtheDTSPonmathmaticalmodelarerecognizedtobederivedfromdynamicaltrafficflowofroadnetwork．Therefore，acomputationalmodeliSbuilttorepresentthecomplicatedDTSP，insteadofmathmatica1mode1．Inthemode1．dynamica1trafficflowofroadnetworkiSmimickedbyunstationarystochasticfunctionviarandomvariablegenerators．Basedonthecomputationalmodel，asimulation—basedgeneticalgorithmisproposedtoseektheoptimalsolutionofDTSP．Finally，thealgorithmisimplementedon3multi—agentsimulationplatform，anda20一cityDTSPisdemonstratedtovalidateandverifytheproposa1．Keywords：dynamictravelingsalesmanproblem；geneticalgorithm；simulation旅行商问题(TravelingSalesmanProblem，问题是一个典型的NP—Hard问题。自从1932年TSP)是一个经典的组合优化问题。它可以简单描TSP问题被KarlMenger正式提出来后，一直是国述为：已知N个城市的网络，目标是寻找一条巡回内外众多专家学者研究的热点问题。路线，能够不重复地经过所有城市，同时使得巡回路虽然TSP问题可以被分支定界法等算法精确线的距离最短。从计算复杂性理论角度上说，TSP求解，但是由于这类精确求解算法的计算量巨大，难以高效地求解大规模TSP问题。因此，更多的研究收稿日期：2008—0905工作集中在寻找计算量较小，同时解的质量较高的基金项目：欧盟项目(CN／ASIA—IINK／031(110-412))；广州市TSP问题启发式算法。TSP问题也因此成为测试哲学社会科学发展‘十一五’规划课题(08B12)各种优化算法性能的标准问题之一。作者简介：李锋(1975一)，男，博士。研究方向为建模与仿真和供应链管理。Email：fenglee@SCUt．edu．cn典型的TSP问题求解算法包括：蚁群算法、神592系统管理学报第18卷经网络算法、模拟退火算法、遗传算法、