Learn to Optimize the Constrained Shortest Path on Large Dynamic Graphs

The constrained shortest path (CSP) problem has wideapplications in travel path planning, mobile video broadcasting andnetwork routing. Existing works do not work well on large dynamicgraphs and suffer from either ineffectiveness or low scalability is-sues. To overcome these issues, in this paper, we propose an efficientand effective solution framework, namelyCSP_GS.Thesolutionframework includes two key components: (1) the techniques todecompose a large CSP instance into multiple small sub-instancesand (2) the developed learning model CSP_DQN to solve small CSP instances. The evaluation result on real road network graphs indicates that our approach CSP_GS performs well on large dynamicgraphs by rather high quality and reasonable running time, and particularly adapt to significant graph changes even with brokenedges. To the best of our knowledge, this is the first learning-basedmodel to well solve theCSPproblem on large dynamic graphs.