Analysis of box and ellipsoidal robust optimization, and attention model based reinforcement learning for a robust vehicle routing problem

In this work, we consider a class of vehicle routing problem that uses simultaneous pickup and delivery and is constrained by a hard service time window with an objective to minimize costs. In a realistic VRP environment, uncertainty or variability with constituent features and its values are the norm. We formulate and solve this class of vehicle routing problem as: (1) a mixed-integer linear programming (MILP) approach with box and ellipsoidal robust optimization mathematical model to handle uncertainty, (2) a MILP based exact box robust optimization mathematical model to handle uncertainty, and (3) a dynamic attention model based reinforcement learning approach to handle uncertainty. We have conducted computational experiments to analyse the impact of effectiveness on solution quality, problem scale, and solution performance in accounting for feature data uncertainty. Our study indicates that accounting for feature data variability using robust optimization approaches impacts solution cost. Simulation results using MILP based Robust optimization (MILP_RO) approaches and Attention Model (AM) based deep reinforcement (DRL) learning approaches show that we can cope with uncertainties to feature data without much of an impact to cost and performance for input customer graphs of smaller to medium node counts. Also, AM based DRL approaches give better quality results when compared with (MILP_RO) approaches for input customer graphs of higher node counts.