Enhancements to the Localized Genetic Algorithm for Large Scale Capacitated Vehicle Routing Problems

Introduction

The Vehicle Routing Problem (VRP) is an optimization problem that seeks to provide a solution to vehicle scheduling while minimizing (for example) cost or total travel times. As the problem is computationally intensive for problems of any realistic size, a sub-task is to find strategies to enhance the efficiency of the algorithm used to solve the VRP. One approach is to decompose the problem into smaller units, solve each one separately, and then recombine them. In this context, the VRP can be said to represent the intersection of two combinatorial problems i.e., finding an optimal problem decomposition (Set Partitioning) and route optimization (Ordering). Please note that the two terms ‘problem decomposition’ and ‘set partitioning’ may have dissimilar meaning in other combinatorial problems. Some approaches optimize VRP as a whole without explicitly separating these two built in sub-tasks, while others perform decomposition then order the elements of the sub-problems independent of each other. Evidence has shown that the latter strategy is more successful. Work using genetic algorithms has mostly treated this problem as a whole. Although some applications of GA have treated these two sub-tasks separately, those applications used GA only for set partitioning and not for ordering. To our knowledge only one application of GA has appeared in the literature where the GA is used for optimization of customer ordering of sub-problems. However, it is a multi-depot problem (Surekha & Sumathi, 2011), where each sub-problem surrounds a single depot constituting a complete Capacitated Vehicle Routing Problem (CVRP). Apart from our earlier work (Ursani et al., 2009, 2011) no report has appeared in the literature where the GA is used for optimization of customer order of sub-problems of either of the two most fundamental VRP problems, that is the CVRP and the Vehicle Routing Problem with Time Windows (VRPTW).

In the following subsections literature regarding the two sub-tasks of VRP i.e., (problem decomposition and ordering) is discussed separately. The ordering section deals with the problem representation of customer order and subsequent genotype to phenotype translation that has remained a core issue of GA in the area of VRP. In the context of VRP the term ‘order optimization’ is preferred to ‘route optimization.’