Stochastic Vehicle Routing Problem with Stochastic Demand: Dual methods

Specialeforsvar ved Eda Güven

Titel: Stochastic Vehicle Routing Problem with Stochastic demand: Dual methods

Abstract: In this thesis, the aim is to provide a description of the Vehicle Routing Problem (VRP) and the Stochastic Vehicle Routing Problem (SVRP) as well as the Stochastic Vehicle Routing Problem with Stochastic Demand (SVRPSD). The Vehicle Routing Problem (VRP) aims to construct the optimal route for a given fleet of vehicles visiting a set of customers, where the vehicles starts and ends in a depot, and all customers are visited by only one vehicle. In the Capacitated Vehicle Routing Problem (CVRP), the vehicles have a capacity and total demand on a route cannot exceed the vehicles capacity. In SVRPSD the customers' demand is not known in advance so the demand is the stochastic share of the problem. The purpose in SVRPSD is to minimize the total cost of the planned routes and the cost of expected failures. If a vehicle cannot satisfy customer demand there is a failure and this causes recourse action. In this situation, the vehicle must return to depot to fill up the vehicle and drive back to the customer. Hereafter the vehicle can continue its planned route. The overall objective of this thesis is to review the exact solution methods to SVRPSD. These can usually be divided into primal and dual methods. We will illustrate the dual methods with a Cutting Plane approach. We will outline the methods application to SVRPSD and provide an example of the method to a specific instance of SVRPSD

Vejleder: Trine Krogh Boomsma
Censor:   Niklas Kohl