Intelligent pickup and delivery collocation for logistics models

Abstract

In the context of sharing economy, logistics companies have begun to adopt a new collection and distribution model based on external vehicles, and external vehicles are used to provide customers with collection/distribution services. A kind of Multi-Vehicle Split Pickup and Delivery Problem with Time Windows (MVSPDPTW) is studied in the paper. The minimum total length of the vehicle’s travel path is the objective function, and a mixed-integer linear programming model is established. A high-efficiency Tabu Simulated Annealing (TSA) algorithm is proposed. Two new neighborhood search operators are designed in the algorithm, they are used to repair the violation of capacity constraints and the operation of car replacement. In the method, the neighborhood search range is expanded and the algorithm is avoided from falling into a local optimum. In addition, a taboo mechanism and a penalty mechanism for violation of constraints are added to the algorithm, the effective tailoring of the search space is realized and the algorithm’s global optimization ability is improved. Finally, a large number of simulation experiments were performed on the algorithm based on the Solomon data set and the constructed simulation data set, and the effectiveness of the algorithm is verified in the experiments.

Keywords

Vehicle routing simulated annealing intelligent optimization split demand pickup and delivery

1 Introduction

The development of network economy is inseparable from logistics technology, and logistics development is inseparable from timeliness and cost saving. In the sharing economy mode, the idea of this paper is to study the optimal allocation of vehicle material receiving and dispatching under this environment, the utilization rate of social resources is improved.

Traditional logistics companies use their own vehicles to provide customers with collection/distribution services. As self-owned vehicles have disadvantages such as high cost of use and difficult management, in the context of the sharing economy, logistics companies have begun to adopt a new collection and distribution model based on external vehicles, and external vehicles are used to provide customers with collection/distribution services. The external vehicles are mainly social citizen idle vehicles. The new collection and distribution model can reduce the use of company-owned vehicles, reduce logistics costs, and it is of great significance to improving the utilization rate of social citizen idle vehicles and environmental protection.

Based on the new pickup and delivery model, a Multi-Vehicle Split Pickup and Delivery Problem with Time Windows (MVSPDPTW) is studied in this paper, social citizen idle vehicles are used as the resources for the pickup and delivery service. For collection/distribution tasks, social citizen idle vehicles have their own starting point, destination, earliest departure time and latest return time. Vehicles must depart from the starting point after the earliest departure time to provide customers with collection/distribution services, and return to the end at the latest before the return time. In the process of serving customers, vehicles need to provide services within the customer’s time window and allow demand splitting. The same customer demand can be fulfilled by multiple vehicles in order to make full use of the vehicle’s loading capacity.

Vehicle Routing Problems (VRP) have been a hot issue in the field of logistics research since it was proposed in 1959 [1, 2]. At present, in the research of VRP, it is generally restricted that the customer’s needs can only be fulfilled by one car, it belongs to the VRP whose demand cannot be separated. In 1989, Split Delivery Vehicle Routing Problems (SDVRP) with split demand was studied for the first time [3, 4]. Reasonable splitting of customer needs was beneficial to increase the vehicle loading rate and save cost. In 1994, these were proved that SDVRP is an NP-hard problem [5]. Many scholars have conducted research on SDVRP from different angles. Since customers usually require services within a given time, a time window-constrained SDVRP has been studied. The time limit is introduced to SDVRP for the first time [6], a time-window-constrained SDVRP model is constructed, and a two-stage heuristic algorithm is proposed for solving. A tabu search algorithm is proposed to solve the SDVRP with time window constraints [7], and a variety of new neighborhood search operators are designed. SDVRP with soft time window constraints is studied [8 –11]. The soft time window constraints allow customers to be served outside a given time window by adding a penalty function. In SDVRP, only the customer’s distribution needs are considered. With the development of reverse logistics, customers often have collection/distribution requirements at the same time. Therefore, the SDVRP of a collection demand has been studied, and the demand can be split into the collection and distribution problem [12, 13], this reveals the benefits of splitting requirements. For a given set of collection and distribution locations, when the customer demand is slightly more than half of the vehicle’s load, it proves to bring the greatest benefit. An improved ant colony algorithm is proposed to solve the demand-separable collection and distribution [14, 15], and the experimental results show that the algorithm can improve the operation efficiency of the distribution center.

In the past, the research on SDVRP was basically based on a single vehicle type, but in actual distribution, vehicles often have multiple vehicle types. The SDVRP of multiple vehicle types is studied, and the loading capacity of the vehicle and the maximum mileage are different, and a simulated annealing algorithm is proposed to solve it [16]. Open vehicle routing problem (OVRP) is another type of vehicle routing problem. The main difference between it and the basic vehicle routing problem (VRP) is that the vehicle is not required to return to the original starting point after completing the pickup and delivery task, or if it is required to return to the original starting point, it will return along the original route. Therefore, the driving route of vehicles is open rather than closed. The multi-model open vehicle routing problem with splittable requirements is studied, the vehicle starts from different distribution centers to serve customers, and ends the service after serving the last customer without returning to the distribution center, a tabu search algorithm is proposed to solve the problem [17]. The SDVRP of single vehicle type and multiple vehicle types are studied separately [18], the experimental results show that vehicles with different loading capacities are more in line with actual needs, and it can effectively increase the loading rate of vehicles.

Most of the above-mentioned documents separately study the demand for collection, distribution, multiple models, and customer time windows. However, with the rapid development of logistics technology, user needs are more complex, and this single-mode research has been difficult to meet actual application needs. Therefore, the above-mentioned multiple factors are comprehensively considerd in this article, and a multi-vehicle demand with a time window is researched, the demand can be split to collect and distribute. To solve this problem, the minimum total length of the vehicle path to perform the task is taken as the objective function, and a mixed integer linear programming model is established, an efficient Tabu Simulated Annealing (TSA) algorithm is proposed to solve the problem.

2 Mathematical model

2.1 Briefly describe the process

In MVSPDPTW, there is a given distribution center, a group of customers with different geographical locations and a group of vehicles with multiple models. The goal of MVSPDPTW is to select the right vehicle to perform all customer tasks, so that the total length of the vehicle’s travel path is minimized.

0 means the distribution center, T ={ 1, 2, …, n } means the collection of customer points, each customer point corresponds to a collection/distribution task, the customer point corresponding to the collection task is called the pickup point, the customer point corresponding to the delivery task is called the delivery point. For customer point i ∈ T, [e_i, l_i] represents the i-th time window, e_i represents the earliest service start time, and l_i represents the latest service start time. q_i represents the quantity of goods i need to collect/deliver. Each customer point can be visited by multiple vehicles, but it is only allowed to be visited by the same vehicle at most once. K = { 1, 2, …, m } represents the set of vehicles. For k ∈ K, s_k, n_k, Q_k, o_k, and f_k represent the starting point, ending point, maximum capacity, earliest departure time, and latest return time of vehicle k, respectively. As shown in Fig. 1, the vehicle needs to depart from the starting point after the earliest departure time, collect the goods at the pickup point and send them back to the distribution center, load the goods at the distribution center and deliver them to the delivery point, and finally return to the destination before the latest return time. The vehicle is allowed to visit the distribution center multiple times during the mission.

Fig. 1

Schematic diagram of vehicle execution tasks.

2.2 Virtualization processing

Since the vehicle may visit the distribution center many times, if a variable is used in the model to distinguish how many times the vehicle visits the distribution center, the difficulty of modeling and solving will increase significantly. In order to reduce the difficulty, the following processing methods are adopted: T ={ 1, 2, …, n } represents the collection of customer points, n is the actual number of customer points, for the pickup point numbered i, a numbered n + i virtual delivery point is constructed to correspond to it; for the delivery point numbered j, it is renumbered as n + j, and a virtual pickup point numbered j is constructed to correspond to it. After the above processing, T = T_P ∪ T_D, T_P ={ 1, 2, …, n } represents the set of pickup points, T_D ={ n + 1, n + 2, …, 2n } represents the set of delivery points, and the vehicle needs to collect the goods from point i (i ∈ T_P) and deliver them to point n + j (n + j ∈ T_D). In this processing method, the distribution center is replaced with n virtual customer points, all virtual customer points are located at the same location as the distribution center and there is no service time window restriction; the amount of goods collected/delivered by each virtual customer point corresponds to the equal actual customer in the points. As shown in Fig. 2, the distribution center in Fig. 1 is virtualized and replaced with virtual customer points in the box, where i^* = n + j.

Fig. 2

Virtualization schematic.

2.3 Model symbol

After the above processing, MVSPDPTW is defined on the upper graph of the fully directed graph G = (V, A), V ={ S ∪ N ∪ T ∪ 0 } represents the vertex set, A ={ (i, j) : i, j ∈ V, i ≠ j } represents the arc set.

S: The starting point set of the vehicle, S ={ s₁, s₂, …, s_m };

N: the set of end points of the vehicle, N ={ n₁, n₂, …, n_m };

T: customer point collection, T ={ 1, 2, …, 2n };

d_ij: the distance between point i and point j, i, j ∈ V;

t_ij: the time between point i and point j, i, j ∈ V;

b_ik: the time when the vehicle k arrives at the point i, k ∈ K, i ∈ T ∪ 0;

a_ik: the start time of vehicle k at point i, k ∈ K, i ∈ T ∪ 0;

r_ik: the service time of vehicle k at point i, k ∈ K, i ∈ T ∪ 0;

q_ik: the amount of cargo loaded/unloaded by vehicle k at point i, k ∈ K, i ∈ T ∪ 0;

w_ik: Cargo capacity of vehicle k after point i, k ∈ K, i ∈ T ∪ 0;

x_ijk: Indicates whether the vehicle k is directly from point i to point j, if yes, it is 1, otherwise it is 0;

M: Represents a very large integer.

2.4 Linear model

$\min \sum_{i \in V} \sum_{j \in V} \sum_{k \in K} x_{ijk} d_{ij}$ (1) $\sum_{i \in T_{P}} x_{s_{k} ik} - \sum_{j \in T_{D}} x_{{jn}_{k} k} = 0, \forall k \in K$ (2) $\sum_{i \in S \cup T} x_{ijk} - \sum_{i \in T \cup N} x_{jik} = 0, \forall k \in K, j \in T$ (3) $\sum_{k \in K} \sum_{i \in S \cup T} x_{ijk} ⩾ 1, \forall j \in T$ (4) $\sum_{i \in S \cup T} x_{ijk} ⩽ 1, \forall k \in K, j \in T$ (5) $\sum_{j \in T} x_{ijk} - \sum_{j \in T \cup N} x_{(n + i) jk} = 0, \forall k \in K, i \in T_{P}$ (6) $a_{ik} ⩽ a_{(n + i) k}, \forall k \in K, i \in T_{P}$ (7) $q_{ik} = q_{(n + i) k}, \forall k \in K, i \in T_{P}$ (8) $w_{s_{k} k} = w_{n_{k} k} = 0, \forall k \in K$ (9) $0 ⩽ w_{ik} ⩽ Q_{k}, \forall k \in K, i \in T$ (10)

$\begin{matrix} w_{ik} + q_{jk} - (1 - x_{ijk}) M ⩽ \\ w_{jk}, \forall k \in K, j \in T_{P}, i \in S \cup T \end{matrix}$ (11)

$\begin{matrix} w_{jk} + q_{jk} - (1 - x_{ijk}) M ⩽ w_{ik}, \\ \forall k \in K, j \in T_{D}, i \in T \end{matrix}$ (12) $\sum_{k \in K} q_{ik} = q_{i}, i \in T$ (13) $a_{ik} + t_{s_{k} i} - (1 - x_{s_{k} ik}) M ⩾ o_{k}, \forall k \in K, i \in T_{P}$ (14) $a_{ik} + r_{ik} + t_{{in}_{k}} - (1 - x_{{in}_{k} k}) ⩽ f_{k}, \forall k \in K, i \in T_{D}$ (15)

$\begin{matrix} a_{ik} + r_{ik} + t_{ij} - (1 - x_{ijk}) M ⩽ b_{jk}, \\ \forall k \in K, i \in T, j \in T \end{matrix}$ (16) $b_{ik} ⩽ a_{ik}, \forall k \in K, i \in T$ (17) $e_{i} ⩽ a_{ik} ⩽ l_{i}, \forall k \in K, i \in T$ (18) $x_{ijk} \in {0, 1}, \forall k \in K, i \in V, j \in V$ (19)

Wherein, formula (1) is the objective function, which minimizes the total length of the mission vehicle’s travel path; formulas (2) and (3) indicate that the vehicle will perform the task from the starting point and finally return to the end; formulas (4) and (5) indicate every customer point can be accessed by multiple vehicles, but it is only allowed to be accessed by the same vehicle at most once; formulas (6), (7), (8) indicate that the vehicle needs to collect goods from the pickup point for delivery to the corresponding delivery point; formula (9) means that the cargo carrying capacity of the vehicle from the starting point and returning to the destination is 0; formula (10) expresses the capacity constraint; formulas (11) and (12) express the change of the vehicle carrying cargo capacity at the customer point; formula (13) means the sum of the divided cargo volume of each customer point is equal to the total cargo volume of the customer point; formulas (14) and (15) indicate that the vehicle needs to depart from the starting point after the earliest departure time to provide services to customers, and return before the latest return time end point; formulas (16) and (17) express the relationship between the time when the vehicle arrives at the customer point and the time when it starts service at the customer point; formula (18) expresses that the vehicle can only provide service within the customer’s time window.

3 Algorithm design

In order to solve MVSPDPTW, a tabu simulated annealing algorithm is proposed, and two new neighborhood search operators are designed, which are used to repair the violation of vehicle capacity constraints and the operation of changing vehicles. A taboo mechanism and a penalty mechanism are added for violation of constraints in the algorithm, the effective tailoring of the search space is realized, and the algorithm’s global optimization capability is improved. First, the dynamic greedy algorithm is used to generate the initial feasible solution, and the initial feasible solution is used as the input of the tabu simulated annealing algorithm, and finally the global best solution is output.

3.1 Initial solution generation

The simulated annealing algorithm is essentially an iterative solution algorithm. The initial solution determines the starting point of the iteration. Therefore, a good initial solution helps the algorithm find a better final solution. In the initial solution generation method in this article, a simple and effective dynamic greedy algorithm is used to generate the initial solution [5]. $\hat{k} = \arg_{k \in K}^{m a x} (f_{k} - o_{k})$ (20) $\hat{j} = \arg_{j \in T}^{m i n} {t_{i j} + \max (e_{j} - b_{j k}, 0)}$ (21)

Formulas (20) and (21) respectively represent the selection criteria of vehicles and customer points, and the selection of vehicles is based on the principle of maximizing service time. The selection of customer points is based on the principle of minimizing the total travel time and waiting time between the last visit object i in the current planning path and the customer point j to be selected. Formula (21) is used to select service customer points for the current vehicle in turn, and to check whether the selected customer points meet the insertion constraints, including time window constraints, capacity constraints, customer point visit times constraints, and demand constraints. Demand constraints refer to all delivery of the goods which come from the distribution center, and all collected goods are sent back to the distribution center. If the constraints are met, the customer points are inserted into the current vehicle planning path, and this process is repeated until all customer needs are met.

The specific process of the dynamic greedy algorithm is as follows:

Input: vehicle collection K, customer point collection T, distribution center 0.

Output: Initial feasible solution S_initial.

Step 1: If the set T is not an empty set, go to step 2, otherwise, the algorithm ends to output the result.

Step 2: Formula (20) is used to select the current vehicle k from K.

Step 3: Construct a set of customer points to be selected C = T.

Step 4: If C is not an empty set, go to step 5, otherwise, go to step 9.

Step 5: Formula (21) is used to select customer j from C.

Step 6: Check whether j satisfies the insertion constraint, if so, insert j into the current vehicle planning path R_k.

Step 7: Check whether all the requirements of j are satisfied, and delete j from T if they are satisfied.

Step 8: Delete j from C, and go to step 4.

Step 9: Check whether the last visited object of R_k is distribution center 0, if yes, go to step 11, otherwise, go to step 10.

Step 10: Check whether 0 meets the time window constraint, if it is satisfied, insert 0 into R_k, go to step 3, otherwise, go to step 11.

Step 11: Delete k from K, go to step 1

3.2 Violation of restraint punishment mechanism

In the iterative process, accepting infeasible solutions can help increase the search range of the neighborhood and improve the ability of the algorithm to jump out of the local optimum, and it helps the algorithm to obtain a better feasible solution in the iterative step [19], so a violation constraint punishment mechanism is designed in this paper. The overall constraint penalty function is designed in formula (22), B represents the fitness value of the path planning solution, β represents the parameter penalty weight, η (i, k) , φ (i, k) , λ (i, k) represent the capacity constraint evaluation value, time window constraint evaluation value and demand constraint evaluation value of point i in R_k, respectively. Their calculation methods are given by the formula (23), (24), (25). R_k ={ o_k, …, n_k } represents the execution task path of vehicle k, which is arranged according to the order of vehicle visits.

$\begin{matrix} B = \sum_{i \in V} \sum_{i \in V} \sum_{k \in K} x_{ijk} d_{ij} + β \sum_{k \in K} \sum_{i \in R_{k}} \\ (η (i, k) + φ (i, k) + λ (i, k)) \end{matrix}$ (22) $η (i, k) = max (w_{ik} - Q_{k}, 0), i \in V$ (23)

$φ (i, k) = {\begin{matrix} q_{ik}, a_{ik} - l_{i} > 0, i \in T \\ Q_{k}, a_{ik} + r_{ik} + t_{{in}_{k}} > f_{k}, i is the penultimate access object in R_{k} \\ 0, other \end{matrix}$ (24)

$λ (i, k) = {\begin{matrix} q_{ik}, i is the pickup point, and there is no 0 behind i in R_{k} \\ q_{ik}, i is the delivery point, and there is no 0 in front of i in R_{k} \\ 0, other \end{matrix}$ (25)

3.3 Taboo mechanism

Tabu search is a meta-heuristic algorithm that simulates the human thought process. Its basic idea is to avoid repeated searches in the searched space and force the algorithm to explore other new solutions.

The current solution of each iteration is taken as the taboo object and stored in the tabu list [20]. In the subsequent iterations of l (the length of the tabu list), the object is set to the taboo state, which is different from the side movement taboo in taboo structures [21, 22]. The length of the tabu list refers to the number of objects which are stored in the tabu list. When the number of the stored objects reaches the upper limit and another object is added, the first in, first out principle is adopted to remove the previous objects from the tabu list and then add them.

3.4 Multi neighborhood structure

The multi-neighbor structure can increase the diversity of solutions and improve the possibility of the algorithm to find the best global solution. In this paper, five kinds of neighborhood search operators are used, the migration operator, the migration division operator, and the exchange operator are derived from the classic neighborhood search operator [23]. In the iterative process of this article, the repair operator and the car exchange operator are designed to accept the infeasible solution and the characteristics of multiple models, and they are used to repair the violation of capacity constraints and the operation of changing vehicles respectively.

In order to better explain the operator operation, the following symbols are defined. R_k (k ∈ K) and R_h (h ∈ K) represent the execution task path of vehicle k and vehicle h, respectively. For client points $i \in R_{k}, z_{ik}^{0}$ and $z_{ik}^{l}$ respectively represents the amount of goods which are loaded/unloaded by vehicle k on customer i before and after the operator operation. The calculation method of B (R_k) is given in Equation (26), and B (R_k) represents the fitness value of path R_k.

$\begin{matrix} B (R_{k}) = \sum_{i \in V} \sum_{i \in V} x_{ijk} d_{ij} + β \sum_{i \in R_{k}} (η (i, k) \\ + φ (i, k) + λ (i, k)), \forall k \in K \end{matrix}$ (26)

Task set: In the planned vehicle path, the starting point, ending point of the vehicle and non-customer points such as the distribution center are used as the boundary, consecutive customer points between two adjacent non-customer points form a task set. If there is no client point between two adjacent non-client points, it does not constitute a task set. As shown in Fig. 3, customer points 1 and 2 form a task set. If there is no customer point between the destination and the distribution center, it does not constitute a task set.

Fig. 3

Schematic diagram of the task set.

Migration operator: The migration operator is used to delete the customer point from the original path and insert it into other paths. As shown in Fig. 4. For the customer point i ∈ R_k, i is deleted from R_k and i is inserted into R_h with the principle to minimize B (R_h).

Fig. 4

Schematic diagram of migration operator operation.

Migration segmentation operator: As shown in Fig. 5, customer i is served by vehicles k and h, customer j is served by vehicle h, and i and j belong to the same task set in the path R_h. Delete i from the path R_k, and then insert j into R_k according to the principle of minimizing B (R_k). At this time, i is served by vehicle h, j is served by vehicles k and h together. When vehicles k and h are loaded at i and j. the amount of unloaded cargo is adjusted to $z_{ih}^{l} = z_{ik}^{0} + z_{ih}^{0}, z_{ik}^{l} = 0, z_{jk}^{l} = z_{ik,}^{0} z_{jh}^{l} = z_{jh}^{0} - z_{jk}^{l}$ .

Fig. 5

Schematic diagram of migration and division operator operation.

Exchange operator: Exchange operator is used to exchange customer points in two paths. As shown in Fig. 6, customer point i ∈ R_k and customer point j ∈ R_h. Exchange i and j. After the exchange, i ∈ R_h, j ∈ R_k.

Fig. 6

Schematic diagram of exchange operator operation.

Repair operator: The repair operator is used to repair violations of vehicle capacity constraints. As shown in Fig. 7, if the cargo capacity of vehicle k exceeds the maximum capacity Q_k of the vehicle when serving customer i, choose a customer point j of the tasks set to which i belongs, j can be i, choose a non-empty path R_h, insert j into R_h with the principle of minimizing B (R_h), and adjust the amount of goods which are loaded/unloaded by vehicles k and h at j to: $z_{jk}^{l} = z_{jk}^{0} - η (i, k), z_{jh}^{l} = η (i, k)$ , the calculation method of η(i,k) is given by formula (23).

Fig. 7

Schematic diagram of repair operator operation.

Car exchange operator: As shown in Fig. 8, for non-empty paths R_k and empty paths R_h, all customer points in R_k form a customer point set C, and then according to the path generation method in the initial solution, the customer points in C are inserted into R_h. If all the customer points in C are successfully inserted into R_h, then the path R_k is cleared, otherwise, the customer points which are inserted into R_h will be deleted from R_k.

Fig. 8

Schematic diagram of car change operator operation.

Since a single customer point is only allowed to be accessed by the same vehicle at most once, after the operator operation, if the situation shown in Fig. 9 occurs, R_k contains two customer points i, then one i is selected to be deleted from R_k based on the principle of minimizing B (R_k), and to combine the quantity of goods which are loaded/unloaded by two services i of k.

Fig. 9

Schematic diagram of merged customer points.

3.5 Tabu simulated annealing algorithm

The dynamic greedy algorithm is used to generate the initial feasible solution, and it is set to the current solution S_now of the 0-th generation and the global best solution S_best, and then the iteration starts. In each iteration, the design criteria is used to update S_now and S_best. Finally, when the current temperature is less than the set minimum temperature, the algorithm terminates and outputs S_best. The specific algorithm flow is as follows:

Input: Initial temperature T₀, termination temperature T_end, cooling rate R_T, iteration step size L, number of neighborhood solutions N_u, initial feasible solution S_initial.

Output: S_best is the best solution globally.

Step 1: Set S_initial to S_now and S_best.

Step 2: Initialize the current temperature T′ = T₀ and initialize the number of iterations L′ = 0 at the current temperature.

Step 3: Initialize the tabu list and add S_now to the tabu list.

Step 4: If T> T_end, go to step 5, otherwise, the algorithm ends to output the result.

Step 5: If L = L+ 1 go to step 6, otherwise, , go to step 4.

Step 6: A neighborhood operator is randomly selected from the five neighborhood operators to convert the current solution and to generate a neighborhood solution.

Step 7: Repeat step 6 until the number of neighborhood solutions reaches N_u.

Step 8: Select the best neighborhood solution S_can which is not taboo from N_u neighborhood solutions.

Step 9: If S_can < S_now, S_can will become the new S_now, go to step 11, otherwise, go to step 10.

Step 10:

If e^{(S_can-S_now)/T} > Random (0, 1), S_can will become the new S_now, Random(0,1) is used to generate random data uniformly distributed on (0,1), otherwise keep S_now.

Step 11: If S_can is a feasible solution and satisfies S_can < S_best, S_can will become the new S_best, otherwise keep S_best.

Step 12: If S_now changes, add S_now to the taboo list.

Step 13: Go to step 5.

4 Simulation and performance analysis

In this paper, the VRP (Vehicle Routing Problem with Time Windows, VRPTW) data set with time window constraints [24], the VPRSD (Split Delivery Vehicle Routing Problem with Time Windows, SDVRPTW) data set with time window constraints [25] and the constructed MVSPDPTW simulation data set are used to test TSA algorithm, the experimental results were compared and analyzed. Each example was run 20 times. All experiments were performed on a desktop computer with i5-8500 CPU 3.0 GHz, 16 GB memory, and myeclipse 2017 environment.

4.1 Parameter setting

Setting reasonable parameters can effectively improve the performance of the algorithm [26]. First, the parameter settings in references [27, 28] are used to determine the test interval of each parameter in this article, and then different scale examples are selected to perform multiple tests by changing the parameter combination. Finally, the best combination of parameters is determined.

The value range and step length of each parameter are shown in Table 1. In order to simplify the calculation complexity, the controlled variable method is used to determine the optimal value of each parameter in turn. The final result of TSA parameter setting is as follows: initial temperature T₀ = 100, termination temperature T_end = 0.1, iteration length L = 30, cooling rate R_T = 0.93, penalty weight β= 4, number of neighborhood solutions N_u = 2n + 150 (n is the number of customers), the length of the tabu list is l = 8.

Table 1
Algorithm parameter combination

Parameter T₀ T_end R_T L β l N_u

Range 60∼120 0.1∼1 0.9∼0.95 30∼60 3∼7 6∼10 200∼450

Step size 20 0.03 0.01 10 1 2 50

Parameter	T₀	T_end	R_T	L	β	l	N_u
Range	60∼120	0.1∼1	0.9∼0.95	30∼60	3∼7	6∼10	200∼450
Step size	20	0.03	0.01	10	1	2	50

4.2 Experiment and performance analysis of VRPTW and SDVRPTW data sets

As there is currently no recognized data set available in the field of MVSPDPTW, there is no way to directly test the algorithm in this article. MVSPDPTW is an extension of the classic VRPTW and SDVRPTW. Many of the constraints in the problem are similar. Therefore, if the algorithm in this article can solve VRPTW and SDVRPTW well, then there is reason to believe that the algorithm in this paper can also effectively solve MVSPDPTW.

4.2.1 Numerical experiment of VRPTW dataset

From the VRPTW data set, 27 VRPTW examples are selected for testing [24], and the vehicle capacity is all 200 in the VRPTW examples. Table 2 records the comparison between R_best and the known best solution K_best of the TSA algorithm for each example. Gap represents the gap between R_best and K_best, and Gap = (R_best - K_best)/K_best. K_best data comes from http://web.cba.neu.edu/ msolomon/problems.htm. The design highlights several factors that affect the behavior of routing and scheduling algorithms. They are: geographical data; the number of customers serviced by a vehicle; percent of time-constrained customers; and tightness and positioning of the time windows. The geographical data are randomly generated in problem, Problem sets have a short scheduling horizon and allow only a few customers per route (approximately 5 to 10). In contrast, there are a long scheduling horizon permitting many customers (more than 30) to be serviced by the same vehicle. The customer coordinates are identical for all problems within one type C. The problems differ with respect to the width of the time windows. Some have very tight time windows, while others have time windows which are hardly constraining. In terms of time window density, that is, the percentage of customers with time windows, I created problems with 25, 50, 75 and 100 % time windows.

Table 2
The TSA algorithm solution result is compared with the known best solution

No. Clients N K_best R_best Gap/%

C101 25 191.30 190.74 –0.29

C102 25 190.30 190.74 0.23

C103 25 190.30 190.74 0.23

C104 25 186.90 187.45 0.29

C105 25 191.30 191.81 0.27

C106 25 191.30 191.81 0.27

C107 25 191.30 191.81 0.27

C108 25 191.30 191.81 0.27

C109 25 191.30 191.81 0.27

C101 50 362.40 363.50 0.30

C102 50 362.40 360.56 –0.23

C103 50 361.40 362.17 0.21

C104 50 361.40 359.96 0.54

C105 50 358.00 363.25 0.23

C106 50 362.40 363.25 0.23

C107 50 362.40 362.08 –0.09

C108 50 362.40 363.25 0.23

C109 50 362.40 362.08 –0.09

C101 100 827.30 828.94 0.20

C102 100 827.30 828.94 0.20

C103 100 826.30 828.06 0.21

C104 100 822.90 829.51 0.80

C105 100 827.30 828.94 0.20

C106 100 827.30 828.94 0.20

C107 100 827.30 828.94 0.20

C108 100 827.30 828.94 0.20

C109 100 827.30 828.94 0.20

No.	Clients N	K_best	R_best	Gap/%
C101	25	191.30	190.74	–0.29
C102	25	190.30	190.74	0.23
C103	25	190.30	190.74	0.23
C104	25	186.90	187.45	0.29
C105	25	191.30	191.81	0.27
C106	25	191.30	191.81	0.27
C107	25	191.30	191.81	0.27
C108	25	191.30	191.81	0.27
C109	25	191.30	191.81	0.27
C101	50	362.40	363.50	0.30
C102	50	362.40	360.56	–0.23
C103	50	361.40	362.17	0.21
C104	50	361.40	359.96	0.54
C105	50	358.00	363.25	0.23
C106	50	362.40	363.25	0.23
C107	50	362.40	362.08	–0.09
C108	50	362.40	363.25	0.23
C109	50	362.40	362.08	–0.09
C101	100	827.30	828.94	0.20
C102	100	827.30	828.94	0.20
C103	100	826.30	828.06	0.21
C104	100	822.90	829.51	0.80
C105	100	827.30	828.94	0.20
C106	100	827.30	828.94	0.20
C107	100	827.30	828.94	0.20
C108	100	827.30	828.94	0.20
C109	100	827.30	828.94	0.20

According to the data in Table 2, the TSA algorithm has updated 4 VRPTW examples (example number C101, number of customers 25; example number C102, number of customers 50; example number C107, number of customers 50; example number C109, number of customers 50) in the best known solution. In the remaining 23 VRPTW calculation examples, although the TSA algorithm’s solution results are inferior to the known best solution, the gap between them is kept within 1%. The experimental results show that the TSA algorithm is effective in solving VRPTW.

4.2.2 Numerical experiment of SDVRPTW dataset

From the SDVRPTW data set [25], 12 SDVRPTW examples were selected for testing. In the SDVRPTW example, the vehicle capacity is all 100. Table 3 records the comparison between TSA algorithm and BPC algorithm (Branch and Price and Cut algorithm) for solving the 12 SDVRPTW calculation examples. Gap represents the gap between the TSA algorithm to solve each example result (R_best) and the BPC algorithm to solve each example result (C_best), Gap = (R_best -C_bestC_best)/ C_best.

Table 3
Comparison of TSA algorithm and BPC algorithm solution results

No. Clients N BPC TSA Gap/%

C_best Time/s R_best Time/s

C101 25 291.80 1.4 291.80 6.17 0.00

C102 25 291.80 4.8 291.80 6.89 0.00

C105 25 291.80 1.9 291.80 5.56 0.00

C106 25 291.80 1.7 291.80 6.12 0.00

C107 25 291.80 1.8 291.80 7.26 0.00

C108 25 291.80 3.3 291.80 6.39 0.00

C101 50 587.50 1724.3 588.92 17.95 0.24

C102 50 584.60 1907.5 585.95 18.71 0.23

C105 50 587.50 2440.5 588.92 17.49 0.24

C106 50 587.50 1103.6 588.92 18.12 0.24

C107 50 587.50 1946.6 588.92 19.12 0.24

C108 50 584.00 44.9 585.57 17.30 0.20

No.	Clients N	BPC	TSA	Gap/%
C101	25	291.80	1.4	291.80	6.17	0.00
C102	25	291.80	4.8	291.80	6.89	0.00
C105	25	291.80	1.9	291.80	5.56	0.00
C106	25	291.80	1.7	291.80	6.12	0.00
C107	25	291.80	1.8	291.80	7.26	0.00
C108	25	291.80	3.3	291.80	6.39	0.00
C101	50	587.50	1724.3	588.92	17.95	0.24
C102	50	584.60	1907.5	585.95	18.71	0.23
C105	50	587.50	2440.5	588.92	17.49	0.24
C106	50	587.50	1103.6	588.92	18.12	0.24
C107	50	587.50	1946.6	588.92	19.12	0.24
C108	50	584.00	44.9	585.57	17.30	0.20

From the data in Table 3, it can be seen that the solution results of the TSA algorithm are the same as the BPC algorithmin the small-scale case with 25 customers. With the increase in the number of customers, although the solution results of the TSA algorithm are inferior to the BPC algorithm, the gap between them remains within 1%. In terms of solution time, the BPC algorithm solution time is less than the TSA algorithm in small-scale cases, but as the number of customers increases, the BPC algorithm solution time far exceeds the TSA algorithm. In the solution time for the same number of customers and different cases, the TSA algorithm remains basically unchanged, while the BPC algorithm is significantly different. The experimental results fully demonstrate that the TSA algorithm is close to the BPC algorithm in solving SDVRPTW, but the TSA algorithm takes less time.

4.3 Experiment and performance analysis of simulation data set

12 MVSPSPTW simulation examples were constructed based on 12 SDVRPTW examples. Without changing the distribution center location, customer location, customer cargo volume, and customer time window in the SDVRPTW example, only half of the customers were randomly selected to change their distribution tasks to collection tasks. The starting point and ending point of the vehicle are no longer set as the distribution center, but they are randomly generated within the 100×100 square area that the customer belongs to. The starting service time of a vehicle is a randomly generated integer between 0 and 800, and the end service time is equal to a randomly generated integer between 500 and 900 plus the starting service time of the vehicle; the maximum vehicle capacity is a randomly generated integer between 70 and 120. In addition, when the number of customers is 25, 15 vehicles are randomly generated, and when the number of customers is 50, 30 vehicles are randomly generated to ensure sufficient vehicle resources.

In Table 4, the TSA algorithm, the simulation results’ comparison of the traditional simulated annealing (SA) algorithm, and particle swarm optimization (PSO) algorithm to solve the MVSPDPTW are recorded. The design and processing method of the PSO algorithm comes from the reference [29, 30]. The parameters of the traditional SA algorithm and the PSO algorithm are determined according to the parameter setting method in Table 1. Gap1 and Gap2 respectively represent the gap between TSA algorithm solving each example result (R_best) and SA algorithm solving each example result (T_best), PSO algorithm solving each example result (P_best), Gap1 = (T_best- R_best)/R_best, Gap2 = (P_best - R_best)/R_best.

Table 4
Comparison of TSA, SA, PSO algorithm solution results

No. Clients N TSA SA PSO Gap1/% Gap2/%

R_best Time/s _t T_best Time/s P_best Time/s

C1 25 445.14 10.58 445.14 13.51 450.17 5.36 0.00 1.13

C2 25 387.12 10.69 391.75 15.73 400.61 5.87 1.20 3.48

C3 25 439.78 12.17 442.16 17.18 451.21 6.12 0.54 2.60

C4 25 385.19 11.85 391.38 14.32 400.32 5.68 1.61 3.93

C5 25 439.71 13.62 441.62 14.89 451.63 4.95 0.43 2.71

C6 25 396.19 12.81 403.17 18.67 411.65 5.02 1.76 3.90

C7 50 681.95 29.68 685.41 35.68 701.81 19.32 0.51 2.91

C8 50 690.99 32.51 698.78 38.16 722.65 21.18 1.13 4.58

C9 50 717.51 31.91 725.42 40.75 743.95 21.93 1.10 3.68

C10 50 668.93 30.84 681.69 37.62 703.68 23.87 1.91 5.19

C11 50 711.96 32.61 719.54 38.65 735.41 22.62 1.06 3.29

C12 50 694.72 31.48 711.37 36.47 727.85 23.36 2.40 4.77

No.	Clients N	TSA	SA	PSO	Gap1/%	Gap2/%
C1	25	445.14	10.58	445.14	13.51	450.17	5.36	0.00	1.13
C2	25	387.12	10.69	391.75	15.73	400.61	5.87	1.20	3.48
C3	25	439.78	12.17	442.16	17.18	451.21	6.12	0.54	2.60
C4	25	385.19	11.85	391.38	14.32	400.32	5.68	1.61	3.93
C5	25	439.71	13.62	441.62	14.89	451.63	4.95	0.43	2.71
C6	25	396.19	12.81	403.17	18.67	411.65	5.02	1.76	3.90
C7	50	681.95	29.68	685.41	35.68	701.81	19.32	0.51	2.91
C8	50	690.99	32.51	698.78	38.16	722.65	21.18	1.13	4.58
C9	50	717.51	31.91	725.42	40.75	743.95	21.93	1.10	3.68
C10	50	668.93	30.84	681.69	37.62	703.68	23.87	1.91	5.19
C11	50	711.96	32.61	719.54	38.65	735.41	22.62	1.06	3.29
C12	50	694.72	31.48	711.37	36.47	727.85	23.36	2.40	4.77

According to the data in Table 4, the TSA algorithm in this paper has better solution performance than the traditional SA algorithm and PSO algorithm. The main factors are: (i) The TSA algorithm has the best solution result, which is up to 2.40% higher than the traditional SA algorithm, and there is an average increase of 1.14%. Compared to the PSO algorithm, the highest increase is 5.19%, and an average increase is 3.52%. (ii) In terms of solving time, the SA algorithm is the longest, the TSA algorithm is second, and the PSO algorithm is the shortest. However, the overall time-consuming gap between the TSA algorithm and the PSO algorithm is not large.

In addition, the required time for the TSA algorithm to solve the same number of customers is basically the same, and it has good stability. The main reasons for the better solution performance of the TSA algorithm are: (i) Due to the characteristics of the multi-models in this paper, the result of the car selection will have a vital impact on the pros and cons of the final solution. The car change operator is helpful to find the most suitable vehicle to perform the task. In addition, a variety of operator coordination methods are beneficial to expand the neighborhood search range and improve the algorithm’s global optimization capability. (ii) A taboo mechanism and a penalty mechanism for violation of constraints are added to the TSA algorithm, the effective tailoring is achieved in the search space, avoiding the algorithm from falling into a local optimum and saving solution time. In contrast, the traditional SA algorithm and the PSO algorithm are easy to fall into a local optimum.

5 Conclusions and outlook

In this paper, under the new mode of solicitation and distribution, we study a kind of multi-vehicle demand with a time window that can be divided into solicitation and distribution. To solve this problem, a mixed-integer linear programming model is established. In the process of constructing the model, a corresponding virtual collection/distribution point was constructed for each customer point, the increase of some variables is reduced in the model, and the big M method was used to linearize the nonlinear constraints. An efficient TSA algorithm is designed. In addition to the traditional SA algorithm framework, the TSA algorithm incorporates a taboo mechanism and a penalty mechanism for violation of constraints, which realizes the effective tailoring of the search space and improves the algorithm’s global optimization capability. The TSA algorithm updates 4 known best solutions in the 27 VRPTW examples. In the solution results of the 12 SDVRPTW examples, the difference between the TSA algorithm and the BPC algorithm is not more than 1%, and the solution time is shorter. As far as the 12 MVSPDPTW simulation examples are concerned, the TSA solution results are not inferior to the traditional SA algorithm and PSO algorithm, and the maximum increase is 2.40% and 5.19%, respectively. The experimental results fully prove the feasibility and effectiveness of the TSA algorithm in this paper to solve MVSPDPTW.

There are still many problems that need to be solved urgently in the research content of this paper. Future research work can be carried out from the following two aspects: (i) Consider the demand to be split according to orders instead of arbitrarily continuous split; (ii) Consider the use of a joint delivery method between external vehicles and self-owned vehicles.

Footnotes

Acknowledgments

This work was sponsored by Scientific Research Project (NO.20C1085) of Hunan Provincial Education Department, China.

References

Dantzig

G.B.

, Ramser

J.H.

The truck dispatching problem, Management Science 10(6) (1959), 80–91.

Kong

, Zhong

Z.L.

, Zhang

J.H.

Bi-objective Vehicle Routing Problems with Path Choice and Variable Speed, Complex Systems and Complexity Science 19(1) (2022), 74–80. doi: 10.13306/j.1672-3813.2022.01.010.

Dror

, Trudeau

Savings by split delivery routing, Transportation Science 23(2) (1989), 141–145.

W.J.

, Zhang

X.Y.

, Xu

Y.C.

, Gao

Loading is the Key: A Novel Genetic Quantum Algorithm for SDVRP. 2021 IEEE Congress on Evolutionary Computation (CEC), 28 June-1 July 2021, Krakow, Poland. pp. 1817–1825.

Dror

, Trudeau

Vehicle routing with split deliveries, Discrete Applied Mathematics 50(3) (1994), 239–254.

Frizzell

P.W.

, Giffin

J.W.

The split delivery vehicle scheduling problem with time windows and grid network distances, Computers & Operations Research 22(6) (1995), 655–667.

S.C.

, Haugland

A tabu search heuristic for the vehicle routing problem with time windows and split deliveries, Computers & Operations Research 31(12) (2004), 1947–1964.

Xie

J.Y.

, Fu

, Qiu

, Xia

Y.K.

Tabu Search Algorithm for Vehicle Routing Problem with Multiple Soft Time Windows, Computer Engineering and Applications 55(6) (2019), 252–256. doi: 10.3778/j.issn.1002-8331.1711-0276.

Xia

, Fu

A tabu search algorithm for distribution network optimization with discrete split deliveries and soft time windows, Cluster Computing 22(6) (2019), 15447–15457.

10.

Cao

, Chen

X.H.

, Lv

Z.H.

, Li

R.C.

, Fan

S.S.

Optimization of Classified Municipal Waste Collection Based on the Internet of Connected Vehicles, IEEE Transactions on Intelligent Transportation 22(8) (2021), 5364–5373. doi: 10.1109/TITS.2020.2981564.

11.

H.F.

, Huang

Z.C.

, Zhang

Q.Z.

et al. Improved pyramid evolution strategy for solving split delivery vehicle routing problem, Journal of Computer Applications 41(1) (2021), 300–306. doi: 10.11772/j.issn.1001-9081.2020050615.

12.

Novak

, Ergun

Pickup and delivery with split loads, Transportation Science 42(1) (2008), 32–43.

13.

Leng

L.L.

, Zhao

Y.W.

, Zhang

C.M.

Shared mechanism based self-adaptive hyper-heuristic for regional low-carbon location-routing problem, Computer Integrated Manufacturing Systems 26(5) (2020), 1407–1424. doi: 10.13196/j.cims.2020.05.025.

14.

Yang

, Zou

, Xu

X.H.

Improved Ant Colony Algorithm for Vehicle Routing Problem with Time Windows and Split Pickups and Deliveries, System Engineering 33(9) (2015), 58–62.

15.

Puttur

Rajappa, J. H. Wilck and J. E. Bell, An Ant Colony Optimization and Hybrid Metaheuristics Algorithm to Solve the Split Delivery Vehicle Routing Problem, International Journal of Applied Industrial Engineering 3(1) (2016), 55–73. doi: 10.4018/IJAIE.2016010104.

16.

Tavakkoli

, Safaei

A new capacitated vehicle routing problem with split service for minimizing fleet cost by simulated annealing, Journal of the Franklin Institute 344(5) (2007), 406–425.

17.

S.B.

, Chai

Y.M.

, Wang

L.M.

Research on Split Delivery Open Vehicle Routing Problem, Computer Engineering 37(6) (2011), 168–171. doi: 10.3969/j.issn.1000-3428.2011.06.058.

18.

Sujoy

, Andrei

, Jean

et al. The multi-depot split-delivery vehicle routing problem model and solution algorithm, Knowledge-Based Systems 7(1) (2014), 238–265.

19.

, Eglose

A new tabu search heuristic for the open vehicle routing problem, Journal of the Operational Research Society 56(3) (2005), 267–274.

20.

H.B.

, Lim

Local search with annealing-like restarts to solve the VRPTW, European Journal of Operational Research 150(1) (2003), 115–127.

21.

Archetti

, Speranza

M.G.

A tabu search algorithm for the split delivery vehicle routing problem, Transportation Science 40(1) (2006), 64–73.

22.

Qiu

, Fu

, Eglose

et al., A tabu search algorithm for the vehicle routing problem with discrete split deliveries and pickups, Computers & Operations Research 100(1) (2018), 102–116.

23.

Wang

, Ma

X.L.

, Lap

Y.T.

et al. Vehicle routing problem: simultaneous deliveries and pickups with split loads and time windows, Transportation Research Record 20(1) (2013), 120–128.

24.

Solomon

M.M.

Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research 35(2) (1987), 254–265.

25.

Luo

, Qin

, Zhu

et al., Branch and price and cut for the split delivery vehicle routing problem with time windows and linear weight-related cost, Transportation Science 51(2) (2017), 668–687.

26.

Franzim

Revisiting simulated annealing: a component based analysis, Computers & Operations Research 104(1) (2019), 191–206.

27.

Xia

Y.K.

, Fu

, Pan

L.J.

et al. Tabu search algorithm for thedistance-constrained vehicle routing problem with split deliveriesby order, Plos One 13(5) (2018), 54–57.

28.

Liu

H.P.

, Hou

X.D.

Research on the Key Parameters in the Simulated Annealing Algorithm, Computer Engineering and Science 10(1) (2008), 55–57. doi: 10.3969/j.issn.1007-130X.2008.10.019.

29.

, Peng

, Liu

Improved Particle Swarm Optimization for Vehicle Routing Problem with time windows, Computer Engineering and Applications 45(27) (2009), 202–218. doi: 10.3778/j.issn.1002-8331.2009.27.061.

30.

Y.F.

, Yan

, Kang

An Improved Particle Swarm Optimization for Simultaneous Pickup and Delivery Vehicle Routing Problems with Time Windows under a Fuzzy Random, Operations Research and Management Science 27(12) (2018), 73–83. doi: 10.12005/orms.2018.0281.

No.	Clients N	BPC		TSA		Gap/%
		C_best	Time/s	R_best	Time/s
C101	25	291.80	1.4	291.80	6.17	0.00
C102	25	291.80	4.8	291.80	6.89	0.00
C105	25	291.80	1.9	291.80	5.56	0.00
C106	25	291.80	1.7	291.80	6.12	0.00
C107	25	291.80	1.8	291.80	7.26	0.00
C108	25	291.80	3.3	291.80	6.39	0.00
C101	50	587.50	1724.3	588.92	17.95	0.24
C102	50	584.60	1907.5	585.95	18.71	0.23
C105	50	587.50	2440.5	588.92	17.49	0.24
C106	50	587.50	1103.6	588.92	18.12	0.24
C107	50	587.50	1946.6	588.92	19.12	0.24
C108	50	584.00	44.9	585.57	17.30	0.20

Intelligent pickup and delivery collocation for logistics models

Abstract

Keywords

1 Introduction

2 Mathematical model

2.1 Briefly describe the process

2.4 Linear model

3.1 Initial solution generation

3.4 Multi neighborhood structure

4 Simulation and performance analysis

4.1 Parameter setting

Table 1 Algorithm parameter combination Parameter T0 T end R T L β l N u Range 60∼120 0.1∼1 0.9∼0.95 30∼60 3∼7 6∼10 200∼450 Step size 20 0.03 0.01 10 1 2 50

4.2.1 Numerical experiment of VRPTW dataset

Footnotes

Acknowledgments

References

Table 1
Algorithm parameter combination

Parameter T₀ T_end R_T L β l N_u

Range 60∼120 0.1∼1 0.9∼0.95 30∼60 3∼7 6∼10 200∼450

Step size 20 0.03 0.01 10 1 2 50