Hausdorff School on Computational Combinatorial Optimization

Vehicle Routing

author: Stephan Held

date: 11.09.2022

disclaimer: Parts of these instructions are based on the VRPSolver documentation

First, we learn how to run the VRPSolver introduced in the lecture. Then, we try to solve a CVRP instance, for which the optimum solution is yet unknown (even to me).

VRPSolver is written in the Julia programming language. You don’t need to know Julia. It is easy to learn. We will run VRPSolver from a docker image. Don’t worry if you do not know docker, just execute the subsequent scripts on

You should log in twice: Once, to run VRPSolver in docker, and once to read/modify code in a Linux shell (-XC allows to open GUIs and enables compression=.

ssh -XC <username>

With the user name and password provided with your badge. From Windows you may use Putty or with Linux on Windows

Creating a copy of the docker image

First, we create a docker image to run VRPSolver.

. /home/sheld/public/

This will take ~30 seconds.

It creates and changes to a new directory vrpsolver-docker-v0.4.1, which contains the Julia code (subdir CVRP/src/) and instances (subdir CVRP/data).

Opening a Julia window

Next, we run the docker image to open a Julia shell, from where we can run the VRP solver using Julia commands.

. /home/sheld/public/

You can exit it using Ctrl-d unless it is actively running. Then you can kill it from your 2nd server login using


From here you can call the script again without re-creating the image.


Running a first example

You can copy & paste the following code block into the Julia shell. The first step (“Loading the CVRP”) takes some time (~10 seconds). The second steps loads and solves an instance.

include("/CVRP/src/run.jl") # load CVRP demo
main(["/CVRP/data/A/A-n37-k6.vrp","-m","6","-M","6","-u","950","-o","/CVRP/sol/A-n37-k6.sol"]) # run CVRP demo

For the parameters that are passed to the main function, please read the documentation inside /CVRP/src/run.jl with your 2nd login shell into the server. You may also read the other source code files. From there you can also inspect the solution which is written to the subdir CVRP/sol/A-n37-k6.sol.

You can solve another instance w/o re-loading the demo:

main(["/CVRP/data/A/A-n37-k5.vrp","-m","5","-M","5","-u","670"]) # running another instance without writing the solution

There are further parameters in a parameter files.


In particular, it contains a running time limit currently set to 600 seconds.

You can also generate a LaTex file containint a tour plot:

main(["/CVRP/data/A/A-n37-k5.vrp","-m","5","-M","5","-u","670", "-t", "A-n37-k5.tex"]) # running another instance without writing the solution

And compile and watch it from your 2nd Linux shell:

pdflatex A-n37-k5.tex; okular A-n37-k5.pdf

Alternative Way to Run VRPSolver the the Julia Shell

Alternatively, you can run VRPSolver right from the command line w/o the interactive Julia shell.

cd CVRP;
./VRPSolver data/A/A-n37-k6.vrp -m 6 -M 6 -u 950 -o sol/A-n37-k6.sol

This has the drawback that Julia is compiled every time taking (~ 30 seconds), before the actual computation starts.

Running the open problem

We now want to solve an open CVRP problem with unit demands. It arises in chip design, where registers need to be connected with so-called scan chains of a maximum length. When the chip is tested, pre-defined bit patterns will be loaded and read to/from the registers through these chains. The objective is to 1st minimize the number of chains and 2nd minimize the total net length.

We will tackle the smallest available instance: CVRP/data/BN/i159TSP3H.vrp

How should -m, -M be chosen?

You may look into the instance file to answer this question.

How should -u be chosen?

If you set the upper bound too small, the problem becomes infeasible. Even the default value of 10,000,000 (if you skip that parameter) might be too small!

Luckily, there are good primal heuristics available. A good one for a fixed number of vehicles is LKH-3 by Keld Helsgaun. It performs local search with random & genetic permutations. You can run it from the bash (2nd login) as follows.

/home/sheld/public/run_LKH_CVRP <instance-file>  <num_vehicles> <max_trials> <runs>

Here, runs specifies the number of random restarts and max_trials the number of “kick” perturbations within the local search. The larger these values, the higher the chance to get a good solution. As a first try, you might set both to 10. The command then becomes:

/home/sheld/public/run_LKH_CVRP CVRP/data/BN/i159TSP3H.vrp  <num_vehicles> 10 10

(after substituting num_vehicles)

With the resulting upper bound, you can try to solve the scan chain instance:

 main(["/CVRP/data/BN/i159TSP3H.vrp","-m", ...

However, you may want to verify that the CVRP code supports the Manhattan metric used in the scan chain instance. If not, adjust the code to support it (a quick fix would be sufficient)! If you change the code, you need to rerun

include("/CVRP/src/run.jl") # load CVRP demo

Finally, solve the problem!

Modified Problem

Actually, we do not need to have a specific depot in the scan chain application. The IO ports of the scan chains can be placed at the first and last stop. Thus, we look for a path cover of the cities, minimizing lexicographically

  1. the number of paths w.r.t. the vehicle capacity

  2. the total path length

Adjust the code to solve this problem.