Heuristics for VRPTW

[bkj]

This is a really wonderful collection of heuristics for CVRPs -- great job!

I'm wondering whether there are any algorithms here that are applicable for VRPs with time windows. Alternatively, do you have any good pointers to descriptions / implementations of heuristics for VRPTWs?

Thanks! ~ Ben

[yorak]

Hi Ben,

be sure to check the alternative open source libraries surveyed in my PhD dissertation: https://jyx.jyu.fi/bitstream/handle/123456789/65790/978-951-39-7826-6_vaitos01112019.pdf#page=154 I do not remember exactly which of them supported TWs, but I think several of them have that feature covered.

Out of the algorithms in VeRyPy, the local search operators could be quite easily be adapted to check also TW constraint violations (now they check for capacity C and the maximum route length L). Few local search (LS) operators (i.e. two-opt and one point move), together with modified savings and sweep with TW support (see Solomon 1987) would allow generating initial solutions and improving those with LS. This would already generate fairly good solutions for some problems. Also, building metaheuristics on top of that would be fairly straightforward. Also, modified sweep and LS ops for TWs would make it possible to use some quite powerful matheuristics in VeRyPy like the Petal set covering algorithm ptl from Foster & Ryan (1976).

BR, Jussi

Foster, B. A. & Ryan, D. M. 1976. An integer programming approach to the vehicle scheduling problem. Journal of the Operational Research Society 27 (2), 367–384.

Solomon, M.M., 1987. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), pp.254-265.

[yorak]

For example, 2-opt would require modifications to (at least) these locations: https://github.com/yorak/VeRyPy/blob/eaac6e210d861441071565575750a2f0e25dfb72/local_search/intra_route_operators.py#L81 https://github.com/yorak/VeRyPy/blob/eaac6e210d861441071565575750a2f0e25dfb72/local_search/inter_route_operators.py#L129 https://github.com/yorak/VeRyPy/blob/eaac6e210d861441071565575750a2f0e25dfb72/local_search/inter_route_operators.py#L164 Here, one should be sure to take reversing the sequence into account (it might violate some TW constraints). Also, one of the assumptions VeRyPy makes is the symmetric distances. It might work for asymmetric distances, but it has not been extensively tested.

[yorak]

Yes, for a single algortihm such as Savings that would be rather straightforward. Please see the work of Solomon (1987), where he proposes a savings calculation for VRPTW -> https://pubsonline.informs.org/doi/abs/10.1287/opre.35.2.254

[yorak]

Hi @s184311 and @bkj ,

I decided to take a quick jab towards VRPTW support today. I implemented the constraint check for the parallel savings (in classic_heuristics/parallel_savings.py, but left the savings calculation for you to implement :)

To see what I have been up to, please consider checking out the branch vrptw_savings where you can find the file classic_heuristics/vrptw_savings.py. There is also a simple example script with two customers smoke testing the savings VRPTW functionality in examples/vrptw_savings_test.py. Just remember that you have to add VeRyPy folder to PYTHONPATH, e.g., with the command export PYTHONPATH=$PYTHONPATH:$(pwd) given that you use *Nix/Bash and are in the VeRyPy root folder.

Now, in the callback of vrptw_savings.py:placeholder_vrptw_savings_f(D, ctrs) you can write the calculation of the time window overlapping savings value part s_t! One could probably come up with a savings formula of ones own, but I'd propose referring to the literature. E.g., see Solomon (1987) and Van Landeghem (1988) that both seem relevant. From my quick read it seems Solomon does not give the formula quite directly (no surprises there, welcome to the world of VRP classical heuristic archaeology!), but I hope Van Landeghem (or some other source) is more explicit in describing how to calculate the overlapping of time windows for merge candidates i and j considering the time D[i,j] it takes to travel from i and j. Best of luck and do not hesitate to ask for clarifications or surprise me with a pull request! :D

Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2).

Van Landeghem, H. R. G. (1988). A bi-criteria heuristic for the vehicle routing problem with time windows. European Journal of Operational Research, 36(2), 217-226.

[yorak]

Oh the hubris. After a good night sleep I came to conclusion that I underestimated the effort. It turned out that my initial attempt in implementing CVPRTW support for parallel savings was plainly and completely wrong in so many ways. However, I've now pushed some additional code to the vrptw_savings branch. The current implementation still fails to respect the time window constraints but should be much closer to working properly. I've also included some external constraint checking (in file cvrp_ops.py) that actually tries to verify that the solution is valid.

However, now I really have to abandon this for a while and jump on more acute work. Good luck.

[yorak]

Made few more fixes (see d7cf87b) and now the TW supported savings in vrptw_savings branch produces feasible solutions \o/. Test it with:

jussi@Ogre:~/Projects/Research/VeRyPy$ python examples/vrptw_savings_test.py 
1) The solution using non TW sensitive savings function was:

SOLUTION: [0, 1, 0, 2, 0, 3, 4, 0, 5, 6, 0, 7, 8, 9, 0, 10, 11, 12, 0,
    13, 15, 16, 0, 14, 21, 0, 17, 18, 19, 23, 0, 20, 22, 0, 24, 25, 0]
ALL SERVED: True
IS C FEASIBLE: True
IS TW FEASIBLE: True
SOLUTION K: 11
SOLUTION COST: 2825 

SOLUTION LENGTH: 575
ROUTES:
No. Cost    Length  Load    Route
1   128.00  38.00   10.0    [0, 1, 0]
2   132.00  42.00   30.0    [0, 2, 0]
3   216.00  36.00   20.0    [0, 3, 4, 0]
4   218.00  38.00   30.0    [0, 5, 6, 0]
5   311.00  41.00   50.0    [0, 7, 8, 9, 0]
6   347.00  77.00   40.0    [0, 10, 11, 12, 0]
7   351.00  81.00   110.0   [0, 13, 15, 16, 0]
8   263.00  83.00   30.0    [0, 14, 21, 0]
9   442.00  82.00   60.0    [0, 17, 18, 19, 23, 0]
10  205.00  25.00   30.0    [0, 20, 22, 0]
11  212.00  32.00   50.0    [0, 24, 25, 0]
Total   2825.00 575.00
...