tsp问题matlab代码步骤旅行商问题
目的与总结
使用约束生成法解决美国48个州的首都
Dantzig-Fulkerson-Johnson公式具有2
^
n-2子轮廓消除约束,这使该问题在计算上难以解决。
对于48个城市的问题,将存在2
^
48-2
=
281,474,976,710,654(281万亿)次子行程消除约束。
因此,我们使用约束生成方法来生成问题并向该问题添加约束,直到找到解决方案为止。
对于使用Mosel(Xpress)代码的48个城市(美国48个州首府)的游览,此方法可在2分钟内收敛为解决方案。
使用相同的方法,还可以解决26个城市的旅行问题。
文件:
TSP-DFJ-48.mos:48城市旅游的Mosel代码
TSP-DFJ-26.mos:26城市旅游的Mosel代码
US48.dat:美国48个州首府的坐标
US26.dat:在美国随机选择的26个州首府的坐标
tourmap_48.png:48个城市游览的地块
tourmap_26.png:26个城市游览的地块
US48TourPlot.m:Matlab代码以绘制使用Mosel代码生成的48个城市游览
US
2022-02-18 22:46:11
118KB
系统开源
1