I need to solve capacitated asymmetrical vehicle routing problem with time windows on ~30k points. Time limits for calculations are 2 hours. I've tried using Clarke and Wright savings algorithm, it is very fast but too inaccurate, and I've tried using LKH-3 util for solving my task. It finds almost optimal solution, but unfortunately it takes up to several days to calculate. Is there some intermediate option with best solution quality on 2 hour runs?
Currently I'm using python 3 for solving this task, although any language is acceptable. The graph is the graph of garbage producers in modern cities and around 20% of the points have time bounds, constraining time it can be visited e.g. from 16:00 to 17:00. The edges of the graph is an estimated time, that a vehicle will spend traveling between nodes.