Using Metaheuristics to solve Dynamic Vehicle Routing Problems

Abstract

The Vehicle Routing Problem (VRP) is considered to be a complex and high-level set of various routing problems. One of its important variants is the Dynamic Vehicle Routing Problem (DVRP), in which not all customers are known in advance, but are revealed as the system progresses. Consequently, DVRP applications are seen to operate on a dynamic basis in various real-life systems. Like the classical VRP, as DVRP is an NP-hard optimization problem, so optimization techniques that have the capability to produce high quality solutions under time limitations, i.e. metaheuristics, are the most suitable and applicable techniques to be used to find good solutions for them. This thesis aims to find good solutions for DVRP by using a Genetic Algorithm (GA) enhanced by five proposed modifications, including the initial population for the first time slice and/or other time slices, the selection process, the swap mutation and the detection and management processes of the Local Optimal Condition (LOC). Through experiments, it is clear that these improvements enhance the GA s ability to solve DVRP. Also, based on the quality of its generated solutions, with regard to its best and average results, the enhanced GA is competitive and out-performs previously published DVRP systems. To date, a time-based evaluation approach has been used to evaluate DVRP systems. However, as all DVRP systems are run for a specified amount of time for each time slice, another objective of this research is to propose a fair evaluation approach whereby four evaluation approaches, including generations, raw fitness, weighted fitness and distance calculations, are tested as alternatives. Of these, as the weighted fitness evaluation technique has the lowest standard deviation, it is the most stable for use, regardless of a running system s specifications and power requirements. Overall, based on its results from both the time-based and weighted fitness evaluation approaches, the modified GA is better than previously published algorithms.