论文部分内容阅读
旅行商问题(Traveling Salesman Problem,TSP)是19世纪由爱尔兰数学家Sir William Rowan Hamilton和英国数学家Thomas Penyngton Kirkman提出的一个数学问题,是指一个旅行商,要访问已知的n个城市,且每个城市只能一次且仅一次,并回到原出发地,使得访问所走的路程最短,该问题已被证明为NP完备问题。与之类似的车辆路径问题,是指有多辆车,使得每辆车只能对所有城市中的一部分进行访问,每个城市只能被一辆车访问,其目标是使得所有车辆的行程之和最小。由于其应用比较广,有许多算法被用于该问题的求解。 而在许多实际应用中,事先是不可能对问题的所有信息完全知晓,对于这样的不确定性问题,有许多方法都可以解决这类优化问题。如可以利用概率分布或整数规划来处理动态问题,即动态优化的方法。但在有些情况下是不可能有足够的数据来精确估计其分布模型,此时可采用在线优化方法,如在线旅行商问题及应急事件中的车辆路径问题。在线优化是指用于解决需要不断地、连续地作出决策的优化问题的方法。 本论文主要围绕在线旅行商问题和应急车辆路径问题展开,分别提出了不利则等待WIN及kWIN响应策略,分以下五个部分进行阐述:(1)在论述旅行商问题的研究概况的基础上,引出本论文的背景、意义和主要研究内容。(2)详细介绍旅行商问题的解在邻接矩阵中的表示,并改进了Z-mapping技术,将ATSP转换成STSP进行研究,还介绍了带有阻塞的 TSP求解方法以及在线算法的性能分析法——竞争分析法。(3)提出基于离散空间下的在线旅行商问题的模型,并设计不利则等待WIN的在线响应策略,得出其为竞争度为2的在线算法,而后将该策略改进,应用于应急事件中的车辆路径问题中,得到一个竞争度为2?(k?1)/n在线算法kWIN。(4)将以上的两个在线响应策略,改进传统的贪婪算法,提出了算法2和算法4,并通过大量的数据模拟测试,来验证该策略的可行性;(5)对所做的研究工作进行了总结,对课题不足及进一步的研究提出了展望。