VRoptBees: A Bee-Inspired Framework for Solving Vehicle Routing Problems

Top

1. Introduction

Optimization consists of determining the values of a set of variables that minimize or maximize a given mathematical expression, satisfying all problem constraints (Cunha et al., 2012; Michalewicz & Fogel, 2013). An intuitive way to solve a given optimization problem is to list all possible solutions, evaluate them, and use the best solution found. However, depending on the characteristics of the problem this approach, known as exhaustive search, is not efficient. The main drawback of using full enumeration is that it becomes computationally impractical depending on the number of possible solutions to the problem. This means that this exact solution approach would be valid only for simpler problems, what hardly occurs in practical applications.

The Vehicle Routing Problem (VRP) corresponds to a class of combinatorial optimization problems that seek for an optimal set of routes for a fleet of vehicles to traverse to attend a given set of customers (Lawler, 1985; Laporte, 1992; Reinelt, 1991; da Cunha, 2000; Toth & Vigo, 2001; Gutin & Punen, 2002; Laporte, 2009). As in most real cases the vehicles have a limited capacity, VRP becomes CVRP, which stands for Capacitated Vehicle Routing Problem. In mathematical terms, the CVRP can be described as follows. Given a number K of identical vehicles, each with a capacity Q, a depot i_d, a set S = {i₁, i₂, i₃, ..., i_n} with n customers, each with a demand q_i (i = 1, 2, 3, …, n), and the cost C_ij (i,j = 1, 2, 3, ..., n + 1) of going from customer i to customer j and from each customer to the depot, the CVRP consists of determining the permutation π of the elements in S so as to minimize:

(1) subject to:(2) where π_k,i represents the city visited in order i in route k, and n_k is the number of customers visited by vehicle k. For a review of practical applications and solution algorithms the work of Laporte et al. (2000) and Laporte (2009) are recommended.

If the vehicle capacity and the demand of each customer (city) constraints are removed, then we have the Multiple Travelling Salesman Problem (MTSP), which is a particular case of the CVRP. Given a number M of salesman, a depot i_d, a set S = {i₁, i₂, i₃, ..., i_n} with n intermediate cities, the cost C_ij (i,j = 1, 2, 3, ..., n + 1) of going from one city to another and also from each city to the depot, the MTSP consists of determining the set of permutations π_m (m = 1, 2, 3, …, M) from the elements in S so as to minimize:

(3) where π_m,i represents the city visited in order i in route m, and n_m is the number of intermediary cities visited in route m. The MTSP already presents enough characteristics to represent practical problems, such as school vehicle routing (Angel et al., 1972). Bektas (2006) presented other examples of practical applications and algorithms for MTSP.