Dynamic service of geographically dispersed time-sensitive demands

This paper presents a new framework that models the novel dynamic vehicle dispatch problem with holding costs (DVDPHC), which focuses on serving stochastic demands at geographically dispersed locations in a timely manner. This framework is applicable, among others, to the post-disaster ambulance bus routing problem, where an ambulance bus must pick up (urgent) patients at geographically dispersed locations and bring them to a centrally-located hospital as quickly as possible. Solving the DVDPHC requires a dynamic decision-making rule at each decision moment for which demands to serve at the current location, and where to direct the vehicle next. We propose a heuristic based on approximate dynamic programming combined with a neural network (ADP-NN) for effectively solving the DVDPHC. Numerical experiments demonstrate that our proposed method is fast, scalable and robust. Furthermore, it keeps up with computationally heavy direct lookahead (DLA) benchmarks on 120 large representative instances, achieving on average 12.77% total cost improvement. Numerical analysis also reveals that our proposed method exhibits complex self-learned flexible behavior, such as waiting near locations in anticipation of new demand.