Travelling Salesman Problem

This is about TSP and VRP problem solvers. The content has been moved out of archive on mar 2 2024.

travelling salesman problem

This was a 3-day run to optimize the rl5934 tour with concorde. The tail of the command is show

Task 26: Branching on node 7
BBnode 7 split into 38 (555965.67) 39 (555969.89) (688.67 seconds)
LOWER BOUND: 555961.524243   ACTIVE NODES: 13

Task 27: Branching on node 22
BBnode 22 split into 40 (555969.47) 41 (555971.19) (693.34 seconds)
LOWER BOUND: 555964.515081   ACTIVE NODES: 14

Task 28: Cutting on node 33
CPXgetijdiv: not implemented yet

real    4763m40.502s
user    4763m10.168s
sys     0m24.640s

Also the time, in real time is 4763 minutes : 79 hours 23 minutes That's 3 days 7 hours and 23 minutes.

The optimum in literature is : 556045

To save you the same search again, here is the list : visit And here is a similar list with the problems : visit

The last number mentioned by the concorde solver was 555964 which is

0.999854328337 off, so I presume the last answer was

LKH

Time.avg = 260.18 sec

556136 this number is 1.00016365582 off, so that's just more than 1 promille.

LKH-3

LKH 3 is an extension to LKH-2, where support is added for much more problems than TSP itself. VRP in different format is solvable as well.

General K-opt submoves paper

LKH-2 is free of charge for academic and non-commercial use and can be downloaded in source code.

But in the paper(s) it is clearly explained how to implement it so i will attempt it. Variables will be named accordingly to descriptions.

Symmetric TSP problem

Let G be a weighted graph

\[G = (N , E)\]

With N the set of nodes

\[N = {1, 2, . . . , n}\]

and E is the set of edges

\[E = {(i, j) | i ∈ N , j ∈ N }\]

Each edge (i, j) has associated a weight c(i, j).

A cycle is a set of edges

\[{(i_1 , i_2 ), (i_2 , i_3 ), . . . , (i_k , i_1 )}\]

with

\[i_p neq i_q for p neq q\]

Read as ...

all nodes ip and iq are different for different values of p and q, or all nodes represent a different node for each value of p and q.

Or, all nodes in the cycle are different nodes.

A Hamiltonian cycle (or tour) is a cycle where k == n. The weight (or cost) of a tour T is the sum (i, j)∈ T c(i, j). An optimal tour is a tour of minimum weight.

A K-Opt is a tour improvement algorithm where K links of a tour are replaced by k other links so that a better tour results, where K is 2 <= K <= N

The lin-kernighan algorithm does so by constructing a sequential string of links that are to be added and deleted in turn. You start with a complete tour, then start at a node t1, then choose t1-t2 to be added, t2-t3 to be deleted, t3-4 to be added, etc... and make sure the last link to be added ends at t1 again : tk-t1. This is called an alternating cycle.

The LKH-2 algorithm extends this with possible moves that are not sequential.

reading the diagrams

Mostly a tour is represented by a circle, which normally turns clockwise, but it does not matter much. The points on the circumference are now numbers t1,t2,t3.. tn and these are alternating segments that are being remove,added, r,a,r,a,..

This example is for the "General submoves for the LK TSP heuristic" image 12a So if you want to follow the new tour you step from :

• t2 to t3 in the direction of the arrow
• follow t3 to the other end because t3-t4 is removed : t8
• follow the new segment which is now added as a dotted line with arrow: t8-t1
• t1-t2 is removed : t6
• new segment : t7
• t7-t8 is removed : t5
• new segment comes from t4 (arrow is reversed) that does not matter : t4
• t3-t4 is removed : t2

That is the new cycle.

Vehicle routing problems

Concorde is a pure TSP solver, LKH is also in it's nature a tsp solver but can be adapted to solve vrp problems as well. However the results are much less impressive as for tsp.

So this part will be about VRP solvers and TSP solvers that can do VRTP.

tsplib vrp format

The .vrp files are a little different from the .tsp files, and also you should know how to interpret the results.

NAME : eil13
COMMENT : (Eilon et al, Min no of trucks: 4, Best value: 290)
TYPE : CVRP
DIMENSION : 13
EDGE_WEIGHT_TYPE : EXPLICIT
EDGE_WEIGHT_FORMAT: LOWER_ROW
DISPLAY_DATA_TYPE: NO_DISPLAY
CAPACITY : 6000
EDGE_WEIGHT_SECTION
 9    14    21    23    22    25    32    36    38    42
50    52     5    12    22    21    24    31    35    37
41    49    51     7    17    16    23    26    30    36
36    44    46    10    21    30    27    37    43    31
37    39    19    28    25    35    41    29    31    29
 9    10    16    22    20    28    30     7    11    13
17    25    27    10    16    10    18    20     6     6
14    16    12    12    20     8    10    10
DEMAND_SECTION
1 0
2 1200
3 1700
4 1500
5 1400
6 1700
7 1400
8 1200
9 1900
10 1800
11 1600
12 1700
13 1100
DEPOT_SECTION
1
-1
EOF

This is the original file, which at the time of writing could not be read by the tsp program yet. But i used that fact to explain the format here. I changed that format to one i do know how to read :

EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW
EDGE_WEIGHT_SECTION
0
9
0
14
21
0
23
22
25
0
32
36
38
42
...

I shortened the output to show the difference, LOWER_DIAG_ROW means the lower rows of a symmetric matrix including the diagonal. LOWER_ROW means no diagonal.

So the top of the matrix could be shown as :

0
9   0
14  21  0
23  22  25  0
32  36  38  42  0

So adding the diagonal zeroes and flattening it to one column converts the first row from the examples above into the one column in the example below that.

The demand section simply states how much goods are to be delivered in each point. The depot has 0 DEMAND and is usually the first location, but that can be set in the DEPOT_SECTION.

The result is put in the file last.opt IF you specify this line in the .par file used for LKH :

OUTPUT_TOUR_FILE = last.opt

Also IF the solution has NO PENALTIES. You can see that in the result :

Successes/Runs = 0/1 
Cost.min = 456, Cost.avg = 456.00, Cost.max = 456
Gap.min = 0.0000%, Gap.avg = 0.0000%, Gap.max = 0.0000%
Penalty.min = 100, Penalty.avg = 100.00, Penalty.max = 100
Trials.min = 1, Trials.avg = 1.0, Trials.max = 1
Time.min = 0.15 sec., Time.avg = 0.15 sec., Time.max = 0.15 sec.
    Size.min = 1, Size.max = 2, Penalty = 100
    Cost.min = 28, Cost.max = 122, Cost.sum = 456
Best CVRP solution:
    Cost = 100_456

For some reason the result file is not written if Penalty is anything more than 0. More on penalty functions later !!.

However the result is something like this :

NAME : eil13.248.tour
COMMENT : Length = 248
COMMENT : Found by LKH [Keld Helsgaun] Wed May 22 08:39:35 2019
TYPE : TOUR
DIMENSION : 16
TOUR_SECTION
1
2
16
5
12
10
13
15
7
11
8
3
14
4
6
9
-1
EOF

The problem started with DIMENSION 13, and can only be done by 4 VEHICLES. The output will show how many vehicles where needed in "VEHICLES = 4". Use of 4 vehicles means 3 extra stops are added to specify the return to depot. So 4 trucks means 4 DEPOTS : 0,14,15,16 This makes these the calculated trips :

1 - 2 - 1 : total capacity used : 1200, driving distance : 9+9=18 16 - 5 - 12 - 10 - 13 - 16 : 1400+1700+1800+1100=6000, 32+13+16+8+18=87 15 - 7 - 11 - 8 - 3 - 15 : 1400+1600+1200+1700=5900, 21+10+16+7+14=68 14 - 4 - 6 - 9 - 14 : 1500+1700+1900=5100, 23+12+10+30=75

18+87+68+75 = 248

That is indeed the solution presented. The distances to 14,15 and 16 are of course as if they were the depot at 1.

Penalties

The Penalty function for ACVRP simply calculates how much cargo is NOT being transported. In the case of 8.vrp when planned with capacity 100 and two vehicles it will fit, because all demands add up to 145.

CAPACITY: 100
VEHICLES: 2
DEMAND_SECTION
1 0
2 36
3 15
4 31
5 18
6 5
7 33
8 7

The solution is : Cost = 0_2550116, tour : 1 7 3 9 5 8 2 6 4 This is penalty 0 _ distance 2550116 ! Note that penalty is the most important and comes first !!

The tour is divided in 1-7-3-9 9-5-8-2-6-4-1 since 9 is a 'depot copy'

173795 + 24065 + 13228 (load 33+13 = 48) 515010 + 178753 + 180748 + 229706 + 656754 + 578057 (load 18 + 7 + 36 + 5 + 31 = 97)

So there is more room to arrange the orders, and we get a small value of distance and 0 penalty.

However if we change Capacity to 50, now we cannot fit it into two vehicles. We should get a result that has penalty 45 because penalty is the most important factor, and so we do. The solution is now 45_2906242. The tour printed is now: 1 8 2 6 7 9 5 4 3

Now the algorithm should attempt to get the smallest possible penalty : 45.

It regards a solution as better when you can deliver more goods. 1 Kg more cargo wins over 100 km less driving.

1-8-2-6-7-9 and 9-5-4-3-1

437372 + 180748 + 229706 + 515927 + 178652 (load = 7 + 36 + 5 + 33 = 81) 515010 + 472198 + 363401 + 13228 (load = 18 + 31 + 15 = 64)

totals are : 2906242 and 64+81 = 145 so 45 penalty.

When you alter the problem to allow 3 vehicles the solution changes again. Now there is an extra depot added, and the route is :

1 8 2 6 10 7 3 9 5 4, so these are 3 trips :

1-8-2-6-10 10-7-3-9 and 9-5-4-1

The costs are 0_3517120.

437372 + 180748 + 229706 + 892941 ( load = 7 + 36 + 5 = 48) 173795 + 24065 + 13228 ( load = 33 + 15 = 48 ) 515010 + 472198 + 578057 (load = 18 + 31 = 49 )

You could see how it still would not fit in 3 vehicles if the demands were different.

The number of vehicles needed is not just total demand / capacity !!

To implement varying truck sizes, the cost function should be rewritten to use an array of capacities rather than just 1. It should not be that difficult to do.

The ACVRP problems contain instances that do not fit at all and for example the A036-10f problem returns vary differing results, here are 10 runs :

Lower bound = 1428.0, Ascent time = 0.02 sec.
Cand.min = 5, Cand.avg = 5.0, Cand.max = 5
Edges.fixed = 45 [Cost = 0]

• 1: Cost = 2225_2540, Time = 0.04 sec.
• 1: Cost = 916_2831, Time = 0.12 sec.
• 1: Cost = 846_2833, Time = 0.06 sec.
• 1: Cost = 1394_2714, Time = 0.04 sec.
• 1: Cost = 440_3166, Time = 0.06 sec.
• 1: Cost = 1303_2747, Time = 0.05 sec.
• 1: Cost = 1360_2656, Time = 0.09 sec.
• 1: Cost = 440_2971, Time = 0.06 sec.
• 1: Cost = 445_3040, Time = 0.05 sec.
• 1: Cost = 1453_2772, Time = 0.05 sec.

The solution 440_2971 is taken as best solely since it's the smallest penalty which means the most cargo is transported.

The total cargo added was 2440, so here are the results as km driven per cargo unit.

2540/(2440-2225) = 2540 / 215 = 11.8139534884 2831/(2440-916) = 2831 / 1524 = 1.85761154856 2833/(2440-846) = 2833 / 1594 = 1.77728983689 2714/(2440-1394) = 2714 / 1046 = 2.59464627151 3166/(2440-440) = 3166 / 2000 = 1.583

So it might not be the ideal situation. The winner is 2.6 km driven per cargo unit. There are various better solutions. But you have to keep in mind that less product was delivered.

To get better solutions than this we have to introduce more TRIALS, since you can than see a definite narrowing down of the solutions. Also this might be the prefect way to charge customers (charge per trial). They get a single trial for free, but pay extra for more cpu time == trials.

The problem shown here has a total demand of 2440 with 10 trucks of capacity 250. So it is impossible to have 0 penalty. But 100 trials is getting there :

* 1: Cost = 769_2949, Time = 0.07 sec. 
* 3: Cost = 440_2935, Time = 0.59 sec. 
* 4: Cost = 225_3506, Time = 0.92 sec. 
* 6: Cost = 191_3279, Time = 1.83 sec. 
* 7: Cost = 122_3389, Time = 2.39 sec. 
* 8: Cost = 66_3559, Time = 3.08 sec. 
* 9: Cost = 29_3361, Time = 4.21 sec. 
* 12: Cost = 28_3600, Time = 7.88 sec. 
* 16: Cost = 24_3714, Time = 12.92 sec. 
* 19: Cost = 3_3505, Time = 17.63 sec. 
* 74: Cost = 1_3579, Time = 108.98 sec. 

The Trial numbers mark when a trial was an improvement. Still the distance diverges as the penalty gets smaller. So providing enough trucks might lead to better distances ? 1 truck extra should theoretically suffice. And it does :

* 1: Cost = 362_3052, Time = 0.05 sec. 
* 2: Cost = 209_3140, Time = 0.30 sec. 
* 3: Cost = 208_3133, Time = 0.66 sec. 
* 4: Cost = 67_3335, Time = 1.06 sec. 
* 5: Cost = 35_3434, Time = 1.62 sec. 
* 6: Cost = 30_3415, Time = 2.14 sec. 
* 8: Cost = 9_3477, Time = 3.62 sec. 
* 12: Cost = 4_3515, Time = 6.93 sec. 
* 13: Cost = 2_3404, Time = 8.24 sec. 
* 14: Cost = 2_3318, Time = 9.67 sec. 
* 37: Cost = 1_3471, Time = 38.83 sec. 
* 38: Cost = 0_3464, Time = 40.92 sec. 
* 46: Cost = 0_3310, Time = 54.05 sec. 
Writing OUTPUT_TOUR_FILE: "last.opt" ... done
Run 10: Cost = 0_3310, Time = 165.61 sec. 

Actually this is 28 km better than the best solution in the ACVRP bundle .pdf file. But as you can see it does take 54 seconds.

ACVRP paths

Asymmetric CVRP problems are converted into a 'normal' TSP by first matching the number of vehicles with extra depots. So each vehicles gets an extra depots with the same location. After that all these are doubled to make it a symmetric problem again.

Original problem locations (depots underlined)

Step 1: using 2 vehicles :
1 2 3 4 5 6 7
- 

Step 2:
1 2 3 4 5 6 7 8 9 
-             - - 

Step 3:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
-             - - --                   -- --

The cost function will return the same distance from those extra point as from depot 1. All costs between nodes and their 'peers' are made 0, all costs between depots are made huge.

The costs make the route move frictionless between nodes and their duplicates. These will end up next to eachother, and depots will always end up far away from eachother.

A real example with 8.vrp :

input :

CAPACITY: 50 
VEHICLES: 3
EDGE_WEIGHT_SECTION 
0 750363 173420 632883 515010 237950 173795 437372
968074 0 938532 834696 341652 229706 527869 975198
13228 689521 0 15289 332351 933727 355543 552727  
578057 864966 363401 0 590368 215810 976239 626475  
720674 248348 838984 472198 0 283102 734494 178753 
892941 719079 439493 656754 999298 0 515927 870821
178652 377052 24065 777759 454758 42683 0 90726 
928291 180748 450715 991265 698634 425994 694239 0 
DEMAND_SECTION 
1 0
2 36 
3 15
4 31
5 18
6 5 
7 33 
8 7 
DEPOT_SECTION
1

So the augmented problem is :

1 2 3 4 5 6 7 8  becomes 
-
                        1  2  3  4  5  6  7  8  9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
-               - -- -- --                -- -- --

The end result in the code prints this internally :

5 15 9 19 3 13 7 17 10 20 6 16 2 12 8 18 1 11 4 14
5 4  9  8 3  2 7  6 10  9 6  5 2  1 8  7 1 11 4  3
5 4  -  8 3  2 7  6  -  - 6  5 2  - 8  7 -  - 4  3

The algorithm always starts at the depot, now position 1. If it's a symmetric problem it just walks the nodes, since the problem is symmetric both directions will give the same result, and so there are two solutions anyway.

If it is asymmetric the order is important. If you take the depot node (1) then walk the route it will always end in it's duplicate depot, which is 11. The formula for that node is (depotnode + dimsaved) (1 + 10) = 11. So you can see 1 has 7 and 11 as neighbours so that means the route goes backwards : 1 -> 7 -> 8 ---> 11 -> 1

Now we walk backwards over the route and record all nodes that are no duplicates (skip all bigger than dimsaved).

1 : ok 18: skip 8 : ok 12: skip 2 : ok 16: skip 6 : ok 20: skip 10: ok 17: skip 7 : ok 13: skip 3 : ok 19: skip 9 : ok 15: skip 5 : ok 14: skip 4 : ok 11: skip 1 : ok.. done

As you see it alternates exactly between the nodes and the nodes 'peer'. This is especially clear when dimsaved is 10 : 9-19, 5-15. I can imagine it will not always alternate that smoothly, but peers will always end up 'back-to-back'.

DIMENSION : 10
TOUR_SECTION
1
8
2
6
10
7
3
9
5
4
-1

notes

The E-n101-k14.vrp set is good for a demonstration about how vrp solutions can change. Look at these iterations :

Lower bound = 817.0, Ascent time = 0.02 sec.
Cand.min = 5, Cand.avg = 5.0, Cand.max = 5
Preprocessing time = 0.02 sec.
* 1: Cost = 0_1136, Time = 13.60 sec. 
Writing OUTPUT_TOUR_FILE: "E-n101-k14.opt" ... done
* 2: Cost = 0_1110, Time = 27.03 sec. 
Writing OUTPUT_TOUR_FILE: "E-n101-k14.opt" ... done
* 4: Cost = 0_1103, Time = 62.84 sec. 
Writing OUTPUT_TOUR_FILE: "E-n101-k14.opt" ... done
* 5: Cost = 0_1098, Time = 87.36 sec. 
Writing OUTPUT_TOUR_FILE: "E-n101-k14.opt" ... done
* 9: Cost = 0_1097, Time = 221.30 sec. 
Writing OUTPUT_TOUR_FILE: "E-n101-k14.opt" ... done
* 11: Cost = 0_1096, Time = 288.72 sec. 
Writing OUTPUT_TOUR_FILE: "E-n101-k14.opt" ... done
* 13: Cost = 0_1095, Time = 383.91 sec. 
Writing OUTPUT_TOUR_FILE: "E-n101-k14.opt" ... done

From 5 to 13 all change the solution by 1 point, which is 1/10 of a percent each time, and the solutions are completely different !. By the way this was done as CVRP problem. (probably the original setting)

This may point out a flaw in using this for VRP problems and MTSP since it cannot just swap some segments and improve, but search MUCH deeper. See if a problem can be preprocessed to resemble a normal TSP with hard weights, then also the preparations (mintree, candidateset) will perform better ?

best known solutions

Seems i am still working with an older version of TSPLIB, there is one at visit 1.0.0 which is called VRPlib !!. At Least the E-n101-k14 problem above has a better solution of 1071 in that set.

There is a best known solution of 1067 now : visit

The problem file itself from tsplib says best solution 1077 This list states it is 1071 : visit That is the same as in VRPLIB-1.0.0 (see link venkatesh20) The publication for 1067 shows the solution, and that publication is from 2004 Coin-or seems to have the most up-to-date list here : visit

It say .old but it seems to be newer than the page without .old added. At least for E-n101-k14 !!

Has it been improved since ?! (Can i ??) third party software ====================

::: {.spelling} cplex lglpk unarchive glpk QSopt :::

introduction

Concorde is a famous TSP solver, sadly it comes without linear programming library. You can choose for QSopt which comes as a binary static library (but in elf so unusable) or cplex which is an IBM library that is not free.

Fortunately we also have glpk, and in the sources is described how to run concorde with glpk.

Download the glpk sources (glpk-4.45 works) and go to /glpk-4.45/examples/cplex.

• configure and build glpk

• Download the Concorde tarball co031219.tgz (version Dec 19, 2003), unpack and unarchive it.

• Copy files cplex.h and cplex.c to subdirectory concorde/LP/.

• Create file named lglpk.c in subdirectory concorde/LP/. This file

  : must contain the following two lines:

#include "cplex.c"
#include "lpcplex8.c"

Then configure concorde as if you are going to use cplex, and make it with the custom command :

./configure --with-cplex=/home/kees/projects/3pty/concorde
make CPPFLAGS=-I. LPSOLVER_INTERFACE=lpglpk.c LPSOLVER_LIB=-lglpk

You should now compile without error.

Test it with the provided tsp file :

./TSP/concorde ../LKH-3.0.4/pr2392.tsp 

The solution will be in pr2392.sol, sadly they don't print the total cost which would be easier to compare.

cplex

::: {.spelling} ldl cplex bcp dlsym dlopen concorde :::

I seem to have a free license for 50 !! years from IBM. Though it is limited to some extent.

The programs that could use cplex are for instance :

• concorde
• bcp_vrp

Log in to the ibm site and download cos_installer_preview-22.1.1.0.R0-M08SWML-linux-x86-64.bin

# we want to install to /opt/cplex 
sudo bash cos_installer_preview-22.1.1.0.R0-M08SWML-linux-x86-64.bin

Answer the questions coming along. However if you don't want to change the sources fill in /opt/ibm/ILOG/CPLEX_Studio_Community129/ for the install directory.

But if you didn't (like me :), here is a quick workaround.

sudo mkdir -p /opt/ibm/ILOG
sudo ln -s /opt/cplex /opt/ibm/ILOG/CPLEX_Studio_Community129
make
./Bin/bcp_vrp

or-tools

See this page for a working guide on installing or-tools

https://developers.google.com/optimization/install/cpp/source_linux#debian

In short the commands

sudo apt update
sudo apt install -y build-essential cmake lsb-release
git clone https://github.com/google/or-tools
cd or-tools
cmake -S . -B build -DBUILD_DEPS=ON
cmake --build build --config Release --target all -j -v

This is with the built-in solvers SCIP https://scipopt.org/index.php#license and gurobi https://www.gurobi.com/

You could also use CPLEX, GLPK and XPRESS SOLVER. Notably : no QSOPT !

Now test the installation (optional)

cmake --build build --config Release --target test -v

After successful tests : do the get started guide. https://developers.google.com/optimization/introduction/cpp

There is also a python version (and java) but c++ suits our needs the best.

HGS-CVRP

A very promising CVRP solver. But is it free to use ? We have the source so we could again do an own version.

The Readme works fine : https://github.com/vidalt/HGS-CVRP

in short

git clone https://github.com/vidalt/HGS-CVRP.git
cd HGS-CVRP
mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release -G "Unix Makefiles"
make bin
# optional :
ctest -R bin --verbose

Now i had an instance of X-n157-k13.vrp installed but that has a VEHICLE line inside. hgs comes with it's own patched vrp files in the Instances directory. So run it like this.

./hgs ../Instances/CVRP/X-n157-k13.vrp mySolution.sol -seed 1 -t 30

The only difference seems to be the absence of the VEHICLE line. We need to specify that on the commandline with -t

Note that you need to alter standard .vrp files on a number of points.

• VEHICLES : X # this does not get recognized, remove these lines
• EDGE_WEIGHT_FORMAT : also not recognized
• NODE_COORD_TYPE : also remove
• EDGE_WEIGHT_TYPE : EUC_2D # change always, FULL_MATRIX etc won't work
• NODE_COORD_SECTION : here there should be integers! so remove all . in the file so 6.4020 becomes 64020
• DISPLAY_DATA_TYPE : also remove
• EDGE_WEIGHT_SECTION : should be completely removed

concorde

Later.. this program has been known to work with gnu GLPK but a cplex comparison would be nice..

But .. later

bcp_vrp

The main advantage of bcp_vrp is that it does VRP where concorde does TSP. This program was provided on the VRPLIB site (visit) and seems to be free for use ?!. I expect this to be very slow but exact, being a branch and cut and price algorithm.

Installation is a bit of a bother, first alter the Makefile to changes this :

tar -zxvf rbcp_cvrp060317.tar.gz
cd bcp_vrp
vi Makefile

#ARCH = $(shell arch) # this gives x86_64 !!
ARCH = "x86-64"

Then you need to install cplex with the installer, and alter the directories for include and lib. Then there will be errors about string conversions, so you need to set the standard to c++98, in Makefile add this :

CCFLAGS += -std=c++98 -w -pthread

The -w just ignores all warnings: we are not here to refactor someone else code. The -p is discussed further down, just add it

The next error will be an undefined constant : MODE_COMPLEX_EXACT, but since it is used in an assert, just remove it :

//assert (mode == MODE_COMPLEX_EXACT);

Next undefined references to dlsym, dlopen etc. So just add -ldl to :

LIB_FLAGS += -lcplex -ldl

In addition : when trying in 2020 there also was a problem with pthreads:

undefined reference to pthread_rwlock_rdlock

I just took the shortcut : add -pthread to all compilation steps. Note : NOT -lpthread !! -pthread. So the CCFLAGS becomes :

CCFLAGS += -std=c++98 -w -pthread

After these changes you will be able to make Bin/bcp_vrp.

Testing it with an instance :

./Bin/bcp_vrp file.vrp nvehicles upperbound

However, it always complains about too many depots. Debugging needed.