  While many time-dependent network design problems can be formulated as
time-indexed formulations with strong relaxations, the size of these
formulations depends on the discretization of the time horizon and can become
prohibitively large. The recently-developed dynamic discretization discovery
(DDD) method allows many time-dependent problems to become more tractable by
iteratively solving instances of the problem on smaller networks where each
node has its own discrete set of departure times. However, in the current
implementation of DDD, all arcs departing a common node share the same set of
departure times. This causes DDD to be ineffective for solving problems where
all near-optimal solutions require many distinct departure times at the
majority of the high-degree nodes in the network. Region-based networks are one
such structure that often leads to many high-degree nodes, and their increasing
popularity underscores the importance of tailoring solution methods for these
networks.
  To improve methods for solving problems that require many departure times at
nodes, we develop a DDD framework where the set of departure times is
determined on the arc level rather than the node level. We apply this arc-based
DDD method to instances of the service network design problem (SND). We show
that an arc-based approach is particularly advantageous when instances arise
from region-based networks, and when candidate paths are fixed in the base
graph for each commodity. Moreover, our algorithm builds upon the existing DDD
framework and achieves these improvements with only benign modifications to the
original implementation.
