Learn from c4v4/LKH3

[tuananhdao]

It looks like they managed to gain a 20 to 30 speedup compared to the original LKH3 in this repo:
https://github.com/c4v4/LKH3

Maybe some ideas to look into:

• Cache? on the cost function (Done and merged WIP: Caching system improvement  #9 ). This results in at least 1.5 speedup in benchmark size 2000.
• Their modified penalty functions, mainly in this commit: c4v4/LKH3@04c636f. In progress, see this PR: Implement c4v4 MTSP #10

Modified penalty functions

MOTIVATION

• Profiling shows that penalty calculation takes the majority of time, close to 100% of each iteration.
• PR Implement c4v4 MTSP #10 will decrease the complexity of penalty calculation from O(N) to O(1) for almost all iterations (except a few special ones).
• For N=number of cities/customers=~O(1000), this will result in a few hundred speedup, as also shown in c4v4 benchmark results.

GOAL

• Improve the penalty function of MTSP_MINMAX similar to CVRP in the c4v4 repo.

Penalty functions

• Realization: CVRP = MTSP MINSUM + Capacity constraints. This means that the improved version of MTSP MINSUM can be obtained by removing all the capacity constraints.
• But we are interested in MTSP MINMAX. See the comments in Penalty_CVRP.c and Penalty_MSTP.c in the PR for helpful info.

Solution presentation
For example, SALESMEN=2 and the number of nodes DIMENSION=6. A solution/tour can be:
LKHpy [0 1 2 3 0 0 5 4 0]
LKH [1 2 3 4 7 6 5 8]
There are 2 routes/petals in this solution/tour because SALESMEN=2. The first salesman traverses first, second, and third nodes. The second salesman visits the rest.
In LKH (the original C library), indices start from 1. Moreover, 7 and 8 are depots (without duplicates such as in LKHpy), which are the same as 1.

New variables

• cava_PetalsData: an array of size SALESMEN+1, containing route data of a petal (a route). The first element cava_PetalsData[0] is a dummy petal, to which all the depot nodes point. cava_PetalsData[1], ..., cava_PetalsData[SALESMEN] corresponds to the routes of the first, second, ... salesmen.
  In the above example, the LKH nodes 1, 2, 3, 4, 5, 6, 7, 8 point to cava_PetalsData 0, 1, 1, 1, 2, 2, 0, 0
• struct RouteData: flag is for counting the involved petals/routes in a penalty calculation, OldPenalty ...