(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science
   

COMPUTER SCIENCE COLLOQUIUM

Fast robust solutions to stochastic VRPs using SIMD instructions

Rune Larsen
Institut for Transport. Transportoptimering og trafikteknik
DTU

Tuesday, 06 December, 2016 at 14:15
IMADA's Seminar Room

ABSTRACT

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. Along with the context of the problem, 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, and the overhead involved is demonstrated to be small.

Host: Jørgen Bang-Jensen


SDU HOME | IMADA HOME | Previous Page
Daniel Merkle