vrptw-powerful-route-minimization-heuristic

Efficient and fast implementation of the algorithm described in the following articles:

• A powerful route minimization heuristic for the vehicle routing problem with time windows, Operations Research Letters, Volume 37, Issue 5, 2009, Pages 333-338 [link]
• A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows, Computers & Operations Research, Volume 37, Issue 4, 2010, Pages 724-737 [link]

The vehicle routing problem with time windows (VRPTW) is one of the most important and widely studied problems in the operations research. The objective of the VRPTW is to minimize the number of routes (primary objective) and, in case of ties, the total travel distance (secondary objective). Given the hierarchical objective, most of the recent and best heuristics for the VRPTW use a two-stage approach where the number of routes is minimized in the first stage and the total distance is then minimized in the second stage. It has also been shown that minimizing the number of routes is sometimes the most time consuming and challenging part of solving VRPTWs. https://www.sintef.no/globalassets/project/vip08/abstract_nagata.pdf

This algorithm does exactly that: it minimizes the primary objective.

Various implementations that minimize the secondary objective can be attached to it. For example, the algorithm described in the following:

• Edge assembly‐based memetic algorithm for the capacitated vehicle routing problem, Networks, Volume 54, 2009 [link]

Its implementation may also appear in this repository at some point, although this is not so interesting.

Benchmark Problem Sets

• Solomon's problem sets (25, 50, and 100 customers)
• Gehring & Homberger's extended benchmark (200, 400, 600, 800, and 1000 customers)

To run the Gehring & Homberger 1000-customer benchmark, first build the solver in Release mode (-DCMAKE_BUILD_TYPE=Release) and place the benchmark instances into the GehringHomberger1000 directory in the repository root. Then run python3 benchmark.py --build-dir <your-build-dir> to execute the full benchmark suite, or add --instance c1_10_1 to run a single case. The script writes the aggregated results to benchmark_results.json.

Benchmark Results

Results on Gehring & Homberger 1000-customer instances (60 test cases):

Time Limit	This Implementation	Paper Results
10 minutes	3423	3420
60 minutes	3418	3419
5 hours	3418	3417

The table shows the total number of routes across all 60 test instances. The optimal sum (if all instances reached their current best-known solution) is 3416 (see this commit date).

Instances that did not reach the best-known solution within 5 hours:

• commit "ejection: replace temporary lists with arrays":
  • c1_10_8: best_known=92, achieved=93
  • c2_10_9: best_known=28, achieved=29
• commit: "optimize (precalc dist), fix beta-correction":
  • c2_10_8: best_known=28, achieved=29
  • c2_10_9: best_known=28, achieved=29

See commit messages. It takes time to carefully figure out which optimizations help and which ones hurt.

Usage

This implementation is just a simple command line utility. But it's also pretty easy to borrow and use as a library in your own project. For example, to use it in conjunction with your own implementation of the algorithm that minimizes the total travel distance (secondary objective).

Before running the cmake build process, you need to load some external submodules (for now these are only public Tarantool helper repositories). Run the following:

$ git submodule update --init --recursive

After that, build in the standard way:

$ mkdir build && cd build && cmake .. -DCMAKE_BUILD_TYPE=Release && make -j && cd ..

Release builds now also enable -march=native, -Ofast, -fno-plt, and -flto by default for extra performance.

If you want a more portable or more conservative binary, you can disable any of them individually:

$ mkdir build && cd build
$ cmake .. -DCMAKE_BUILD_TYPE=Release \
    -DENABLE_MARCH_NATIVE=OFF \
    -DENABLE_OFAST=OFF \
    -DENABLE_FNO_PLT=OFF \
    -DENABLE_LTO=OFF
$ make -j

For profile-guided optimization, use scripts/build_pgo.sh. It creates a PGO generate build, runs one or more training solver runs to collect profile data, and then rebuilds the final PGO use binary. Example:

$ ./scripts/build_pgo.sh --run C1_10_1:100:60 --run RC2_10_1:20:60

This means:

1. configure and build an instrumented Release binary with -fprofile-generate;
2. run the solver on the listed benchmark instances to collect execution profiles;
3. configure and build the final Release binary with -fprofile-use.

If you want to collect the profile manually instead of using the script:

$ cmake -S . -B pgo-gen -DCMAKE_BUILD_TYPE=Release \
    -DPGO_MODE=GENERATE \
    -DPGO_PROFILE_DIR="$PWD/pgo-data"
$ cmake --build pgo-gen --target routes -j

$ ./pgo-gen/routes GehringHomberger1000/C1_10_1.TXT C1_10_1.sol \
    --lower_bound 100 \
    --t_max 60 \
    --beta_correction \
    --log_level normal

$ cmake -S . -B pgo-use -DCMAKE_BUILD_TYPE=Release \
    -DPGO_MODE=USE \
    -DPGO_PROFILE_DIR="$PWD/pgo-data"
$ cmake --build pgo-use --target routes -j

The training run should be representative of the instances you care about, because the final binary is optimized using the collected execution profile.

Then you can run the utility:

$ ./build/routes --help
Usage: ./build/routes <file1> <file2> [<options>]
file1 - problem statement, file2 - where to output the solution

Options:
  --beta_correction       - Enables beta-correction mechanism.
  --log_level <option>    - Log level: none, normal, verbose.
  --n_near <value>        - Sets the preferred n_near.
  --k_max <value>         - Sets the preferred k_max.
  --t_max <value>         - Sets the preferred t_max (in secs).
  --i_rand <value>        - Sets the preferred i_rand.
  --lower_bound <value>   - Sets the preferred lower_bound.
  --seed <value>          - Sets the pseudo-random seed.
$ ./build/routes GehringHomberger1000/C1_10_1.TXT C1_10_1.sol --lower_bound 100 --t_max 120

After completion, the current directory will contain a file with the solution, the name of which you specified when starting. In this example it is "C1_10_1.sol".