An improved artificial bee colony algorithm for vehicle routing problem with time windows: A real case in Dalian

Abstract

This study has been motivated from a real western-style food delivery problem in Dalian city, China, which can be described as a vehicle routing problem with time windows. An integer linear model for the problem is developed, and an improved artificial bee colony algorithm, which possesses a new strategy called an adaptive strategy, a crossover operation, and a mutation operation, is proposed to solve the problem. Then, the effectiveness of the proposed improved artificial bee colony is first validated by some benchmark instances. Furthermore, results obtained on a real-case instance for western-style food delivery problem in Dalian city are also discussed. In this case, the results indicate that the improved artificial bee colony algorithm is a feasible method to solve the real vehicle routing problem with time windows such as western-style food delivery.

Introduction

In real life, some types of transport have a strict time limit, with which not only the vehicle capacity but also the time requirement should be considered when planning the trips for the carriers. The problem is defined as the vehicle routing problem (VRP) with time windows (VRPTW), and “time windows” is referred to strict time limit. Because of time windows, VRPTW is more complicated compared with conventional VRP and is one of the most significant branches of VRPs.

This study has been motivated from a real western-style food delivery problem in Dalian city, China. And the requirements for the freshness of the food make the delivery time very strict.^1–3 Thus, the western-style food delivery routing problem is thought as a VRPTW based on real-life route network. The objective of the VRPTW is to find a minimum cost routes for serving all the customers during their given intervals.^4–8

VRPTW is also proved to be NP-hard problem. Heuristic algorithms are the first choice to solve this combinational problem.^7–16 Chiang and Russell ¹⁷ proposed a simulated annealing metaheuristic for solving the VRPTW. Tan et al. ¹⁸ presented a hybrid genetic algorithms (GAs) to solve the VRPs with time window constraints. Ho and Haugland ¹⁹ tried to use a tabu search heuristic for solving the VRPTW and split deliveries. Furthermore, due to the complexity of real-life route network, for example, one-way road, the transportation cost is different with different routes between two points. Thus, a western-style food delivery routing problem is more complex than a classical VRPTW. Therefore, this article attempts to find an effective method to solve the western-style food delivery routing problem.

While many heuristics have been widely used and successfully applied to solve the VRPTW for several years, artificial bee colony (ABC) algorithm is a fairly new approach introduced just a few years ago by Karaboga ²⁰ and has been applied to solve some complicated problems. Özbakir et al. ²¹ presented an ABC algorithm to solve generalized assignment problems with an ejection chain neighborhood mechanism. Koudil et al. ²² attempted to use ABC algorithm to solve integrated partitioning or scheduling problem in codesign. Karaboga et al. ²³ proposed a modified ABC algorithm to determine the parameters of the Schottky barrier diode. Cuevas et al. ²⁴ developed an ABC algorithm to solve image segmentation problem by computing threshold selection. Yao et al. ²⁵ used an ABC algorithm to solve the periodic VRP. It is worthwhile to evaluate the ability in applying ABC algorithm to solve the VRPTW. Therefore, these successful applications motivate us to apply ABC algorithm to look for the optimum routes for VRPTW in this article.

The ABC algorithm is a popular optimization algorithm but often easily trapped in local optima before finding the global optimum. Thus, it is necessary to expand the solution space of this algorithm and, equivalently, to expand the diversity of its search information. Many methods have been proposed to improve the performance of the original ABC algorithm. Zhang et al. ²⁶ proposed a hybrid ABC algorithm to solve the job shop scheduling problem. In this article, the authors introduced a tree search algorithm to improve the performance of ABC algorithm. Wang et al. ²⁷ proposed a modified ABC algorithm for solving the order acceptance problem in two-machine flow shops. Yildiz ²⁸ used a new hybrid ABC algorithm for designing a vehicle component and a multi-tool milling optimization problem. Inspired by the GA, in this article, the crossover and mutation operation of GA are introduced to increase the diversity of food sources and speed up the convergence of the ABC algorithm. Finally, in the numerical analysis, the new algorithm effectively accelerated the convergence speed and improved the solutions to VRPTW, relative to original ABC.

The remainder of this article is organized as follows: In section “Mathematical formulations,” we construct a mathematic model for the western-style food delivery problem which is defined as a VRPTW. Section “Improved ABC algorithm” presents the ABC algorithm and some improvement strategies. In section “Numerical examples,” some computational results are discussed, and finally, the conclusions are provided in section “Conclusion.”

Mathematical formulations

The real-life VRPTW in our article is formulated as an integer programming model. And the objective is looking for the least cost while meeting the following constraints: the service time constraint and the vehicle capacity constraint. In addition, one node must be served only once by exactly one vehicle, and all vehicles should start and end at the depot. The total demand of all nodes on one particular route cannot exceed the capacity of the vehicle. Therefore, the formulation can be described as follows

$$\mathrm{Min}\sum _{i=0}^N\sum _{j=0j\ne i}^N\sum _{k=1}^K{c}_{\mathrm{ij}}{x}_{\mathrm{ijk}}$$

(1)

$$s.t.\{\begin{array}{cc}\hfill \sum _{k=1}^K\sum _{j=1}^N{x}_{\mathrm{ijk}}\le K\hfill & \hfill \mathrm{for}i=0(\mathrm{a})\hfill \\ \multicolumn{1}{c}{\sum _{j=1}^N{x}_{\mathrm{ijk}}=\sum _{j=1}^N{x}_{\mathrm{jik}}\le 1}& \hfill \mathrm{for}i=0k\in \{1,\dots ,K\}(\mathrm{b})\hfill \\ \multicolumn{1}{c}{\sum _{k=1}^K\sum _{j=0,j\ne i}^N{x}_{\mathrm{ijk}}=1}& \hfill \mathrm{for}i\in \{1,\dots ,N\}(\mathrm{c})\hfill \\ \multicolumn{1}{c}{\sum _{k=1}^K\sum _{i=0,i\ne j}^N{x}_{\mathrm{ijk}}=1}& \hfill \mathrm{for}j\in \{1,\dots ,N\}(\mathrm{d})\hfill \\ \multicolumn{1}{c}{\sum _{i=1}^N{q}_i\sum _{j=0,j\ne i}^N{x}_{\mathrm{ijk}}\le Q}& \hfill \mathrm{for}k\in \{1,\dots ,K\}(\mathrm{e})\hfill \\ \multicolumn{1}{c}{\sum _{i=1}^N\sum _{j=0,j\ne i}^N{x}_{\mathrm{ijk}}(t_{\mathrm{ij}}+s_i+w_i)\le T_k}& \hfill \mathrm{for}k\in \{1,\dots ,K\}(\mathrm{f})\hfill \\ \multicolumn{1}{c}{t_0=w_0=s_0=0}& \hfill (\mathrm{g})\hfill \\ \multicolumn{1}{c}{\sum _{k=1}^K\sum _{i=0,i\ne j}^N{x}_{\mathrm{ijk}}=x_{\mathrm{ijk}}(t_i+t_{\mathrm{ij}}+s_i+w_i)\le t_j}& \hfill \mathrm{for}j\in \{1,\dots ,N\}(\mathrm{h})\hfill \\ \multicolumn{1}{c}{e_i\le (t_i+w_i)\le u_i}& \hfill \mathrm{for}i\in \{1,\dots ,N\}(\mathrm{i})\hfill \end{array}$$

where $x_{\mathrm{ijk}}=\{\begin{array}{cc}\hfill 1\hfill & \hfill \mathrm{the\; link\; from\; customers}i\mathrm{to}j\mathrm{is\; visited\; by\; vehicle}k\hfill \\ \multicolumn{1}{c}{0}& \hfill \mathrm{otherwise}\hfill \end{array}$ .

The parameters in the model are defined as follows: t_i is the time that vehicle k arrives at node i, w_i is the wait time at node i, K is the total number of vehicles, N is the sum of notes (the nodes and the depot), c_ij is the distance between nodes i and j, t_ij is the travel time from nodes i to j, q_i is the requirements of node i, Q is the capacity of a vehicle, e_i is the earliest service time at node i, u_i is the latest service time at node i, s_i is the service time at node i, and T_k is the longest time allowed for vehicle k.

In the above model, equation (1) is the optimum cost model for the VRP. Constraint (a) ensures the number of vehicles cannot exceed the maximum number. Constraint (b) makes sure every vehicle starts and ends the depot. Constraints (c) and (d) assume that each node can be served exactly once by one vehicle. Constraint (e) assumes the quantity of the food in a vehicle cannot exceed its capacity. Constraint (f) guarantees that the drive time of a vehicle in the maximum time constraint. Constraints (g)–(i) assure that each service process must be within the time constraint of each node.

The improved ABC algorithm

The principle of ABC

ABC algorithm is a heuristic which simulates the process of bees looking for the honey (food source). ¹³ ABC algorithm is a bio-mimetic cluster algorithm based on the following principles. First, the bee population is classified into three categories: scouts, leaders, and onlookers. Scouts are the bees which are responsible for looking for new food sources randomly. Leaders with elite features play a role of keeping good food sources. Onlookers will select which food source to follow. When onlookers turn into the following bees, it will increase the number of bees corresponding to better food sources which will speed up the convergence of the algorithm. Based on the intelligent behavior of bees in looking for food sources, ABC algorithm has the ability to look for the feasible routes.

In ABC algorithm, each food source position represents a possible solution of the optimization problem. The amount of honey in each food source corresponds to the fitness of each solution. First, the ABC algorithm will produce SN original solutions randomly. Each solution x_i (i = 1, 2, …, SN) is a D-dimensional vector, and D is the number of the optimization parameters. Then, the leaders conduct a neighborhood search on the corresponding food source. In order to produce a candidate food position from the old one in memory, the ABC uses the following expression

$$v_i=x_i+{\Phi }_i(x_i-x_k)$$

(2)

among them, 1 ≤ i ≤ SN; Φ _i is a parameter which is named as the search factor, and it is a random number within the range of [−1, 1]; it controls the appearance of new solutions in the x_i field and represents the comparison of the locations of two visible nectar sources for the bees. After each search, every leader attains the fitness of a new food source. The value of the fitness for each food source is based on the following expression

$$f_i=\frac{1}{d_i}$$

(3)

where d_i is the total path length of nectar source i.

According to the computing results, if new f_i > f_i, then the old food sources will be abandoned, and the new ones will be chosen to enter the next iteration; if new f_i < f_i, the old ones will be reserved. From formula (2), it can be seen that the disturbance to the locations becomes smaller and smaller with the decreasing distance between x_i and x_k.

When all the leaders have finished their searching and returned to the hive, they shared the information of the food sources with onlookers. The higher the fitness value of a food source, the higher the probability that the food source will be chosen by onlookers. And the probability p_i of selecting a food source i is determined by the following expression

$$p_i=\frac{f_i}{\sum _{n=1}^{\mathrm{SN}}{f}_n}$$

(4)

Furthermore, if nectar source x_i cannot be improved under a limited cycle index, which is defined as a maximum cycle number (MCN), then this location will be given up. A new location will replace the old one by the following formula

$$x_i=x_{min}+\mathrm{rand}(0,1)(x_{max}-x_{min})$$

(5)

In the classical ABC algorithm, the new food source is produced using a perturbation which comes from a randomly chosen bee. However, there are two weaknesses existing in this way. One is that the information exchanged is limited causing the converge speed to be quite slow. The other is that the food sources with high fitness are not utilized.

Improved strategies

In the ABC algorithm, each alternative solution known as food sources and the process of ABC algorithm is looking for the optimal solution. The fitness of the food sources will directly affect the optimization goal of the algorithm. Therefore, to improve the performance of the ABC algorithm, it is important to acquire more feasible solutions during the searching process. Inspired by the idea of crossover and mutation operation in GA, the fitness of solutions can be improved to be more suitable for the problem using the two genetic operations. That is, first, the food source can be put in order based on the information of the food source. Then, a new generation of food source can be acquired by the two genetic operations. Therefore, crossover operation and mutation operation are used to increase the diversity of food sources and speed up the convergence of the ABC algorithm in this article.

Crossover operation

Crossover operation is a reproduction operation in GA, which combines two parents to produce a new offspring at a predefined probability. ⁶ The idea of crossover operation is the new offspring may be better than both the parents. The operation can help ABC to reach further solution in the search space. In this article, the crossover operation is applied to generate new better food source. Therefore, the child population whose generation is similar to the natural evolution will be more adaptive than the former generation to find the global optimal solution of the problem.

Different crossover method can be used in this operator. In this article, an arithmetic crossover ²⁹ is used to create a new offspring. For example, two initial chromosomes, I and II, are (75, 150, 375) and (80, 120, 400), respectively. Suppose the three random numbers are ${\alpha }_1=0.2$ , ${\alpha }_2=0.4$ , and ${\alpha }_3=0.6$ . After the first crossover, ${\mathrm{gen}}_{1,I}^1=0.2\times 75+(1-0.2)\times 80=79$ and ${\mathrm{gen}}_{1,\mathrm{II}}^1=0.2\times 80+(1-0.2)\times 75=76$ .

Similarly, ${\mathrm{gen}}_{2,I}^1=132$ , ${\mathrm{gen}}_{2,\mathrm{II}}^1=138$ , ${\mathrm{gen}}_{3,I}^1=375$ , and ${\mathrm{gen}}_{3,\mathrm{II}}^1=400$

$$\begin{array}{c}{\mathrm{gen}}_{k,I}^t={\alpha }_k{\mathrm{gen}}_{k,I}^{t-1}+(1-{\alpha }_k){\mathrm{gen}}_{k,\mathrm{II}}^{t-1}\hfill \\ {\mathrm{gen}}_{k,\mathrm{II}}^t={\alpha }_k{\mathrm{gen}}_{k,\mathrm{II}}^{t-1}+(1-{\alpha }_k){\mathrm{gen}}_{k,I}^{t-1}\hfill \end{array}$$

(6)

where ${\mathrm{gen}}_{k,I}^{t-1},{\mathrm{gen}}_{k,\mathrm{II}}^{t-1}$ is a pair of “parent” chromosomes; ${\mathrm{gen}}_{k,I}^t,{\mathrm{gen}}_{k,\mathrm{II}}^t$ is a pair of “children” chromosomes; ${\alpha }_k$ is a random number between (0, 1); and $k\in [1,2,3]$ (k is the total genes for the crossover operation).

Mutation operation

Mutation operation is also a genetic operator in GA, which is used to maintain genetic diversity from one generation of a population to the next generation. In mutation operation, the solution may change entirely from the previous solution. Hence, mutation operation is applied to large diversity of the food source in ABC during evolution. The mutation operation is described by the following equation. ²⁹

Assume a chromosome is $G=({\mathrm{gen}}_1^{t-1},{\mathrm{gen}}_2^{t-1},{\mathrm{gen}}_3^{t-1})$ , if the ${\mathrm{gen}}_2^{t-1}$ was selected for the mutation, the mutation can be shown in equation (7)

$$\begin{array}{c}G\prime =({\mathrm{gen}}_1^{t-1},{\mathrm{gen}}_2^t,{\mathrm{gen}}_3^{t-1})\hfill \\ {\mathrm{gen}}_2^t=\{\begin{array}{c}\hfill {\mathrm{gen}}_2^{t-1}+\Delta (t,{\mathrm{gen}}_{2max}^t-{\mathrm{gen}}_2^{t-1})\begin{array}{c}\hfill \mathrm{if}\mathrm{random}(0,1)=0\hfill \end{array}\hfill \\ \multicolumn{1}{c}{{\mathrm{gen}}_2^{t-1}+\Delta (t,{\mathrm{gen}}_2^{t-1}-{\mathrm{gen}}_{2min}^t)\begin{array}{c}\hfill \mathrm{if}\mathrm{random}(0,1)=1\hfill \end{array}}\end{array}\hfill \end{array}$$

(7)

The function $\Delta (t,y)$ returns a value between [0, y] given in equation (8)

$$\Delta (t,y)=y\times (1-{r^{(1-t/T_{\max })}}^{\lambda })$$

(8)

where $r$ is a random number between [0, 1], $T_{max}$ is the maximum number of generations, and here, λ = 3.This property causes this operation to make a uniform search in the initial space when $t$ is small, and a very local one in later stages.

Since the mutation operation may violate the constraints of the parameters, there are two ways to handle this problem. One is to assign a relatively high weight to reduce the probability of being selected in the following search. The other is the solution can be remained, but the value needs to be adjusted to the constraints. The advantage of the second way is that it can maintain the solution which may enable the algorithm to investigate further points in the search space. Therefore, the second approach is adopted to deal with the chromosome which violates the constraints of parameters. The chromosome will be reassigned a value by random which meets the constraints of parameters.

In this article, the crossover operation and the mutation operation are introduced into the original ABC algorithm to improve its optimizing ability. The algorithm process is the same as the original ABC except the crossover phase and mutation phase are added between the onlooker bees’ and scout bees’ phase. After all the onlooker bees complete their searches, these two phases start. The pseudo code is listed in Table 1.

Table 1.

The pseudo code of proposed artificial bee colony algorithm.

1: Set Iteration = 0;

2: INITIALIZE.

Initialize the food source position;

Evaluate the fitness of food sources;

3: WHILE (the termination condition are not met)

4: //Leaders Bees’ Phase

FOR (each leader bee)

Produce a new food source following equation (2);

Evaluate the fitness of the new food source;

Apply greedy selection;

END FOR.

5: Calculate the probability p for each food source

6: //Onlooker Bees’ Phase

FOR (each onlooker bee)

Send onlooker bees to food sources depending on p;

Produce a new food source following equation (2);

Evaluate the fitness of the new food source;

Apply greedy selection;

END FOR

7: //Crossover Phase

Produce parent population applying tournament selection;

Select a certain amount of worse food sources;

FOR (each selected food source)

Select two parents randomly from the parent population;

Produce two new food sources by crossing the selected parents;

Apply greedy selection for the selected food source and the newly produced food sources;

END FOR

8: //Mutation Phase

Select a certain amount of food sources;

FOR (each selected food source)

Produce a new food sources by the mutation operation;

Apply greedy selection for the selected food source and the newly produced food sources;

END FOR

9. //Scout Bees’ Phase

IF (an employed bee becomes into a scout bee)

Send the scout bee to a new randomly produced food source;

END IF

10: Memorize the best solution achieved so far;

Iteration = Iteration + 1;

END WHILE

Numerical examples

For comparisons, some well-known benchmark problems of VRPTW are adopted to examine the feasibility and performance of the improved ABC (IABC) algorithm in this article. Then, the IABC algorithm is applied to solve the VRP for western-style food delivery in Dalian city. The following will describe how to use the IABC algorithm to solve these benchmark problems and the western-style food delivery problem, respectively.

The classical VRPTW

In order to examine the performance of the IABC in this article, some well-known benchmark problems which can be found in the literatures^{4–6,12,18,30–33} are selected. The heuristics described in the previous sections were coded in Visual studio. Net 2003: C++. The operating environment is the Pentium IV 2.93-GHz processor and 3 GB for the Windows platform. A large number of experiments to determine the parameters are performed. The number of employed bees and the number of onlooker are set to be the same as the number of food sources, which is 50. This method is proposed by Karaboga and Basturk, ³⁶ which set the number of employed bees to be equal to the number of onlookers to reduce the number of parameters, and the population size (i.e. the total number of leaders and onlookers) of 100 can provide an acceptable convergence speed for search. Besides, the maximum iteration is set to be 1000, $P_{\mathrm{PScouter}}^0=0.5$ and $P_{\mathrm{Leader}}^0=0.5$ . In addition, crossover and mutation operations are used to improve the performance of ABC algorithm. Before the implement of the two genetic operations, there are p_c and p_m need to be predetermined. In general, p_c varies from 0.3 to 0.9, and p_m varies from 0.01 to 0.1. Considering the features of this problem and our experiences in GA, p_c and p_m are set as 0.6 and 0.05, respectively. Table 2 shows the best results of these benchmark problems and the best solution calculated by the IABC algorithm.

Table 2.

Comparison of best-known solution and best solution for the improved ABC algorithm.

No.	Reference	Best-known		This work		DBF (%)
		NV	TD	NV	TD
C101	Desrochers et al. 6	10	827.3	9	827.3	0
C102	Desrochers et al. 6	10	827.3	9	831.5	0.507
C103	Tavares et al. 33	10	826.3	10	828.26	0.237
C104	Tavares et al. 33	10	822.9	10	824.78	0.228
C105	Tavares et al. 33	10	827.3	9	828.94	0.198
C106	Desrochers et al. 6	10	827.3	10	833.7	0.773
C107	Tavares et al. 33	10	827.3	10	828.9	0.193
C108	Tavares et al. 33	10	827.3	10	830.6	0.398
C109	Tavares et al. 33	10	827.3	10	829.22	0.232
R101	Desrochers et al. 6	18	1607.7	17	1618.3	0.659
R102	Desrochers et al. 6	17	1434	17	1491.18	3.987
R103	Lau et al. 30	13	1175.67	13	1207	2.664
R104	Tan et al. 18	10	974.2	10	982.01	0.801
R105	Kallehauge et al. 34	14	1346.12	14	1377.11	2.302
R106	Cook and Rich 35	12	1234.6	11	1252.03	1.411
R107	Kallehauge et al. 34	10	1051.84	10	1126.3	7.079
R108	Tan et al. 18	9	954.03	9	968.59	1.526
R109	Chiang and Russell 17	12	1013.16	12	1101.99	8.767
R110	Cook and Rich (1999)	11	1068	10	1088.2	1.891
R111	Cook and Rich (1999)	10	1048.7	10	1099.46	4.840
R112	Rochat and Taillard 31	10	953.63	10	960.5	0.720
RC201	Tan et al. 18	4	1134.91	4	1249	10.052
RC202	Tan et al. 18	4	1130.53	4	1164.25	2.982
RC203	Tan et al. 18	3	1026.61	3	1083.6	5.551
RC204	Homberger and Gehring 11	3	799.12	3	799.12	0
RC205	Tan et al. 18	4	1295.46	4	1302.42	0.537
RC206	Yu et al. 14	3	1112.2	3	1171.2	5.304
RC207	Tan et al. 18	3	1040.67	3	1082.32	4.002
RC208	Rousseau et al. 32	3	829.69	3	833.97	0.515

ABC: artificial bee colony; NV: number of vehicles; TD: total distance; DBF: deviation from the best-known solution.

From Table 2, it can be attained that the results achieved by the IABC algorithm are close to the best-known solutions and the average deviation from the best-known solution is 2.35%, which is relative low. Thus, the proposed algorithm is suitable for VRPTW. Furthermore, from Table 2, it is also found that although only two solutions of the IABC algorithm reached the best solution in terms of the total distance, in six results, the number of vehicle with the IABC algorithm is obviously less than the one used by the other algorithms while the optimal solutions are almost equal. In addition, the solution calculated in C1, in which customers are clustered in groups, is encouraging. For most heuristics, it is difficult to find the best solution in local and is easily trapped in local optimal because the similarities between customers in instance set C1. The improved strategies can expand solution space and obtain relatively good solution. So, when the number of vehicles and the total distance are considered simultaneously, the IABC algorithm seems a powerful method for the kind of problem such as VRPTW.

Improved strategies are proposed to improve the performance of the IABC algorithm. Thus, the original ABC algorithm and the IABC algorithm are compared to examine the effectiveness of the improved strategies. The compared results are shown in Table 3. The compared results are shown in Table 3. The numbers in bold are the best between the original ABC algorithm and the IABC algorithm in terms of computation times and total distance. It can be observed that the computation times and the solutions from the two algorithms are almost equal when solving some simple problems such as C101, C102, C104, C105, C106, C107, and C108. However, when solving more complex problems, for example, RC204 and RC208, the effectiveness of the IABC is more obvious.

Table 3.

Comparison results between ABC and the improved ABC.

No.	ABC		This work		No.	ABC		This work
	Time	TD	Time	TD	Time	TD	Time	TD
C101	12	828.9	14	827.3	R107	976	1126.3	907	1126.3
C102	18	831.5	20	831.5	R108	563	969	452	968.59
C103	1106	1035.35	876	828.26	R109	678	1209	599	1101.99
C104	657	828.9	623	824.78	R110	692	1159.4	605	1088.2
C105	27	828.9	33	828.94	R111	712	1108.9	618	1099.46
C106	51	833.7	52	833.7	R112	554	1003.8	503	960.5
C107	42	828.9	49	828.9	RC201	897	1407	754	1249
C108	40	830.6	45	830.6	RC202	1259	1374.3	1106	1164.25
C109	679	1000.6	628	829.22	RC203	914	1089.1	867	1083.6
R101	2060	1650.8	1869	1618.3	RC204	387	818.7	379	799.12
R102	1894	1491.18	1456	1491.18	RC205	1120	1302.42	1058	1302.42
R103	1086	1292.7	993	1207	RC206	877	1171.2	853	1171.2
R104	987	1013.4	915	982.01	RC207	568	1082.32	551	1082.32
R105	1253	1377.11	1189	1377.11	RC208	497	852.8	482	833.97
R106	1075	1252.6	896	1252.03	Avg.	747.62	1089.63	668.69	1049.03

ABC: artificial bee colony; TD: total distance.

The western-style food delivery routing problem

The IABC algorithm is verified by the benchmark problems of the classical VRPTW, which shows that the IABC algorithm is suitable to solve VRPTW. Then, the IABC algorithm in this article is attempted to solve a real-life delivery route problem which is the western-style food delivery routing problem in Dalian city. With the improvement of living standard, people, in China, begin to concern on the quality of the western-style food. However, it is quite difficult to manage the delivery process and ensure maximum freshness under different weathers for its extended travel time. In addition, it is important for the restaurants to have food supplied timely when it sold out. The restaurants must update its supply within an allowable time. Therefore, in this article, the western-style food delivery routing problem is solved as a VRPTW. However, real-life routing is slightly different from classical VRPTW problem using a rectilinear metric. In the real-life routing problem, the road network is used to suggest the length of vehicle routing. Data management plays a major role in the efficient functioning of the distribution system. The information of the real-life delivery route problem with spatial characteristics of Dalian can be described in Figure 1. The vehicle capacity is 20 ton, and the weight and size are 2 and 13 m, respectively.

Figure 1.

The location information of the western-style food company and its chain nodes in Dalian.

Then, the IABC algorithm will continue calculating 10 times, the results are shown in Figure 2. From Figure 2, we can find that the results are relatively stable and the difference between the optimum and the worst value is <5%, which shows a good convergence performance of this algorithm. Moreover, the calculating time can be accepted for a real-life problem which is between 520 and 684 s. It can also be observed that our algorithm seems to be superior in terms of solution quality in a relatively smaller time. Thus, considering the optimization quality and the calculating time of this algorithm simultaneously, the IABC algorithm is suitable for solving the real-life western-style food delivery routing problem. The optimization results can be shown in Figure 3.

Figure 2.

Computational results of the improved ABC algorithm after running 10 times.

Figure 3.

Delivery routes of the western-style food delivery routing problem based on the improved ABC algorithm.

Figure 3 shows that six delivery routes, which are the optimum delivery routes of the western-style food delivery routing problem based on the IABC algorithm, are developed. From the distribution of these routes, it can be found that the optimized routes are feasible results for the proposed problem.

Conclusion

This article has attempted to improve the performance of ABC algorithm for VRPTW, in which an adaptive strategy, a crossover operation, and a mutation operation are proposed. The benchmark problems of VRPTW are first used, and the results suggest the effectiveness of the IABC algorithm for solving VRPTW. Moreover, the results of western-style food delivery routing problem in Dalian city also prove that the IABC algorithm is a feasible method for solving the western-style food delivery routing problem.