Efficient Algorithms for Continuous Time Service Network Design Models that Accurately Estimate Consolidation Opportunities in Time

该奖项支持的研究目标是开发服务系统的规划方法，以经济有效的方式实现高速服务。主要动机是在规划运输服务的整合承运人。整合运营商在订单履行和支持产品制造的供应链中发挥着突出的作用。随着准时制实践的持续趋势，零售业的快速运输要求在提供订购产品的供应链中得到了回应。因此，许多合并承运人面临着在更短的时间内以更低的成本交付货物的压力。整合承运人的运输规划决策既有地理因素又有时间因素。在规划模型中处理时间的一种常用技术是离散化，这意味着模型将包括调度在某个时间窗口内发生的决策。规划模型将用一系列窗口表示每个设施的时间，窗口的选择是先验确定的。客户对快速交付的需求需要精细的粒度，即许多狭窄的时间窗口。现有的解决方案方法无法有效地处理这种粒度级别，因此无法在实际设置中发挥作用。该奖项将产生能够处理精确时间表示的解决方案方法，使运营商能够以经济有效的方式提供客户所要求的短交付时间（一些节省甚至可以传递给客户）。这些方法将有助于运营商及其支持的公司在全球经济中竞争。由于成本主要是拖车行驶里程的函数，减少行驶里程也可以减少排放。通过更精确地建模时间，运营商还可以更好地同步他们的运输选择，从而更多地使用铁路等更环保的选择。虽然在服务网络设计模型中广泛使用时间离散化，但其使用背后的基本问题尚未得到回答；也就是说，“是否可以产生一种方法，在不明确地对每个离散时间点建模的情况下，将时间离散到非常精细的程度？”这个奖项支持的研究将肯定地回答这个问题。一个服务网络设计问题定义在一个非常精细的离散时间将被研究，以便整合机会可以准确地捕获。一个可以适应这个问题的算法框架将被开发出来，产生一个可以在实际使用中可接受的运行时解决这个问题的算法。该框架本质上将是原对偶的，遵循该框架的算法将反复求解服务网络设计模型，同时动态调整时间表示。一种表示将产生问题的松弛（对偶），而另一种表示将产生可行的解决方案（原始）。该框架将被扩展，以便它可以用于为更广泛类别的服务网络设计模型启动算法的开发。例如，评估或选择货物可提取和交付时间的模型，这会影响它们如何与其他货物合并。此外，该框架将被扩展以产生能够在合理的运行时间内解决这些模型的算法。

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.