Reoptimizing the Vehicle Routing Problem with Urgent Stochastic Customers

In this paper we propose an alternative online solution to the Vehicle Routing Problem with Urgent Stochastic Customers, a Vehicle Routing Problem with stochastic customers and demands where lowering response times to service requests is the main objective. Here, the bi-objective problem of minimizing tours while also minimizing response times to urgent stochastic customers needs to be solved, taking longer tours as a cost of reducing response times. Our proposition is to recalculate tours whenever stochastic customers request service, using a more efficient (but less optimised) Vehicle Routing Problem with Time Windows. The proposed heuristic (Reoptimization Heuristic) is evaluated through a simulation study. Results show the Reoptimization Heuristic to deliver an increase in travel times without im- provement of the response times. However, results indicate that the Reoptimization Heuristic becomes more efficient with a frequency of urgent requests.