基于随机机会约束规划模型的旅行商问题及其求解算法

作者：马慧茹; 赵峰; 贾利民; 张星臣

来源：长安大学学报(自然科学版), 2015, S1: 179-183.

DOI：10.19721/j.cnki.1671-8879.2015.s1.037

• 旅行商问题
• 随机机会约束规划
• 遗传算法

为了提高旅行商的效率,将旅行时间引入旅行商问题(TSP),以最短时间和最短路径为目标对旅行商问题进行求解。假设旅行商在不同城市间的旅行时间服从正态分布,以最短路径为优化目标,将旅行时间以一定的置信水平成立作为机会约束条件,构建了旅行商问题的随机机会约束规划模型。提出已构建模型的确定性等价类,设计出遗传算法并编写算法代码,以一定规模的城市为例进行仿真验证。结果表明:给定期望的总旅行时间和置信水平时,可经过计算得出最短距离,并绘制出最优路径图,同时验证了所提出模型的可行性和算法的有效性。

• 单位
  北京交通大学; 交通运输学院; 轨道交通控制与安全国家重点实验室