Vehicle Routing Problem

Some solutions are discussed here, involving the VRP problem. I wanted to see what open source packages are capable of and also a BCP (Branch and Cut and Price) algorithm to try and get optimal solutions.

The optimal solutions can then be generated over time to get a real percentage for each solution.

LP solvers

First a docker/almost ready to use solver was found here :

visit

The guide there works if you use the free version of CPLEX that can be downloaded from ibm (todo : how !?).

However one of the first problems encountered was that the free version is limited in the sized it can handle, en hence USELESS !!

So on to a real free example :

SYMPHONY

Do NOT use the latest version (5.6) vrp is just forgotten in that version !!

On servert1 the version is 5.4.0, this one is known to work!

This works best (if not, take version 5.4 !) :

wget https://www.coin-or.org/download/source/SYMPHONY/SYMPHONY-5.5.0.tgz
tar -zxvf SYMPHONY-5.5.0.tgz
cd SYMPHONY-5.5.0
# will make the lib and Application makefiles :
./configure --with-application --enable-openmp 
make
make install # do NOT forget, or you will miss headers etc..
cd SYMPHONY/Application/VRP
make
./vrp -F sample.vrp -N 5 -u 522

The openmp will enable multiple processor usage. Later in this chapter will be explained how to enable that, it needs some manual patching !!

Note that you will have to give an upper bound bigger than the optimum or it will give no solution.

Take your best known solution (mostly lkh) and add 1. Use that as upper bound.

Note that smaller problems will return fairly quick with an exact match (dim 20 and 50), but bigger ones go on for quite a bit.

Here will be a table with running times and it will take some time to finish (if at all) . You can just copy the executable to the test directory.

Run these tests like this :

time ./vrp -F data/N-D20-V10-C10-1.vrp -Now run configure again, and recompile.

Put the results in a file :

Route #1: 6 35 45 39 20 4 34 49 22 31 44 12 25 27 10 5 33 7 
Route #2: 23 13 11 29 14 30 36 26 41 17 40 
Route #3: 21 16 42 48 37 19 47 9 2 24 32 8 38 46 15 3 28 43 1 18 

Then run sym.py on this file to get a usable result file, you can do it by hand but all stops have to be increased by one so sym.py is handy also for the header. Since we already use .opt for optimoroute, use .sym for these results.

problem	dimension	time	first solution
N-C20* N-C50*	20 50	< 1s 0-4s
N-C100*	100	10s-10m	< 1min

Parallel version

The code should simply be compile by a openmp capable compiler. G++ has been capable of that since version 4.2.0 but the configure setup tests 420 against 8 (gcc version 8) and that simply fails because 8 is smaller than 420 (sigh!) I just patched the test and reversed it from -lt to -gt inside SYMPHONY/configure

[   if test ${major_gcc_version} -gt ${gcc_required_version}; then

Now start the configure like this :

./configure --with-application --enable-openmp
make 
make install
... etc

Now you can use -p to use as many cores as you have : .. code-block:

./vrp2 -F data/N-D150-V10-C10-2.vrp -N 8 -p 20

As a test i will now start data/N-D200-V10-C10-1.vrp that has been running for 2 days on 1 core and see if it catches up :)

./vrp2 -F data/N-D200-V10-C10-1.vrp -N 10 -u 195559 -p 20

This is a test for only processors, maybe better use of memory would help as well. See SYMPHONY_30_Users_Manual.pdf for that.

multiple machines

This is not a multiprocessor version, but parallel virtual machines. So if you want to do this with a cluster of nodes :

apt-get install pvm pvm-dev
vim SYMPHONY/config

In the config file alter these settings:

#COMM_PROTOCOL = NONE
COMM_PROTOCOL = PVM

SYM_COMPILE_IN_CG = TRUE
SYM_COMPILE_IN_CP = TRUE
SYM_COMPILE_IN_LP = FALSE
SYM_COMPILE_IN_TM = TRUE

Now run configure again, and recompile.

coinor build

Newer versions of coinor come with a general build script. Use it like this.

mkdir coinor
cd coinor
git clone https://www.github.com/coin-or/COIN-OR-OptimizationSuite
# now answer the menu questions as you need them :
# get coffee ...

Or to dismiss with the menu :

./coin.install.sh fetch build --no-prompt --main-proj=SYMPHONY

The base is built and installed now.

heuristics

VRPH

This one i encountered already it is available here : visit

It is also a COIN-OR source tree (as is SYMPHONY). It solves ok, and beats optimoroute and PTV, but not LKH.

I think it is best to start with this heuristic as base for the website and than add new algorithms (LKH and lkh after it is debugged) Also Since VRPH is a construction of various VRP subsolutions maybe it can be used to mimic the algorithm described here : visit

troubleshooting

Some common errors :

compile error on SYMPHONY_SVN_VER

That macro seems defined but "" so the printf goes wrong. Remove the printf statement !!

fatal error: OsiSolverInterface.hpp: No such file or directory

You forgot to run make install !!