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

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

Ziauddin Ursani (School of Engineering and Information Technology, Australian Defence Force Academy, University of New South Wales, Sydney, NSW, Australia), Daryl Essam (School of Engineering and Information Technology, Australian Defence Force Academy, University of New South Wales, Sydney, NSW, Australia), David Cornforth (School of DCIT, University of Newcastle, Callaghan, Newcastle, NSW, Australia) and Robert Stocker (School of Engineering and Information Technology, Australian Defence Force Academy, University of New South Wales, Sydney, NSW, Australia)
Copyright: © 2013 |Pages: 22
DOI: 10.4018/jaec.2013010102
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

This paper is a continuation of two previous papers where the authors used Genetic Algorithm with automated problem decomposition strategy for small scale capacitated vehicle routing problems (CVRP) and vehicle routing problem with time windows (VRPTW). In this paper they have extended their scheme to large scale capacitated vehicle routing problems by introducing selective search version of the automated problem decomposition strategy, a faster genotype to phenotype translation scheme, and various search reduction techniques. The authors have shown that genetic algorithm used with automated problem decomposition strategy outperforms the GAs applied on the problem as a whole not only in terms of solution quality but also in terms of computational time on the large scale problems.
Article Preview

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.’

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing