The objective of the research supported by this award is the development of planning methods for in service systems that will enable high-velocity services in a cost-effective manner. The main motivation is in planning of transportation services by consolidation carriers. Consolidation carriers play a prominent role in order fulfillment and the supply chains that support product manufacturing. With the continued trend towards just-in-time practices, fast shipping requests in the retail sector are echoed in the supply chains providing the products ordered. As a result, many consolidation carriers are facing increased pressure to deliver goods in less time and at low cost. Transportation planning decisions for a consolidation carrier have both a geographic and temporal component. A common technique for handling time in planning models is discretization, which means that a model will include the decision that the dispatch occurs in a certain time window. The planning model will represent time at each facility with a series of windows, with the choice of windows determined a priori. Customer demands for rapid delivery necessitate a fine granularity, i.e., many narrow time windows. Existing solution methods cannot handle that level of granularity efficiently enough to be useful in practical settings. This award will yield solution methods that can handle precise representations of time, enabling carriers to provide, in a cost-effective manner, the short delivery times requested by their customers (some of the savings may even be passed on to the customers). These methods will help both the carriers and the companies they support compete in a global economy. As cost is primarily a function of (trailer) miles traveled, reducing miles can also lead to a reduction in emissions. By modeling time more precisely, carriers may also be able to better synchronize their transportation options, leading to greater use of greener options like rail.
While there is widespread use of discretizations of time in service network design models the fundamental question behind their use has not yet been answered; namely, "Can one produce a methodology that yields the benefits of discretizing time to a very fine degree without explicitly modeling each discrete point in time?" The research supported by this award will answer this question in the affirmative. A service network design problem defined on a very fine discretization of time will be studied so that consolidation opportunities can be accurately captured. An algorithmic framework that can be adapted to this problem will be developed, yielding an algorithm that can solve it in a runtime that is acceptable for use in practice. The framework will be primal-dual in nature, and algorithms that follow it will repeatedly solve service network design models, while dynamically adjusting the time representation. One representation will yield a relaxation of the problem (the dual), while the other will produce a feasible solution (the primal). The framework will be extended so that it may be used to initiate the development of algorithms for a broader class of service network design models. For example, models that value or choose the times when shipments are available for pickup and due for delivery, which impact how they can be consolidated with other shipments. Moreover, the framework will be extended to produce algorithms that can solve these models in reasonable run-times.
