Models and Metaheuristics For Vehicle Routing Problems Under Uncertainty

Publication Type:
Issue Date:
Full metadata record
Within the logistics and transportation industry, the vehicle routing problem (VRP) bears significant importance in many real-life logistics activities. As one of the most important and widely studied combinatorial optimization problems in the past sixty years, the VRP, also known as the capacitated VRP (CVRP), focuses on minimizing transportation costs: it concerns how to serve a set of geographically dispersed customers with a fleet of homogeneous vehicles at minimum cost. Given the potentially substantial savings from optimizing routing strategies in practical logistics activities, various complex extensions of the CVRP inspired from real-life applications have increasingly received attention. In the CVRP and most of its extensions, a common assumption is that the values of all problem parameters are readily available and can be precisely known in advance. However, this assumption does not invariably hold in many practical routing problems due to uncertainty, which could be secondary to factors such as imprecise information on customer demands, unfixed service times for customers, and varying travel times for vehicles. Thus, routing strategies generated without considering uncertainty may ultimately be found infeasible in real-life applications. This thesis studies three important extensions of the CVRP under uncertainty. Firstly, we study the vehicle routing problem with time windows considering uncertainty in customer demands, service times, and travel times. Secondly, we study the vehicle routing problem with simultaneous pickup and delivery and time windows under pickup demand and travel time uncertainty. Finally, we study the two-echelon multiple-trip vehicle routing problem with time windows and satellite synchronization under customer demand uncertainty. To model these problems, we adopt the robust optimization paradigm and present three robust mathematical formulations with novel uncertainty sets. Given their complexity, we propose efficient metaheuristic solution approaches. We conduct extensive numerical experiments which employ benchmark instances from the literature. The computational results show that the proposed solution approaches can generate high-quality deterministic and robust solutions for large-sized instances within a reasonable running time. In addition, Monte Carlo simulation tests are designed to evaluate the robustness of the obtained solutions. Useful managerial insights for decision-makers in the logistics and transportation industry are derived from a comprehensive analysis of the computational results.
Please use this identifier to cite or link to this item: