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 warshall@or.uni-bonn.de.
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>@warshall.or.uni-bonn.deWith the user name and password provided with your badge. From Windows you may use Putty or with Linux on Windows
First, we create a docker image to run VRPSolver.
. /home/sheld/public/cpvrp.sh
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).
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/runvrp.sh
You can exit it using Ctrl-d unless it is actively running. Then you can kill it from your 2nd server login using
/home/sheld/public/killvrp.shFrom here you can call the runvrp.sh script again without re-creating the image.
RUN DOCKER ONLY THOUGH THESE SCRIPTS! OTHERWISE YOU MIGHT INTERFERE WITH OTHER PARTICIPANTS RUNS!
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 demoFor 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 solutionThere are further parameters in a parameter files.
CVRP/config/CVRP.cfgIn 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 solutionAnd compile and watch it from your 2nd Linux shell:
pdflatex A-n37-k5.tex; okular A-n37-k5.pdf
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.solThis has the drawback that Julia is compiled every time taking (~ 30 seconds), before the actual computation starts.
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
-m, -M be chosen?You may look into the instance file to answer this question.
-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 demoFinally, solve the 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
the number of paths w.r.t. the vehicle capacity
the total path length
Adjust the code to solve this problem.