ALNS算法解决VRPTW城市内即时配送Java/Python代码

这篇博客不涉及算法基本框架，只有我的一些理解以及我写的代码。
在今年我研究了三个月的ALNS算法用于解决城市内即时配送问题，完成了两个版本的代码。在查资料阶段发现很多博客没有写清楚一些细节，在研究了2006年算法创始人的论文后，在此进行总结，不打算系统地讲解这个算法。
代码需要自己研究然后修改，没办法复制粘贴一般效果不理想。

python代码写的很烂，速度慢，不推荐，可参考画图部分、框架部分。

java代码速度快，易于修改，结构清晰，十分推荐，但没有可视化部分。

代码与算例地址：https://github.com/MonsterPPPP/ALNS-Java-Python-code-and-Samples

求star~

实验做完了，不想维护代码了，有问题就在csdn评论区问吧，别把报错直接扔出来我也看不懂哈。

0.关于算法解决的问题
Multiple vehicle-VRPTWPD
多车辆的-带时间窗的-取送货的-车辆路径问题
通俗的问题描述就是规划城市内的外卖配送.有很多外卖订单，要求送A地送到B地，骑手需要从A地取餐，然后送到B地去。
算法就是要规划：
1.谁来送某个订单。
2.一个骑手该如何规划他的路径，使得所要求的损失值最小。
1. 算法核心理解

算法是如何找到解的：
本质上就是一种优化之后的查找。邻域搜索，搜索的是解空间。首先生成一个差不多的初始解，然后开始对这个初始解进行邻域搜索。先把解移除一部分，在把这部分插入到解中，就能得到一个跟移除前差不多的解，要是损失值比前面的小，就作为新解保留。然后就不断地移除插入，在解附近查找，直到找到迭代次数达到上限。

类比在机器学习算法中是按照梯度下降原则，从损失值下降最大的方向迭代参数。而在邻域搜索的过程中，是在这个当前解的四面八方都可能作为新出现，要是找到了个损失值低的解，就用它继续向下搜索。

算子的作用：
算子就是解向四面八方搜索的方式，有的算子随机乱走，有的算子走眼前最好的路，有的算子按照一些准则走特殊的路…这就是算子的本质。所以，算子设计的越好，种类越多，就越容易在一定时间内找到较优解。

自适应的理解:
每个算子在一开始有个分，当它找到比较好的解的时候，这个分就加。这样每次选算子的时候这个算子选择的可能性就增加了。这样好的算子就越来越好，用的越来越多。

模拟退火准则：
为了防止陷入局部最优解，引入了模拟退火准则，应对新解不如当前解的状态。也就是当出现的新解不好的时候，也可能被接受。想要理解这里还要自己研究，专门讲退火的相关文献。

2. 算法参数

算法终止条件：
有的博客是按照温度降低到一定程度就停止，有的是按照迭代次数达到一定程度就停止。这里我推荐使用迭代次数。并且大多数的论文也都是按照迭代次数达到上线他就停止。因为温度这个东西比较麻烦，下面再说。可以在实验的过程中根据你要解决的问题进行参数搜索，一直解不再更新了就结束。

初始温度T：
这是一个十分重要的参数！它的值设立十分重要，否则有可能你的模拟退火永远接受不了，或者一直在接受差解。
结论是：初始温度应当设置为，比初始解弱5%(这个值你也可以设为别的，越小算法对差解的包容度就越高)按照模拟退火准则被接受的概率是50%。这样不管你的损失函数的数量级是多少，都能保证这个模拟退火算法是好用的。解一个对数方程就可以解出来初始温度了，这一点在java代码里面实现了，可参考，高中数学程度。

3. 关于源代码
python 代码框架参考博客：
https://blog.csdn.net/weixin_46651999/article/details/113065064?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162942057916780261911162%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=162942057916780261911162&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_allsobaiduend~default-5-113065064.first_rank_v2_pc_rank_v29&utm_term=ALNS&spm=1018.2226.3001.4187

使用整数编码：商家用偶数，客户用奇数，在路径中奇数前面必须有比它小1的偶数才可以进行插入和删除。

损失函数：包括距离损失（都使用经纬度之间的直线距离），时间损失，超时损失。在损失函数可调整三者的比例。

距离：使用了直线距离，首先计算一下每个点之间距离，形成距离矩阵，之后直接使用。要是你有距离的话可以直接把距离矩阵导入，就不用计算距离了。

代码结构：
python版本：迭代->画图
java版本：生成初始解->迭代->输出结果
可以将结果输入到python版本里，然后进行画图。

着重讲解java版本的内容：

courier.java：
实现了底层三个损失函数
有一个骑手路径

couriers.java
实现了算子
实现初始解的生成
实现了总的损失函数，可以在这里调整各个损失之间的比例。
里面实现了很多courier，是骑手的集合

Helper.java：
调整算法参数

Main.java：
主函数，包括算法结构，与算法主逻辑。

写在最后
代码不完美，懒得改了，不要做伸手党，自己研究才是王道。鄙人学疏才浅，只能指路到这里了。有不对的地方希望大家指正。本文着重讲我的理解，与其他博客未涉及的关键部分。