Sim-heuristic algorithms for Robust Vehicle Routing Problem with Stochastic Demand

  • Abdulwahab Almutairi

Student thesis: Doctoral Thesis


The Vehicle Routing Problem with Stochastic Demand (VRPSD) is a fundamental problem underlying many operational challenges in the field of logistic and supply chain management. The VRPSD is a well-known NP-hard problem whereby a fleet of vehicles is located at a single depot. Each vehicle has a limited capacity and has to serve a number of customers whose actual demands are known only when the vehicle arrives at the customers’ locations. The VRPSD arises in practice whenever a company faces the problem of delivering to a set of customers, whose demands are uncertain. The solution to the VRPSD includes the optimisation of complete routing schedules whilst minimising the transportation costs (fixed costs and variable costs) to satisfy all the constraints in the problem. This study proposes three approaches: the robust routing model with sim-heuristic, randomised Iterated Greedy (IG) algorithm with Monte Carlo Simulation (MCS) and finally IG algorithm with local search to solve the VRPSD. The main aim of using the robust routing model with sim-heuristics is to build robust solutions by combining simulation and optimisation using heuristic methods. This is to handle uncertainty as well as to optimise against any worst instance that might arise due to data uncertainty. Several heuristics have been combined with simulation to deal with stochastic demand. In our version of the approach, the first one is a randomised Clarke and Wright Saving (CWS) algorithm step after which an MCS is incorporated in order to improve the final solutions of VRPSD. The second approach proposed the combination of randomised IG algorithm with MCS to be applied on the VRPSD. The final approach is to use an IG algorithm with local search, based on the aforementioned first approach, in order to improve the solutions generated. Local search has been proven to be an effective technique for obtaining good solutions.
The developed robust routing model and sim-heuristic algorithms are tested on well-known benchmark instances and a real-life case study is considered in order to evaluate the effectiveness of the proposed methodologies. The computational results showed that the proposed methodologies are capable of finding useful solutions for the VRPSD and that they are good/robust for the stochastic nature of the problem instances. After computing the average costs from each instance, we also computed the best solution and found that they both could be highly promising and useful for decision makers. The results obtained are quite competitive when compared to the other algorithms found in the literature.
Date of AwardSept 2016
Original languageEnglish
Awarding Institution
  • University of Portsmouth
SupervisorDjamila Ouelhadj (Supervisor), Dylan Jones (Supervisor) & Banafsheh Khosravi (Supervisor)

Cite this