The 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.