Solving Multi-Depot Vehicle Routing Problems with Dynamic Customer Demand Using a Scheduling System TS-DPU Based on TS-ACO

1  Introduction

Logistics is essential to connect trade and business activities worldwide with high efficiency in today’s society. As the logistics industry moves towards intelligence, digitalization, and automation in the era of booming technology, companies aim to establish an effective vehicle dispatching system to reduce operating costs. In this context, the vehicle routing problem has gained significant attention as a crucial aspect of logistics services. In the classical vehicle routing problem (VRP), a set of vehicles is dispatched from a central depot to serve a predetermined group of customers. All information about the routing network and the customer base is known in advance. As the logistics industry continues to evolve, numerous VRP extensions have been proposed to address more practical constraints. These include the Capacitated VRP (CVRP) [1,2], the VRP with Time Windows (VRPTW) [3,4], and Multi-Depot VRP (MDVRP) [5], all of which are categorized as Static VRP (SVRP) [6].

According to [7], a dynamic path problem (DARP) was initially proposed for a single vehicle, in which dynamic requests occur randomly between the start and end nodes. Psaraftis [8] proposed a periodic optimization strategy for dynamic demands but only for small-scale data, and he summarized the dynamic path problems and distinguished them from static path problems. Powell et al. [9] then classified methods for solving dynamic demand into two categories. The first category is a priori optimization, where dynamic demand is fitted based on probabilistic methods before planning begins to create a distribution network that meets future expectations. The second category is multi-stage optimization, in which the demand is unpredictable and therefore requires a high dynamic processing capability to cope with unexpected demand.

However, due to the advancement of communication technology, customers can now provide their demands to logistics companies at any time, leading to the constant submission of orders during the distribution process. This dynamic customer demand, along with the constraints of the distribution process caused by the real situation’s special circumstances, gives rise to a dynamic vehicle routing problem (DVRP). The factors driving the dynamics are broadly classified into two categories [10]: dynamic customer demand and dynamic environment. Savelsberg and Sol [11] proposed a dynamic routing of independent vehicles method and a branch-and-price algorithm, which uses real data to simulate dynamic environments for testing, effectively reducing operating costs. Gendreau et al. [12] proposed a parallel taboo search for solving dynamic versions of courier service applications, which responds to and processes new customer demand as soon as it is available. Kilby et al. [13] dividing each workday into time slots and inserting dynamic customer demand into the appropriate location within each time slot. Montemanni et al. [14] introduced an ant colony-based approach to handle dynamic customer demand by segmenting the workday into discrete time slices and using a re-optimization method to solve the whole again. Potvin et al. [15] investigated a dynamic vehicle routing and scheduling issue incorporating time window constraints and compared the advantages and disadvantages between different scheduling strategies by considering a DVRP that combines two dynamic variables: real-time customer requests and dynamic travel times. Azi et al. [16] proposed a heuristic approach based on adaptive large neighborhood search to address vehicle routing scenarios involving multiple delivery routes, where customer demands arise dynamically and require immediate response. de Armas and Melián-Batists [17] introduced a metaheuristic based on variable neighborhood search to tackle dynamic vehicle routing problems constrained by time windows, and it has been used by a Spanish company. Jia et al. [18] designed a new scheduling system that combines the PSO algorithm with periodic optimization to address the dynamic capacitated VRP (DCVRP), using a region partitioning approach to simplify the problem and solving the subproblems in parallel. Xiang et al. [19] proposed an ant colony algorithm(ACO) based on pairwise proximity learning, called PPL-ACO, for dealing with the DVRP considering the nodal relationships during the cycle period in periodic optimization. Pan and Liu [20] propose GENM-A3C, a graph-POMDP-DRL framework that yields near-optimal routes in milliseconds under dynamic, uncertain, and partially observable conditions. Sze et al. [21] proposed a two-stage AVNS that embeds critical nodes to overcome the traditional AVNS’s inability to handle dynamic accidents and impractical diversion constraints, thereby significantly reducing DVRP delays. Demirbilek [22] introduced Multi-Planning with Acception/Rejection Policy (MPA) and Multi-Planning with Mandatory Assignment Policy (MPM) for DVRP. Results show that MPA outperforms under tighter time windows and high-demand settings, while MPM demonstrates robust performance across broader conditions.

Up to now, most research on the DVRP assumes that service is carried out by a single depot [19,23–25]. In practice, logistics networks typically rely on multiple depots to optimize operations. A multi-depot structure enhances demand responsiveness and reduces costs by sharing resources across depots. Therefore, single-depot VRP models are insufficient for addressing real-world logistics challenges [26]. By combining a multi-depot structure into the DVRP, vehicles can be pre-positioned near real-time demand hotspots, thereby reducing response times at the same time, shared inventory and pooled fleets across depots absorb demand surges and mitigate delay risks. In turn, reduced empty-running distances translate into lower operating costs. Consequently, existing studies on DVRP are not effectively applicable in current scenarios.

In this paper, we first introduce a vehicle routing problem with time windows, which combines the multi-depot environment and dynamic customer demand, named Multi-depot and Dynamic VRP with Time Windows (MD-DVRP). Fig. 1 depicted a conception of this problem. At the outset of the day’s delivery task, some accepted orders already exist (non-red circles), including those unfulfilled from the previous day and those received the day before the delivery task began. As shown in Fig. 1a, by first making arrangements for these known orders, the routes indicated by the arrows in the figure can satisfy all currently known demands, where the dashed arrows represent routes already completed at the current moment. Over time, dynamic orders (red circles) will continue to be received until the delivery time ends. As can be seen in Fig. 1b, the green, blue, and purple circles represent the current completed orders, the current unfinished orders, and the current vehicle locations, respectively. Fig. 1c presents the adjusted routes that satisfy dynamic orders. The goal of the MD-DVRP is to dynamically adjust and optimize vehicle travel routes based on real-time changes in various information, to achieve efficiency and economy in logistics distribution.

Figure 1: The conception of MD-DVRP

Based on the conception of MD-DVRP provided, it can be inferred that MD-DVRP has repeating elements over time, such as customers and partial routes. Thus, we adopt the ACO algorithm because it retains memory of what worked well before by the pheromone. It can use pheromones from previous time slices to guide the route plan when new orders are received in a later time slice, whereas GA must re-initialize its entire population and TS must completely reset its tabu list, so neither competitor can rapidly reuse prior experience. Moreover, by constructing routes probabilistically edge-by-edge, ACO is able to insert newly arrived customers in real time without disrupting the existing route backbone, while GA’s crossover and mutation operators and TS’s neighborhood moves typically trigger large-scale route reconstructions that markedly increase computational overhead. So ACO may make finding good delivery plans faster and easier.

To solve MD-DVRP, we proposed a scheduling system, TS-DPU. It centers on a dynamic processing unit and addresses the MD-DVRP in the following steps. Initially, it captures dynamic customer demands in real time. To address dynamic customer demand, we first adopt a time-slicing strategy [13] by partitioning the entire day into equal intervals. Subsequently, at the end of each time interval, our system obtains the positions of all vehicles and the completed orders. Then, it combines incomplete orders with current vehicle locations to form static problems for different depots. An improved ACO algorithm, named TS-ACO, is proposed to optimize vehicle routes and assign the results to the corresponding vehicles for each static problem. Finally, we conduct several simulations to evaluate our system. The results showed that our system achieved great results. By flexibly converting dynamic problems into static ones and solving them efficiently, this system effectively responds to dynamic distribution scenarios, enhancing the timeliness and adaptability of vehicle routing optimization.

Our main contributions are summarized as follows.

(1)   We first introduce a vehicle routing problem with time windows, which combines the multi-depot environment with dynamic customer demand, MD-DVRP. MD-DVRP can better match today’s complex logistics than DVRP.

(2)   We propose a scheduling system, TS-DPU, which transforms our proposed MD-DVRP into several static problems. TS-DPU uses proven techniques for low-cost, high-quality solutions.

(3)   We propose an improved ACO algorithm with spatio-temporal distances, TS-ACO, and apply it to our TS-DPU. It achieves better results in the MD-DVRP compared to the classical ACO algorithm.

The remainder of this paper is structured as follows. Section 2 provides a detailed description of the proposed MD-DVRP, along with its corresponding mathematical formulation. Section 3 outlines the general procedure and implementation of the scheduling system TS-DPU proposed in this study. Section 4 conducts a parameter sensitivity analysis of the improved ACO algorithm, TS-ACO, using the Cordeau instance and compares its performance against the classical ACO algorithm in 19 instances. Section 5 concludes the paper by summarizing the key findings and contributions, and also discusses the limitations of the study.

2  Problem Definition and Mathematical Modeling

2.1 The Definition of MD-DVRP

The classical VRP is defined on an undirected graph G=(V,E), where the set of nodes V=V0,V1,V2,...,Vn includes a central depot V0 and customer nodes V1 through Vn. The edge set E=i,j∣i,j∈V represents the connections between nodes, each associated with a spatial distance. Every customer node i is assigned a demand qi and a soft delivery time window denoted by [ETi,LTi]. DVRP turns the static undirected graph G into a dynamic undirected graph Gt=(Vt,Et), which means that when a customer demand is suddenly submitted to the depot or modified, the undirected graph adds this customer node and all the arcs with this customer node as the end node, and the undirected graph is changed.

MD-DVRP is an extension of the above unique depot V0 into multiple depots D={D1,D2,...,Dn}, then MD-DVRP is defined as a dynamic undirected graph Gt=(Vt,Et), where Vt={D,V1,V2,...,Vn},Et={i,j|i,j∈Vt}. Here in Fig. 2 as an example, the red customer nodes 15, 16, 17, 18 in Fig. 2b indicate the new demand submitted to the depot from Fig. 2a in the current time slice. If the original route cannot be modified, logistics enterprises need an additional vehicle to pick up the new route node for additional service. In other words, Depot 1 and Depot 3 need to add one vehicle to serve the new customer nodes 15 and 16; Depot 4 further needs two additional vehicles to serve the new customer nodes 17 and 18. This situation will greatly increase the overall operating costs, as a vehicle to serve a single customer will also make the vehicle utilization rate low.

Figure 2: An example of MD-DVRP

Therefore, in order to improve vehicle utilization and reduce operating costs, it is a critical issue to modify the original route to add new customer nodes to the original route. As shown in Fig. 2c, adding node 16 to the original route R=[D2,12,4,D2], then R′=[D2,12,4,16,D2], and similarly adding customer node 17 and customer node 18 to the corresponding routes to get brand new routes [D4,7,3,17,D4] and [D4,14,18,9,D4], respectively, without Additional new routes can serve additional customers, which will greatly improve the utilization of vehicles, effectively improve operational effectiveness of each depot, greatly reduce operating cost and significantly improve the profit of the enterprise.

The symbols and parameter definitions employed throughout the paper are provided in Table 1.

2.2 Mathematical Model

Eq. (1) represents the final solution to this problem, minimizing the total cost including fixed cost, time window cost, and travel cost. Eq. (2) means that the vehicles used by each depot in all time slices should not exceed the maximum available vehicles for each depot. Eq. (3) implies that the total demand allocated to individual vehicles in all time slices should stay under the vehicle’s maximum load constraint. Eq. (4) ensures that each customer is visited exactly once across all time slices and by only one vehicle. Eq. (5) restricts each vehicle to having a single departure and return depot. Eq. (6) indicates that each customer’s demand must be served by a unique depot and cannot be split. Eq. (7) is used to eliminate subtour constraints. Eq. (8) implies that all routes leave the repository and return to the repository no later than the final cut-off time after serving all customer nodes. Eqs. (9) and (10) represent decision variables in the model.

minC=cfixed∑n=1nts∑i∈D∑j∈C∑k∈Kxijkn+ce∑n=1nts∑i∈V∑j∈C∑k∈Kxijknmax{(ETj−tja),0}+cl∑n=1nts∑i∈V∑j∈C∑k∈Kxijknmax{(tja−LTj),0}+cd∑n=1nts∑i,j∈V∑k∈Kxijkndijs(1)

s.t.

∑n=1nts∑j∈C∑k∈Kxijkn≤|K|,∀i∈D(2)

∑n=1nts∑i∈V∑j∈Cxijknqj≤Q,∀k∈K(3)

∑n=1nts∑i∈V∑k∈Kxijkn=∑n=1nts∑i∈V∑k∈Kxjikn=1,∀j∈C(4)

∑n=1nts∑i∈D∑j∈Cxijkn=∑n=1nts∑i∈C∑j∈Dxjikn≤1,∀k∈K(5)

∑i∈Dyij=1,∀j∈C(6)

∑n=1nts∑i∈S∑j∈Sxijkn≤|S|−1,∀k∈K,|S|=∑n=1nts∑j∈Cxijkn,∀i∈D, ∀k∈K(7)

Ts+∑n=1nts∑i∈V∑j∈Vtijxijkn+∑n=1nts∑i∈V∑j∈Ctisxijkn≤Tf,∀k∈K(8)

∑n=1ntsxijkn∈{0,1},∀i∈V, ∀j∈V, ∀k∈Kand{i∈D}∩{j∈D}=∅(9)

yij∈{0,1},∀i∈D, ∀j∈C(10)

By integrating dynamic requirements, multi depots and more comprehensive cost-benefit analysis, MD-DVRP solves the problems of vehicle scheduling and resource allocation between warehouses in the existing MDVRP and the insufficient applicability of DVRP under the complex logistics challenges. Therefore, It helps enterprises reduce logistics costs and improve economic benefits.

Consider any instance of the (single-depot) dynamic VRP (DVRP). Build an instance of MD-DVRP by setting the number of depots to 1 and copying all other data and dynamic revelation events unchanged. Any algorithm that solves MD-DVRP in polynomial time would therefore solve the original DVRP instance in polynomial time. But DVRP is known to be NP-hard [27], so a polynomial-time solver would contradict these results. Hence MD-DVRP is NP-hard.

3  Proposed Scheduling System TS-DPU

Our system depicted in Fig. 3 is centered on the dynamic processing unit, which has the functions of capturing dynamic customer demands, obtaining current distribution progress, creating static problems and planning optimal routes. Whenever a dynamic requirement is submitted to the depot, the dynamic processing unit will capture the dynamic order and save it to the unprocessed order set. Assign dynamic orders to corresponding depots based on the principle of proximity. The dynamic processing unit provides separate services for each depot. At each time slice end, the dynamic processing unit will obtain the positions of all vehicles and completed orders. Then, the unplanned order set is combined with the current vehicle location to form multiple new static vehicle routing problems based on different depots. Finally, to solve each static problem to obtain the route of vehicles, the results are assigned to the corresponding vehicles.

Figure 3: The architecture of TS-DPU

To further clarify the operation of the proposed TS-DPU system, a simple example is provided to illustrate how a dynamic order flows through each stage shown in Fig. 3.

Step 1 (Dynamic demand reception). During each time slice, the dynamic processing unit continuously receives new customer requests. For example, at t=2.5 h, a new demand (C_new) arises near Depot A and is stored in the unprocessed order set.

Step 2 (Status collection). At the end of the time slice (t=3 h), the system gathers real-time information on all vehicles and unserved customers. Suppose Vehicle 2 from Depot A has just completed a delivery and is available for new tasks.

Step 3 (Static problem formulation). The dynamic processing unit integrates the new order, current vehicle locations, and remaining customers to construct a new static MDVRP for the next time slice.

Step 4 (Static optimization). The TS-ACO algorithm solves each static subproblem to obtain optimized routes. In this case, C_new is assigned to Vehicle 2 due to its spatial proximity and availability.

Step 5 (Route execution). The optimized routes are transmitted to vehicles for execution, and Vehicle 2 immediately proceeds to serve C_new.

This concise example demonstrates how TS-DPU dynamically transforms real-time information into solvable static problems and maintains system responsiveness to emerging customer demands.

The MILP formulation in the previous chapter addresses the static vehicle routing problem (VRP) with time windows in a multi-depot environment. In this paper, the TS-DPU scheduling system adapts this formulation by converting dynamic problems into a series of static subproblems at each time slice. When new customer demands arrive, they are treated as new static instances, solved using the TS-ACO algorithm. This approach allows us to maintain the MILP structure while efficiently incorporating dynamic demands into the routing plan without disrupting existing routes.

3.1 Temporal-Spatial Distance

In this system, we use a combined distance, which is referred to as the temporal-spatial distance. The details of the temporal-spatial distance are explained below.

As a critical component of the temporal-spatial distance, the temporal distance is calculated using the method proposed by Fan et al. [28]. Suppose that there are two nodes i and j with time windows [ETi,LTi] and [ETj,LTj], and ETi≤ETj. Then at some time t∈[ETi,LTi] the time it takes for a vehicle arriving at node i to arrive at node j is t+tis+dijs/v. Thus, the time t′ required to go from node i to node j lies between the interval [ETi+tis+dijs/v,LTi+tis+dijs/v], using [a,b] to represent the above interval. Fig. 4 presents the relationship between the intervals [a,b] and [ETj,LTj].

Figure 4: Example chart of interval distance

There are four cases of temporal distance between customer nodes:

•   When there is a duplicated part between [a,b] and [ETj,LTj], then it means that there is an overlapping part between the moment when the vehicle arrives at node j and the time window of node j. Then the temporal distance between the customer node i and the customer node j is defined as μ1(tij+tis).

•   When a>LTj, this indicates that the vehicle’s arrival at node j from node i will be delayed. The temporal distance between the customer node i and the customer node j is μ2(a−LTj).

•   When b<ETj, this implies that the vehicle will arrive at node j from node i earlier than allowed. In this situation, the temporal distance between the customer node i and the customer node j is μ3(ETj−b).

•   When ETj<a<b<LTj, arrival at node j from node i takes place within the valid time window. Thus, the temporal distance between the customer node i and the customer node j is (tij+tis).

Here, we define an equation to describe the above four cases in Eq. (11).

dijt={μ1(tij+tis)a<ETj<bora<LTj<bμ2(a−LTj)LTj<aμ3(ETj−b)ETj>btij+tisETj<a<b<LTj(11)

The spatial distance is calculated using the classical Euclidean distance. That is, Eq. (12).

dijs=(xi−xj)2+(yi−yj)2(12)

Due to the difference between temporal and spatial distances in the representative meaning, they are summed up as temporal distances after normalization, respectively. As shown in Eq. (13).

dij=αdijt−minm,n∈C,m≠ndmntmaxm,n∈C,m≠ndmnt−minm,n∈C,m≠ndmnt+βdijs−minm,n∈C,m≠ndmnsmaxm,n∈C,m≠ndmns−minm,n∈C,m≠ndmns,α+β=1,i,j∈C(13)

To illustrate the computation of the temporal distance in Eq. (11), consider two customers i and j. The spatial distance between customers i and j is 6, the time distance tij is constant at 1 hour for all cases, and the service time at each node is tis=1 h. The weighting factors for the temporal and spatial distances are α=0.1 and β=0.9, respectively. Furthermore, the parameters used for the temporal distance calculation are μ1=3, μ2=5, and μ3=1. For all customer j nodes, the time window is fixed at [10,14]. The calculation results of temporal-spatial distance are shown in Table 2.

This example shows how overlapping and non-overlapping time windows yield different temporal distance values. After normalization, these values are combined with spatial distance in Eq. (13) to obtain the final temporal-spatial distance dij.

3.2 TS-ACO

In Section 3.1, we explain the temporal-spatial distance, which takes into account the influence of the time window and the spatial distance between nodes. Here, we propose an improved ACO algorithm, TS-ACO. It utilizes the temporal-spatial distance to solve the proposed MD-DVRP.

3.2.1 The Proposed TS-ACO

In the classical ACO algorithm, the choice of the next visited node in the construction of the optimal route is guided by the probability distribution over all feasible nodes. This probability distribution is solved as shown in Eq. (14).

pij={(πij)σ(ηij)ρ∑u∈Ω(πiu)σ(ηiu)ρj∈Ω0otherwise(14)

πij denotes the pheromone generated during the construction of the optimal route by the ants, and ηij denotes the visibility of the ants to all feasible nodes. Typically, πij and ηij use the inverse of the spatial distance directly, as shown in Eqs. (15)–(17).

πij=(1−ρ)πij+ρΔπij(15)

Δπij={1Rbest,if (i,j)∈ best solution0,otherwise(16)

ηij=1dijs(17)

where ρ is the rate of evaporation of pheromones, and Rbest is the best routes in this iteration.

However, MD-DVRP involves the time window cost of customers, so it is insufficient to consider only the spatial distance to the selection of feasible nodes. Therefore, we use the temporal-spatial distance to represent the relationship between the two nodes, so that the algorithm can comprehensively consider how to reduce operating cost while meeting customer needs on time when planning routes. A detailed pseudocode can be found in Algorithm 1.

The differences between TSACO and ACO are shown in Table 3.

3.2.2 The Time Complexity of TS-ACO

A. Single Dynamic Stage.

At each stage n∈{1,…,nst}, a new instance of the TSACO solver is executed. The computational work at this stage comprises two main parts:

1.   Initialization: The solver initializes based on the current state of the system. This involves constructing the spatiotemporal and heuristic information matrices for all Vn known nodes. The complexity of this step is determined by the pairwise calculations between all nodes.

O(Vn2)(18)

2.   Iterative Solving: The core Ant Colony Optimization process runs for NCmax iterations to generate routes for the Cn unassigned customers. Within each iteration, the most computationally intensive task is the solution construction for all m ants, which has a quadratic relationship with the number of customers to be routed.

O(NCmax⋅m⋅Cn2)(19)

B. Total Dynamic Stages.

The total computational complexity for the entire dynamic simulation is the sum of the complexities from each individual planning stage.

Total Complexity=∑n=1nstO(Vn2+NCmax⋅m⋅Cn2)(20)

We can approximate the overall complexity as:

O(nst⋅NCmax⋅m⋅Ctotal2)(21)

4  Experiment

In this section, we compare the evaluation results of TS-ACO, which considers both temporal and spatial distances, with that of the classical ACO, which only considers spatial distance. The experiments are implemented in Pycharm2025.1 and executed on a Windows 11 platform, equipped with an Intel Core i5-14400 (2.50 GHz) and 32 GB RAM. The algorithm was evaluated using the following parameter settings: μ1=3, μ2=5, μ3=1.0, v=80, ce=50, cl=100, cd=20, and cfixed=300.

4.1 Dataset

As there was no available dataset for the problem addressed in this paper, we modified the instances proposed by Cordeau et al. [29] to obtain the dataset needed for our study. Specifically, assuming that nts=5, we divided the first half of the instance into initially known customers in Table 4 and then equally divided the second half into four datasets of dynamic customers in Tables 5–8. The time window of each customer was generated randomly from the interval [8,16], with a fixed random seed 42 to ensure the reproducibility of the experiment.

4.2 Parameter Sensitivity Analysis

For an ACO algorithm, the colony size and the iteration count are two very important parameters. Here, we make a parameter sensitivity analysis to find the best combination of them shown in Fig. 5. The parameter ranges used in this analysis were selected with reference to previous studies on ACO parameter tuning [30], ensuring that the experimental settings are consistent with established practices in the literature. According to Fig. 5, it is obvious that when the iteration number and the number of ant colonies are 150 and 60, respectively, the solution cost is the lowest.

Figure 5: Fitness under different iteration times and ant colony number combinations

Under NCmax=150, m=60, pheromone evaporation rate is equal to 0.7, heuristic factor is equal to 2.2, pheromone factor is equal to 1.4. We then to find the best α. The results are shown in Fig. 6. Note that α=0 means that spatial distance is only considered. As can be seen in Fig. 6a, in terms of average fitness, when α is equal to 0.1 and β is equal to 0.9, the solution effect is optimal. Although the results obtained with different values of α are very similar and in terms of the minimum fitness value, the result obtained by α=0.3 is better than α=0.1. It is easy to find that considering the temporal distance is significantly better than considering only the spatial distance. Moreover, The optimal values of α and β reflects the fact that in many dynamic logistics scenarios, especially those with multiple depots and time windows, spatial distances typically play a more dominant role in determining optimal routes. The time component, while important, is generally less critical when the logistics network is relatively stable, and the customer demand is spread across a broader area, making spatial factors more influential in the overall solution quality.

Figure 6: Fitness of 150 iterations under different α

Similarly, under the above parameter settings, we also conducted a sensitivity analysis on the μ1, μ2 and μ3.

As shown in Table 9, the combination (μ1 = 3, μ2 = 5, μ3 = 1) achieves the lowest average cost (32,856.65) among all tested configurations. It also yields the smallest minimum cost (29,970.17), indicating that this parameter setting provides the most cost-efficient performance in the spatio–temporal distance calculation. Therefore, (3,5,1) can be regarded as the optimal configuration for minimizing the overall routing cost.

4.3 Further Experiments

To further evaluate the performance of TS-ACO, additional 18 instances (pr2–pr19) from Cordeau et al. [29] were adapted, and comparative experiments were carried out. As illustrated in Fig. 7, TS-ACO demonstrates notable improvements over classical ACO in instances pr1–pr4, pr7–pr15, while performing close in the remaining instances. Specifically, instances pr5, pr6, pr16 and pr19 involve a relatively large number of customers. In contrast, although pr17 and pr18 contain fewer customers, they include more depots. The results demonstrate that TS-ACO performs better in reducing operating costs in scenarios with moderate data set sizes and depot quantities.

Figure 7: The average operating cost of ACO and TS-ACO

In addition, a Wilcoxon signed-rank test was performed between TS-ACO and classical ACO to statistically assess the significance of the observed performance differences. As shown in Table 10, TS-ACO achieves statistically significant improvements over classical ACO in pr11, pr13, and pr15, with p-values of 0.0215, 0.0049, and 0.0094, respectively—all below the 0.05 significance level. In pr16, the p-value reaches 0.0897, which is close to the threshold, indicating a marginal yet consistent advantage of TS-ACO. These results suggest that TS-ACO delivers significantly better performance in several instances and maintains generally superior or comparable outcomes across the remaining datasets. Overall, TS-ACO achieves a favorable balance between solution quality and computational efficiency, demonstrating both effectiveness and practicality for dynamic routing scenarios.

Moreover, a comprehensive comparison was conducted among classical ACO, PSO [31], VNS [32], TSACS [30], and TS-ACO.

As shown in Tables 11 and 12, although PSO and VNS achieve slightly better solution quality than TS-ACO, their computational times are significantly longer. As the number of customers increases, their runtime grows rapidly—reaching several times that of TS-ACO. PSO is somewhat faster than VNS but still far from meeting real-time requirements. In contrast, TSACS exhibits high computational efficiency but produces inferior solutions compared with TS-ACO.

In this section, we compare the evaluation, TS-ACO, which incorporates temporal-spatial distances, outperforms the classical ACO algorithm in 13 instances. To further verify the effectiveness of TS-ACO at different time slices, we compare the different cost increments between consecutive time slices for both algorithms. As illustrated in Fig. 8, where TC, EC, LC, and DC denote the total cost, the early arrival cost, the late arrival cost and the distance cost, respectively. Compared to the classical ACO algorithm, TS-ACO reduces all the cost increment in all time slices except the early arrival cost. Although the 2nd time slice has a higher early arrival cost increment than the classical ACO in the early arrival cost, TS-ACO reduces the cost increment by a large amount at the other time slices, especially at the 1st time slice. This comparative analysis confirms that the ACO algorithm with temporal-spatial distance achieves superior performance in cost reduction across all time slices.

Figure 8: Comparison of TS-ACO and ACO at different costs

The results demonstrate that TS-ACO achieves a significant cost reduction within each time slice, attesting to its superior performance in contemporary logistics. When new customer orders emerge in real time, it seamlessly inserts these dynamic requests into the existing delivery routes at a lower marginal cost, thereby offering a measurable cost-saving advantage for the enterprise.

Fig. 9 illustrates the distribution of depots and customers, where star-shaped icons represent depots and circular dots denote customers. Customers who share the same color as a depot are served by vehicles departing from that depot. The figures show the depot–customer assignments under the optimal routes generated by the classical ACO and TS-ACO, respectively, using the pr1 instance. In particular, TS-ACO requires fewer deployed depots to complete the routing task, thereby reducing overall operational costs.

Figure 9: Distribution of customers of each depot after optimization

5  Conclusion

In today’s rapidly developing era, the logistics industry needs real time service, so many logistics companies choose to expand a single depot into multiple depots to meet customer demand in time. Due to the rapid development of communication technology, customers can submit their requirements to service providers at any time. Consequently, a scheduling system TS-DPU driven by the TS-ACO is developed in this paper to tackle the proposed MD-DVRP. It expands the traditional DVRP and brings it closer to the real environment. Here, we add the time cost to the calculation of the total cost and propose TS-ACO that considers the spatial and temporal distance to solve the problem. Experiments have shown that TS-ACO considering spatial and temporal distance is significantly better than the classical ACO only considers spatial distance.

However, our study did not consider multi-objective optimization, thereby overlooking the simultaneous minimization of operational costs and maximization of customer satisfaction, both of which are critical in real-world logistics operations. In addition, environmental dimensions such as carbon emissions and energy consumption, which are increasingly emphasized in contemporary logistics practice, have not been explicitly integrated into the proposed framework. Future work should therefore extend the current single-objective model to a multi-objective model that jointly optimizes economic efficiency, service quality, and environmental sustainability.

Acknowledgement: None.

Funding Statement: This work was supported by the Startup Foundation for Introducing Talent of Nanjing University of Information Science and Technology.

Author Contributions: The authors confirm contribution to the paper as follows: Conceptualization, Tsu-Yang Wu and Chien-Ming Chen; methodology, Tsu-Yang Wu and Yanan Zhao; validation, Chengyuan Yu; formal analysis, Yanan Zhao and Chengyuan Yu; investigation, Saru Kumari and Chien-Ming Chen; data curation, Saru Kumari and Chien-Ming Chen; writing—original draft preparation, Tsu-Yang Wu, Yanan Zhao, Chengyuan Yu, Saru Kumari and Chien-Ming Chen. All authors reviewed the results and approved the final version of the manuscript.

Availability of Data and Materials: The data are contained within the article.

Ethics Approval: Not applicable.

Conflicts of Interest: The authors declare no conflicts of interest to report regarding the present study.

References

1. Kalatzantonakis P, Sifaleras A, Samaras N. A reinforcement learning-variable neighborhood search method for the capacitated vehicle routing problem. Expert Syst Appl. 2023;213:118812. doi:10.1016/j.eswa.2022.118812. [Google Scholar] [CrossRef]

2. Souza IP, Boeres MCS, Moraes REN. A robust algorithm based on differential evolution with local search for the capacitated vehicle routing problem. Swarm Evol Comput. 2023;77:101245. doi:10.1016/j.swevo.2023.101245. [Google Scholar] [CrossRef]

3. Wu Q, Xia X, Song H, Zeng H, Xu X, Zhang Y, et al. A neighborhood comprehensive learning particle swarm optimization for the vehicle routing problem with time windows. Swarm Evol Comput. 2024;84:101425. doi:10.1016/j.swevo.2023.101425. [Google Scholar] [CrossRef]

4. Wu H, Gao Y, Wang W, Zhang Z. A hybrid ant colony algorithm based on multiple strategies for the vehicle routing problem with time windows. Complex Intell Syst. 2023;9(3):2491–508. doi:10.1109/icie.2009.237. [Google Scholar] [CrossRef]

5. Zhang K, Lin X, Li M. Graph attention reinforcement learning with flexible matching policies for multi-depot vehicle routing problems. Phys A Stat Mech Appl. 2023;611:128451. doi:10.1016/j.physa.2023.128451. [Google Scholar] [CrossRef]

6. Montemanni R, Gambardella LM, Rizzoli AE, Donati AV. Ant colony system for a dynamic vehicle routing problem. J Comb Optim. 2005;10(4):327–43. doi:10.1007/s10878-005-4922-6. [Google Scholar] [CrossRef]

7. Wilson NHM, Colvin NJ. Computer control of the Rochester dial-a-ride system. Cambridge, MA, USA: Massachusetts Institute of Technology, Center for Transportation Studies; 1977. [Google Scholar]

8. Psaraftis HN. A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transp Sci. 1980;14(2):130–54. doi:10.1287/trsc.14.2.130. [Google Scholar] [CrossRef]

9. Powell W, Jaillet P, Odoni A. Stochastic and dynamic networks and routing. Handb Oper Res Manag Sci. 1995;8(C):141–295. [Google Scholar]

10. Zhang H, Ge H, Yang J, Tong Y. Review of vehicle routing problems: models, classification and solving algorithms. Arch Comput Methods Eng. 2022;29(1):195–221. doi:10.1007/s11831-021-09574-x. [Google Scholar] [CrossRef]

11. Savelsbergh M, Sol M. Drive: dynamic routing of independent vehicles. Oper Res. 1998;46(4):474–90. doi:10.1287/opre.46.4.474. [Google Scholar] [CrossRef]

12. Gendreau M, Guertin F, Potvin JY, Taillard E. Parallel tabu search for real-time vehicle routing and dispatching. Transp Sci. 1999;33(4):381–90. doi:10.1287/trsc.33.4.381. [Google Scholar] [CrossRef]

13. Kilby P, Prosser P, Shaw P. Dynamic VRPs: a study of scenarios. University of Strathclyde Technical Report [Internet]. 2002 [cited 2025 Nov 20]. Available from: https://www.researchgate.net/publication/2944001. [Google Scholar]

14. Montemanni R, Gambardella LM, Rizzoli AE, Donati AV. A new algorithm for a dynamic vehicle routing problem based on ant colony system. Handbook Syst Autoimmune Dis. 2003;1(1):27–30. doi:10.1007/s10878-005-4922-6. [Google Scholar] [CrossRef]

15. Potvin JY, Xu Y, Benyahia I. Vehicle routing and scheduling with dynamic travel times. Comput Oper Res. 2006;33(4):1129–37. [Google Scholar]

16. Azi N, Gendreau M, Potvin JY. A dynamic vehicle routing problem with multiple delivery routes. Ann Oper Res. 2012;199(1):103–12. doi:10.1007/s10479-011-0991-3. [Google Scholar] [CrossRef]

17. de Armas J, Melián-Batista B. Variable neighborhood search for a dynamic rich vehicle routing problem with time windows. Comput Ind Eng. 2015;85(1):120–31. doi:10.1016/j.cie.2015.03.006. [Google Scholar] [CrossRef]

18. Jia YH, Chen WN, Gu T, Zhang H, Yuan H, Lin Y, et al. A dynamic logistic dispatching system with set-based particle swarm optimization. IEEE Trans Syst Man Cybern Syst. 2017;48(9):1607–21. doi:10.1109/tsmc.2017.2682264. [Google Scholar] [CrossRef]

19. Xiang X, Tian Y, Zhang X, Xiao J, Jin Y. A pairwise proximity learning-based ant colony algorithm for dynamic vehicle routing problems. IEEE Trans Intell Transp Syst. 2021;23(6):5275–86. doi:10.1109/tits.2021.3052834. [Google Scholar] [CrossRef]

20. Pan W, Liu SQ. Deep reinforcement learning for the dynamic and uncertain vehicle routing problem. Appl Intell. 2023;53(1):405–22. doi:10.1007/s10489-022-03456-w. [Google Scholar] [CrossRef]

21. Sze JF, Salhi S, Wassan N. An adaptive variable neighbourhood search approach for the dynamic vehicle routing problem. Comput Oper Res. 2024;164:106531. doi:10.1016/j.cor.2024.106531. [Google Scholar] [CrossRef]

22. Demirbilek M. Optional and mandatory assignment strategies for dynamic vehicle routing with time windows. Ain Shams Eng J. 2025;16(9):103462. doi:10.1016/j.asej.2025.103462. [Google Scholar] [CrossRef]

23. Hanshar F, Ombuki-Berman BM. Dynamic vehicle routing using genetic algorithms. Appl Intell. 2007;27(1):89–99. doi:10.1007/s10489-006-0033-z. [Google Scholar] [CrossRef]

24. Ouaddi K, Benadada Y, Mhada FZ. Ant colony system for dynamic vehicle routing problem with overtime. Int J Adv Comput Sci Appl. 2018;9(6):306–15. doi:10.14569/ijacsa.2018.090644. [Google Scholar] [CrossRef]

25. Mańdziuk J, żychowski A. A memetic approach to vehicle routing problem with dynamic requests. Appl Soft Comput. 2016;48:522–34. doi:10.1016/j.asoc.2016.06.032. [Google Scholar] [CrossRef]

26. Mogale DG, Ghadge A, Jena SK. Modelling and optimising a multi-depot vehicle routing problem for freight distribution in a retail logistics network. Comput Ind Eng. 2025;207:111315. doi:10.1016/j.cie.2025.111315. [Google Scholar] [CrossRef]

27. Psaraftis HN, Wen M, Kontovas CA. Dynamic vehicle routing problems: three decades and counting. Networks. 2016;67(1):3–31. doi:10.1002/net.21628. [Google Scholar] [CrossRef]

28. Fan H, Zhang Y, Tian P, Lv Y, Fan H. Time-dependent multi-depot green vehicle routing problem with time windows considering temporal-spatial distance. Comput Oper Res. 2021;129:105211. doi:10.1016/j.cor.2021.105211. [Google Scholar] [CrossRef]

29. Cordeau JF, Laporte G, Mercier A. A unified tabu search heuristic for vehicle routing problems with time windows. J Oper Res Soc. 2001;52(8):928–36. doi:10.1057/palgrave.jors.2601163. [Google Scholar] [CrossRef]

30. Zhang W, Gajpal Y, Appadoo SS, Wei Q. Multi-depot green vehicle routing problem to minimize carbon emissions. Sustainability. 2020;12(8):3500. doi:10.3390/su12083500. [Google Scholar] [CrossRef]

31. Ai TJ, Kachitvichyanukul V. A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Comput Oper Res. 2009;36(5):1693–702. doi:10.1016/j.cor.2008.04.003. [Google Scholar] [CrossRef]

32. Kuo Y, Wang CC. A variable neighborhood search for the multi-depot vehicle routing problem with loading cost. Expert Syst Appl. 2012;39(8):6949–54. doi:10.1016/j.eswa.2012.01.024. [Google Scholar] [CrossRef]