The Robust Vehicle Routing Problem

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

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.