Two-stage robust optimization with recourse for the vehicle routing problem with time windows and multiple deliverymen

Abstract

In this research project, we intend to use the two-stage robust linear programming methodology withrecourse to contemplate the uncertainties in the vehicle routing problem with time windows and multiple deliverymen (VRPTWMD). This problem arises in situations where customer sites are located in heavily congested centers, preventing the parking of vehicles near the delivery site. Therefore, in this situation, performing the service by more than one deliveryman is indispensable for the customer's allowed service times, since, it is expected that this service time will be reduced. Considering uncertain demand a priori, when a vehicle arrives at a customer site is possible that the customer's demand can not be met. At this point, a failure has occurred and, therefore, a recourse action must be taken. There has been different recourse actions proposed in the literature. For instance, returning to the depot from the customer's site where the failure occurred and continue with the pre-stablished route, serving the customer with anextra vehicle, among others. Regardless of the recourse used, additional costs related to transportation are incurred by the extra trips to the depot. Depending on the recourse, the second-stage decision variables used to represent it can be integer, resulting in a two-stage robust linear program with integer recourse. This problem presents several theoretical and computational challenges. For this reason, the objective ofthis research project is to propose a solution method that efficiently explore the particular structure of the two-stage robust linear program with recourse for the VRPTWMD with uncertain parameters.