Sage Journals: Discover world-class research

Abstract

In some special rescue scenarios, the needed goods should be transported by drones because of the landform. Therefore, in this study, we investigate a multi-objective vehicle routing problem with time window and drone transportation constraints. The vehicles are used to transport the goods and drones to customer locations, while the drones are used to transport goods vertically and timely to the customer. Three types of objectives are considered simultaneously, including minimization of the total energy consumption of the trucks, total energy consumption of the drones, and the total number of trucks. An improved artificial bee colony algorithm is designed to solve the problem. In the proposed algorithm, each solution is represented by a two-dimensional vector, and the initialization method based on the Push-Forward Insertion Heuristic is embedded. To enhance the exploitation abilities, an improved employed heuristic is developed to perform detailed local search. Meanwhile, a novel scout bee strategy is presented to improve the global search abilities of the proposed algorithm. Several instances extended from the Solomon instances are used to test the performance of the proposed improved artificial bee colony algorithm. Experimental comparisons with the other efficient algorithms in the literature verify the competitive performance of the proposed algorithm.

Keywords

Vehicle routing problem artificial bee colony time window drone transportation multi-objective

Introduction

The utilization of smart manufacturing and intelligent devices has greatly promoted the transforming of traditional industries.¹ Thus far, many emerging computer technologies^2,3 and sophisticated equipment such as the robotics⁴ and drones⁵ have extremely improved the production efficiency and reduced the cost of the enterprise. Recently, numerous excellent enterprises have invested various drones to deliver their commodities^6,7 while many researchers have also concentrated on the vehicle routing problem with drones (VRPD),^8

–12 which can be observed as an extended version of the vehicle routing problem (VRP).¹³ Many exhaustive overviews of the VRP could be found in the literature,^14
–16 where a number of customers need to be visited successively by a fleet of vehicles. In VRPD, the customers should be served by both vehicles and drones.⁸ The applications of drones in the VRP systems have attracted many unexpected benefits.¹⁰ Wang et al. implemented a set of thoroughly mathematical experiments to testify that combining the drones with trucks or vehicles can decrease nearly 75% costs.¹⁰ Wang and Sheu generalized that avoiding crowdedness, quick delivery, and saving manpower and material resources are the primary characteristics of the VRPD.¹⁷ Besides, Yurek and Ozmutlu suggested the drones’ own unique advantages when delivering goods on the rough or difficult terrains.¹⁸

In the last decades, many algorithms have been applied to the vehicle routing problem with time window (VRPTW), such as the genetic algorithm (GA),¹⁹ the tabu search (TS) algorithm,²⁰ the variable neighborhood search (VNS) algorithm,²¹ the gradient evolution algorithm,²² the particle swarm optimization,²³ the ant colony optimization,²⁴ the adaptive large neighborhood search heuristic,²⁵ and the simulated annealing algorithm.²⁶ However, for some special requirements, the drones can complete transportation tasks. Chang and Lee established a model for one truck equipped a set of drones.²⁷ Wang et al. studied a group of trucks with several drones.¹⁰ Murray and Chu designed a dispatching manner in which one drone cooperates with one truck to serve a fleet of customers.⁸ Furthermore, another valuable research direction involving the VRPD is the vehicle routing problem with time window and drones (VRPTWD).^28,29 Guerriero et al. proposed a VRPTWD model considering the soft time window and customer satisfactions.²⁸ Phan and Suzuki studied a multi-objective optimization problem of VRPTWD with the constraints of simultaneous receiving and dispatching.³⁰ In a nutshell, the VRP with drones should be taken more and more research focuses, especially in special scenarios, such as the disaster relief.^15,31,32

The artificial bee colony (ABC) algorithm was firstly proposed by Karaboga.^33,34 Since then, the ABC algorithm has been applied in many types of optimization problem, such as the graph selection problem,³⁵ the flexible job shop scheduling problem,^36,37 the path planning problem,³⁸ the distributed flow shop scheduling problem,^39,40 the block flowshop,⁴¹ the prefabricated optimization problem,⁴² the VRPTW problem,⁴³ the fuzzy scheduling problem,⁴⁴ and the task scheduling problem.⁴⁵ The ABC algorithm has been shown as a competitive optimization method compared with other efficient optimization methods, such as the Jaya algorithm,⁴⁶ the invasive weed optimization algorithm,⁴⁷ the differential evolution algorithm,⁴⁸ the harmony search algorithm,⁴⁹ the shuffled frog-leaping algorithm,⁵⁰ the bioinspired metaheuristic algorithm,⁵¹ the krill herd algorithm,⁵² the TS algorithm,⁵³ the particle swarm algorithm,⁵⁴ and other multi-objective optimization algorithms.^55,56

Considering the special requirements of drones in the VRP problem, and the efficiency of the ABC algorithm, we design an improved ABC (IABC) to solve the multi-objective VRPTWD (MO-VRPTW-D) problem. The main contributions of this study are as follows: (1) to the best of our knowledge, this study is the first one to dispose the VRPTW with drone transportation by using the ABC algorithm; (2) to enhance the exploitation abilities, an improved employed heuristic is developed to perform detailed local search; and (3) a novel scout bee strategy is presented to improve the global search abilities of the proposed algorithm.

The remainder of this report is organized as follows. The second section describes the MO-VRPTW-D model and exhibits an example; the third section clarifies the framework of the proposed algorithm; the fourth section introduces the simulation results and the fifth section draws the conclusion and future work.

Problem statement and MO-VRPTW-D model

Problem description

The proposed MO-VRPTW-D can be generalized from three aspects: customers, trucks and drones, objectives and constraints.

For the customers, the complex transportation scenario, such as the disaster relief and rescue or the transport of delicate goods, should be considered. Besides, each customer has multiple pairs of productions or demands. Except from the special of height and demand, the customers also have the synchronized visits and time windows constraints.

For the trucks and drones, each truck equips a drone and the multiple pairs of productions are delivered to the horizontal location of a customer by the truck and raised to the customer by the drone. Moreover, each truck has two types of capacities due to the multiple pairs of productions for customers and the capacity of each truck is different. The truck that has a greater capacity will consume more fuels and generate more energy consumption than the smaller one. Furthermore, each drone possesses different flight speed and different energy consumption, that is, the faster drone will create greater energy consumption.

Additionally, the objectives of MO-VRPTW-D are to minimize the total energy consumptions of trucks, the entire energy consumptions of drones, and the maximal number of the employed trucks. And the total energy consumptions are respected to the energy consumption index and the travel distances for each truck or drone. For the constraints, first, each truck has the limit of maximum capacity and maximal travel distance, and the maximum number of the trucks is fixed; secondly, each customer has a time windows and the penalty will emerge when the arrival time of a truck at a customer is overstepped the time window. Besides, all the truck must depart and return to the depot and each customer must be visited only once by exactly one truck.

MO-VRPTW-D model

The MO-VRPTW-D is modeled as a directed complete graph $G = (N, A)$ : N is the vertex set including the customers set $C = {1, 2, ..., n}$ and the depot node 0; here 0_s and 0 _e are respecting the start and end depot, respectively, and we set the $0 = 0_{s} = 0_{e}$ for clear expression; while A is the arc set comprising the set of horizontal distances between customers $A_{h} = {(i, j) | i, j \in C, i \neq j}$ and a set of perpendicular distances $A_{p} = {(i_{b}, i_{t}) | i \in C}$ ; here i_b and i_t are symbolizing the bottom and top location of the perpendicular arc for customer i, respectively.

$V = {1, 2..., v}$ is the trucks set and $D = {d_{1}, d_{2} ..., d_{v}}$ is a set of drones, where d_k respects the drone of the truck k. Each truck k has two types of capacities bm_k and bs_k while the former is the capacity of the main materials and the latter is the supplementations. Each customer $i \in C$ also has two kinds of demands dm_i and ds_i . There is a certain amount of proportional relationship between dm_i and ds_i such as one tent must be equipped four or more tent frames when building the temporary accommodations for the victims of a natural calamity. Notice that the amount of all these demands carried by truck k must be less than or equal to the corresponding maximal capacities of truck k. There is a maximal travel distance r_k of each truck k which starts at depot 0_s and ends at depot 0_e after serving some customers.

Moreover, each customer must be visited only once by exactly one truck and each customer i has a time window [e _i, l_i ]. [e ₀, l ₀] is the time window of depot, e ₀ is equal to zero while l ₀ is equal to r_k . The wait time w_i will be produced if the arrival time z_i of truck k at customer i is early than e _i and when z_i is later than l_i , the penalty will be attached to this route.

Specially, there is an energy consumption coefficient wt_k for each truck k while each drone d_k has an energy consumption coefficient wd_k and a flight speed yd_k . In this article, each customer i has a vertical trip distance tp_i and the serving duration s_i of customer i can calculate by dividing the double trip distance 2tp_i of by the yd_k . Here yd_k is the speed of drone equipped at truck k which visiting the customer i. Besides, α, β, and γ are the weight coefficients of the total energy consumption of the trucks, total energy consumption of the drones, and the total number of trucks, respectively.

Finally, all of the travel distance t_ij or tp_i is numerically equal to the travel or trip time in the MO-VRPTW-D model. The mathematical formulations are described below.

Decision variables

x_{i j}_{k} = \{\frac{1, if truck k travel from vertex i to vertex j}{0, otherwise}

y_{i}_{k} = \{\frac{1, if vertex i is served by vehicle k}{0, otherwise}

Objective

min α \sum_{i = 0}^{n} \sum_{j = 0}^{n} \sum_{k = 1}^{v} x_{i}_{j k} w t_{k} t_{i j} + β \sum_{i = 1}^{n} \sum_{k = 1}^{v} x_{0 j k} 2 t p_{i} \frac{1}{y d_{k}} w d_{k} + γ \sum_{k = 1}^{v} x_{0 j k}, i \neq j, i, j \in N, k \in V

Constraints

\sum_{i = 1}^{n} d m_{i} y_{i k} \leq b m_{k}, \forall k \in V

\sum_{i = 1}^{n} d s_{i} y_{i k} \leq b s_{k}, \forall k \in V

\sum_{k = 1}^{v} y_{i k} = 1, \forall i \in C

\sum_{i = 0}^{n} x_{i j k} = y_{j k}, \forall k \in V, \forall j \in C

\sum_{j = 0}^{n} x_{i j k} = y_{j k}, \forall k \in V, \forall i \in C

\sum_{j = 1}^{n} x_{0 j k} - \sum_{i = 1}^{n} x_{i 0 k} = 0, \forall k \in V

s_{i} = 2 t p_{i} \frac{1}{y d_{k}}, \forall i \in C, \forall k \in V

\sum_{i = 0}^{n} \sum_{j = 0}^{n} x_{i j k} (t_{i}_{j} + s_{i} + w_{i}) \leq r_{k}, \forall k \in V

w_{0} = s_{0} = 0

\sum_{k = 1}^{v} \sum_{i = 0}^{n} x_{i j k} (z_{i} + w_{i} + s_{i} + t_{i j}) = z_{j}, \forall j \in C

e_{i} \leq z_{i} + w_{i} \leq l_{i}, \forall i \in C

w_{i} = max {0, e_{i} - z_{i}}, \forall i \in C

x_{i}_{j k} \in {0, 1}, \forall i, j \in C, \forall k \in V

y_{i}_{k} \in {0, 1}, \forall i \in C, \forall k \in V

z_{i} \geq 0, \forall i \in C

The objective (1) aims to minimize the weighted sum of the total energy consumption of the trucks, total energy consumption of the drones, and the total number of trucks. Constraints (2) and (3) ensure the two kinds of truck capacities are not excessed; constraints (4) to (6) guarantee that each customer is visited by only one truck and served only once; constraint (7) safeguards that each truck starts and ends at the depot; constraint (8) sets the serving duration; constraint (9) guarantees the maximal trip distance is not exceeded; constraint (10) indicates the waiting and starting time of depot; constraint (11) gives the connection between the arrival time of a vertex and the departure time of its predecessor; constraints (12) and (13) illuminate that the arrival time should be within the time window and the wait time.

Example of MO-VRPTW-D

Figure 1 displays an example of the proposed problem, which includes seven customers, two trucks and drones, which is conducive to comprehending the dispatching process. Figure 1(a) is the whole delivery routes for all customers, while Figure 1(b) is the situation of dispatching goods to the customer 3. For convenience, we only discuss the delivery process of customer 3 and other conditions are as follows: (1) the route {0, 1, 2, 3, 4, 0} and {0, 5, 6, 7, 0} are executed by the truck 1 and truck 2, respectively; (2) drone 1 is equipped on the truck 1 and the speed of drone 1 is 0.5. It can be acquired from Figure 1 that, when the truck 1 arrival at customer 3, the drone 1 starts to dispatch goods. According to the height of customer 3 is 5 and the dispatching route is a double journey, thus, the total distance of drone 1 is 10. Moreover, on the basis of the speed of drone 1 is 0.5, thus, the trip time of the drone is 10 divided by 0.5 is 20. Furthermore, the serving duration of customer 3 is 20. And Figure 2 explains the more detailed distribution scheme, where each route is built by a truck with a drone and each customer has two types of demands. The bottom of Figure 2 shows a part of the route, in which the main materials and the supplementations of customer 2 are 1 and 3; of customer 4 are 1 and 2; of customer 4 are 1 and 4, respectively.

Figure 1.

The example of MO-VRPTW-D. MO-VRPTW-D: multi-objective vehicle routing problem with time window and drones.

Figure 2.

The illustration of two types of demands and the combination of truck and drone.

Proposed algorithm

The framework of the proposed IABC algorithm is shown in Algorithm 1.

Algorithm 1.

The framework of the IABC.

Encoding and decoding methods

For the problem encoding, this study states each solution as a 2-D array where each array representing the sequence of a set of vertexes, and Figure 3 gives an example of the encoding. In Figure 3, {0, 1, 2, 3, 4, 0} represent a visiting sequence of a truck, where this truck starts at depot then visits customer 1, 2, and so on until it returns to the depot. And {0, 5, 6, 7, 0} is symbolizing another route. Notice that each customer in the constructed route must be selected under the constraints of the MO-VRPTW-D model.

Figure 3.

Example of the problem encoding.

Repair strategy

For each infeasible solution, Algorithm 2 gives the proposed repair strategy and the time complexity is O(n ² m).

Algorithm 2.

Repair strategy.

Initialization strategy

Solomon proposed the Push-Forward Insertion Heuristic (PFIH) for the VRPTW in 1987 and the general process of PFIH is as follow: first, select one of the unscheduled customers who must satisfy all the constraints of VRPTW model if insert it into the current route; then, calculate all the costs of inserting it into each location of the current route; thirdly, insert this customer into current route at the position of minimum costs; fourthly, repeat the above three steps until all customers are arranged.²⁹ In this study, we also embed the PFIH method in the proposed algorithm.

Enhanced employed bee strategy

Algorithm 3 gives an enhanced employed bee strategy of this study. In the traditional employed bee strategy, we select some customers randomly of certain route, then rearrange these customers to other routes. When some customers cannot be inserting into the current route, we could deploy a new truck if there was an empty one. This method is easy to accomplish but hard to receive a better solution. Thus, we propose a novel and effective strategy to obtain better routing schemes, where we expect rearranging a fleet of relevant customers with similar location.⁵⁷ And the time complexity of our strategy is O(n ² m).

Algorithm 3.

Enhanced employed bee strategy.

Scout bee strategy

When the IABC algorithm comes to the scout phase, we expect to make large changes to a solution in order to enhance the fitness and reduce the energy consumptions of these routes. Thus, the scout bee strategy described in Algorithm 4 has two parts. First, we execute a kind of local search method to reinsert some customers of a solution; then, replacing a truck of this solution with another empty one for increasing the probability to reduce the energy consumption of current routes. The steps 6–11 of Algorithm 4 is called the truck replacement strategy and the time complexity of the scout bee phase is O(n ² m).

Algorithm 4.

Scout bee strategy.

Experimental comparisons

In this study, in order to testify the validity of IABC, three relevant and effective algorithms, that is, GA,¹⁹ TS,²⁰ and VNS²⁵ are selected as the comparing algorithm. The “Experimental parameters and instances” subsection describes the parameters and instances setting of the MO-VRPTW-D and other experimental results are expressed in the rest of the fourth section.

Experimental parameters and instances

The two most significant parameters of IABC, that is, are the size of population P_s and the iteration times without improvement L_n . We set four levels for the each parameter in Table 1 and perform a mass of adjustable parameter experiments according to these levels. Accord to the result of design of experiments (DOE) in Figure 4, we set P_s = 100 and L _n = 10, respectively.

Table 1.

The levels of the two parameters.

Parameter	Level 1	Level 2	Level 3	Level 4
P_s	50	100	150	200
L_n	5	10	15	20

Figure 4.

The result of the DOE experiments for P_s and L_n . DOE: design of experiments.

For the instances of this study, we design our instances based on the 55 famous Solomon Benchmark examples of the VRPTW.²⁹ Each Solomon example has 100 customers and the distributions of customers’ location have three levels: random, cluster, and semi-cluster. Each customer in the Solomon examples has a time window, a demand, a severing duration, and a pair of coordinate points. The designed instances have the same customer numbers, locations, and time windows with the Solomon example and the name of our instances are corresponding to the order of Solomon instances. Due to the two kinds of demands constraints, we randomly set the dm_i : ds_i for each customer i from [1:1] to [1:5]. Besides, each customer has an integer height which is generated randomly from 5 to 14. Moreover, the total number of trucks is 25, and each truck has different energy consumption coefficient and two kinds of capacities. And the speed and energy consumption coefficient of drone on each truck is also different.

Effectiveness of the enhanced employed bee strategy

To testify the effectiveness of the proposed employed bee strategy, we perform a detailed experiment. Table 2 illustrates the comparison results of the enhanced employed bee strategy and the canonical employed bee method. In Table 2, the last two columns introduce the deviation of the objective value of each strategy compared with the best value. According to the results in Table 2, the IABC obtains 35 best values while the improved artificial bee colony with a random employed bee strategy without the enhanced employed bee strategy (IABC-NE) only gets 20 best ones, which demonstrate that the proposed employed bee strategy of this study indeed contributes to improving the algorithm performance. Figure 5 exhibits the result of analysis of variance (ANOVA) for the two different methods.

Table 2.

The comparison results of IABC-NE and IABC.

Instance	Deviation
Instance	IABC-NE	IABC
Inst1	0.00	3.65
Inst2	6.25	0.00
Inst3	0.00	4.57
Inst4	0.00	2.75
Inst5	0.00	1.95
Inst6	1.23	0.00
Inst7	2.44	0.00
Inst8	0.00	3.32
Inst9	8.12	0.00
Inst10	0.00	1.46
Inst11	7.31	0.00
Inst12	0.88	0.00
Inst13	11.35	0.00
Inst14	0.00	0.10
Inst15	0.00	2.34
Inst16	5.08	0.00
Inst17	8.51	0.00
Inst18	3.35	0.00
Inst19	2.14	0.00
Inst20	1.05	0.00
Inst21	5.45	0.00
Inst22	0.00	0.92
Inst23	3.45	0.00
Inst24	6.36	0.00
Inst25	0.00	1.28
Inst26	1.52	0.00
Inst27	7.48	0.00
Inst28	0.00	0.15
Inst29	0.18	0.00
Inst30	7.08	0.00
Inst31	0.00	8.35
Inst32	1.04	0.00
Inst33	3.48	0.00
Inst34	2.55	0.00
Inst35	1.33	0.00
Inst36	1.14	0.00
Inst37	0.00	3.03
Inst38	1.21	0.00
Inst39	0.00	1.35
Inst40	0.00	3.23
Inst41	0.44	0.00
Inst42	0.00	2.47
Inst43	0.00	2.88
Inst44	3.29	0.00
Inst45	0.00	1.75
Inst46	0.00	0.63
Inst47	1.99	0.00
Inst48	4.06	0.00
Inst49	3.18	0.00
Inst50	0.00	1.66
Inst51	2.20	0.00
Inst52	5.25	0.00
Inst53	1.36	0.00
Inst54	2.52	0.00
Inst55	2.31	0.00
Mean	2.30	0.87

IABC: improved artificial bee colony.

IABC-NE: improved artificial bee colony with a random employed bee strategy without the enhanced employed bee strategy.

Figure 5.

The ANOVA comparisons of IABC-NE and IABC. ANOVA: analysis of variance; IABC: improved artificial bee colony.

Effectiveness of the scout bee strategy

To investigate the performance of the proposed truck replacement strategy in the scout bee method, we also made a detailed comparison of the scout bee strategy. The results are revealed in Table 3, where IABC-NS represents the IABC without the scout bee strategy. It can be concluded from Table 3 that: (1) IABC obtains 37 best values while IABC-NS only obtains 18 optimal solutions; (2) the deviation values from the last two columns also show the superiority of the proposed scout bee strategy; and (3) the average performance given in the last line verify the average performance of the proposed method. The ANOVA comparison of the two methods given in Figure 6 also verifies that the proposed scout bee strategy improved the performance significantly.

Table 3.

The results of the IABC-NS and IABC.

Instance	Deviation
Instance	IABC-NS	IABC
Inst1	0.29	0.00
Inst2	10.22	0.00
Inst3	0.53	0.00
Inst4	0.00	2.32
Inst5	2.20	0.00
Inst6	0.25	0.00
Inst7	0.00	2.42
Inst8	2.16	0.00
Inst9	1.54	0.00
Inst10	0.00	4.34
Inst11	0.00	5.79
Inst12	6.98	0.00
Inst13	17.64	0.00
Inst14	0.00	5.00
Inst15	0.00	1.02
Inst16	0.00	2.99
Inst17	14.80	0.00
Inst18	0.68	0.00
Inst19	0.56	0.00
Inst20	0.10	0.00
Inst21	5.46	0.00
Inst22	6.08	0.00
Inst23	3.87	0.00
Inst24	0.00	2.25
Inst25	0.06	0.00
Inst26	1.21	0.00
Inst27	2.84	0.00
Inst28	0.00	0.78
Inst29	1.07	0.00
Inst30	0.68	0.00
Inst31	0.00	0.85
Inst32	1.69	0.00
Inst33	4.78	0.00
Inst34	0.00	0.19
Inst35	0.90	0.00
Inst36	0.00	10.45
Inst37	0.00	4.10
Inst38	3.46	0.00
Inst39	0.00	3.79
Inst40	5.51	0.00
Inst41	0.00	1.32
Inst42	1.78	0.00
Inst43	3.16	0.00
Inst44	2.95	0.00
Inst45	2.64	0.00
Inst46	1.59	0.00
Inst47	2.33	0.00
Inst48	3.04	0.00
Inst49	0.77	0.00
Inst50	2.17	0.00
Inst51	0.00	2.20
Inst52	0.00	7.47
Inst53	6.72	0.00
Inst54	9.65	0.00
Inst55	0.00	2.62
Mean	2.41	1.09

IABC: improved artificial bee colony.

Figure 6.

The ANOVA of the IABC-NE and IABC. ANOVA: analysis of variance; IABC: improved artificial bee colony.

Comparison of several efficient algorithms

To further attest the powerful performance of the IABC, we compare the proposed algorithm with GA,¹⁹ TS,²⁰ and VNS.²⁵ These three selected algorithms are efficient for solving the VRPTW. The comparison results are given in Table 4, where the three columns from 3 to 6 correspond to the results obtained by GA, TS, VNS, and IABC, respectively. The best values of these four algorithms are shown in the second column. The deviations between each algorithm and the best values are present in the last four columns. Obviously, IABC gains 38 best values which account for about 70% of the 55 instances. The mean of deviation of IABC is only 0.42 which less than 5% of the second best result. Thus, in terms of the effectiveness and stability of the algorithm, the IABC is superior to the other three algorithms. Figure 7 gives the ANOVA among these four algorithms, which demonstrate that the IABC is significantly better than the three compared algorithms.

Table 4.

The results of comparing with GA, TS, and VNS.

Instance	Best	Algorithm				Deviation
Instance	Best	GA	TS	VNS	IABC	GA	TS	VNS	IABC
Inst1	1038.78	1571.34	1306.84	1351.27	1038.78	51.27	25.81	30.08	0.00
Inst2	1001.63	1275.01	1163.90	1125.35	1001.63	27.29	16.20	12.35	0.00
Inst3	950.11	1134.35	950.11	980.92	966.26	19.39	0.00	3.24	1.70
Inst4	956.58	1217.11	981.48	1011.20	956.58	27.24	2.60	5.71	0.00
Inst5	1010.41	1313.63	1108.59	1112.75	1010.41	30.01	9.72	10.13	0.00
Inst6	1018.00	1443.83	1175.09	1220.65	1018.00	41.83	15.43	19.91	0.00
Inst7	993.27	1246.36	1116.44	1151.58	993.27	25.48	12.40	15.94	0.00
Inst8	898.22	1244.89	908.67	968.04	898.22	38.60	1.16	7.77	0.00
Inst9	891.91	1152.61	975.02	946.11	891.91	29.23	9.32	6.08	0.00
Inst10	401.30	927.18	783.94	747.19	401.30	131.05	95.35	86.19	0.00
Inst11	519.29	802.33	733.91	801.66	519.29	54.51	41.33	54.38	0.00
Inst12	525.56	779.52	657.00	661.34	525.56	48.32	25.01	25.83	0.00
Inst13	518.87	751.77	591.87	600.71	518.87	44.89	14.07	15.77	0.00
Inst14	503.33	932.10	811.10	791.39	503.33	85.19	61.15	57.23	0.00
Inst15	464.63	796.87	680.49	707.22	464.63	71.51	46.46	52.21	0.00
Inst16	558.53	839.41	664.32	714.66	558.53	50.29	18.94	27.95	0.00
Inst17	499.76	680.18	499.76	513.54	509.22	36.10	0.00	2.76	1.89
Inst18	1578.94	1643.01	1585.90	1578.94	1599.14	4.06	0.44	0.00	1.28
Inst19	1355.03	1461.51	1355.03	1390.12	1355.08	7.86	0.00	2.59	0.00
Inst20	1063.10	1151.01	1064.14	1082.83	1063.10	8.27	0.10	1.86	0.00
Inst21	797.18	895.03	813.34	818.38	797.18	12.27	2.03	2.66	0.00
Inst22	1117.63	1185.05	1142.73	1117.63	1135.03	6.03	2.25	0.00	1.56
Inst23	981.92	1062.77	981.92	1002.99	999.78	8.23	0.00	2.15	1.82
Inst24	832.25	887.26	870.08	892.30	832.25	6.61	4.55	7.22	0.00
Inst25	687.64	769.06	687.64	730.08	694.18	11.84	0.00	6.17	0.95
Inst26	955.97	1038.45	965.79	971.37	955.97	8.63	1.03	1.61	0.00
Inst27	824.02	881.13	860.44	858.06	824.02	6.93	4.42	4.13	0.00
Inst28	807.97	909.46	844.24	830.10	807.97	12.56	4.49	2.74	0.00
Inst29	692.69	746.96	696.30	698.55	692.69	7.84	0.52	0.85	0.00
Inst30	844.25	899.89	887.98	911.36	844.25	6.59	5.18	7.95	0.00
Inst31	746.70	780.15	753.14	746.70	748.66	4.48	0.86	0.00	0.26
Inst32	634.32	699.21	647.16	639.32	634.32	10.23	2.02	0.79	0.00
Inst33	432.21	449.42	447.22	446.69	432.21	3.98	3.47	3.35	0.00
Inst34	561.85	575.88	561.85	567.96	565.48	2.50	0.00	1.09	0.65
Inst35	460.63	501.04	460.63	476.30	465.17	8.77	0.00	3.40	0.98
Inst36	435.31	485.19	463.62	450.79	435.31	11.46	6.50	3.56	0.00
Inst37	351.92	358.75	351.92	355.68	352.98	1.94	0.00	1.07	0.30
Inst38	527.66	544.00	542.80	527.66	536.13	3.10	2.87	0.00	1.61
Inst39	538.09	615.62	538.09	553.50	541.62	14.41	0.00	2.86	0.65
Inst40	428.06	479.07	462.60	462.27	428.06	11.92	8.07	7.99	0.00
Inst41	1324.72	1401.42	1324.97	1349.98	1324.72	5.79	0.02	1.91	0.00
Inst42	1087.30	1231.29	1158.80	1169.08	1087.30	13.24	6.58	7.52	0.00
Inst43	936.53	1000.98	937.17	974.72	936.53	6.88	0.07	4.08	0.00
Inst44	878.78	933.55	887.90	878.78	903.21	6.23	1.04	0.00	2.78
Inst45	1269.41	1417.76	1290.85	1303.18	1269.41	11.69	1.69	2.66	0.00
Inst46	987.55	1040.40	998.61	987.55	1016.75	5.35	1.12	0.00	2.96
Inst47	939.38	1000.64	952.59	952.25	939.38	6.52	1.41	1.37	0.00
Inst48	876.64	937.55	891.03	919.59	876.64	6.95	1.64	4.90	0.00
Inst49	855.66	899.20	864.75	873.83	855.66	5.09	1.06	2.12	0.00
Inst50	731.28	811.90	756.29	780.86	731.28	11.02	3.42	6.78	0.00
Inst51	544.70	627.43	564.02	569.84	544.70	15.19	3.55	4.62	0.00
Inst52	479.69	511.90	485.82	479.69	483.92	6.72	1.28	0.00	0.88
Inst53	826.79	912.19	844.77	826.79	842.60	10.33	2.17	0.00	1.91
Inst54	626.18	658.18	627.59	626.18	631.60	5.11	0.23	0.00	0.87
Inst55	565.48	707.02	589.38	688.58	565.48	25.03	4.23	21.77	0.00
Mean	787.92	931.25	841.23	852.65	791.37	20.61	8.60	10.10	0.42

GA: genetic algorithm; TS: tabu search; VNS: variable neighborhood search; IABC: improved artificial bee colony.

Figure 7.

The result of comparing the IABC, GA, TS, and VNS. GA: genetic algorithm; TS: tabu search; VNS: variable neighborhood search; IABC: improved artificial bee colony.

Conclusion

This article proposes a novel VRPTW for the special customers must be served by trucks and drones. Based on the problem features, the mathematic model of MO-VRPTW-D is designed and solved by the presented IABC Figure 8. However, there still have many challenges between the model and the practical applications. For trucks and drones, we usually deem the motion states of these as a linear process but the speeds are nonlinear in reality. The route also may be impacted by the emergency and weather. As a result, our future work will be devoted to following works: (1) refer to He et al.,^58,59 and extend the model from a static scenario to a dynamic scenario; and (2) considering the fuzzy features of the realistic system,^60,61 and explore the new mode of combining drone with vehicle under uncertain environments.

Figure 8.

The convergence curves of instances. (a) Convergence curve for Inst 1. (b) Convergence curve for Inst 10. (c) Convergence curve for Inst 16. (d) Convergence curve for Inst 25. (e) Convergence curve for Inst 33. (f) Convergence curve for Inst 40. (g) Convergence curve for Inst 48. (h) Convergence curve for Inst 55.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This study is partially supported by National Science Foundation of China under Grants 61773192, 61803192, and 61773246, Shandong Province Higher Educational Science and Technology Program (J17KZ005), special fund plan for local science and technology development lead by central authority, major basic research projects in Shandong (ZR2018ZB0419), and a Grant of Key Laboratory of Intelligent Optimization and Control with Big Data.

ORCID iD

Jun-qing Li

References

Kusiak

. Smart manufacturing. Int J Prod Res 2018; 56(1–2): 508–517.

Shao

Wang

, et al. Product environmental footprints assessment for product life cycle. J Clean Prod 2019; 233(10): 446–460.

Liu

Zeng

, et al. Product carbon footprint across sustainable supply chain. J Clean Prod 2019; 241: 118320.

Wang

Liu

. Underactuated robotics: a review. Int J Adv Robot Syst 2019; 16(4): 1729881419862164.

Floreano

Wood

. Science, technology and the future of small autonomous drones. Nature 2015; 521(7553): 460–466.

Yurek

Ozmutlu

. A decomposition-based iterative optimization algorithm for traveling salesman problem with drone. Transp Res Part C Emerg Technol 2018; 91: 249–262.

Otto

Agatz

Campbell

, et al. Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: a survey. Networks 2018; 72(4): 411–458.

Murray

Chu

AG.

The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery. Transp Res Part C Emerg Technol 2015; 54: 86–109.

Dorling

Heinrichs

Messier

, et al. Vehicle routing problems for drone delivery. IEEE Trans Syst Man Cybern Syst 2016; 47(1): 70–85.

10.

Wang

Poikonen

Golden

. The vehicle routing problem with drones: several worst-case results. Optim Lett 2017; 11(4): 679–697.

11.

Agatz

Bouman

Schmidt

. Optimization approaches for the traveling salesman problem with drone. Transp Sci 2018; 52(4): 965–981.

12.

Karak

Abdelghany

. The hybrid vehicle-drone routing problem for pick-up and delivery services. Transp Res Part C Emerg Technol 2019; 102: 427–449.

13.

Dantzig

Ramser

. The truck dispatching problem. Manag Sci 1959; 6(1): 80–91.

14.

Eksioglu

Vural

Reisman

. The vehicle routing problem: a taxonomic review. Comput Ind Eng 2009; 57(4): 1472–1483.

15.

Pillac

Gendreau

Guéret

, et al. A review of dynamic vehicle routing problems. Eur J Oper Res 2013; 225(1): 1–11.

16.

Braekers

Ramaekers

Van Nieuwenhuyse

. The vehicle routing problem: state of the art classification and review. Comput Ind Eng 2016; 99: 300–313.

17.

Wang

Sheu

. Vehicle routing problem with drones. Transp Res Part B Methodol 2019; 122: 350–364.

18.

Yurek

Ozmutlu

. A decomposition-based iterative optimization algorithm for traveling salesman problem with drone. Transp Res Part C Emerg Technol 2018; 91: 249–262.

19.

Ghoseiri

Ghannadpour

. Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm. Appl Soft Comput 2010; 10(4): 1096–1107.

20.

Cordeau

Maischberger

. A parallel iterated tabu search heuristic for vehicle routing problems. Comput Oper Res 2012; 39(9): 2033–2050.

21.

Belhaiza

Hansen

Laporte

. A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows. Comput Oper Res 2014; 52: 269–281.

22.

Zulvia

Kuo

Nugroho

. A many-objective gradient evolution algorithm for solving a green vehicle routing problem with time windows and time dependency for perishable products. J Clean Prod 2019; 242: 118428.

23.

Goksal

Karaoglan

Altiparmak

. A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Comput Oper Res 2013; 65(1): 39–53.

24.

Yang

ZZ.

An ant colony optimization model: the period vehicle routing problem with time windows. Transp Res Part E Logist Transp Rev 2011; 47(2): 166–181.

25.

Ribeiro

Laporte

. An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Comput Oper Res 2012; 39(3): 728–735.

26.

Mousavi

Tavakkoli-Moghaddam

. A hybrid simulated annealing algorithm for location and routing scheduling problems with cross-docking in the supply chain. J Manuf Syst 2013; 32(2): 335–347.

27.

Chang

Lee

. Optimal delivery routing with wider drone-delivery areas along a shorter truck-route. Expert Syst Appl 2018; 104: 307–317.

28.

Guerriero

Surace

Loscri

, et al. A multi-objective approach for unmanned aerial vehicle routing problem with soft time windows constraints. Appl Math Model 2014; 38(3): 839–852.

29.

Solomon

. Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 1987; 35(2): 254–265.

30.

Phan

Suzuki

. Evolutionary multiobjective optimization for the pickup and delivery problem with time windows and demands. Mobile Netw Appl 2016; 21(1): 175–190.

31.

Chowdhury

Emelogu

Marufuzzaman

, et al. Drones for disaster response and relief operations: a continuous approximation model. Int J Prod Econ 2017; 188: 167–184.

32.

Rabta

Wankmüller

Reiner

. A drone fleet model for last-mile distribution in disaster relief operations. Int J Disaster Risk Reduct 2018; 28: 107–112.

33.

Karaboga

Basturk

. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Glob Optim 2007; 39(3): 459–471.

34.

Karaboga

Akay

. A comparative study of artificial bee colony algorithm. Appl Math Comput 2009; 214(1): 108–132.

35.

Tian

Ren

Feng

, et al. Modeling and planning for dual-objective selective disassembly using AND/OR graph and discrete artificial bee colony. IEEE Trans Ind Inform 2018; 15(4): 2456–2468.

36.

Pan

Tasgetiren

. A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities. Appl Math Model 2014; 38(3): 1111–1132.

37.

Sun

. Flexible job shop green scheduling with an energy-saving measure. J Clean Prod 2018; 172: 3249–3264.

38.

Liu

, et al. A path planning approach for crowd evacuation in buildings based on improved artificial bee colony algorithm. Appl Soft Comput 2018; 68: 360–376.

39.

Song

Wang

, et al. Hybrid artificial bee colony algorithm for a parallel batching distributed flow shop problem with deteriorating jobs. IEEE Trans Cybern 2019: 1–15.

40.

Bai

Duan

, et al. An improved artificial bee colony algorithm for addressing distributed flow shop with distance coefficient in a prefabricated system. Int J Prod Res 2019; 57(22): 6922–6942.

41.

Han

Gong

Sun

. A discrete artificial bee colony algorithm incorporating differential evolution for flow shop scheduling problem with blocking. Eng Optim 2015; 47(7): 927–946.

42.

Han

Duan

, et al. Meta-heuristic algorithm for solving vehicle routing problems with time windows and synchronized visit constraints in prefabricated systems. J Clean Prod 2019; 250: 119464.

43.

Tai

Liu

, et al. An improved artificial bee colony algorithm for vehicle routing problem with time windows: a real case in Dalian. Adv Mech Eng 2016; 8(8): 1687814016665298.

44.

Gao

Suganthan

Pan

, et al. Artificial bee colony algorithm for scheduling and rescheduling fuzzy flexible job shop problem with new job insertion. Knowl-Based Syst 2016; 109: 1–16.

45.

Han

. A hybrid multi-objective artificial bee colony algorithm for flexible task scheduling problems in cloud computing system. Clust Comput 2019; 1–17.

46.

Gao

Yang

Zhou

, et al. Flexible job-shop rescheduling for new job insertion by using discrete Jaya algorithm. IEEE Trans Cybern 2018; 49(5): 1944–1955.

47.

Zheng

Han

. An improved invasive weed optimization algorithm for solving dynamic economic dispatch problems with valve-point effects. J Exp Theor Artif Intell 2019; 1–25.

48.

Shen

, et al. Ensemble of differential evolution variants. Inf Sci 2018; 423: 172–186.

49.

Wang

Gandomi

Zhao

, et al. Hybridizing harmony search algorithm with cuckoo search for global numerical optimization. Soft Comput 2016; 20(1): 273–285.

50.

Pan

Sheng

. An effective shuffled frog-leaping algorithm for multi-objective flexible job shop scheduling problems. Appl Math Comput 2012; 218(18): 9353–9371.

51.

Wang

. Moth search algorithm: a bio-inspired metaheuristic algorithm for global optimization problems. Memetic Comput 2018; 10(2): 151–164.

52.

Wang

Deb

Gandomi

, et al. Opposition-based krill herd algorithm with Cauchy mutation and position clamping. Neurocomputing 2016; 177: 147–157.

53.

Pan

Liang

. An effective hybrid tabu search algorithm for multi-objective flexible job shop scheduling problems. Comput Ind Eng 2010; 59(4): 647–662.

54.

Zhao

. A perturbed particle swarm algorithm for numerical optimization. Appl Soft Comput 2010; 10(1): 119–124.

55.

Tao

Jia

, et al. Efficient multi-objective algorithm for the lot-streaming hybrid flowshop with variable sub-lots. Swarm Evol Comput 2020; 52: 100600, doi:10.1016/j.swevo.2019.100600.

56.

Sun

Miao

Gong

, et al. Interval multiobjective optimization with memetic algorithms. IEEE Trans Cybern 2020; 1–14. https://doi.org/10.1109/TCYB.2019.2908485.

57.

Ropke

Pisinger

. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 2006; 40(4): 455–472.

58.

Huang

Wang

. Product low-carbon design using dynamic programming algorithm. Int J Precis Eng Manuf Green Technol 2015; 2(1): 37–42.

59.

Zhang

Wang

. Automated synthesis of mechanisms with consideration of mechanical efficiency. J Eng Design 2014; 25(4-6): 213–237.

60.

Wang

, et al. Interval data driven construction of shadowed sets with application to linguistic word modelling. Inf Sci 2020; 507: 503–521.

61.

Pan

. Solving fuzzy job-shop scheduling problems by a hybrid optimization algorithm. Journal of Mechanical Engineering 2013; 49(23): 142–149.

Metaheuristic algorithm for solving the multi-objective vehicle routing problem with time window and drones

Abstract

Keywords

Introduction

Problem statement and MO-VRPTW-D model

Problem description

MO-VRPTW-D model

Example of MO-VRPTW-D

Proposed algorithm

Encoding and decoding methods

Repair strategy

Initialization strategy

Enhanced employed bee strategy

Scout bee strategy

Experimental comparisons

Experimental parameters and instances

Effectiveness of the enhanced employed bee strategy

Effectiveness of the scout bee strategy

Comparison of several efficient algorithms

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References