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

连续时间服务网络设计模型的高效算法，可准确估计时间整合机会

• 批准号: 1435625
• 负责人: Mike Hewitt
• 金额: $ 34.99万
• 依托单位: Loyola University of Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1435625&HistoricalAwards=false
• 关键词: Efficient; Algorithms; Continuous; Time; Service

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.

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