Finding Minimal Discretizations in Dynamic Discretization Discovery for Continuous-Time Service Network Design

The dynamic discretization discovery framework is a powerful tool for solving network design problems with a temporal component by iteratively refining a time-discretized model. Existing approaches refine the time discretization in ways that guarantee eventual termination. However, refinement choices are not unique, and better choices can yield smaller and easier-to-solve time-discretized models. We pose the optimal refinement problem (ORP) of finding a discretization that minimizes the number of timed arc copies, and we show that ORP is NP-hard. We further develop a mixed-integer programming model for ORP.  Experiments show that, within a dynamic discretization discovery algorithm, solving ORP can reduce model size and improve solution times on benchmark instances.

Article

Download

View PDF