100万个客户点的cvrp算例解可视化
FILO2
上篇文章分享了INFORMS上最新发表的vrp问题求解的开源工具，它们在性能和灵活性上各具优势，甚至有在DIMACS竞赛中都得过第一的，可以说算是先进了。不过，粉丝留言说推荐一下FILO2，说它是求解超大规模VRP目前的SOTA（State-of-the-Art，最先进的）。
之前还真没听过这个工具，不过能求解超大规模那还是要看看。一看才知道是vrp大佬vigo24年1月份参与的工作，早在2021年在transportation science上已经推出过FILO，这次的FILO2可以说是性能上有了极大的改进。（FILO2在DIMACS竞赛中的very large-scale instances性能表现上第一）
FILO
FILO2
对于CVRP问题目前常用的测试集主要是Uchoa等人提出的X系列（如X-n101-k25.vrp），最大的客户点需求能达到1000个；以及Arnold等人提出的B系列（如Antwerp1.txt），最大的客户点需求能到30000个。但是FILO2，能够用非常普通的计算系统处理更大规模的 CVRP 实例，对于 100 万客户的实例，执行 10 万次 FILO2 迭代并获得一个解决方案所需的时间不到十分钟，且内存占用不超过 10GB。这真算的上是工业级的了，机器学习深度学习方法顶多在1000多个客户点的算例上秀一下操作，在百万级的算例面前应该也走不了几步，嗯运筹学不用在大模型时代焦虑了（狗头）。
1
Part.1
FILO算法简介
FILO（Fast and Scalable Heuristic for Large-scale Capacitated Vehicle Routing Problems）算法是一种专门为大规模容量受限车辆路径问题（CVRP）设计的随机、有效且高效的算法，其主要步骤包括构建阶段和改进阶段。
构建阶段
使用 Arnold 等人（2019）提出的受限版节约算法（CW）构建初始可行解。该算法并非计算所有可能的节约（其数量随实例大小呈二次增长），而是仅计算其中的线性数量。这种有限的节约算法已通过实验证明，对于中大规模实例，能够生成与完整节约算法质量相当的初始解。
改进阶段
一是路线最小化（Route Minimization）
定义构建阶段生成的初始解为S，当前最优解为S*
根据定义的迭代次数，执行以下主要步骤：
从 S 中移除一对路线及其相关客户
按照特定标准对客户进行排序后，采用贪婪规则将其重新插入到移除后的部分解 S 中，使其插入到成本最小的位置
对 S 应用局部搜索
当无法在现有路线中找到某个客户的插入位置时（即所有可能的插入位置都会违反路线可行性），该客户可能会在当前迭代中保持未服务状态，后续迭代会考虑这些未服务客户
当局部搜索后解 S' 比 S更好时，S会被 S' 替换。S'和 S通过成本和路线数量进行比较，S’被认为比 S更好时它的成本应该更低或成本相同但路线数量更少
二是核心优化（Core Optimization）
是 FILO 中解改进的主要程序
初始解为路线最小化程序优化后的解
在每次迭代中，通过对解S进行扰动和局部搜索生成邻域解S'。如果 S' 的成本低于S*，S*被S'替换；此外，S' 也可能基于经典的模拟退火准则替换S。
扰动程序以破坏和重建的方式进行，从随机选择的种子客户开始进行随机游走并移除访问的客户，然后重新插入移除的客户。SVC（Selective Vertex Caching）在扰动过程中起重要作用，顶点会被插入到 SVC 中，使得局部搜索主要优化受扰动影响的解区域，提高了核心优化迭代的效率且使其在很大程度上独立于实际算例大小。
FILO 算法中的多个局部搜索算子（如 CROSS - exchange、2 - opt 变体等）以可变邻域下降（VND）的方式进行探索，共同进行优化操作。路线最小化进行路线压缩时可以访问不可行解，而核心优化程序仅探索可行空间。
2
Part.2
FILO2算法创新
FILO2 在FILO 算法基础上主要在以下几个方面进行了创新。
成本矩阵存储（Cost matrix storage）
原始 FILO 算法：在初始算例预处理阶段，计算并将所有弧（i,j）的成本存储在成本矩阵c中，这种二次内存占用在处理超大规模算例时不可行。
FILO2 算法：成本矩阵c从不明确存储，而是按需计算成本。此外，每个解对象跟踪组成它的弧的成本，例如，若j在i之后被服务，成本c(i,j)与顶点i相关联并可在常数时间内访问。同时，由于每个局部搜索算子根据 GN 范式(Granular Neighborhoods)设计，弧成本与移动生成器关联，可实现额外的常数时间成本检索。
邻接列表存储（Neighbor lists storage）
FILO 算法：在初始预处理期间，为每个节点i建立完全填充邻接列表V(i)，即对所有顶点按距离排序并存储，这在内存和计算时间上对于超大规模算例不可行。
FILO2 算法：邻接列表被限制为仅包含有限数量的顶点，通过kd - tree 数据结构高效识别这些顶点。
重新创建策略（Recreate strategy）
原始 FILO 算法：核心优化和路线最小化扰动程序的重新创建步骤会将所有被破坏步骤移除的客户，根据特定标准（与仓库的距离或客户需求）排序，贪婪地重新插入到最佳位置，若在现有路线中找不到这样的位置，在核心优化程序中会创建新的单客户路线，或在路线最小化程序中客户可能概率性地保持未服务状态。
FILO2 算法：对于超大规模算例，完全扫描扰动后的部分解并搜索最佳插入位置的计算成本过高，因此对于每个被移除的客户，仅扫描为邻居客户服务的路线来搜索候选插入位置。
解的复制（Solution copy）
FILO 算法：每个核心优化迭代中，解的简单复制对于超大规模算例会产生较高的计算成本，且当执行次数多时会成为主要瓶颈，此外，FILO 优化的局部性使得在算例较大且 SVC 最大容量有限时，解之间的差异通常较小。
FILO2 算法：采用基于 do/undo 列表的技术来避免完整的解的复制。该技术假设三个解S、S'、S*和在开始核心优化程序之前相同，通过将正确的更改记录到 do 列表D中，逆更改记录到 undo 列表V中，实现解决方案的同步。当S'因 SA 准则被接受替换时，D中的更改应用于S并插入到额外的 do 列表D*中，用于转换最佳解S*为S'；S'若不被接受替换，则V以逆时序应用于S'，最后在两种情况下都清除列表D和V。通过这种方式，同步不再是算例大小的线性操作，而是受扰动和局部搜索应用执行的实际更改数量限制，且大多与算例大小无关。
tail 和 split 局部搜索算子的懒惰预处理（Lazy preprocessing for tail and split local search operators）
FILO 算法：局部搜索使用 tail 和 split 这两个基于 2 - opt 算子，执行这些扰动及其可行性检查受所计算所有客户的需求之和影响很大，但对于超大规模算例这非常耗时且可能无用。
FILO2 算法：仅在需要时按需计算客户属于路线r的累积载重并缓存，直到路线r未被更改，若对r进行编辑，则标记r相关的累积载重不再有效。
分层随机可变邻域下降（Hierarchical randomized variable neighborhood descent）
FILO 算法：局部搜索算子根据 Hierarchical Randomized Variable Neighborhood Descent (HRVND) 原则组织，算子按相同基数分组，每层根据 Randomized Variable Neighborhood Descent (RVND) 原则应用算子，内外部 VND 循环根据改进情况重新考虑算子。在 FILO2 的新实验中发现内 RVND 循环很少对求解效果带来显著改进。
FILO2 算法：简化了 HRVND，去除了内部 RVND 循环，即每个外 VND 循环中，每个层级的算子仅执行一次，这样可节省一些计算成本昂贵的操作且不会显著降低最终解的质量。
3
Part.3
运行效率
3万左右规模的算例可以在200s内求到gap为百分之零点几的解，百万级的算例也可在10分钟内求到gap为百分之零点几的解
4
Part.4
代码运行
FILO算法代码的地址:https://github.com/ac co93/filo2,基于c++编写
运行方法：
cd filo2mkdir buildcd buildcmake .. -DCMAKE_BUILD_TYPE=Release -DENABLE_VERBOSE=1make -j./filo2 ../instances/I/Lazio.vrp
用CLion在编译器里亲测了一下，建议运行时注释掉cmake里的几行设置
然后在主函数中手动设置数据读入路径即可运行
int main(int argc) {std::cout << "******************************\n";std::cout << "Probably running in DEBUG mode\n";std::cout << "******************************\n\n";cobra::Timer global_timer;cobra::Timer timer;char* argv[]={"./filo2","../instances/I/Lazio.vrp"};const auto params = Parameters(2, argv);
试了下Lazio算例，果然很棒
Best solution found:obj = 3157310478, n. routes = 40094Run completed in 758 secondsResults stored in- ./Lazio.vrp_seed-0.out- ./Lazio.vrp_seed-0.vrp.solProcess finished with exit code 0
还提供了可视化
放一部分其它大规模算例：
Valle d'Aosta (20k)
Molise (50k)
Trentino-Alto Adige (100k)
Basilicata (150k)
Umbria (200k)
Abruzzo (250k)
Friuli-Venezia Giulia (300k)
Liguria (320k)
Calabria (380k)
Marche (420k)
Sardegna (470k)
Veneto (850k)
Emilia-Romagna (900k)
Lombardia (950k)
