FILO2

FILO2 is an evolution of FILO able to tackle much larger CVRP instances with a very ordinary computing system. Less than ten minutes and 10GB of RAM are enough to execute 100k FILO2 iterations and get a (possibly very bad) solution for an instance with 1 million customers. On the X and B datasets FILO2 behaves pretty much like FILO in terms of quality (sometimes it is even slightly better) but it has a considerably lower time growth rate that becomes very visible for instances with more than 5k customers.

Changes and computational results are described in the draft and in the paper. This repository contains raw results and the algorithm source code.

Updates

The code has received some updates related to implementation details

• Mar 11, 2024 - Commit 42276b7: use faster rounding procedure
• Mar 13, 2024 - Commit 2127972: use a more efficient set implementation in ruin&recreate and local search procedures
• Nov 24, 2024 - Commit 292c3c1: simplify move generator class. The algorithm ìs ≈27% faster (on short runs) and uses ≈7% less memory

Get the code

git clone git@github.com:acco93/filo2.git

Note that the repo includes ≈1.5GB of result files.

Build & run

cd filo2
mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release -DENABLE_VERBOSE=1
make -j

./filo2 ../instances/I/Lazio.vrp

Compile time cmake options

• ENABLE_VERBOSE: prints info while processing
• ENABLE_GUI: shows a graphical representation (slows down thing a little)

The I dataset ... in pictures

• 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)

• Campania (500k)

• Piemonte (600k)

• Toscana (700k)

• Puglia (750k)

• Sicilia (800k)

• Veneto (850k)

• Emilia-Romagna (900k)

• Lombardia (950k)

• Lazio (1M)