Ant Colony Optimization and Genetic Algorithm Approaches to Solving the Split Delivery Vehicle Routing Problem

Headnote

Abstract

The Split Delivery Vehicle Routing Problem (SDVRP) allows customers to be visited by more than one vehicle. Two solution approaches are presented and computational results are provided for benchmark problems from the literature. The first solution method is an Ant Colony Optimization method, and the second solution method is a hybrid Genetic Algorithm method. The computational results indicate that the two approaches are competitive in both solution quality and solution time. In some instances, the Ant Colony Optimization method achieves the best known results to date for the benchmark problems.

Keywords

Vehicle Routing, Ant Colony Optimization, Genetic Algorithms

1. Introduction

The Vehicle Routing Problem (VRP) is a well-known optimization problem that can be applied to the supply chain, logistics, distribution, and transportation industries. With an objective to minimize the delivery cost of goods to a set of customers from either a single depot or multiple depots, numerous variants of the VRP have been developed and studied over the years. One such variant is the Split Delivery Vehicle Routing Problem (SDVRP) which is a relaxation of the Capacitated Vehicle Routing Problem (CVRP). For the CVRP each customer is served by only one vehicle; whereas for the SDVRP, the customer demand can be split between vehicles. The SDVRP was first developed by Dror and Trudeau [1, 2]. They showed that if the demand is relatively low compared to the vehicle capacity and the triangular inequality holds, then an optimal solution exists in the SDVRP in which two routes cannot have more than one common customer. In addition, it was proven that the SDVRP is NP-hard and has potential in savings in terms of the distance traveled as well as the number of vehicles used.

This paper is organized as follows. The next section will provide a brief literature review. The third section will provide an overview of the Ant Colony Optimization (ACO) methodology and the hybrid Genetic Algorithm (GA) methodology. The fourth section will provide computational results for the two methods for benchmark problems from the published literature. The last section will provide conclusions and future research directions.

2. Literature Review

2.1 SDVRP Review

In recent work on the SDVRP, several researchers developed approaches for generating solutions to the SDVRP. A Tabu search algorithm solved...