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

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