ABSTRACT

According to the characteristics and requirements of urban vegetable logistics and distribution, the optimization model is established to achieve the minimum distribution cost of distribution center. The algorithm of artificial bee colony is improved, and the algorithm based on MATLAB software is designed to solve the model successfully. At the same time, combined with the actual case, the two algorithms are compared to verify the effectiveness of the improved artificial bee colony algorithm in the optimization of urban vegetable distribution path.

Keywords:

Urban Vegetable, Vehicle Routing, Optimized Artificial Bee Colony Algorithm, Path Optimization

1. Introduction

City vegetable logistics is engaged in transportation, warehousing and other series of vegetable logistics activities within the city limits, it is one of the logistics, business flow and information flow, according to different customers on the delivery time and quantity of vegetables and other requirements, to provide personalized service for customers and distribution [1] . As the characteristics of the city itself, making the city vegetable logistics and distribution with a wide range of customers, the number of customer points, customer points between the distribution distance is relatively close to the characteristics of urban vegetable logistics and distribution generally use the car for distribution, not only because the special truck has the advantages of strong maneuverability, flexible response [2] , and these advantages can also meet the customer a small number of goods, the number of purchases, delivery to the door of the consumer characteristics. In addition, the urban vegetable logistics and distribution of urban residents have a great impact on daily life. It is necessary to construct a reasonable urban vegetable logistics and distribution system not only to meet the requirements of timeliness, convenience, distribution environment and high distribution efficiency, but also should meet the characteristics of urban customers, distribution flow and other characteristics [3] .

Urban vegetable logistics distribution vehicle routing problem can be described as: there are a number of customers need the distribution center to deliver a certain amount of goods, the specific location of each customer point is known. The distribution center with the delivery task has the same type of distribution vehicle, and the quantity meets the demand, all the delivery vehicles have the same carrying capacity of [4] . The vehicles that carry the goods depart from the distribution center, along the planned route, the goods to the customer on the route of the hands of the final return to the distribution center. There are certain conditions in the distribution process constraints, each customer can only be a distribution vehicle responsible for the distribution of the task, the time of delivery of the goods within the time required by the customer, otherwise given the appropriate delivery vehicle must be punished [5] [6] . In this paper, the establishment of the model first considers the requirements of the customer point to the delivery time, and then considers the optimization model with the total cost as the goal, which is based on the load and distance constraints of the vehicle. Using the improved artificial bee colony algorithm, using MATLAB software programming solution, combined with the case, to verify the feasibility and effectiveness of improving the artificial bee colony algorithm.

2. Establishment of Model

2.1. Assumptions

As a result of the actual distribution, we will encounter a variety of practical problems, from a different point of view, to solve the problem achieved by the target results are not the same, in order to study and establish the issue of urban vegetable distribution mathematical model [7] . Here make the following assumptions: 1) The starting point of each delivery vehicle for the distribution center, and ultimately return to the distribution center. 2) The total delivery amount of each distribution route is less than the maximum load of the vehicle. 3) The distance traveled by each delivery vehicle shall not exceed its distance. 4) Each customer can only be completed by a car distribution, the cost of each vehicle start and travel unit distance is known.

2.2. Model Establishment

In order to facilitate the description of the constructed model, the following symbols are defined:

(a) $S=\left\{i|i=0,1,2,\cdots ,n\right\}$ : collection of a single distribution center and all of its customers, $i=0$ is the distribution center, $i=1,2,\cdots ,n$ is customer who provides delivery services by the distribution center;

(b) $K=\left\{k|k=0,1,2,\cdots ,m\right\}$ : a set of vehicles that can be used by the distribution center;

(c) $Q$ : the maximum load of a vehicle, in which the vehicle is the same type of vehicle;

(d) $q_i$ : the customer needs, that is, distribution center should be provided for the customer point of delivery, $i=1,2,\cdots ,n$ ;

(e) $D$ : the maximum distance of the vehicle is the same type of vehicle, so the maximum distance is the same;

(f) $d_{ij}$ : the distance from the point i to the point j, $i,j=0,1,2,\cdots ,n$ ;

(g) $t_{ij}$ : the time is used from point i to point j, $i,j=0,1,2,\cdots ,n$ ;

(h) $C_0$ is the fixed cost of the vehicle, the starting cost required for each vehicle to be delivered, $C_1$ is the distance traveled by the vehicle, the cost per unit length of time per vehicle;

(m) $t_i$ : the time at which the vehicle serves the customer, $i=0,1,2,\cdots ,n$ ;

(p) $S_{ik}$ : the time period during which the vehicle provides services to the customer, $S_{ike}$ and $S_{ikl}$ are the starting and ending time of vehicles serving customers respectively, $i=0,1,2,\cdots ,n$ ;

(r) $E{T}_i,L{T}_i$ : the customer service time window start and end time, during this time to provide delivery services is the highest customer satisfaction, $i=0,1,2,\cdots ,n$ ;

(v) $P_i\left(S_{ik}\right)$ : the penalty cost caused by the service of the customer, that is, the punitive cost caused by the failure to provide service at the time of customer satisfaction.

(w) $x_{ijk}$ : whether or not the vehicle provides service from the customer to the customer, $i,j=0,1,2,\cdots ,n$ , $k=1,2,\cdots ,m$ ;

(q) $y_{ik}$ : whether the vehicle provides the customer with the delivery, $i=1,2,\cdots ,n$ , $k=1,2,\cdots ,m$ ,

The decision variables for the problem are as follows:

$x_{ijk}=\{\begin{array}{l}1\text{thevehicleisservedfrompoint}i\text{topoint}j\\ 0\text{otherwise}\end{array}i,j=0,1,2,\cdots ,n;k=1,2,\cdots ,m$

$y_{ik}=\{\begin{array}{l}1\text{thetaskofcustomer}i\text{isdonebyvehicle}k\\ 0\text{otherwise}\end{array}i=1,2,\cdots ,n;k=1,2,\cdots ,m$

In this question, the penalty coefficient is introduced and the opportunity cost is expressed as the unit weight per unit time. When the distribution vehicle fails to provide service in the customer satisfaction period, it will be punished in certain proportion. When the actual delivery time is earlier than the service time window, the penalty coefficient is α, when the actual delivery time is later than the service time window, the penalty coefficient is β. $P_i\left(S_{ik}\right)$ formula of penalty cost is as follows:

$P_i\left(S_{ik}\right)=\{\begin{array}{l}\alpha q_i\left(E{T}_i-S_{ike}\right)S_{ike}<E{T}_i\\ 0E{T}_i\le S_{ike},S_{ikl}\le L{T}_i\\ \beta q_i\left(S_{ikl}-L{T}_i\right)S_{ikl}>L{T}_i\end{array}i=0,1,2,\cdots ,n$ (2-1)

When the cost of cargo damage is calculated, it is assumed that the damage rate of the vegetables is related to the time of the vegetables in the prescribed low-temperature transportation environment, and the deterioration rate of the vegetables is constant and the deterioration rate of the vegetables is constant and the metamorphic function [8] as follows:

${Q^{\prime }}_i=Q_{i}C{\text{e}}^{-\delta t}$ (2-2)

Among them, $Q_i$ the product is the quality of the goods in good condition, $t$ is the product experience the logistics time, $\delta$ is the product of the sensitivity coefficient of time, $C$ for the product at a constant temperature deterioration of a constant speed change. In the metamorphic function, the product is more sensitive to time, the $\delta$ value is relatively small, on the contrary, the value is larger.

The cost of the entire distribution process is:

$H={\displaystyle \sum _{i=1}^n{q}_i\left(1-C{\text{e}}^{-\delta S_{ike}}\right)p}$ (2-3)

$p$ is the unit of the value of the loss of vegetable products.

The VRPSTW studied in this paper will be time cost, with the lowest total cost as the optimization target. The objective function is shown in (2-4).

$\min Z={\displaystyle \sum _{k=1}^m{\displaystyle \sum _{i=0}^n{\displaystyle \sum _{j=0}^n{C}_1{d}_{ij}{x}_{ijk}}}}+{\displaystyle \sum _{i=1}^n{P}_i\left(S_{ik}\right)}+C_0{\displaystyle \sum _{i=0}^n{\displaystyle \sum _{k=1}^m{x}_{i0k}}}+{\displaystyle \sum _{i=1}^n{q}_i\left(1-C{\text{e}}^{-\delta S_{ike}}\right)p}$ (2-4)

The constraints are:

${\displaystyle \sum _{i=1}^n{q}_i{y}_{ik}\le Q,}k=1,2,\cdots ,m$ (2-5)

${\displaystyle \sum _{k=1}^m{y}_{ik}=1,}i=1,2,\cdots ,n$ (2-6)

${\displaystyle \sum _{k=1}^m{y}_{0k}=m}$ (2-7)

${\displaystyle \sum _{j=1}^n{x}_{0jk}=1},k=1,2,\cdots ,m$ (2-8)

${\displaystyle \sum _{i=1}^n{x}_{i0k}=1,}k=1,2,\cdots ,m$ (2-9)

${\displaystyle \sum _{i=0}^n{x}_{ijk}}=y_{jk},j=1,2,\cdots ,n;k=1,2,\cdots ,m$ (2-10)

${\displaystyle \sum _{j=0}^n{x}_{ijk}=y_{ik}},i=0,1,\cdots ,n;k=1,2,\cdots ,m$ (2-11)

${\displaystyle \sum _{i=0}^n{\displaystyle \sum _{j=0}^n{d}_{ij}{x}_{ijk}\le D,}}k=1,2,\cdots ,m$ (2-12)

$x_{ijk}=0,1,i,j=0,1,\cdots ,n;k=1,2,\cdots ,m$ (2-13)

$y_{ik}=0,1,i=0,1,\cdots ,n;k=1,2,\cdots ,m$ (2-14)

$\begin{array}{l}{S}_{ike}+t_i{x}_{ijk}+t_{ij}{x}_{ijk}-M\left(1-x_{ijk}\right)\le S_{jke},\\ i=0,1,\cdots ,n;j=0,1,\cdots ,n;k=1,2,\cdots ,m\end{array}$ (2-15)

$S_{ikl}+t_{ij}{x}_{ijk}-M\left(1-x_{ijk}\right)\le S_{jke},i=0,1,\cdots ,n;j=0,1,\cdots ,n;k=1,2,\cdots ,m$ (2-16)

$S_{ikl}=S_{ike}+t_i{y}_{ik},i=0,1,\cdots ,n;k=1,2,\cdots ,m$ (2-17)

$S_{ike}\le M{y}_{ik},i=0,1,\cdots ,n;k=1,2,\cdots ,m$ (2-18)

$S_{ike}\ge 0,S_{ikl}\ge S_{ike},i=0,1,\cdots ,n;k=1,2,\cdots ,m$ (2-19)

$S_{0ke}=0,S_{0kl}=0,k=1,2,\cdots ,m$ (2-20)

The description of the constraint is as follows: Equation (2-5) indicates that the total demand for all customers per vehicle service does not exceed the capacity limit of the vehicle. (2-6) (2-8) means that each customer point can only be delivered by one car. Type (2-7) means that each vehicle from the distribution center. (2-9) means that each car finally returns to the distribution center. (2-10) means that each car if the arrival point must be service. (2-11) means that if the vehicle is customer service, the vehicle will leave the point after the task is completed. Equation (2-12) indicates that the total travel distance of each vehicle must not exceed its travel distance limit. (2-15) and (2-16) show the time relationship in which the vehicle arrives at two customers in their distribution route. Equation (2-17) indicates the relationship between the starting and ending time of the vehicle for customer service. (2-18) means that if the vehicle does not provide delivery to the customer, the vehicle will not reach the customer. Equation (2-19) represents the time limit for the start and end of the service time for the customer service. Equation (2-20) indicates that the departure time of the vehicle from the distribution center is zero.

3. Improved Artificial Bee Colony Algorithm

Human beings based on the nature of bees to collect honey activities, summed up the artificial anthropocentric algorithm theory and to describe. The take bee (the lead bee) to go out looking for honey, and then by jumping dancing and another worker bees in the form of probability to share the source of food information, follow the bee and reconnaissance bee first wait, until the bees bring back the food source information, then choose to follow the honey or find the food near the source to find nectar. From the above description can be learned to adopt bees, follow the bee and reconnaissance bee be able to achieve the identity of the conversion.

3.1. Parameter Initialization

According to the constructed path optimization model, the number of customers to remove the distribution center is n − 1. The number of vehicles participating in the distribution center is defined by m, and Q is the number of vehicles in each distribution vehicle. In the actual urban vegetable distribution vehicle routing problem, q_i represents customer demand. The expression formula for setting N before the initialization phase is as follows:

$N=m-\left(\left|\frac{{\displaystyle {\sum }_{i=1}^n{q}_i}}{q}\right|+1\right)$ (3-1)

Population size N = 50; N/2 indicates the number of food sources is also the number of honey mining bee; single maximum limit = 20; maximum number of iterations MaxCycle = 500.

Solution of the initialization function [solu] = Initial (num), this method is used to generate the problem of the initial solution. Method of production: by looking for the nearest customer service point, one by one distribution, and meet the constraints.

The solution space is defined by V[N][n][n], and the initial feasible solution number is denoted by N.

$v\left[i\right]\left[j\right]\left[0\right]=-1,i\in N,j\in n$ (3-2)

3.2. Evaluation Method of Profitability

Based on the optimization model of the urban vegetable distribution VRP problem created by the objective function Formula (2-4), we can see that the actual problem to achieve is to minimize the total distribution costs. Artificial colony algorithm uses the reciprocal of the minimum distribution cost as the fitness function, so that the high cost corresponds to the low fitness and the small food source income value.

3.3. Population Update

The algorithm at the beginning of operation, there is not much difference in the probability of each food source is worker to find the number of iterations, a gradual increase in worker, not only to expand the search probability of each food source, and previously set good pheromone is gradually cut, resulting in not being left in to find a food source on early in the process of iterative pheromone is nearly equal to zero. In addition, in the posterior iteration of the algorithm, the algorithm will generate local extreme value because of the large amount of information gathered on the path. The update formula is as follows:

$Q_{ij}\left(N+1\right)=\{\begin{array}{l}{\rho }^{1+\epsilon \left(N\right)}{Q}_{ij}\left(N\right)+\Delta Q_{ij}\left(N\right),Q⊲Q_{\max }\\ {\rho }^{1-\epsilon \left(N\right)}{Q}_{ij}\left(N\right)+\Delta Q_{ij}\left(N\right),Q⊳Q_{\min }\end{array}$ (3-3)

Formula: $\epsilon \left(N\right)=N/\tau$ , $\tau$ is a constant. According to this formula can be achieved with the change of the pheromone solution to adjust the use of such methods can improve the efficiency of the ABC algorithm in the global scope, and can effectively prevent the local extreme situation.

When the algorithm is in different iterative stages, the algorithm can not only avoid the local optimization but also accelerate the convergence speed. The setting of the constant is as shown in Equation (3-4).

$\delta =\{\begin{array}{l}{\delta }_1,0\le N<N_1\\ {\delta }_2,N_1\le N<N_2\\ {\delta }_3,N_2\le N<N{C}_{\max }\end{array}$ (3-4)

3.4. Nectar Selection

Follow the bee according to the nectar fitness value corresponding to the selected probability to choose the appropriate honey to go honey, the formula is as follows:

$P_i=\frac{fi{t}_i}{{\displaystyle \sum _{i=1}^{N}fi{t}_i}}$ (3-5)

Follow the bee according to the nectar fitness value corresponding to the selected probability to choose the appropriate honey to go honey, the formula such as follow the bee to a certain probability in the poor near the nectar to find a new source. Compare the current nectar and the previous nectar fitness value, if the former is greater than or equal to the latter, then use the current nectar to replace the previous nectar, otherwise, remain unchanged.

3.5. Population Elimination

When the bees (or follow bees) continuous limit failed to search better circulation nectar, this solution is determined (i.e. the nectar will fall into the local optimal solution). Bees (or follow bees) to give up the nectar, and into the investigation bee, continue to search for new nectar, the search formula is:

$x_{ij}=x_{\min j}+rand\left[0,1\right]\left(x_{\max j}-x_{\min j}\right)$ (3-6)

4. Case Analysis

The distribution center of an enterprise provides distribution service for 15 customer points. The distribution center is represented by the serial number 0, and the serial number 1 - 15 represents 15 clients respectively. The enterprise uses the same type of freight car for 15 customer point distribution. Among them, the maximum carrying capacity of each car is 5 tons, the vehicle fixed cost is 100, the consumption time cost of 250 vehicles, earlier than the time window to the customer point penalty cost is 250 per ton per hour, the vehicle later arrived time windows penalty cost customers per ton of 300 per hour. The distribution center and customer information statistics are shown in Table 1. It is necessary to arrange vehicles to complete the distribution task, so that the total cost of the distribution cost and the penalty cost is the least, so as to find the reasonable distribution route for the distribution center. Data processing was carried out by Matlab2010 software.

Distribution center and customer distribution status are shown in Figure 1.

4.1. Case Solving and Analysis

The number of leading bees accounted for 50%, followed by bees accounted for 10%, reconnaissance bees accounted for 40%, A = 1.5, B = 2, the number of iterations Nmax = 200, of which 50 times before the iteration, Delta 1 = 100, the middle 51 - 150 times, Delta 2 = 50, 50 times after the iteration, Delta 3 = 200. The distribution route diagram and convergence process of artificial bee colony algorithm are shown in Figure 2, and the distribution route diagram and convergence process of artificial bee colony algorithm are improved, as shown in Figure 3.

4.2. Comparison of Different Algorithms

In order to facilitate the comparison, the paper analyzes the data of the same enterprise and the customer point of the same group. On the basis of the same distance, traffic volume and distance limit, the optimization process of vehicle routing problem under soft time window constraint is simulated, The optimal target value of the algorithm is the total cost of distribution, and the specific data of the number of iterations of the total distribution vehicle convergence are shown in Table 2.

Comparison of the case data can be seen, the same customer restrictions on the distance, distance, volume, when the time constraint is not too strict, is the vehicle routing problem with soft time windows, an improved artificial bee colony algorithm in general distribution vehicle problems and artificial bee colony algorithm is the same, but the distribution of the total cost savings of 1091.78;

and convergence the speed of the improved artificial bee colony algorithm is faster. The main reason is the analysis algorithm, improved artificial bee colony algorithm with variable neighborhood search update strategy, the best individual search direction is better than stronger, compared with the traditional artificial bee colony algorithm, optimize the operation speed and quality optimization.

5. Conclusion

Logistics and distribution activities is an important part of the logistics system to achieve the optimization of vehicle routing that can directly optimize the logistics and distribution activities, not only can improve the economic efficiency of enterprises, but also to help achieve the logistics management of scientific. Vehicle routing problem as a combinatorial optimization problem, has a strong theory, application value, in the field of logistics and distribution has been widely used [9] . Although the degree of attention to the research of vehicle routing problem is growing, but the expansion of the basic distribution routing problem with time constraint is not deep enough, but has yet to find the solution more quickly and accurately, so there are many scholars pay close attention in the limited time to find the most satisfactory solution to the problem of [10] . On the basis of the previous scholars’ research, this paper studies the vehicle routing problem with time constraints, takes into account the influence of time on the distribution path, analyzes the different criteria of the customer’s time requirements, but the problems studied in this paper do not consider the actual distribution. The impact of road conditions on the speed of the road, in the next step can also be added to the peak period, the impact of non-peak time on the speed of the introduction of real-time changes in speed to study.

Cite this paper

Zhang, Z.Z. and Wang, L.H. (2017) Application of Improved Artificial Bee Colony Algorithm in Urban Vegetable Distribution Route Optimization. Journal of Applied Mathematics and Physics, 5, 2291-2301. https://doi.org/10.4236/jamp.2017.511186

References