Dynamic and Continuous-Time Service Network Design

The thesis focuses on two fundamental problems in transportation and logistics, namely, service network design, and operation, with a focus on high precision, and large scale. A typical approach to solving the design problem is by modeling with time-expanded networks and solving using integer programming, however this often yields an approximation to the continuous-time optimal solution. We investigate the price of this approximation caused by the discretization of parameters involving time, and introduce two algorithms that efficiently solve the continuous-time problem. Both algorithms dynamically build and refine a subset of the full time-expanded network, so that the associated integer program is more computationally tractable, while still providing a guarantee of continuous-time optimality. While both approaches share the same overall structure, as well as many modeling similarities, the predominant difference is in the dynamic refinement step, and the underlying principles used to guarantee convergence. The second algorithm is further extended to support in-tree loading, and freight splitting. In-tree loading simplifies operational overhead by requiring freight with common ultimate destination cross-docked at a terminal to travel along the same path; in this way terminal operators need only look at the ultimate destination in order to load shipments. Freight splitting allows for increased utilization by arbitrarily breaking shipments into smaller pieces; it is also a modeling technique to support aggregating shipments with common origin/destination in order to keep the model size tractable. The design problem is primarily concerned with the routing of freight and service capacity, and is typically solved infrequently using predicted freight, whereas the operation problem is highly dynamic, using actual day-to-day volumes, and focuses on loading/dispatching vehicles, as well as crew and resource scheduling. We introduce an efficient heuristic to solve a large scale real-life operation problem, as well as providing new and useful metrics for evaluating operational performance.