1 Introduction

Logistics distribution impacts all enterprises as it is vital to service quality, transport costs, and revenue. The multi-depot vehicle routing problem (MDVRP) is an extension of VRP. Classic VRP has only one depot, while MDVRP includes multiple depots. The MDVRP has been applied to practical problems. For example, Wang et al. (2023) studied a real-world logistics distribution network with 4 depots and 160 customers. Soeanu et al. (2020) studied a small-scale risk-constrained multi-depot vehicle routing problem with 16 nodes and 3 depots. Kronmueller et al. (2023) investigated a grocery delivery in Amsterdam with 20 depots and 10,000 orders.

The MDVRP is a typical NP-hard problem, the complexity and significance of which has attracted significant research attention.

Current solutions to multi-depot vehicle routing problems (MDVRP) can be roughly divided into 4 categories.

(1) The part method clusters customers with the depot as the center and then optimizes the routes for each depot. That is, turn the multi-depot VRP into single-depot VRP, as shown in Fig. 1a. Chen et al. (2023) and Xue et al. (2023) first assigned each customer to its nearest depot, after which hybrid algorithms were introduced to optimize the vehicle routes. Kim et al. (2023) combined ant colony optimization with a k-means clustering algorithm to solve garbage collection on a large scale.

Fig. 1
figure 1

The part and overall method for MDVRP

Full size image

(2) The overall method is establishing a virtual center so all vehicles start from the virtual center. That is, turn MDVRP into MDVRP with a virtual center (V-MDVRP), as shown in Fig. 1b. Yu et al. (2011) established a virtual center, turned an MDVRP into a V-MDVRP, and proposed an improved ACO to solve the V-MDVRP. Yan et al. (2017) analyzed the advantages and disadvantages of the part method, the overall method, and heuristic algorithms in solving MDVRP. Then, they combined the overall method and a heuristic algorithm to solve the MDVRP. In the overall method, there is no standard for setting the location of the virtual center; although it becomes a single depot problem, it still needs to assign the route to the nearest depot according to the distance.

(3) The coding method expresses the corresponding position of the depot and the customer using different coding methods and then designs the algorithm to solve the MDVRP, as shown in Fig. 2. Azuero-Ortiz et al. (2023) and Ge et al. (2023) adopted coding methods and hybrid algorithms to solve MDVRP. Lavigne et al. (2023) provided a Memetic Algorithm with a Sequential Split procedure (MASS) for solving a real-life waste collection problem in Brussels with multiple depots.

Fig. 2
figure 2

The coding method for MDVRP

Full size image

The part method optimizes the routes in each part but does not optimize the whole, and while the overall method considers all customers every time and seeks to optimize the whole, it does not optimize the part. Further, it isn’t easy to design suitable and efficient coding methods for practical MDVRP.

Regardless of the overall method, the part method, or the coding method, the distance-based clustering method will be involved in selecting the depot. To avoid the distance-based clustering method, the virtual center is set at the circumcenter of the polygon formed by the depot. The algorithm can adaptively complete the selection of the virtual center to the depot without considering the influence of distance.

(4) In other methods, Wang et al. (2021) proposed a GA based on column generation to solve multi-depot electric VRP, which first generates a set of columns (each referring to a route), and then uses the GA to select a subset of columns to construct the final solution. Wang et al. (2022) propose a branch-and-price (BAP) algorithm for solving multi-depot GVRP with time windows to reduce the total carbon emissions, but it is very time-consuming in solving large-scale problems.

Few kinds of the literature integrate algorithm principles and mathematical ideas to solve MDVRP. For example, Yücenur et al. (2011) proposed a geometric shape (circle)-based genetic clustering algorithm for solving MDVRP. Draw a circle with the depot as the center, and assign the customers in the circle to the current depot. ACO has many advantages, such as excellent global search abilities, distributed computing, and easy combination with other algorithms, all of which can contribute to solving MDVRPs (Londoñoa et al. (2023); Zheng et al. (2023)).

This paper makes three major contributions:

  1. 1.

    Combines the advantages of the part and overall method, integrating ACO principle and mathematical ideas, then proposes the BPC-HACO to solve the MDVRP.

  2. 2.

    MDVRP benchmarks and data sets from other papers are employed to verify the effectiveness of the BPC-HACO in solving various types of MDVRP.

  3. 3.

    FLA has been applied to analyze the structural features of MDVRP to choose the appropriate algorithm.

The remainder of this paper is structured as follows. Section 2 describes the DMDVRP model and defines the problem, Sect. 3 details the hybrid BPC-HACO, Sect. 4 proves the effectiveness of the BPC-HACO algorithm, and Sect. 5 concludes the paper and outlines future research directions.

2 MDVRP model

MDVRP includes multiple depots and multiple vehicles in each depot. It is assumed that each vehicle starts its travel from a depot, and upon completion of service to customers, it has to return to the depot. The notations and the mathematical model are as follows:

Sets:\(i = 1,2,...,I\): Set of all depots\(j = 1,2,...,J\): Set of all customers\(k = 1,2,...,K\): Set of all vehicles

Parameters:

\(Cij\): Distance between points \(i\) and \(j\), \(i,j \in I \cup J\).

\(Vi\): Maximum throughput at the depot \(i\),\(dj\): Demand of customer \(j\),

\(Qk\): Capacity of vehicle \(k\),

Decision variables:

$$ x_{ijk} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {{\text{when}}\;{\text{vehicle}}\;k\;{\text{ serves}}\;{\text{ point}}\; \, j\;{\text{after}}\; \, i \, } \hfill \\ {0,} \hfill & {{\text{otherwise}}} \hfill \\ \end{array} } \right. $$

Mathematical model:

$$ \min \sum\limits_{i \in I \cup J} {\sum\limits_{j \in I \cup J} {\sum\limits_{k \in K} {C_{ij} x_{ijk} } } } $$
(1)
$$ \sum\limits_{k \in K} {\sum\limits_{i \in I \cup J} {x_{ijk} } } = 1,j \in J $$
(2)
$$ \sum\limits_{j \in J} {d_{j} \sum\limits_{i \in I \cup J} {x_{ijk} } } \le Q_{k} ,k \in K $$
(3)
$$ \sum\limits_{i \in I \cup J} {x_{ijk} - \sum\limits_{i \in I \cup J} {x_{jik} } } = 0,k \in K,j \in I \cup J $$
(4)
$$ \sum\limits_{i \in I} {\sum\limits_{j \in J} {x_{ijk} } } \le 1,k \in K $$
(5)
$$ \sum\limits_{j \in J} {d_{j} *x_{ijk} } \le V_{i} ,i \in I $$
(6)
$$ \sum\limits_{i \in J} {\sum\limits_{j \in J} {x_{ijk} } } \le \left| J \right| - 1,\;k \in K $$
(7)

Equation (1) minimizes the total cost. Each customer has to be assigned a single route according to Eq. (2). The capacity constraint for a set of vehicles is given by Eq. (3). Equation (4) shows the new sub-tour elimination constraint. The flow conservation constraints are expressed in Eq. (5). Each route can be served almost once according to Eq. (6). The capacity constraints for the depots are given in Eq. (7).

3 Hybrid ant colony optimization based on polygonal circumcenter (BPC-HACO)

ACO has some excellent properties, such as strong search ability, easy parallel operations, and robustness. However, it also has some disadvantages, such as slow convergence and falling easily into a local optimum (Wu et al. (2023); Ren et al. (2023)). The simulated annealing (SA) algorithm, which is an intelligent algorithm developed in the 1980s, has certain advantages for local searches as it uses the Metropolis criterion to ensure that solutions with better fitness are accepted or that solutions with poor fitness are accepted with a certain probability (Vincent et al. (2023)). Both the ACO and SA have been widely used in optimization problems. For example, Li et al. (2019) adapted the ACO to solve a multi-depot, multi-objective vehicle routing problem and proved that the algorithm performed well. However, the efficiency decreased when the algorithm was used to solve large-scale problems. Nia et al. (2023) and Wang et al. (2023) combined the advantages of the SA and ACO to enhance local search abilities. They proved that they could better solve larger-scale combinatorial optimization problems.

3.1 Ant colony optimization

3.1.1 Determine a virtual center

Suppose there are customers, \(M\) depots, and a virtual center at the circumcenter of a polygon formed by the depots, as shown in the MDVRP with three depots in Fig. 3. There is no vehicle in the virtual center, and the vehicle starts from the actual depot. For example, if the virtual center selects depot 1, then depot 1 schedules a vehicle to serve the corresponding customers.

Fig. 3
figure 3

An example of MDVRP with three depots

Full size image

3.1.2 Initialize pheromone matrix and heuristic information

The initial pheromone matrix is set as a constant matrix \((N + M + 1) \times (N + M + 1)\). The heuristic information matrix is also set as \((N + M + 1) \times (N + M + 1)\), which is calculated using the distance between two customers.

3.1.3 Select the depot

The virtual center is set at the circumcenter of a polygon formed by the depots to ensure that the distances between the virtual centers and the depots are equal (as Eq. (8)), which ensures that the heuristic information between the virtual center and different depots is equal (as Eqs. (9–10)). The probability (\(P_{0j} (j = 1,2,3)\))of the virtual center selecting the depot is only influenced by the pheromone (as Eqs. (11–12)), as shown in Fig. 4. With the increase in iterations, the adaptive selection of the depot is completed.

$$ d_{01} = d_{02} = d_{03} $$
(8)
$$ \eta_{0i} = \frac{1}{{d_{0i} }},i = 1,2,3 $$
(9)
$$ \eta_{01} = \eta_{02} = \eta_{03} = A $$
(10)
$$ P_{0i} (t) = \frac{{\left[ {\pi_{0i} (t)} \right]^{\alpha } [\eta 0i]^{\beta } }}{{\sum\limits_{i \in depot} {[\pi_{0i} (t)]^{\alpha } [\eta_{0i} ]^{\beta } } }},i \in \{ 1,2,3\} $$
(11)
$$ P_{0i} (t) = \frac{{\left[ {\pi_{0i} (t)} \right]^{\alpha } [A]^{\beta } }}{{\sum\limits_{{i \in \;{\text{depot}}}} {[\pi_{0i} (t)]^{\alpha } [A]^{\beta } } }} = \frac{{\left[ {\pi_{0i} (t)} \right]^{\alpha } }}{{\sum\limits_{{i \in \;{\text{depot}}}} {[\pi_{0i} (t)]^{\alpha } } }},i \in \{ 1,2,3\} $$
(12)
Fig. 4
figure 4

“Virtual center-Depot” selection method

Full size image

3.1.4 Select the customer

After the depot is selected, the vehicle at the depot chosen selects customers (as Eq. (13)), which completes the “Depot-Customer” selection, then continues to select other customers (as Eq. (14)), as shown in Fig. 5.

Fig. 5
figure 5

“Depot-Customer” selection method

Full size image

As a whole, the method clusters the customers with the depots. As part, the method optimizes the customer combinations within each depot, which combines the overall method and part method advantages.

$$ P_{2j} (t) = \left\{ {\begin{array}{*{20}l} {\frac{{\left[ {\pi_{2j} (t)} \right]^{\alpha } [\eta_{2j} ]^{\beta } }}{{\sum\limits_{{j \in \;{\text{Customer}}}} {[\pi_{2j} (t)]^{\alpha } [\eta_{2j} ]^{\beta } } }},} \hfill & {{\text{if}}j \in \in \{ a,b,...,m\} } \hfill \\ {0,} \hfill & {{\text{otherwise}}} \hfill \\ \end{array} } \right. $$
(13)
$$ P_{ej} (t) = \left\{ {\begin{array}{*{20}l} {\frac{{\left[ {\pi_{ej} (t)} \right]^{\alpha } [\eta ej]^{\beta } }}{{\sum\limits_{{j \in \;{\text{Customer}}}} {[\pi_{ej} (t)]^{\alpha } [\eta_{ej} ]^{\beta } } }},} \hfill & {{\text{if}}j \in \in \{ a,...d,f,...,m\} } \hfill \\ {0,} \hfill & {{\text{otherwise}}} \hfill \\ \end{array} } \right. $$
(14)

3.1.5 Update the pheromone

After the routes are constructed, formula (15) updates all pheromones and is calculated using formula (16), where \(Q\) is a known constant, and \(\rho\) is the pheromone evaporation rate.

$$ \pi_{ij} (t + 1) = (1 - \rho )\pi_{ij} (t) + \sum\limits_{k = 1}^{m} {\Delta \pi_{ij}^{k} (t)} $$
(15)
$$ \Delta \pi_{ij}^{k} (t) = \left\{ {\begin{array}{*{20}l} {Q/fk(t),} \hfill & {{\text{if}}\;{\text{link}}(i,j){\text{on}}\;k{\text{th }}\;{\text{ route}}} \hfill \\ {0,} \hfill & {{\text{otherwise}}} \hfill \\ \end{array} } \right. $$
(16)

3.2 Simulated annealing algorithm

The SA algorithm, which has strong local optimization ability, is introduced to optimize the local optimum solution for the ACO and encourage it to converge to the global optimum solution. The neighborhood operation mechanism in the SA algorithm is “Select-Insert-Optimize-Delete”; that is, it randomly selects a customer in one route, inserts them into another route, minimizes the increased length of the route, and then deletes the customer from the original route, as shown in Fig. 6. Figure 7 shows the pseudo-code for the SA algorithm.

Fig. 6
figure 6

Neighborhood operation mechanism

Full size image
Fig. 7
figure 7

SA algorithm pseudo-code

Full size image

As the temperature decreases, the probability gradually decreases that the solutions with poor fitness are accepted, which guides the ant colony to evolve toward the global optimum.

3.3 Local interchange operation

2-Opt is a common, classical local optimization algorithm that usually involves two exchanges: exchanging customers on different routes and exchanging customers within the route (Manullang et al. (2023)). Three local optimization operations are adopted to avoid local optimization and obtain a better route: (1) inter-route optimization, (2) intra-route optimization, and (3) angle scanning optimization, which includes both inter-route and intra-route optimization (Asefi et al. (2019)).

3.3.1 Inter-route optimization

To determine the optimal situation, inter-route optimization randomly selects two routes, exchanges the customers on the two routes, and ensures the vehicle capacity limit, as shown in Fig. 8.

Fig. 8
figure 8

Inter-route optimization

Full size image

3.3.2 Intra-route optimization

To determine the optimal situation, intra-route optimization randomly selects a route and exchanges two customers, as shown in Fig. 9.

Fig. 9
figure 9

Intra-route optimization

Full size image

3.3.3 Angle scanning optimization

If there is a crossover between two routes, the solution can be improved using local optimization to eliminate this crossover in the solution (Wu et al. (2023)). While enumeration can be used to identify the crossover, it reduces the efficiency and practicality of the algorithm, especially when trying to solve a large-scale VRP. Therefore, to improve the local optimization efficiency, angle scanning optimization can effectively reduce the crossover in the solution (Cai et al. (2014)), as shown in Fig. 10.

Fig. 10
figure 10

Angle scanning optimization

Full size image

Figure 10 illustrates the coordinate system with the depot as the center, in which the right direction is the reference direction. The angle between all customers and the reference direction is calculated, and the route number they belong to is recorded. For example, in (59.6, 1), “59.6” represents the angle, and “1” represents the route number.

Then, it is necessary to judge whether the customer's angle on each route becomes larger in turn; if not, it needs to be optimized. For example, the angles for customers 1, 3, 4, and 6 on route 1 are 9.8, 59.6, 116.1, and 138.2, all of which become larger. Therefore, the shortest route for customers 1, 3, 4, and 6 is “D-1-3-4-6-D,” which reduces the crossovers between the routes, as shown in Fig. 11.

Fig. 11
figure 11

The shortest route for customers 1, 3, 4, and 6

Full size image

Then, it is necessary to judge whether the customer angles between the different routes become larger; if not, there is a route crossover. For example, the angle for customer 2 (105.6) on route 2 is smaller than that for customer 4 (116.1) on route 1, indicating a crossover between routes 1 and 2, and then exchanging customers 2 and 4. After the exchange, the angle of customer 4 (116.1) on route 2 is smaller than the angle of customer 6 (138.2) on route 1, and then exchange customers 4 and 6, as shown in Fig. 10b. After these two exchanges, as the routes in the depot do not cross, the routes are optimal.

3.4 BPC-HACO flowchart

The BPC-HACO flowchart is shown in Fig. 12.

Fig. 12
figure 12

The steps of the BPC-HACO algorithm

Full size image

4 Experimental results and discussion

This section first introduces some MDVRP benchmarks, then the algorithm’s running results, and some comparative experiments to verify the algorithm’s effectiveness in solving various types of MDVRP. Finally, FLA is performed on the MDVRP data set to know their structural features and select suitable algorithms for solving MDVRP.

4.1 Benchmark experiments 1

To illustrate the effectiveness of the BPC-HACO in solving an MDVRP, several experiments based on the benchmark are simulated for the instances available at http://www.bernabe.dorronsoro.es/vrp/, the detailed information for which is given in Table 1. The first column gives the instance name, the second and third columns show the number of customers and the number of depots, the fourth column indicates the vehicle capacity constraint, and the fifth column indicates the maximum vehicle delivery distance constraint, where “–” means no distance constraint.

Table 1 Detailed information for the instances
Full size table

Figure 13 shows the distribution of the original depots for instances 1–23, in which the subtitle “1–50–4” refers to instance 1, which has 50 customers and 4 depots. The depot locations for instances 12, 13 and 14 are the same; the depot locations for instances 15, 16 and 17 are the same; the depot locations for instances 18, 19 and 20 are the same; and the depot locations of instances 21,22 and 23 are the same.

Fig. 13
figure 13

Depot distribution before the movement of instances 1 to 21

Full size image

From Fig. 13, it can be seen that instances 1, 2, 3, 7, 11, 18, and 21 do not have circumcenters, which are solved as follows. First, some depots are moved to ensure that the polygon formed by these depots has a circumcenter, after which these depots are input to the BPC-HACO to determine the optimal solution. Finally, the original depots are reintroduced into the optimal solution to obtain the true route lengths, as shown in Fig. 14. Figure 15 is the depot distribution for instances 1, 2, 3, 7, 11, 18, 21 without circumcenters.

Fig. 14
figure 14

Depot setting for the instances without a circumcenter

Full size image
Fig. 15
figure 15

Depot distribution after the movement of instances 1,2,3,7,11,18, and 21

Full size image

The parameters of the BPC-HACO algorithm are shown in Table 2. The algorithm is implemented in MATLAB R2014a, Windows 7 (× 64).

Table 2 The parameters of the BPC-HACO algorithm
Full size table

All instances are run 30 times, the result from which are shown in Table 3. The second column gives the Best Solution Known (BSK), the third column shows the best solution from all 30 runs, the fourth column gives the average solution from all 30 runs, and the fifth column shows the error between the best solution and the BSK, the sixth column shows the error between the average solution and the BSK, and the seventh column shows the standard deviation for the 30 runs. The E_Sbest, E_Savg, and SD are determined using Eqs. (17)–(19).

$$ E{\text{\_}}Sbest\left( \% \right) \, = \, \left( {Sbest - BSK} \right)/BSK \, \times \, 100\% $$
(17)
$$ E{\text{\_}}Savg\left( \% \right) \, = \, \left( {Savg - BSK} \right)/BSK \, \times \, 100\% $$
(18)
$$ SD = \, \sqrt {\frac{{\sum\limits_{i = 1}^{N} {(Si - Savg)^{2} } }}{N}} $$
(19)
Table 3 Results from the 30 runs
Full size table

In Table 4, the E_Sbest for 23 instances is no greater than 2.0%, the E_Savg is no greater than 3.1%, and the SD is no greater than 15, which indicates that the algorithm is stable and robust, and the algorithm performs balanced in each instance. The best solutions are compared with Bezerra et al. (2018); Yao et al.(2019); Sadati et al.(2020); Zhang et al.(2020); Gu et al.(2022); Torres et al. (2022), as shown in Table 4.

Table 4 Comparison results based on benchmark 1
Full size table

The bold numbers in Table 4 represent the number of BSKs found or the instances that are better than the BSK. The last row in the table shows the average E_Sbest for the 23 instances. The BPC-HACO algorithm finds 14 optimal solutions; meanwhile, instances 7, 8, and 9 have better results than the BSK. The numbers of depots for instances 7, 8, and 9 are 4, 2, and 3, and the numbers of customers are 100, 249 and 249, indicating that the method remainders feasible when there are more or fewer customers and depots.

Instances 1, 2, 3, 7, 11, 18, and 21 need to move some depots, where instances 1, 2, and 3 find the BSK, and instance 7 finds a better result than the BSK. Figure 16 shows the distributions for the original depots and the moved depots and the distributions for the optimal solution in the original depots and the moved depots for instance 7. The distributions for the optimal solution differ only in depot 2 for the original depots and the moved depots. No difference is found between the routes for the other three depots. Therefore, the optimal solution is found by moving some depots. The errors for instances 11 and 18 are 0.75% and 1.06%, and the error for instance 21 is 1.84%, considered relatively large and mainly due to the significant changes in the depot position in instance 21.

Fig. 16
figure 16

Depot and optimal solution distribution for instance 7

Full size image

4.2 Benchmark experiments 2

The performance of the BPC-HACO algorithm in solving MDVRP with distance constraints and the dynamic multi-depot vehicle routing problem (DMDVRP) is evaluated using a series of experiments based on another benchmark, which is available at http://neo.lcc.uma.es/vrp/vrpinstances/multiple-depot-vrp-instances/, the detailed information for which is shown in Table 5.

Table 5 Detailed information on the instances
Full size table

4.2.1 BPC-HACO for solving DMDVRP

DMDVRP is an extension of MDVRP. In MDVRP, all customers are known. In DMDVRP, some customers are known (known customers). Other customers dynamically appear during the service period (new customers), and the objective is to find the shortest route for both the known and new customers (Hu et al.(2023)). The performance of the BPC-HACO algorithm solving for DMDVRP is evaluated based on instances 1–13 in Table 5; the results are compared with Yu et al. (2013) and Xu et al. (2018), as shown in Table 6.

Table 6 The comparison results of DMDVRP
Full size table

Yu et al. (2013) introduced a distance-based clustering algorithm to cluster each customer to the nearest depot. To plan the routes, they proposed an improved ant colony optimization (IACO) with ant colony weight and mutation operations. Xu et al. (2018) used K-means to cluster the customers and introduced a hybrid ant colony optimization (HACO) with mutation operations and local optimization. Both papers randomly selected 30% of the customers to be new customers and then used “The nearest addition method” to deal with the new customers, as shown in Fig. 17. After the new customers (N1, N2, N3, N4) appear, the distances are calculated between the new customers and the customers (V1, V2, V3, V4) that are being or have been served. Then, the new customers (N3, N4) are added to the nearest route, on which customers V3 and V4 are located. While N1 and N2 are close to V1 and V2, the vehicles in these routes have no remaining capacity. Therefore, depot 1 needed to arrange new vehicles to serve new customers N1 and N2.

Fig. 17
figure 17

An example of DMDVRP

Full size image

As can be seen from Table 6, the BPC-HACO performs better, especially when the customer and depot numbers are relatively large (instances 8, 9, 10, and 11). This is because the BPC-HACO selects the depot and the customers based on probability. Then, the algorithm adaptively completes the “depot-customer-vehicle” selection as the number of iterations increases.

BPC-HACO regards the depot and the customer as a whole and then optimizes the whole. In contrast, the IACO and HACO first clustered the customers to the depot and then optimized the routes inside the depot. However, as previously discussed, optimizing the part does optimize the whole. The number of ants and the number of iterations of the three algorithms are the same (100 iterations and 30 ants). When the number of customers or depots is large, the time is shorter because BPC-HACO does not need to select the depot by other means, such as clustering, thus saving time.

4.2.2 BPC-HACO for solving MDVRP with distance constraints

MDVRP with distance constraints has one more vehicle constraint than MDVRP. Therefore, as well as considering vehicle capacity, it is also necessary to consider a vehicle travel distance less than the maximum distance constraint (Yuan et al.(2020)), as shown in Fig. 18.

Fig. 18
figure 18

An example of MDVRP with distance constraints

Full size image

To demonstrate that the BPC-HACO is also effective in solving MDVRP with distance constraints, experiments are conducted based on instances R1-R10 in Table 5, after which the results are compared with the Best Solution Known (BSK), as shown in Table 7. The third column shows the best solution over the 30 runs, and the fourth column shows the average solution for the 30 runs, which are determined using Eqs. (12)–(14), and the seventh column “T” is the average running time (seconds).

Table 7 The comparison results of MDVRP with distance constraints
Full size table

The E_Sbest for the 10 instances is not greater than 5.0%, the E_Savg is not greater than 6.0%, and the T is not greater than 230 s. The BPC-HACO is found to be able to effectively solve the MDVRP with distance constraints within a reasonable running time. The E_Sbest for instances R5 (240 customers, 4 depots) and R10 (288 customers, 6 depots) are, respectively, −0.55% and -0.66%, indicating that the BPC-HACO algorithm can achieve better solutions for large-scale problems. The E_Sbest for instances R1 (48 customers, 4 depots), R2 (96 customers, 4 depots), and R7 (72 customers, 6 depots) is 0%, indicating that the BPC-HACO algorithm can achieve a BSK for small-scale problems.

4.3 BPC-HACO for solving small-scale MDVRP

The BPC-HACO is also effective for solving small-scale MDVRP (MDVRP with a small number of customers and depots). The experimental data come from Wang et al. (2012), Luo et al. (2014), Ma et al. (2014), Yan et al. (2017), Zhang et al. (2009), Ling et al. (2017), where the number of depots is 3, and the number of customers ranged from 15 to 30. The detailed information for the data sets and the solution results are shown in Table 8.

Table 8 The comparison results of small-scale MDVRP
Full size table

The fifth column shows the lengths, the sixth and seventh columns show the lengths and the routes solved by the BPC-HACO, and in the seventh column, 1 is the virtual center, 2, 3 and 4 are the depots, 5 is customer 1, 6 is customer 2, and so on. The BPC-HACO can get better solutions than Wang et al. (2012), Ma et al. (2014), Yan et al. (2017), and Ling et al. (2017) and finds the same result as Luo et al. (2014). The length of the BPC-HACO is 0.52 more than Zhang et al. (2009), but it had one less vehicle, demonstrating that the BPC-HACO has advantages for solving small-scale MDVRP.

4.4 Fitness landscape analysis of the algorithm

There are many metaheuristic algorithms for solving MDVRP, such as Ant Colony Optimization (ACO), Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Differential Evolution (DE), and Tabu Search (TS).

Hence, a fundamental question arises: how to select a best-suited heuristic? Fitness landscape analysis (FLA) has been applied successfully (Zhou et al. (2023); Rodríguez et al. (2023); Dokeroglu et al. (2023)), which provides structural features of the problem to choose the most appropriate algorithm for solving the problem. Fitness landscape generated by random walks in search spaces obtained using different local operators on MDVRP. The fitness landscape is a surface in the search space that defines the fitness for each sample.

4.4.1 Landscape analysis

FLA measures the ruggedness of a landscape in two ways:1. Information analysis measure (\(H(\varepsilon )\), \(M(\varepsilon )\), \(\varepsilon *\)) 2. Statistical analysis measure (\(rFD\), \(\tau\), \(\delta\)). The calculation methods of these 6 parameters refer to Jana et al. (2017). Table 9 summarizes the mean and standard deviation (Std.) of the parameters of the landscape measure for 23 benchmark instances (detailed information in Table 1) over 20 runs.

Table 9 Information and Statistical measures for 23 instances of landscapes
Full size table

\(H(\varepsilon )\) increases with the number of customers or depots, and the Entropy measure indicates that all instances’ landscapes are rugged. \(M(\varepsilon )\) does not change significantly and indicates the existence of multi-modality on the instance landscape structure. \(\varepsilon *\) increases with the complexity of the instance. The more complex the instance, the greater the fitness difference between samples. To make the landscape structure becomes flat, the greater \(\varepsilon *\) will be.\(rFD\) is small for all instances, indicating that the samples’ fitness and distances to the global minimum are uncorrelated. Moreover, the negative value indicates that many local optimums exist on the landscape structure, which is deceptive. \(\tau\) decreases with an increase in the number of customers or depots, which indicates that the degree of nonlinear correlation between neighbor samples increases with the complexity of the instance.\(\delta\) indicates a significant increase in dispersion with length, which indicates the existence of multi-funnels in the landscape structure and the best solution is far away from the possible solutions.

4.4.2 Performance analysis for algorithms

We consider the 5 widely used algorithms for solving MDVRP (ACO, GA, PSO, DE, TS) and only use the standard versions of these algorithms. The parameter settings of these algorithms refer to (Jana et al. (2017)). For fair comparisons, the algorithm’s parameters are consistent, such as population size and the number of iterations.

Table 10 reports the best and mean results and standard deviation of 20 runs for each algorithm on 23 instances. Wilcoxon’s rank sum test is conducted to judge whether has a statistical difference between the best algorithm and the competitors (Bo et al. (2023)). The mean results on each row are in boldface, while ‘italics’ indicate no significant difference between the best algorithm. The best result is underlined.

Table 10 Results of Best, Mean and Std. for 5 optimization algorithms
Full size table

From the above results and discussions, we summarize the landscape features and the most appropriate algorithm for solving MDVRP in Table 11.

Table 11 Summary of landscape features and most appropriate algorithm
Full size table

ACO performs well when the number of customers or depots is small (instances 1 ~ 14), and the standard deviation does not change much, indicating that ACO is robust. GA performs well when the number of customers or depots is large (instances 15 ~ 21), but GA has large standard deviations in some instances. TS achieved the best results on instances 5, 9, 22 and 23 and performed on average similarly to ACO and GA. The standard deviation shows that TS is also robust in some instances. DE provided the best results for instances 1 and 12, and no significant performance improvement except for instances 1 and 12. DE performance decreases as the complexity of the instance increases. In general, the success of DE depends heavily on mutation and crossover operators. PSO obtains the best results on instances 11 and 16. PSO performance degrades as the complexity of the instance increases, similar to DE.

In conclusion, ACO, GA and TS algorithms perform well in solving MDVRP. For other algorithms, some improvements are made to get better results.

5 Conclusions and future work

This paper proposes a hybrid ant colony optimization (BPC-HACO) to solve the MDVRP model based on the polygonal circumcenter. As the BPC-HACO avoids clustering and uses pheromone accumulations to guide the algorithm to select depots and customers intelligently, it can optimize the routes in each depot and the total route of all depots to achieve a unity of quality and efficiency. Furthermore, local search and elite strategies are added to increase the population diversity and retain better solutions. Two kinds of MDVRP benchmarks and six small-scale data sets are employed to verify the effectiveness of the BPC-HACO in solving MDVRP, MDVRP with distance constraints, DMDVRP and small-scale MDVRP. Finally, FLA technology is used to analyze the structural features of MDVRP to choose a suitable algorithm to solve it. Further research could consider an MDVRP with customer priority, distance, and time asymmetries, closer to the needed practical applications.