代码 | 自适应大邻域搜索系列之(1) - 使用ALNS代码框架求解TSP问题

前言

上次出了邻域搜索的各种概念科普，尤其是LNS和ALNS的具体过程更是描述得一清二楚。不知道你萌都懂了吗？

小编相信大家早就get到啦。不过有个别不愿意透露姓名的热心网友表示上次没有代码，遂不过瘾啊~哎，大家先别急，代码有得你们酸爽的……

不过由于ALNS的代码量实在太大，小编打算把这个做成一个系列来一一为大家讲解，好让小伙伴们彻底把这个算法框架的代码吃透。

今天暂时还是先不对代码进行讲解，先来教大家怎么使用ALNS的框架求解一个TSP问题吧~

01 环境准备

小编的演示是基于Windows 10 x64位环境的（Linux党就更简单了），其他Windows 环境也类似。在此之前我们需要配置几个东西。

1.1 安装MinGW

这玩意单独装比较麻烦，但是安装devC++会自带这玩意儿，特别方便。没有安装devC++的小伙伴请移步留言区获取安装包下载链接。

去下一个安装上。然后在电脑上找到devC++的安装位置，把其目录下的MinGW64\bin文件添加环境变量。如下图所示：

打开cmd命令行，输入下面命令：mingw32-make 出现下面提示就成功了。

2.1 下载源代码

请大家 移步留言区 把源代码下载下来，然后解压到某个位置（路径不要有中文）。

2.2 修改源代码

找到\trunk\src\alns下的OperatorManager.cpp：

打开，在头文件位置加入下面这句话，把调试模式给禁用掉：

2.3 编译

在命令行下进入\trunk\Release目录，首先输入mingw32-make clean，清理以前编译的中间文件。

然后输入：mingw32-make。进行编译。

得到我们的目标文件：libALNS-framework.so。这是ALNS框架的动态链接库，稍后我们要使用到的。

可以在该目录下看到：

在命令下进入\trunk\examples\tsp，把main.cpp替换为小编修改好的main.cpp。

然后照例：首先输入mingw32-make clean，清理以前编译的中间文件。

然后输入：mingw32-make。进行编译。

最终得到我们的程序TSP.exe。这里还有一步，把刚刚编译好的libALNS-framework.so文件复制到当前目录，TSP程序运行需要用到它。

最后可以在命令行下输入TSP，运行我们的程序：

至此，已经完成了。最后说一下，修改的代码为求解Berlin52问题的代码。如果需要求其他TSP问题，在小编修改好的main.cpp文件里，把城市坐标和CITY_SIZE改过来，重新编译tsp文件夹里面的内容就行。

最优解是7542，至于这里的解为什么比7542少，原因是代码算总距离的时候没有加上第一个和最后一个city的距离。

03 小结

最后再多说两句，上述求解的代码是根据ALNS框架定制而来的。其实，大家想用ALNS算法求解任何问题，只需要把框架内容做相应的定制就可以啦。在下面的几篇推文里，小编将详细解析ALNS代码框架的内容，然后把上面求解TSP例子的代码定制内容也给大家讲解一下。期待我们后面的文章吧~