Routing Optimization in Distribution of Cold Chain Logistics-毕业作品网站

In this paper, we studied the problem of routing in cold chain logistics distribution with the goal of minimizing the total cost. Due to the characteristics of cold-chain products, the customer penalty cost is considered with soft time windows, which is modeled as a piecewise function to reflect the satisfaction of customers in delivery. We formulate our problem as a constraint optimization problem, and then propose a CC-ant algorithm based on ant colony framework to solve it. Two approaches are adopted to improve the original AC to avoid local optimum, including routing path selection and pheromone updating. Numerical experiments show that our algorithm is superior to existing work in both total cost and path length with less computing time. Therefore, CC-ant algorithm is well-designed and suitable for the cold chain VRP problem.

[1] W. Yachao, “The optimization analysis of cold chain logistics distribution route based on particle swarm optimization (pso) algorithm,” Advances in Information Sciences and Service Sciences, vol. 5, no. 2, p. 801, 2013.

[2] W. Yang, Q. Zhang, and G. D. Li, “Agricultural optimization of cold-chain logistics distribution routing based on pso,” in Advanced Materials Research, vol. 756. Trans Tech Publ, 2013, pp. 3941–3945.

[3] Q. Hua, “Research for the vrp in agricultural products based on genetic algorithm,” Logistics Sci-Tech, vol. 9, p. 030, 2012. [4] Z.-p. Li and S. Wang, “Research on end distribution path problem of dairy cold chain,” in The 19th International Conference on Industrial Engineering and Engineering Management. Springer, 2013, pp. 983–992.

[5] J. Tang, K. Liu, and Q. Chen, “Study on cold chain logistics of vehicle routing problem for agricultural products,” in Proceedings of 2013 IEEE International Conference on Service Operations and Logistics, and Informatics, July 2013, pp. 317–322.

[6] C.-I. Hsu, S.-F. Hung, and H.-C. Li, “Vehicle routing problem with time-windows for perishable food delivery,” Journal of food engineering, vol. 80, no. 2, pp. 465–475, 2007.

[7] Solomon dataset for vrptw problem, http://web.cba.neu.edu/msolomon/problems.

[8] J. Chai, “Study on route optimization of cold chain logistics of fresh food.” Carpathian Journal of Food Science & Technology, vol. 8, no. 2, 2016.

2. Shenzhen Key Laboratory of Internet Information Collaboration, Shenzhen, China

Abstract—In recent years, cold chain logistics is becoming more and more important, which always guides the transportation of the perishable food or agricultural products to the designated locations with least time to keep them fresh. It is mainly composed of four parts: the cost of vehicles to be used, transportation cost, customer penalty cost and the cost of damage, reflecting the basic operation expenditures, total routing length, and customer satisfaction during transportation indirectly. Here, the cost of customer penalty is generated only when the delivery time of a product exceeds its given time window. Numerical experiments show that our routing method can provide a feasible transportation path with both less cost and less running time in comparison with existing work.

I. INTRODUCTION

Cold chain logistics distribution is to deliver the easy to decay food, agricultural products, or drugs to the retailers or supermarkets in different locations with minimum transportation time and cost. According to a report, the economic losses due to the lack of efficient path design and refrigeration during cold chain transportation has even exceeded 1 hundred billion RMB for only vegetable and fruit in China from 2012 to 2015, let alone for other agricultural products [1]. Therefore, there is urgent need to optimize the routing path of the vehicles in cold chain logistics distribution considering the freshness of perishable agricultural products as well as total cost. The routing of cold chain logistics is a special application in VRP (vehicular routing problem), which is more concerned with the delivery time of the perishable products, which usually can be solved using intelligent algorithms include PSO (particle swarm optimization), genetic algorithms, and so on. For example, authors in [1], [2] adopt PSOto find the optimal routing with shortest path in the distribution of cold chain logistics. Qian et al. in [3] use genetic algorithm to solve VRP problem in agricultural products transportation with consideration of customer satisfaction in decision making. Li et al. in [4] propose a scanning-insert algorithm to deliver dairy products within customers’ time window. Tang et al. in [5] uses ant colony method in routing optimization in agricultural products transportation. Hsu et al. in [6] construct a SVRPTW model that considers the randomness of the perishable food delivery process, based on which they plan the routing path under cost constraint while satisfying customers’ time-window strictly. In fact, the total cost and delivery time are the two most important issues in cold chain VRP, but not well considered in existing work.

However, it is hard to design the routing path with shortest length while satisfying the time demands of delivery window for customers. We introduce the penalty cost that occurs only when the delivery time of a product exceeds its given time window, which is a reflection of the both service quality and cold-chain product quality. Thus, different goals can be transformed and combined into one optimization goal of minimizing the total cost, including the cost of vehicles to be used, transportation cost, customer penalty cost and damage cost. Considering the characteristics of cold chain distribution, we formulate the problem as a constraint optimization problem. To solve it, we propose a CC-ant algorithm based on ant colony framework with novel designs in path selection, pheromone updating and initialization processes instead of the original formulas in ant colony algorithm to avoid locally optimal solutions. Numerical experiments show that our method can provide a feasible transportation path with both less cost and less running time in comparison with existing work. The remainder of paper is organized as follows. In Section II, the modeling and problem formulations will be given in detail. In Section III, we will present the design of our CCant algorithm. In Section IV, we introduce experiment setup and make evaluations for our method. Finally, Section V concludes this paper.

Notation	Definition
N	The total number of customers to be served
K	The maximum number of vehicles in the distribution center
C车辆	The fixed costs for each vehicle to be used
C运输	The transportation cost per unit distance
C货物	The price of per unit cold chain goods
	The distance between customer i and customer j, where i, j ∈ {1, 2, ...,N}
	The maximum load capacity of each vehicle k, where k ∈ {1, 2, ...,K}
	The cargo demand of customer i
	The arriving time of vehicle k at customer i
[]	The time window that customer i want
[]	The time window that customer i can accept
	The penalty cost of vehicle k arrives at the customer i at time
M1，M2	Penalty cost caused by delivery before and after acceptable time window
	Penalty cost coefficients between acceptable and wanted time window
	The damage rate during transportation and during offloading goods
	The transporting delay from distribution center to customer i
	The offloading delay for customer i’s goods
	0-1 variable indicates whether vehicle k travels from customer i to j
	0-1 variable indicates customer i’s goods are delivered by vehicle k

II. COLD-CHAIN MODELS AND PROBLEM FORMULATION

In this Section, the mode lings and problem formulation will be given in detail. The optimization goal of our problem is composed of four parts: fixed cost for vehicles, transportation cost, customer penalty cost and cargo cost. The notations to be used are listed in Table I.

For distribution center, it has to pay the fixed cost for the use of each vehicle, which may include wages of drivers, lease rental of the vehicle and so on. Let C vehicle denote the fixed cost per vehicle, the total cost for vehicles are:

where sign(k) is a boolean indicator to show whether vehicle k is scheduled to deliver goods to customers, which can be represented as:

The transportation cost distribution vehicle includes the cost of fuel consumption, maintenance. Generally, the transportation cost of the vehicle is proportional to the traveling mileage. Let C transp denote the transportation cost per unit distance, the total cost for transportation are:

We consider using the soft window for the cold chain logistics distribution, which divides the arriving time into five segments with different penalty cost. The penalty cost are larger when the vehicles arrive earlier or later than the wanted time window of customer, so there is a tradeoff about whether to dispatch a new vehicle or paying penalty cost with less vehicles.

• Premature service time window is the time span much earlier than the wanted time window of customers. When vehicles arrive during this window, it may cause customers’ extreme inconvenience, so there should be a heavier punishment to avoid this in routing design.

• Service in advance time window is the time span just before the wanted time window of customers. Immediate delivery may cause customers’ inconvenience and complaint, so there should be a small penalty cost.

• Service by time window is the wanted time window of customers, so there should be no penalty cost.

• Service delay time window is the time span a little later than the wanted time window of customers. A small penalty will be paid when arriving in this time window.

• Late service time window is time span much later than the wanted time window of customers. The quality of the goods in this time window is not guaranteed, even causing food decayed, so the penalty cost is very high.

In the cold chain, the main factor causing fresh products damaged is the transportation time including the traveling time and offloading time after arriving. The total cost for damage during transportation can be represented as:

where ρ1, ρ2 denote the loss ratios for transportation and offloading, and D0→i, Doff i denote the traveling time and offloading time, respectively. Thus, our problem of can be formulated as follows:

The optimization goal of our problem is to minimize the total cost, as shown in the objective function. Constraint (1) means that each customer will be serviced by only one vehicle. For any customer in location j, there should always be a vehicle traveling from location i to it, including that from distribution center when i = 0, as shown in constraints (2). Similarly, for any location i, it should always find a next service customer in location j, including going back to the center when j = 0, so we have constraints (3). Constraint (4) means that the total delivery demand of the cargos on the distribution path should not exceed the maximum load per vehicle. Constraints (5) is the restrictions of service time window for each customer i.

III. ALGORITHM DESIGN

Ant colony algorithm is designed by simulating the behavior of colony of ant when looking for food in different locations. During their walks, the ants always release pheromone to determine the specific range of food, and the pheromone concentration is used as the judgment basis of path selection. In other words, the path with high pheromone concentration will be walked by more ants with high probability. In return, more pheromone will be released through this path. In routing path planning of our problem, ant is compared to the vehicle, the target customer is compared to food. Through cooperation and exchange of information between ants, the shortest paths between food and ant nest (distribution center) will be found finally. Table II shows the notations to be used in our algorithm.

Notation	Definition
N	The total number of cities
m	The total number of ants
	The distance between city i and city j, where i, j ∈ {1, 2, ...,N}
	The probability that ant k can transfer from city i to city j
	The total amount of pheromone on the path (i, j) in this cycle
	The visibility on the path (i, j) at time t
a	The pheromone heuristic factor
b	The expected value heuristic factor
	The set of cities that ant k can choose
r	The evaporation factor of pheromone
D	The total increment pheromone on path (i, j) after this round of search
D	The pheromone increment left by ant k walked through path (i, j)
Q	The total amount of pheromone released by ants in one cycle

We suppose there are m ants traveling around N cities or sites searching for food. There are three important formulas that affect the routing selection:

When ant k is in city i, it needs to make selection for the next city j, which is closely related with the pheromone concentration and the visibility of the next city that can walk to. The probability that ant k can transfer from city i to city j, denoted as

where τij denotes the pheromone in the path (i, j), ηij denotes the expectations of ants moving from city i to city j, which is usually set to be 1/dij , where dij is the length of path (i, j). In addition, allowed k is the set of cities that ant k can choose. As for coefficients, α denotes information heuristic factor, reflecting the relative importance of the accumulated information in guiding ants searching, whileβdenotes the expectative heuristic factor that reflects the relative importance of the expectative heuristic information in search guiding.

When all the ants complete their cycles, the pheromone concentration in each walking path (i, j) will be updated in the following formula:

where

is the pheromone concentration after this round of searching. It is composed of residual pheromone after evaporation and that newly increased by the ants walked through. Here Δτij(t) denotes the total increment pheromone on path (i, j) after this round of search, which is composed of the pheromone increment by all ants walked through that can be represented as:

where Q denotes the total amount of pheromone released by ants in one cycle. B. Modified Ant Colony Algorithm: CC-ant Base on ant colony framework, we propose a modified algorithm called CC-ant that can well suit the distribution in cold chain logistics. 1) Improvement in Path Selection Traditional ant colony algorithm can always provide locally optimal solutions rather than globally due to the two drawbacks as follows:

• It assumes the probability to choose the next traveling city is the same at the beginning, so that the algorithm is hard to converge with low efficiency.

• The cities with higher probability are more likely to be chosen. With the positive feedback in pheromone updating, more pheromone will be accumulated in a certain popular paths, so that they are more prone to be selected in the following searching, causing local optimum as a result.

To avoid falling into local optimum, we propose to combine random probability with roulette method. In order to increase the solution space, we first use random probability in path selection until the result cannot be further optimized. Under this condition, we adopt roulette method to search for possible path that is more optimal than existing ones while updating the pheromone. The basic idea of roulette method is to give a probability for path selection, which may use random probability or generated number by roulette method. Z0 is the probability value in the roulette, which corresponds to different values of (p1, p2, p3 ∈ (0, 1)) under different iteration times, as shown in the following:

where R is current iteration times, R max is maximum number of iterations. When selecting the next city, a random number in (0, 1) is generated, denoted as Z. If Z < Z0 , we randomly select the next allowable city; Otherwise, we select the next allowable city using probability of pkij(t) as mentioned before.

The advantages of the combination of random probability with roulette method are that the search space is expanded and the convergence speed is accelerated in the later period of this algorithm.

• No pheromone updating in the returning path In path searching, if there is no other allowable cities can be accessed within time constraints, the ants will return to the origin location. We do not update the pheromone in the returning path after arriving all possible cities, or else it will break the positive feedback mechanism in pheromone updating, and it’s hard to rely on pheromone concentration to find a better solution.

• Optimization of solution selection in iteration In order to avoid the local optimum, we optimize the iteration based on the solution including: selecting the best solution after repeated running of the same ant in one iteration, and selecting the best solution from previous iterations. The specific rule is as follows:

where Δτ best is the pheromone concentration corresponding to the current optimal solution, which can be obtained through the above mentioned two methods. The former solution is to use one ant to travel all the cities within constraints. Repeat this process several times in one iteration, and then select the best solution for the next iteration. The latter is to select the best solution from all previous iterations, not just its precedent iteration. In practice, we run the optimization using the former method once every 10 iterations. In other cases, we select the current optimal solution using the latter method. The pheromone feedback mechanism using the above two methods is better than that of traditional ant colony method, which can effectively avoid local optimum, as to be discussed in experiment analysis.

IV. EXPERIMENT AND ANALYSIS

To make evaluations, we adopt the commonly used Solomon dataset, which was initially used in VRPTW problem by Solomon [7]. This dataset can be divided into three categories: R-type, R-type and RC-type.

Note that, our cold-chain VRP considers the soft time window, so that Solomon dataset with only hard time window should be adjusted. We insert two time points b, c into the original hard window of [a,d], so our soft time window has spans of [a, b, c, d] in arithmetic progression. The experiments are executed on a ThinkPad with Inter-Core i7-2630QM CPU 2.00GHz, 8GB RAM, and the OS is Window 7 (64bit). As for other parameters, we set α = 1,β = 3, ρ = 0.1, m = 15, Q = 100, Qk = 50, Cvehicle = 50, Ctransp = 4, Cgoods = 20,M1 = 30,M2 = 60, ρ1 = 0.001. For each dataset, the iteration times of our method is 500. We repeat 10 rounds of the iterations to get an average result, so as to objectively make evaluations.

In ant colony algorithm, the path is initially selected using random probability. To accelerate the generation of initial solution, we select the next allowable city with shortest distant to travel if not violating time constraints. Therefore, the nearest neighbor search algorithm is used. Table III gives comparisons our method CC-ant with the original ant colony method and genetic algorithm [8] in total cost and total path length, which are the average of the results obtained from 10 times of repetition. As can be seen, the total cost of our method of CC-ant is less than both of the benchmarks even under different datasets. For R-type datasets, the cost saving is the most obvious, which can even reach 3.90%, while for C-type and RC-type, the promotion rate is a little less, about 0.5% and 1.0%, respectively. For aggregated distribution of city nodes, the cities selected in path planning have very little affect on the ultimate result of routing, so the improvement for both C-type and RC type are small, though RC-type is a little bigger due to its distribution having both aggregated and randomized city nodes. The total path length is in linear relationship with the transportation cost, which account for a major part in the total cost. Therefore, the promotion ratio of total path length is similar to that of total cost in comparison. In a word, our method is suitable for the cold chain problem.