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

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.