So no, we haven't yet tested using GPUs.
edit: Can you provide insight?
It is a local search algorithm that probably has simulated annealing or tabu search as a metaheuristic.
Although, they probably segment the deliveries to some common starting points and the problem size is reduced significantly - maybe to around thousand orders per starting point.
Research can easily optimize thousands of deliveries very effectively.