As information availability increases, and the ability to redirect vehicles becomes evermore common and cheap, methods for exploiting the new capabilities are evolving. Routing problems from the real world tends to be stochastic in nature, and their deterministic counterparts from academia an approximation. If the degree of stochasticity is significant, including it in the optimization often results in solutions that are of better quality and much more likely to be feasible. Given enough time, the optimal robust solution to the stochastic problem can be found. For online problems that time is rarely available.
A method is presented, that allows for more robust solutions through distribution sampling and Single Instruction Multiple Data (SIMD) instructions. SIMD instructions such as Advanced Vector Extensions (AVX) are available on most modern desktop processors, and they can be integrated into most existing heuristics for the deterministic problems with modest effort.
The focus is on the application of these methods in a dynamic reoptimization environment. The overhead of the method is demonstrated to be small, and different sampling strategies are presented, and their impact on solution cost and robustness are analysed.
| Subject : | : | Abstracts |
| Topics | : | Dynamic vehicle routing |
| Topics | : | Parallelism |
| Topics | : | Stochastic vehicle routing |
| PDF version | : |  PDF version |
