Stochastic Programming and Robust Optimization to Variants of Vehicle Routing Problem: Formulations and Exact Methods

Abstract

In this doctoral research, we intend to approach two variants of vehicle routing problem with time windows. In the first of them, the customers can request the pickup and delivery of goods simultaneously and, thus, they model relevant urban situations such as beverage distribution, public transport system, reverse logistic, among others. The second variant considers the use of multiple deliverymen in each route and, therefore, besides involving the classical routingdecisions, the crew size in each vehicle must also be decided. In practical environments, a very important aspect to consider is the uncertainty. Neglecting uncertainty may lead to solutions that are not implementable in practice or are inefficient. For example, if at some point, a significant difference is found between the estimated demands and that which actually happened, or traveling and service time is found to be different from that determined, an additional visit to the customer may be required or visits to other subsequent customers on the route may not be possible, incurring additional costs that may considerably increase the total operating cost. For this reason, approaches to deal with the inherent uncertainty of the problem must be addressed and the stochastic programming with resources and robust optimization are the most currently used in mathematical programming. Hence, these approaches will be used to formulate more realistically the problems to be addressed in this doctoral research. Using these approaches may significantly increase the number of decision variables and constraints, which may indicate that a greater computational effort to solve problem is required. However, these resulting formulations present particular structures that can be used by the methods of decomposition and cutting planes. Therefore, this research also aims to use these methods to solve the two variants of the problem. Some studies have used these methods recently to solve the variants of stochastic vehicle routing problem, obtaining promising results. For this reason, we believe that these methods have potential to provide good results here. The proposed methods will be implemented and evaluated using instances of literature test as well as it is intended to use real data collected from companies.