A survey of genetic algorithms for solving multi depot vehicle routing problem

Highlights

• We reviewed the use of genetic algorithms on the MDVRP (multi depot vehicle routing problem).

• Survey was made on every operator and setting of genetic algorithm for this problem.

• We tested different genetic operators and compared the results.

• We compared the genetic algorithms to other metaheuristic algorithms on MDVRP based on the results on standard benchmarks.

Abstract

This article presents a survey of genetic algorithms that are designed for solving multi depot vehicle routing problem. In this context, most of the articles focus on different genetic approaches, methods and operators, commonly used in practical applications to solve this well-known and researched problem. Besides providing an up-to-date overview of the research in the field, the results of a thorough experiment are presented and discussed, which evaluated the efficiency of different existing genetic methods on standard benchmark problems in detail. In this manner, the insights into strengths and weaknesses of specific methods, operators and settings are presented, which should help researchers and practitioners to optimize their solutions in further studies done with the similar type of the problem in mind. Finally, genetic algorithm based solutions are compared with other existing approaches, both exact and heuristic, for solving this same problem.

Introduction

Vehicle routing problem (VRP from now on) is the classic problem initially described by Dantzig and Ramser in 1959 [1] and it derives from the traveling salesman problem or arc routing problem. Arc routing problem is basically a problem where we strive to find the optimal way to construct a route in such a way that the route is the shortest one possible. VRP extends this problem in a way that there is a set of customers or stops, and they have to be visited by a vehicle and this vehicle has to start and finish its trip at the home depot stop [2]. This is basically a reflection of real life distribution problems like delivering and picking up passengers, mail, packages and different kind of goods. Since its proposition by Dantzig, it has received much attention in the scientific community and a lot of exact and also heuristic methods have been proposed to solve it. Our research focuses on one of the most widely used variations of this problem – multi depot VRP (MDVRP). It extends the classical problem by introducing the capacity to the vehicles and demand to the customers and adding multiple depots. MDVRP is, as is VRP, a NP hard combinatorial optimization problem and therefore it is difficult to find its optimal solution [3]. While exact methods solve small problems quite efficiently [4], issues still exist for the larger problems or the special types of the VRP variants. On the other hand, meta-heuristic methods find solutions in less time and one such method is the genetic algorithm (GA) – an algorithm that mimics the natural process of evolution [5].

There are several meta-heuristic approaches to solving VRP and its variant transportation problems. State of the art solutions include: particle swarm optimization approach [6], [7], ant colony optimization [8], [9], genetic approach [10], simulated annealing [11], [12] and tabu search [13], [14]. These approaches are useful in various types of transportation problems, similar to VRP, such as facility location problem, where the goal is to find the optimal location of central depot considering the locations of stops. The topic of facility location problem has already been thoroughly researched in survey papers [15], [16], [17]. In [18] and [19] authors compared the meta-heuristic approaches on this facility location problem and location planning respectively. Results from these papers show that the main advantage of GA in comparison to other meta-heuristic algorithms is the performance and final result on time constraints and limited computer power, while still resulting in competitive solutions. Although some other meta-heuristics are able to find better solutions than GA, GA can generally find adequate (good enough) solutions in a shorter time frame [18], [19]. This is also the main reason that GAsare still used in solving the routing, locating and other NP hard problems.

There have been a lot of the researches done about solving VRP with GAs, where researchers focused on the practical usage of the GAs on VRP in real world problems. A systematic research on how different aspects, operators, variants and settings of GAs influence the search process and thus the obtained solutions still does not exist. Goals of this paper are thus to explore the background of solving MDVRPs with GAs, to look into, evaluate and compare different approaches used, and to discuss how to build this kind of GAs to solve MDVRP efficiently.

Although the MDVRP itself and the use of GAs to solve it have been known for many years, the number of GAs for solving MDVRP keeps growing (Fig. 1). Namely, literature reports good GA solutions to MDVRPs, not far from optimal, while keeping the computational resources, needed to find the solution, within very reasonable boundaries. In this context, we provide a detailed survey of GAs to solve MDVRP. Furthermore, we provide results of using different genetic operators and/or settings, most commonly used in literature, on a set of standard benchmark problems, together with detailed discussion.

The remainder of the paper is organized as follows. We start with the overview of the VRP and its variations. We describe the most frequent variations and formulate the MDVRP, as it is the main focus of our research. We continue with the basics of the GA – we describe the whole process from the data preparation to the main evolutionary loop of the algorithm and end up with the insights into genetic operators. Then we follow up with the main topic of this paper – solving MDVRP with the GAs. It starts with the basic background overview of this approach. Then the most common method of representing this problem in genetic form is listed. Next we look into the genetic operators used for this specific problem – we describe crossover, mutation, selection and other operators used. For the second part of the paper we developed a working prototype of GA for solving MDVRP and test it intensively. At the beginning we start with the comparison of some of the most used operators and try to decide which of these are most suitable for this type of problem. At the end we compare GA based solutions with some other existing solutions, both exact and heuristic, on a set of standard benchmark problems.