Action-based Representation for Stochastic Optimization of Complex Real-World RVRP

Rich Vehicle Routing Problem, RVRP, Vehicle Routing Problem, VRP, Logistics, Stochastic Optimization

Logistic planning is, in some cases, still done mostly manually with supporting software tools, mainly due to the high complexity of real-world constraints. While research of the classical Vehicle Routing Problem variants is often not directly applicable to real-world logistics problems, this work deals with the problem of logistic planning faced by a particular European logistics company. The studied problem can be modeled as a static, multi-trip, single objective Rich Vehicle Routing Problem with multiple depots, pickup and delivery operations, load splitting, limited heterogeneous vehicles, multiple capacities, single time windows, and compartmentalized cargo groups, alongside various additional incompatibility constraints. The presented research investigates whether the currently used handmade logistic plans can be automatically improved while considering the given real-world constraints. We propose a suitable problem representation based on actions, together with two mutation operators, and compare three stochastic optimization methods (Metropolis-Hastings algorithm, Evolutionary Strategy, Evolutionary Programming). The proposed optimizers achieved an average improvements of 7.7 % on real-world data sets with historic plans provided by the logistics company.