An Ant Colony Optimization and Hybrid Metaheuristics Algorithm to Solve the Split Delivery Vehicle Routing Problem

An Ant Colony Optimization and Hybrid Metaheuristics Algorithm to Solve the Split Delivery Vehicle Routing Problem

Gautham Puttur Rajappa (The University of Tennessee, Knoxville, TN, USA), Joseph H. Wilck (United States Air Force Academy, Colorado Springs, CO, USA) and John E. Bell (The University of Tennessee, Knoxville, TN, USA)
Copyright: © 2016 |Pages: 19
DOI: 10.4018/IJAIE.2016010104
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Split Delivery Vehicle Routing Problem (SDVRP) is a relaxation of the Capacitated Vehicle Routing Problem (CVRP) that allows the same customer to be served by more than one vehicle. Existing literature has applied Ant Colony Optimization (ACO) and Genetic Algorithm (GA) to other variants of VRP but no known research effort has applied ACO or a combination of ACO and GA to solve the Split Delivery Vehicle Routing Problem (SDVRP). Hence, two algorithms using ACO and hybrid metaheuristics algorithm comprising a combination of ACO, Genetic Algorithm (GA) and heuristics is proposed and tested on existing benchmark SDVRP problems. The results indicate that the two proposed algorithms are competitive in both solution quality and solution time and for some problem instances, the best ever solutions have been found.
Article Preview

Introduction

The Vehicle Routing Problem (VRP) is a prominent problem in the area of logistics, operations research, and transportation management. With an objective to minimize the delivery cost of goods to a set of customers from depot(s), numerous variants of the VRP have been developed and studied over the years. One such variant is the Capacitated Vehicle Routing Problem (CVRP) where the objective is to minimize the cost of delivering a single product to a set of customers from a single depot using a homogenous fleet of vehicles (Liu et al., 2009). The Split Delivery Vehicle Routing Problem (SDVRP) is a relaxation of the Capacitated Vehicle Routing Problem (CVRP). In the case of a CVRP, each customer is served by only one vehicle, whereas in SDVRP, the customer demand can be split between vehicles.

Several heuristic methods such as a construction heuristic (Wilck and Cavalier, 2012a), a genetic algorithm (Wilck and Cavalier, 2012b), and Tabu search algorithm (Archetti et al., 2006) have been applied to solve the SDVRP. An IEEE conference proceeding paper by Sui et al. (2008) presents an ant colony optimization (ACO) approach for the SDVRP but does not present empirical results compared to published methods. Hence, an ACO approach for the SDVRP is developed and further, by using the initial set of population (vehicle routes) generated by ACO, a hybrid metaheuristics algorithm comprising a combination of genetic algorithm and heuristics is applied to discover a more optimal vehicle route. The capability of the proposed algorithms is tested on different benchmark test problems found in the literature.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 4: 2 Issues (2017)
Volume 3: 2 Issues (2016)
Volume 2: 2 Issues (2014)
Volume 1: 2 Issues (2012)
View Complete Journal Contents Listing