The Robust Vehicle Routing Problem

鲁棒车辆路径问题

• 批准号: 0409887
• 负责人: Fernando Ordonez
• 金额: --
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-07-01 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0409887&HistoricalAwards=false
• 关键词: Robust; Vehicle; Routing; Problem

A growing number of industries decide daily how to route a fleet of vehicles from a depot to service a geographically dispersed set of customers, for example courier services, trucking companies, and demand responsive transportation services. This is known in the academic literature as the vehicle routing problem (VRP). The routing usually takes place in an uncertain environment in which the travel times are variable (due to current traffic conditions) and the demand is also uncertain (customers could "call in" during operations). Under these uncertainties it turns out that the optimal routing solution decided a priori can in fact be very inefficient. This research aims at obtaining a routing solution that performs well for all possible uncertainty scenarios and, therefore, is a better solution in practice for these industries. These robust solutions have the potential to reduce operating costs in practice for the broad range of industries which face routing problems daily. In addition the techniques developed for the routing problem can in principle be applied to other discrete choice problems important for industry, such as the problem of deciding where to open a warehouse to meet geographically dispersed and uncertain demand.The investigators propose to develop a novel approach to address the vehicle routing problem with uncertain demand and travel times. The approach is to obtain a solution which is robust with respect to the uncertainty, as opposed to obtaining the optimal solution for certain fixed uncertainty scenario. The robust solution is defined as the solution which has a worst case scenario of minimum cost. The proposed research is separated into two main parts: (1) To formulate the problem that provides the robust solution, known as the robust vehicle routing problem (RVRP), and to develop exact and approximate solution methods specifically tailored for this robust problem and (2) To evaluate whether the RVRP provides a solution that is better in practice, through studies of how different uncertainty assumptions affect the trade-offs between robust and optimal solutions. The proposed approach (1) requires solving problems of the same inherent complexity as the original routing problem, (2) assumes only that the uncertainty is bounded, and (3) provides a solution that will be efficient for all possible uncertainty values.

越来越多的行业每天都在决定如何将车队从仓库路由到服务地理上分散的一组客户，例如快递服务、卡车运输公司和需求响应运输服务。这在学术文献中被称为车辆路径问题（VRP）。该路由通常发生在一个不确定的环境中，其中的行程时间是可变的（由于当前的交通状况），需求也是不确定的（客户可以在操作期间“打电话”）。 在这些不确定性下，事实证明，先验决定的最优路由解决方案实际上可能是非常低效的。 本研究的目的是获得一个路由解决方案，表现良好的所有可能的不确定性的情况下，因此，在实践中，这些行业是一个更好的解决方案。 这些强大的解决方案有可能降低日常面临路由问题的广泛行业的实际运营成本。 此外，开发的路由问题的技术可以在原则上适用于其他离散选择问题的重要工业，如决定在哪里开一个仓库，以满足地理上分散和不确定的需求的问题，调查人员建议开发一种新的方法来解决不确定的需求和旅行时间的车辆路径问题。 该方法是为了获得一个解决方案，这是强大的不确定性，而不是获得最佳解决方案，为某些固定的不确定性的情况。 鲁棒解被定义为具有最小成本的最坏情况的解。 拟议的研究分为两个主要部分：（1）将提供鲁棒解决方案的问题公式化，称为鲁棒车辆路径问题（RVRP），并开发专门针对该鲁棒问题的精确和近似解决方法，以及（2）评估RVRP是否提供了在实践中更好的解决方案，通过研究不同的不确定性假设如何影响稳健和最佳解决方案之间的权衡。所提出的方法（1）需要解决与原始路由问题相同的固有复杂性的问题，（2）仅假设不确定性是有界的，以及（3）提供对于所有可能的不确定性值都有效的解决方案。