1. Introduction

Inventory and transportation are the most important functional elements of the logistics system, which are the two main links of the logistics to obtain the "time value" and "space value", and their consumption accounts for the total cost of logistics 2/3 ^[1]. The classical inventory routing problem is mainly to study a supplier provides distribution services to several customers with the constraints of the customer's demand, customer's delivery time window and inventory capacity in order to minimize the total cost. Birger Raa ^{[2, 3]} et al. assumed that the customer’s demand rate is constant and got a periodic replenishment strategy with the objective of minimizing the average distribution and inventory costs without causing out of stock when they studied the inventory routing problem at 2007 and a particle swarm algorithm was designed to solve the model. In 2008, the vehicle using cost was added in the model while using insert genetic algorithm to solve the model step by step. Li ^[4] et al. studied the inventory routing problem in the process of refined oil distribution with the constraints of vehicle capacity, storage capacity of each gas station, number of vehicles and other factors. A mathematical model was built with the maximum travel time minimization as the objective function and the tabu search algorithm was designed to solve this model. In 2014, Zhao ^[5] et al. put forward the stochastic demand inventory - routing problem model of retailer system and designed a heuristic algorithm based on (s, S) inventory policy and modified C-W saving algorithm. In 2016, we ^[6] have stuied the secondary distribution routing optimization of refined oil with the constraint of time window. Taking the working time equilibrium as the objective, an integer programming model was built and a heurstic algorithm was designed to solve the model.

Ant colony algorithm, also known as the ant algorithm, is a probabilistic algorithm which is used to find the optimized route. Ant colony algorithm is a swarm intelligence algorithm, which has the characteristics of distributed computing, self-organization and positive feedback, and has good robustness. Although ant colony algorithm has been applied to solve the TSP problem successfully, the existing literatures merely use the ant colony algorithm to solve the distribution routing problem. Wang ^[7] established the mixed integer programming model of inventory routing problem in the VMI (Vendor Managed Inventory) mode and designed an improved ant colony algorithm for solving the model to verify the accuracy of the model. Guo ^[8] built a model of stochastic demand inventory which took the total cost minimzation as the objective and proposed an improved ant colony algorithm to solve the model. Han ^[9] proposed a route optimization model that accords with lean logistics. Compared the ant colony algorithm with genetic algorithm, they proposed an improved ant colony algorithm that can solve the model of VRP efficiently.

Refined oil problem is a typical inventory routing problem. Due to the refined oil of each gas station is stored in the limited capacity of the tank and the vehicles that distribute refined oil to gas station are specific oil tankers, oil depot must distributes refined oil to meet the need of each gas station to avoid the case of out of stock during the process of sales. In the study of inventory routing problem of refined oil, if the gas station sales rate is constant, the amount of demand for a period of time can be determined according to the current storage capacity of the gas station. According to the capacity of distributon vehicle and the tanks, the distribution time window can be determined..In this condition, the refined oil distribution inventory routing problem is simplified as a vehicle routing problem with capacity and time window constraints. This paper studies the optimization of the refined oil distribution routing problem. The mathematical model of this problem is established and an improved ant colony algorithm is designed for solving the model.

2. Problem Description

The refined oil distribution routing problem can be described as: an oil depot supplies a certain kind of refined oil to multiple gas stations; The demand for refined oil of each gas station is knownin a given time period; Each gas station has a fixed unloading time window, the tanker mustunload oil for the gas station at the specified time window; The tankers discharging the refined oil at each gas station need to consume a certain amount of time; The tankers that distribute refined oil for gas stations are single compartment vehicles and the quantity of tankers is adequate; The load capacity, fixed cost and travel cost per unit distance of each tanker are different; Each tanker can supply the refined oil to a number of gas stations and each station can only accept a tanker for its oil supply; The average ruuning speed of each tanker is same which is 50 . The objective of the system is to make a distribution plan which has the minimum system operating cost in the case of the demand of each gas station and the distance between each gas station are known.

In the process of refined oil distribution, assuming that the tankers start from the oil depot to distribute refined oil for a number of gas stations and return to the depot after finishing the distribution tasks. The total demand for a number of gas stations with the same tanker service must not exceed the capacity of the tanker. Because each gas station can only accept a tanker for its oil supply, the discharge amount that the tanker unloads at the gas station equals to the demand of the gas station. Tanker starts to unload the refined oil when it arrives at the gas station and unloading time should be in the time window of the gas station. Each car will spend a certain time to unload the refined oil. The unloading time is proportional to the unloading amount of the refined oil, and the tanker will proceed to the next gas station immediately when the tanker completes distribution task in a gas station. Because the capacity, the fixed cost and variable cost of each tanker are different and the quantity of tankers is sufficient, it is required to select a part of the available tankers to send refined oil to the gas stations and further determine the set of gas stations that each tanker service for and the distribution route which has the minimum total cost. The distribution route of each tanker that is selected can be expressed by the ordinal of oil depot and gas stations in accordance with the distribution sequence. Such as 0-1-5-3-0 indicates that a tanker sets from the oil depot 0 and distributes refined oil for gas station 1,5,3 successively, and returns to the oil depot 0 after the distribtion task is completed.

3. Problem Formulation

Set of oil depot and gas stations, 0 represents oil depot, 1, 2… n represents gas station;

Set of tankers;

Demand for gas station;

The earliest time of gas stationto receive service;

The latest time of gas stationto receive service;

The amount of refined oil delivered to gas station by tanker;

The capacity of tanker;

The distance between gas stationand;

The time that a tanker travels from gas stationto;

Binary variable. , if tankerpasses through the edge (); , otherwise;

The required time of gas stationfor unloading oil;

The time that tanker starts to serve gas station;

The fixed cost of tanker;

Travel cost per unit distance of tanker;

Binary variable. , if tankeris used; , otherwise;

For the gas station, the main factors affecting the inventory are maximum physical volume and the pump capacity of the oil tank. In order to simplify the problem, this paper only considers meeting the needs of the gas station; do not consider the inventory holding cost of the gas station. Therefore, the total cost of the system is mainly composed of two aspects, namely, the fixed cost of the tanker and the variable cost of the tanker . The fixed cost of the tanker is related to the use of the tanker. If the tanker is used, it is required to pay a fixed fee. If the tanker is not used, it does not need to pay the fixed fee . is used to indicates whether tankeris used, that is

(1)

If the tankeris used, the fixed cost is . Therefore, the fixed cost of tankeris:

(2)

On the distribution network, the length of edgeindicates which is the distance between gas stationand. denotes the travel cost per unit distance of tanker. indicates whether the distribution route of tankerincldes edge , namely

(3)

The variable cost of the tankeris proportional to the travel distance, therefore, the variable cost of the tankeris:

(4)

The operating cost of a single tanker is. Therefore, the total operating cost of the system is:

(5)

(6)

(7)

(8)

(9)

(10)

(12)

(13)

(14)

(15)

(16)

The objective function (6) represents to minimize the total cost including the fixed cost of tankers and the variable cost of tankers running on the road;

Constraint (7) indicates that the number of tankers that are used must not exceed the number of tankers owned by the fleet;

Constraint (8) indicates that the total amount of refined oil that a tanker delivers to each gas station must not exceed the capacity of the tanker;

Constraint (9) indicates that the starting point of each tanker's distribution route must be oil depot;

Constraint (10) indicates that if a tanker drives into a gas station, it must leave the gas station when the task is completed;

Constraint (11) indicates that each gas station is serviced by only one tanker;

Constraint (12) means that the amount of refined oil that all tankers distribute to the gas station equals to its demand;

Constraint (13) indicates the relationship of arrival time between two adjacent gas stations on the same distribution route;

Constraint (14) means that the time for a tanker to arrive at gas station must be in the time window of the gas station;

Constraints (15) - (16) mean the value constraints of variables.

4. Design of the Improved Ant Colony Algorithm

An improved ant colony algorithm for solving the model will be designed in this section. The ant colony algorithm is apply in solving TSP (traveling salesman problem) widely, but the TSP problem has not considers the constraints of the time window, demand and the capacity of the vehicle. Therefore, the ant colony algorithm can not directly solve the vehicle routing optimization problemthat refers to above. In this section, an improved ant colony algorithm is designed to solve the optimization problem of the refined oil distribution route by adding the constraints of the time window, demand and the capacity of the tanker.

Step 1. Parameters initialization: the pheromone of each edge is equal at the beginning, ,, number of ants , the important degree of pheromone , the important degree of heuristic factor , the pheromone evaporation coefficient , the maximum number of iterations , the increases strength coefficient of pheromone .

Step 2. Take an ant and place it in the initial point, establish the set of unvisited pointsand tabu table.

Step 3. Caculate the tranferable points that belong toaccording to the tanker's residual load and the time window of gas stations and store these points in the matrix. Caculate the transitionprobility and select the next point by the roulette wheel method. Then delete the point from and add in the. Repeat the above operations until.

Step 4. Judge whetheris empty. If it is, turn to step 5; otherwise, turn to step 3.

Step 5. Calculate the pheromone that the ant leaves on each edge and the ant dies.

Step 6. Repeat Steps 2~5 until the caculations of all ants are completed.

Step 7. Caculate the pheromone increment of each edge and the amount of pheromone .

Step 8. Record the route of this iteration and update the current optimal route. Caculate the optimal system operating cost and clear the tabu table.

Step 9. Judge whether the number of iterations has reach the predetermined number of steps, or whether the phenomenon of stagnation appears. If it is, terminate algorithm and output the current optimal route; oterwise turn to step 2.

The specific flow chart of the improved ant colony algorithm is depicted in Figure 1.

Download as

• PPT
  PowerPoint Slide
• PNG
  Larger image(png format)

Veiw figureFigures index

•  NEW
  View larger figure in new window

View next figure

Figure 1. The flow chart of the ailgorithm

5. Example Analysis

In this paper, we take an example of1 oil depot, 10 gas stations and 5 oil tankers to verify the model and the improved ant colony algorithm. The rated capacities, the fixed and variable cost of each tanker are shown in Table 1.

The demand, unloading time and time window of each gas station are shown in Table 2.

The shortest driving distance and driving time between gas stations are shown in Table 3 and Table 4.

Table 1. The rated capacity Z, Fixed cost of use F, Variable cost of use C

Download as

PowerPoint Slide

Larger image(png format)

• Tables index

Veiw figure

View current table in a new window

View next table

Table 2. The demand Q, Unloading time S, Time window [E,L]

Download as

PowerPoint Slide

Larger image(png format)

• Tables index

Veiw figure

View current table in a new window

View previous table

View next table

Table 3. The shortest driving distance between gas stations (unit: km)

Download as

PowerPoint Slide

Larger image(png format)

• Tables index

Veiw figure

View current table in a new window

View previous table

View next table

Table 4. The shortest driving time between gas stations (unit: h)

Download as

PowerPoint Slide

Larger image(png format)

• Tables index

Veiw figure

View current table in a new window

View previous table

View next table

Firstly, the lingo programming is used to solve the problem according to the integer programming model established in this paper. After 50 hours running, the exact optimal solution of the model is obtained. The calculation result shows that four vehicles are used in the process of refined oil distribution. They are the first, second, fourth and fifth tankers respectively. The specific route of each tanker is shown as follows:

V(1): 0——2——10——0;

V(2): 0——9——4——1——0;

V(4): 0——7——5——0;

V(5): 0——6——8——3——0.

The total driving distance of all the tankers are 300 and the minimum operating cost of the system is 4287 yuan.

Then, using MATLAB programming according to the design of the improved ant colony algorithm, the approximate optimal solution of the model is got after 2 minutes running. In the approximate optimal solution, four tankers are used. They are the first, second, fourth and fifth tanker respectively. The specific route of each tanker is shown as follows:

V1: 0——2——10——0;

V2: 0——1——4——9——0;

V4: 0——5——7——0;

V5: 0——6——8——3——0.

The total driving distance of all the tankers are 300 and the minimum operating cost of the system is 4287 yuan. The specific distribution routes of each tanker are shown in Figure 2.

By comparison, it can be seen that the exact optimal solution obtained by lingo is the same as the approximate optimal solution obtained by the improved ant colony algorithm. But it takes more than 50 hours to run lingo, and the ant colony algorithm runs only 2 minutes. The improved ant colony algorithm greatly reduces the running time. Therefore, the efficiency of the improved ant colony algorithm for solving large-scale problem is more obvious. The solution obtained by the improved ant colony algorithm can be changed with the different parameters, which leads to the optimal solution of each operation may be slightly different. In this paper, we first set up the initial parameters , . Then, we discuss the influence of the parameter setting on the result by keeping one parameter constant and changing the other parameter. Each group of data experiments 10 times and takes the average value. The results are shown in Table 5.

Download as

• PPT
  PowerPoint Slide
• PNG
  Larger image(png format)

Veiw figureFigures index

•  NEW
  View larger figure in new window
• PREV
  View previous figure

Figure 2. Distribution route of each tanker

Table 5. Effect of parameters setting on ACO performance

Download as

PowerPoint Slide

Larger image(png format)

• Tables index

Veiw figure

View current table in a new window

View previous table

From Table 5, we can see that the average solution and the optimal solution is the best by setting parameters , . So we select this set of parameters to caculate. In addition, it can be seen from Table 5 that the set of different parameters values has slight influence on the optimal solution of multiple caculations. In this example, the optimal solution can be obtained when , . Therefore, in the actual calculation, we can take any group values of , to calculate several times and choose the best solution as the approximate optimal solution.

6. Conclusion

The distribution routing problem of refined oil is a key problem in the process of secondary distribution of refined oil. When formulating the refined oil distribution plan, distribution cost is one of the most important factors to consider under the premise of avoiding the gas station out of stock. This paper studies the refined oil distribution routing problem to minimize the system operating cost in consideration of the constraints of the demand and time window of each gas station under the premise of the demand is determined. An integer programming model is established with the minimum system operating cost as the objective, and the improved ant colony algorithm is designed to solve the model. Finally, the model and algorithm are verified by numerical example.

In this paper, we only consider the problem of the distribution of refined oil with determining demand under a single product, without considering the constraints of the compartment and full load of the tanker. In the actual product oil distribution, the demand of each gas station is usually a random variable, and the demand of different varieties of refined oil is different from the random variable distribution. The capacity and the number of compartments of the tanker are also different, and require full load transport. In addition, in order to simplify the problem in this paper, we assume a gas station can only be serviced by a tanker. In fact, a gas station can be serviced by multiple tankers. In the follow-up study, we will gradually consider these constraints to establish a more reality refined oil distribution routing model, and design a fast and effective algorithm for solving the model. The results will provid a theoretical basis to solve practical problems.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (11131009, 71540028), and Major Research Project of Beijing Wuzi University, High level scientific research project of Beijing Wuzi University (GJB20164005). The Funding Project of Beijing high level innovation and entrepreneurship program teaching teacher. Funding Project for Beijing Key Laboratory of Intelligent Logistics System (NO:BZ0211); FundingProject of Construction of Innovative Teams and Teacher Career Development for Universities and CollegesUnder Beijing Municipality (ID:IDHT20130517).

References

[1]	HERER Y, LEVY R. The metered inventory routing problem, an integrative heuristic algorithm [J]. International Journal of Production Economics, 1997, 51(1): 69-81.
	In article		View Article
[2]	Birger Raa, El-Houssaine Aghezzaf. A practical solution approach for the cyclic inventory routing problem [J]. European Journal of Operational Research, 2007, 1922: 429-441.
	In article
[3]	BirgerRaa.New models and algorithms for the cyclic inventory routing problem [J]. 4OR, 2008, 61:97-100.
	In article
[4]	KunpengLi, Bin Chen, AppaIyer Sivakumar, Yong Wu. An inventory–routing problem with the objective of travel time minimization [J]. European Journal of Operational Research, 2014: 936-945.
	In article
[5]	Zhao Da, Li Jun, Ma Danxiang, Li Yanfeng. Optimization algorithm for solving stochastic demand inventory routing problem with hard time window constraints [J]. Operations research and management science, 2014, 23(1): 27-37.
	In article
[6]	Zhenping Li, Zhiguo Wu.Study on the inventory routing problem of refined oil distribution based on working time equilibrium [J].American Journal of Operations Research, 2016. 6(1): 17-24.
	In article		View Article
[7]	Wang Zhe. Research on VMI Inventory Routing Optimization Based on ant colony algorithm [D].Northeastern University, 2012.
	In article
[8]	Guo Meile. Research on Stochastic Demand Inventory Routing Problem Based on improved ant colony algorithm [D]. Northeastern University, 2011.
	In article
[9]	Han Jing. Research on lean logistics path optimization based on improved ant colony algorithm [D]. Wuyi University, 2008.
	In article