Introduction
Try to learn it someday.
stretch image
First tip : don't try to do this with a svg file !!! I would imagine http can resize svg to whatever it wants, but NOT when using these constructs:
.prodload {
position: absolute;
bottom: 0px;
left: 0px;
overflow: visible;
white-space: nowrap;
background-image: url("/assets/triangle_load.png");
background-size: 100% 100%;
}
This works fine with a png, but NOT with svg !!
The problem i tried to solve here was showing load and unload actions in the trip-detail page with a diagonal line. Before this was done like this.
+---+ +---+ +---+ +---+
| | | | | | | |
| | |---|==drive== | | ==drive= | |
|---| |###| |---| | |
|###| |###| |###| | |
+---+ +---+ +---+ +---+
load Load Unload Unload
This has the disadvantage that we have to choose the amount at the start or at the end of the load/unload. In this case we took the end.
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
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
With N the set of nodes
and E is the set of edges
Each edge (i, j) has associated a weight c(i, j).
A cycle is a set of edges
with
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.
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 :
| input file | |
|---|---|
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 :
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 file | |
|---|---|
Also IF the solution has NO PENALTIES. You can see that in the result :
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 :
| tour file | |
|---|---|
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.
| penalties | |
|---|---|
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 :
| output | |
|---|---|
- 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 :
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 :
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)
| acvrp | |
|---|---|
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 :
So the augmented problem is :
| augmented problem | |
|---|---|
The end result in the code prints this internally :
| result | |
|---|---|
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'.
notes
The E-n101-k14.vrp set is good for a demonstration about how vrp solutions can change. Look at these iterations :
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:
Then configure concorde as if you are going to use cplex, and make it with the custom command :
| compile | |
|---|---|
You should now compile without error.
Test it with the provided tsp file :
| test run | |
|---|---|
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)
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
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.
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 :
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 :
| more tweaks | |
|---|---|
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 :
| disable | |
|---|---|
Next undefined references to dlsym, dlopen etc. So just add -ldl to :
| add libraries | |
|---|---|
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 :
| add flags | |
|---|---|
After these changes you will be able to make Bin/bcp_vrp.
Testing it with an instance :
| test run | |
|---|---|
However, it always complains about too many depots. Debugging needed. Would be better to just show what amount was added/removed with a triangle : (something like)
+---+ +---+ +---+ +---+
| | | | | | | |
| | | |==drive== | | ==drive= | |
| | | /#| |#\ | | |
| /#| |###| |###| |#\ |
+---+ +---+ +---+ +---+
load Load Unload Unload
But that means we need to draw a triangle with the exact sizes to match the action. That is not a html default option so i chose to create two images like this.
+------+ +------+
| /| |\ |
| /#| |#\ |
| /##| |##\ |
| /###| |###\ |
| /####| |####\ |
|/#####| |#####\|
+------+ +------+
And resize-stretch those to form the top of the loads/unloads. We can generate such an image with svg :
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<svg height="100" width="100" xmlns="http://www.w3.org/2000/svg">
<polygon
points="0,100 100,100 100,0"
style="fill:salmon;stroke:purple;stroke-width:0"
id="polygon2" />
</svg>
However it we NEED to create a PNG from that to make it work. Since convert seems to hang completely i used inkscape export for that. Now this file can be stretched with the css above. The html code for a trip detail then becomes :
<!-- could be multiple trips on one day -->
<div *ngFor="let a of (trip.sequence)" style="float: left">
<!-- load actions -->
<div *ngIf="a.type=='l'" [style.width.px]=a.widd [ngClass]="'load-item'">
<div [style.width.px]=a.widd [style.bottom.%]=a.prct [style.height.%]=a.slope class="prodload"></div>
<div [style.width.px]=a.widd-2 [style.height.%]=a.prct class="prodinner"></div>
</div>
<!-- unload actions -->
<div *ngIf="a.type=='u'" [style.width.px]=a.widd [ngClass]="'unload-item'">
<div [style.width.px]=a.widd [style.bottom.%]=a.prct [style.height.%]=a.slope class="produnload"></div>
<div [style.width.px]=a.widd-2 [style.height.%]=a.prct class="prodinner"></div>
</div>
<!-- drive actions -->
<div *ngIf="a.type=='d'" [style.width.px]=a.widd [ngClass]="'drive-item'"></div>
</div>
Note we use two divs, a square one with the amount still in the truck. And a triangular one for the top part.
Look in setSizes() to see how the prct and slope are filled.
Quick tips
Using flexbox
Try this site visit
Using grid
Interactive :
Prevent line breaks on whitespace in div
.tpc-root {
display: flex;
white-space: nowrap;
justify-content: left;
grid-area: txt;
}
The correct output
examining css
Sometimes we can learn a lot from how others have styled a webpage. But how to extract the styles is not all that clear. Here is an attempt to describe that process.
chrome devtools
ctrl-shift-i opens up the devtools page. Find the exact component you need by using the elements tree. As an example, i had a similar top navbar for the root tree item in the topics bar, but it just was not performing the same. Here is a print of the GQueues topbar
<div class="gq-queue-panel-header">
<div class="gq-queue-panel-title-wrapper">
<div class="gq-queue-panel-toggle material-icons md-dark">arrow_drop_down</div>
<div class="gq-queue-panel-title">My Queues</div>
<div class="gq-queue-panel-menu-btn gq-icon-button material-icons md-dark">more_vert</div>
</div>
</div>
I have almost the same bar, however i also want the same hover style but that is not shown by default. Here is how to enable that.
- click on the gq-queue-panel-header and will be highlighted.
- click on the :hov next to Filter in the right tab with all the styles
- You now get a sheet with togglebuttons for various element states.
- Choose the one you want to see, and it will show in the output
- But also the styles to create this will be shown in the styles window.
- Copy the styles you need with the right mouse button
For instance, i copied.
So attempt 1 was this in the RootBlock.vue file
.topic-line {
display: grid;
grid-template-columns: 30px auto;
grid-template-areas:
"check txt";
justify-items: stretch;
border-top-right-radius: 20px;
border-bottom-right-radius: 20px;
}
.topic-line:hover {
background: grey;
}
However this painted the text grey when hovered over, but the rest of the line stayed white. Here is where i always get lost and revert to trying all permutations i can find. But you should actually debug this like this.
- Walk to the element tree to the component that should be grey.
- select it and watch the styles pane
- if the styles are greyed out, they are just not editable/adjustable in devtools
- Mostly just proceed to 'computed' tab and find the style, in my case background-color
- Next to the background-color it says white/rgb()
- Underneath it says white .topic-line.
- You can right click the line and choose navigate to style
It will bring you to the css definition that gave it this value. It still says
Here you will recognize your mistake, since you left the old definitions in the TopicBlock.vue file. So there are two sections of topic-line { } in the vue app and you can see how vue handles by clicking on the style link in the right corner of the style box. It will bring you to a rough layout of the complete document with rows of
<style type="text/css">...</style>
<style type="text/css">...</style>
<style type="text/css">...</style>
<style type="text/css">...</style>
<style type="text/css">...</style>
<style type="text/css">...</style>
<style type="text/css">
.topic-id {
display: flex;
justify-content: center;
align-items: center;
grid-area: id;
width: 30px;
height: 100%;
border-radius: 10px 0px 0px 10px;
}
.topic-check {
display: flex;
justify-content: left;
grid-area: check;
}
.topic-icon{
flex-grow: 1;
justify-content: center;
grid-area: check;
background: white;
}
.topic-caption {
width: 200%;
flex-grow: 14;
border: none;
justify-content: left;
}
.topic-line {
display: grid;
grid-template-columns: 30px auto;
grid-template-areas:
"check txt";
justify-items: stretch;
background: white;
}
.container {
font-family: sans-serif;
background: white;
margin: 8px 0;
}
.tree-node {
border: none !important;
}
</style>
<style type="text/css">...</style>
<style type="text/css">...</style>
They are just placed after eachother and later ones will override earlier ones. You can change this behavior in vue by adding "scoped" to the style tag.
<style scoped>
.topic-id {
display: flex;
justify-content: center;
align-items: center;
grid-area: id;
width: 30px;
height: 100%;
border-radius: 10px 0px 0px 10px;
}
...
You should probably always do this, and provide a separate css file for shared css !!
troubleshooting
grid cell does not expand to multiple columns
In the grid layout for the config-editor of the planner this occurred. We wanted two edit fields start and end time next to eachother and the next field (postal code) spanning two columns.
Various problems were encountered so here is what worked.
- use grid-template-areas: (i did it in the style sheet) and NOT gdAreas=
- use [style.grid-area]="'u2'" (not gdArea=...)
- use it in the outer element (mat-form-field in this case)
So it now looks like :
<div [formGroup]="configGroup"
class="config-edit-item"
display="grid"
gdGap="1px 10px"
gdRows="auto auto"
>
...
<mat-form-field floatlabel="auto" [style.grid-area]="'l1'" >
<mat-label for="config-depot-input">Depot postcode:</mat-label>
<input matInput id="config-depot-input" type="text" class="form-control" formControlName="depot">
</mat-form-field>
With css