Hybrid 2-stage Imperialist Competitive Algorithm with Ant Colony Optimization for Solving Multi-Depot Vehicle Routing Problem

The gist The proposed ACO-ICA hybrid 2-stage algorithm solves the Multi-Depot Vehicle Routing Problem (MDVRP) by using Imperialist Competitive Algorithm for customer assignment to depots and Ant Colony Optimization for routing and sequencing customers across vehicles from depots.

Problem Formulation

The main aim of the MDVRP is to route a fleet of vehicles from multiple depots to multiple customers requiring goods or services, starting from a depot and terminating at the same depot while complying with constraints such as maximum vehicle capacity and maximum vehicle duration The MDVRP can be formalized in a mathematical model based on [8] and [9] Given direct graph G = (S, E) where S = C ∪ U is a set of customers C = and depots D = and E is a set of edges between all the nodes in the graph. In a fully connected graph, every edge Eij between nodes Si and Sj (i ≠ j) has associated positive cost cij - distance or time, for example. Each customer has a positive demand di (i ∈ C). Furthermore, there is also a fleet of K identical vehicles available at each depot Dk ε D (that are not allowed to exceed capacity Qmax and duration Rmax). The goal is to minimize the total cost across all vehicles (1) where xij equals 1 if i comes after j in the customer sequence on any route of all vehicles and 0 otherwise. The problem is subject to the following constraints • each vehicle route starts and ends at the same depot; • the total demand on each route does not exceed vehicle capacity Qmax; • the maximum route duration Rmax is not exceeded; • each customer is served by exactly one vehicle.

Ant Colony Optimization Component

The Ant Colony Optimization (ACO) algorithm was first introduced by Marco Dorigo in 1992 and since been used for many routing problems The algorithm is inspired by the movement of ants searching for food; each ant leaves a scent called pheromone for other ants to follow. An algorithm can be divided into two stages – the construction of the solution and pheromone feedback to other ants. In the MDVRP, the ant starts the tour from a depot and visits nodes (customers) and returns to the same depot. As there are multiple depots, the algorithm uses multiple ant colonies (one per each depot) to solve the problem. Once all customers have been visited, routes from all colonies are combined and evaluated as the final solution. For paths that improved cost, a pheromone is deposited on the edges of the graph to guide ants in the next iteration. Furthermore, an evaporation process takes place after each iteration to avoid getting stuck in local optima. During the creation of the solution, an ant can visit any of the customers that have not yet been visited.

Imperialist Competitive Algorithm Component

The Imperialist Competitive Algorithm (ICA) was first introduced in 2007 for solving continuous optimization problems The ICA is inspired by geopolitical relationships between countries where developed countries attempt to take over less-developed countries – colonize them to extend their power. The initial population of countries is divided into imperialists and colonies based on the country’s strength (inverse of cost value). After the grouping, each colony inside empire moves closer to their imperialist (assimilation operator). Imperialists compete for the colonies and the imperialist competition gradually results in an increase in power of strong empires while decreasing the power of weak ones. Weak empires eventually lose all colonies and collapse, with the strongest remaining imperialist providing the final best solution. Although no ICA implementation for solving the MDVRP with ICA exists in the literature, the algorithm was applied for VHR with time windows in [26] where the authors encoded the routes in the country based on the vehicle. Furthermore, authors in [27] used slightly different encoding, where not only the visited customer sequence but also the number of visited customers is embedded in the country representation. In contrast to other approaches, the ICA implementation in this paper encodes the depots as part of the country, not the customers.

Hybrid 2-stage ACO-ICA Algorithm

The Hybrid 2-stage Imperialist Competitive Algorithm with Ant Colony Optimization (ACO-ICA) combines an ICA based algorithm previously proposed by authors in [21] for customer assignment to depots. At the same time, ACO (also already used by authors in [22]) is dedicated for customer sequencing and routing in the MDVRP. The proposed ACO-ICA 2-stage hybrid algorithm uses the ICAwICA algorithm previously developed by authors in [21] for the customer assignment process. The search starts by empire initialization, where random solutions are created, and countries are split into imperialist and colonies. Each new country created by ICA follows the 2-stage process for creating a feasible solution: Stage 1: Customer assignment to depots First, customer-depot relationships are encoded as the country. Each country is represented as a vector of the size of the number of customers where each customer is assigned a depot index. An example of new country creation via assimilation is shown in Figure 2, where the initial colony has encoded the following grouping: Customer 2 and 8 will be routed from Depot 1; Customers 1, 3 and 6 will be routed from Depot 2; Customers 5,7,9 and 10 will be routed from Depot 3 and finally, Customer 4 will be routed from Depot 4. Each time new country is created as part of ICA assimilation process, capacity constraints are considered such that the total demand for all customers assigned to the depot does not exceed the maximum capacity available across all vehicles to the given depot. Stage 2: Customer routing Once customers have been assigned to the depots, an ant colony for each depot is created. Furthermore, persistent global pheromone matrix for the country is used to guide the colony search, where the pheromone matrix is represented as all connections E between two edges in the graph G. The probability of visiting a customer that is not assigned to the depot is set to 0, therefore, no customer can be visited from more than one depot. The ants in each depot’s ant colony build routes complying with the MDVRP constraints and update the local pheromone matrix. This process is repeated until the termination condition is reached. Partial solutions for each depot are then combined and the final solution evaluated. The global pheromone matrix for the country is updated based on the best solution and global pheromone evaporation operator.

Experimental Results

The proposed ACO-ICA hybrid algorithm was evaluated on well-known Cordeau’s [32] MDVRP benchmark instances The dataset with the best-known solutions (BKS) was obtained from [33]. All three algorithms – ACO (based on [22]), ICA (based on [21]) and ACO-ICA were implemented in C++ using Visual Studio 2019 (v142) compiler.

1. Improved MDVRP solution quality via hybrid metaheuristics: The proposed ACO-ICA hybrid algorithm outperforms both non-hybrid algorithms in terms of average error and demonstrates very competitive results when compared to other rival algorithms. This allows the system to find solutions with significantly lower error percentages, such as the reported 0.2% average error on benchmark instances.

2. Enhanced customer assignment accuracy: The ICA component is responsible for customer clustering to their depots, which is integrated into Stage 1 of the hybrid algorithm where capacity constraints are considered such that the total demand for all customers assigned to the depot does not exceed the maximum capacity available across all vehicles to the given depot. This enables more realistic and feasible customer-to-depot allocations.

3. Optimized routing and sequencing: The ACO component is dedicated for routing and sequencing the customers, ensuring routes comply with MDVRP constraints. This allows the system to generate efficient vehicle routes by utilizing pheromone feedback, as described in Section 3.1 where a pheromone is deposited on the edges of the graph to guide ants in the next iteration.

4. Improved solution robustness through staged search: The separation into two distinct stages—Stage 1: Customer assignment to depots and Stage 2: Customer routing—provides a structured approach. This structure allows for persistent global pheromone matrix for the country to guide the colony search in Stage 2, leading to better final solutions than previous hybrid attempts where ACO was used as a local search.

5. Increased hyperparameter flexibility: The system's complexity is managed by combining two algorithms, necessitating increased parameter tuning. Future work suggests that the number of hyperparameters for the algorithm has also been increased, which could be addressed by investigating simpler alternatives like evolution strategy for customer grouping.