Continuous-time service network design : new models, relaxations, and solution methods

Abstract

This thesis aims to enrich both deterministic and robust optimization techniques for the continuous-time service network design problem (CTSNDP), which occurs widely in practice. It consists of two studies, with the first one incorporating holding costs and the second one further considering uncertain travel times. The CTSNDP is to minimize the total operational cost for consolidation carriers by optimizing the schedules of transportation services and the routes of shipments for dispatch, which can occur at any time point along a continuous-time planning horizon. In order to be cost effective, shipments often wait to be consolidated, which incurs holding costs. Holding costs not only contribute to the overall total cost, but also affect the decisions on routing and consolidation plans in the CTSNDP. Despite their importance, holding costs have not been considered in existing exact solution methods for the CTSNDP, since incorporating them significantly complicates the problem. The correctness of all these methods relies on the assumption of zero holding costs. To tackle this challenge, the first study of this thesis develops a new dynamic discretization discovery (DDD) algorithm, based on the typical time-expanded network, that can solve the CTSNDP with holding costs (CTSNDP-HC) to exactly optimum. The algorithm is based on a novel relaxation model, a new upper bound heuristic, and a new discretization refinement procedure. Results of computational experiments demonstrate the effectiveness and efficiency of our proposed algorithm, both in finding optimal solutions to the CTSNDP-HC and in producing tight lower and upper bounds. The experimental results also show the benefits of considering holding costs in the CTSNDP-HC. Due to various uncertainty factors, such as weather and traffic conditions, actual travel times often fluctuate. Travel time uncertainty is thus a vital source of variability in the CTSNDP-HC. This motivates the second study of this thesis on the robust CTSNDP-HC. With uncertain travel times incorporated, solutions to the robust CTSNDP-HC can lead to service network designs that not only provide reliable services to transit shipments, but also minimize their operational costs. However, the time-expanded network used in modeling and solving the deterministic CTSNDP-HC turns out to be inappropriate for incorporating uncertain travel times in the robust CTSNDP-HC. To address this challenge, a new deterministic optimization model for the CTSNDP-HC based on the physical network is newly proposed. This new model formulates the time component of the CTSNDP-HC by a set of variables and constraints, with their indices indicating shipment consolidations. Based on this, we derive a two-stage robust optimization model for the robust CTSNDP-HC, using a probability-free budgeted uncertainty set to incorporate uncertain travel times. To solve the robust CTSNDP-HC, we apply a classical column-and-constraint generation (C&CG) method, and then enhance the method via some novel optimization techniques of dynamic parameter adjustment. Results of computational experiments demonstrate the effectiveness and efficiency of the two-stage robust optimization model and the enhanced C&CG solution method, as well as the benefits of incorporating uncertain travel times in the robust CTSNDP-HC.