Methodology Article
Full Load Distribution Scheduling Problem for Refined Oil
Xiaocun Mao, Xinxin Zhang, Zhenping Li
School of Information, Beijing Wuzi University, Beijing, China
Email address:
To cite this article:
Xiaocun Mao, Xinxin Zhang, Zhenping Li. Full Load Distribution Scheduling Problem for Refined Oil. Science Journal of Applied Mathematics and Statistics. Vol. 4, No. 5, 2016, pp. 183-188. doi: 10.11648/j.sjams.20160405.11
Received: June 27, 2016; Accepted: August 13, 2016; Published: August 25, 2016
Abstract: This paper presents solution approaches for the multi-period multi-compartment Vehicle Routing Problem in fuel delivery. Multi-compartment vehicles are used for fuel distribution from one depot to a set of petrol stations that have deterministic fuel consumption of each hour. Due to the highly complicated assignment compartments of the same vehicle to petrol stations in full load distribution scheduling problem, a heuristic method will be adopted to solve this problem. By means of a case study, the heuristic developed is shown to be very effective in solving such comprehensive full load distribution scheduling problem for refined oil, and the results obtained are promising.
Keywords: Vehicle Routing Problem, Full-Load, Multi-period Delivery, Heuristics Algorithm
1. Introduction
With the improvement of living standard and the development of economy, refined oil became the necessities of daily life and Chinese refined oil market continues to grow. The efficiency and quality of the refined oil distribution affect enterprise's service level and income. In the distribution process of refined oil, the key to cost control and enhance the competitiveness of enterprises is the optimal scheduling problem of logistics distribution vehicles [1]. Since refined oil belong to dangerous chemicals, its distribution has to meet the requirement of vehicles fully loaded. Study on the distribution problem of finished oil has important significance to enhance the competitiveness of enterprises’ refined oil distribution.
In this paper, taking the lowest cost of distribution as the goal to plan the delivery path of each vehicle that ensures each gas station is not out of stock in business hours. Vehicle load as an objective function for VRP has not received much attention. Most of the VRP studied in the literature are focus on the minimization distance [2]. Song and Kong (2012) studied the VRP routing selection based on time-varying network, which the shortest path doesn’t necessarily bring about last time [3]. Ghahremani-Gol, H. et al. (2016) proposed to minimum cost of total consumed energy of VRP in three dimensional space [4]. Nouveaux, FV and Salazar-Gonzalez. JJ (2016) considered the vehicle routing problem have as objective minimize a function of the acquisition cost and travelled distance, in which vehicle capacity can be selected [5]. Though load flow is considered in the objective function of a VRP, it is represented as a step function [6]. Luo et al. (2015) studied the multi-period VRP with time windows and limited visiting quota of different vehicles over the planning horizon [7]. Mildred V. et al. (2014) proposed a mixed integer programming model for a heuristic approach and without fleet size costs to solve the multi-product multi-period Inventory Routing Problem in fuel delivery [8]. Yang et al. (2015) proposed an environmental routing optimization problem with time windows and multiple vehicle types, in which the vehicle speed and load capacity affect the operation cost and environmental pollution [9]. Fernando B. O. et al. (2016) studied the multi-depot vehicle routing problem, which is decomposed into a single depot VRP and evolves independently in its domain space, to minimize the total route cost [10]. The vehicle routing problem, which involves assigning a fleet of multi-compartment limited capacity vehicles to serve a set of petrol stations without violating the capacity and full load constraints, has been increasingly discussed in practice recently.
In this paper, total vehicles cost, which is a function of total transportation without considering distance, is minimized. The novelty of this paper is to solve the vehicle routing problem with full-load limitation constraints on the multi-period delivery operation performance. Due to the highly complicated assignment compartments of the same vehicle to petrol stations in full load distribution scheduling problem, the problem cannot be solved analytically. Hence, a heuristic approach with fleet size costs is developed to solve the multi-compartment multi-period Vehicle Routing Problem in fuel delivery.
2. Problem Description
In this paper, the process of gas oil distribution from the depot to each gas station is the background of research. In consideration of the refined oil is classified as dangerous goods. The delivery has to meet the requirement of vehicles fully loaded. That means each compartment of vehicles need full of refined oil when the vehicle starting from the depot; meanwhile, all refined oil which installed in the same compartment must be unloaded to one gas station at once(which can’t be divided into two or more than two gas station at different time); the refined oil in each compartment of the same vehicle can be discharged to different gas stations; the optimization of full-load distribution routing problem for refined oil which with multi-period distribution cost minimum as the objective can be described as: There are stations in a city which selling the same kind of oil products from the same oil depot. The effective volume of every gas station is. The depot has two types of delivery vehicles that single compartment vehicle and double compartment vehicle. The single compartment vehicle has only one compartment which capacity is 8000L and the double compartment vehicle has two compartments which have the same capacity of 10000L. The number of each type vehicle is adequate. The transportation cost of each vehicle is known. During the business hour from to , the gas station can be delivered. How to arrange the distribution plan and the distribution path of each vehicle to minimize distribution cost under each gas station is not out of stock.
If the arriving time of distribution vehicle is later than the latest time (which is the shortage time) of the gas station, it will make the gas station being out of stock, so it is not allow that the arriving time of the delivery vehicle later than the latest time of each gas station. Assuming that all delivery vehicles are parked at the depot, vehicles starting from the depot and end to the depot. From the oil depot to each gas station, as well as each gas stations the shortest travel time is . Take no consideration of the loading and unloading time of delivery vehicles at the depot or the gas station. Assume that per hour sales of each gas station during business hours are constant .
3. Heuristic Algorithm
• Several definitions are given as follows:
In order to simplify the solving method, we chose to check the inventory at the whole point and delivery at the whole point, when determining the distribution plan.
Must Distribution Point: check the physical inventory of the gas station of the whole point; round of current physical inventory which is divided by hourly consumption is equal to1, the gas station is defined as must distribution point.
Stock Point: the moment time for physical inventory is less than the hourly consumption of the gas station. To ensure that unloading before the gas station is out of stock, we need an hour in advance to determine the distribution vehicle for the gas station. That is, to ensure the gas station being out of stock, it’s time to delivery for the gas station, otherwise the next period of time will appear in the phenomenon of gas station being out of stock.
Time Window: the current time for the earliest time points to make delivery for the gas station. To ensure the gas station being out of stock, the latest time point for the distribution is . So the time window for delivery to the gas station is [,].
Combined with the actual characteristics of the problem, the following heuristic algorithm is designed for solving the problem. Objective function of the model is to minimize distribution costs under the situation of gas station not being out of stock, which means delivery vehicles can unload before the gas station being out of stock, so given priority to unload at the time of gas station being out of stock as much as possible. Secondly, there are fixed costs for each vehicle, it is wise to send vehicles as little as possible. Unit transportation cost of double compartment vehicle is far lower than the single compartment vehicle, so it should minimize the number of single compartment vehicles.
• The steps of heuristic algorithm:
Input: The effective volume of each gas station , the amount of per hour sales of each gas station , at the time of whole point, the initial physical inventory when , the capacity of each vehicle , single-trip costs for per vehicle; closing time of gas stations;
Step 0: Initialization
The departure time of vehicle k from the oil depot is, the current position of vehicles are oil depot , the initial time is , the beginning of the business time for gas station is ; To determine whether the initial inventory of the various stations is greater than consumption per hour, and if so, at time do not send any vehicles, go to step 1.
Step 1: In operating time, make a distribution plan for the time . According to the physical inventory of gas stations at time t, calculate the follow-up time point set of gas station being not out of stock, to determine whether there is of all gas stations, and if so, go to step2; otherwise, do not to send any vehicles; update the next time physical inventory of each gas station, .
Step 2: If , do not send any vehicles, terminate the algorithm; otherwise, , go to Step 3.
Step 3: Calculate the amount of oil that can be accepted in the gas station and select the appropriate vehicles for distribution. According to the effective volume and the current physical inventory of the gas station, calculate the amount of reception at Must Distribution Point, to determine whether the amount of reception is greater than the capacity of the double compartment vehicles, if so, choose a double compartment vehicle for the distribution and unload all of the refined oil to the gas station; otherwise, go to step 4.
Step 4: To determine whether the amount of receiving is more than 10000L and less than 20000L, and if so, turn Step 5; otherwise, go to Step 6.
Step 5: To determine whether there is a single compartment of double compartment vehicles which has been sent at time full-loaded, if so, give priority to choose another compartment of the double compartment vehicle to unload all refined oil of one compartment to this gas station; otherwise, go to Step 6.
Step 6: Consider the distribution plan of time , if not, select the single compartment vehicle for distribution; otherwise, give priority to select the double compartment vehicle to unload one compartment refined oil for the gas station, go to Step 1.
Output: The physical inventory of gas stations in time of whole point; vehicle distribution plan; the total transportation costs.
The heuristic algorithm for solving the problem of refined oil distribution plan is coded by Java programming to realize. The initial state is given, according to the constraint conditions of heuristic algorithm to obtain the distribution plan of each vehicle at each whole time point. The objective of the model is determined, which focus on the distribution plan of each whole time point, so two for loops are used to constrain the time and gas stations. The implementation environment of the heuristic algorithm is: java version "1.8.0_91", Java (TM) SE Runtime Environment (build 1.8.0_91-b15). The main configurations of the computer are given in Table 1.
CPU | RAM | OS | ||
Model | Clock Speed | L3 Cache | ||
Intel Core i3 | 2.53GHz | 3MB | 2GB | Microsoft Windows 7 |
The flow chart of heuristic algorithm is as follows:
4. Instance and Result
There are five stations in a city which selling the same kind of oil products from the same oil depot. The depot has two types of delivery vehicles which start working at 7:00 in the morning every day. Between the depot and various stations as well as each station that travelling time is 1h. The information of the gas station and an oil tank is shown in Table 2 the capacity information of each vehicle is shown in Table 3. Vehicles can unload oil from 8:00 to 22:00. Make a distribution program of the lowest distribution cost under each gas station is not out of stock.
Name of gas station | Tank information (With L as a unit) | ||
Effective volume | Sales per hour | 8 o'clock Physical inventory | |
S1 | 17000 | 2000 | 8010 |
S2 | 17000 | 3000 | 6008 |
S3 | 19000 | 5000 | 15015 |
S4 | 40000 | 8000 | 16020 |
S5 | 26500 | 4000 | 26009 |
Vehicle model | Capacity | Single freight | |
Single compartment vehicle | 8000L | 100yuan | |
Double compartment vehicle | 10000L | 10000L | 120yuan |
The solving process of the heuristic algorithm is as follows:
Name of gas station | Physical inventory | 8 o'clock Amount receivable | Time set of not being out of stock |
S1 | 8010 | 8990 | {8,9,10,11} |
S2 | 6008 | 10992 | {8,9} |
S3 | 15015 | 3985 | {8,9,10} |
S4 | 16020 | 23980 | {8,9} |
S5 | 26009 | 491 | {8,9,10,11,12,13} |
Initial inventory of each gas station is shown in table 4. Compare the initial stock of each gas station and the consumption per hour, when the number of elements in the set of time points is equal to 1, the gas station will be a Must Distribution Point. Table 4 shows that there is no Must Distribution Point, so it doesn’t send vehicles at 7 o’clock and update the physical inventory of the next time. Similarly, send no vehicles at 8 o’clock and update the physical inventory of the next time (see in Table 5).
Name of gas station | Physical inventory | 10 o'clock Amount receivable | Time set of not being out of stock |
S1 | 6010 | 12990 | {9,10,11} |
S2 | 3008 | 16992 | {9} |
S3 | 10015 | 13985 | {9,10} |
S4 | 8020 | 39980 | {9} |
S5 | 22009 | 8491 | {9,10,11,12,13} |
According to the criteria, the gas station S4 and S2 are Must Distribution Points. At 10 o'clock gas station S2 can receive more than 10000L less than 20000L refined oil, so to send one double compartment vehicle to S2, and unload one compartment refined oil of the double compartment vehicle. The amount of reception of gas station S2 for the next time is more than 20000L, so to send one double compartment vehicle to S2, and unload the refined oil of two compartments. Then update the physical inventory of the next time (see in Table 6).
Name of gas station | Physical inventory | 11 o'clock Amount receivable | Time set of not being out of stock |
S1 | 4010 | 12990 | {10,11} |
S2 | 10008 | 9992 | {10,11,12} |
S3 | 5015 | 18985 | {10} |
S4 | 20020 | 27980 | {10,11,12} |
S5 | 18009 | 12491 | {10,11,12,13} |
According to the criteria, the gas station S3 is a Must Distribution Point. At 11 o'clock gas station S3 can receive more than 10000L less than 20000 L refined oil and there is one compartment refined oil remained of the last time, so to unload refined oil of another compartment of the double compartment vehicle to S3 which come from S2, and update the physical inventory of the next time as usual and so on.
Similarly, and so that the physical inventory of the whole point can be obtained in Table 7, the vehicle distribution plan during in the whole point of Business time can be seen in Table 8. According to the above algorithm and run Java programs, there are 12 double compartment vehicles and 1 single compartment vehicle in the distribution plan. The minimum distribution cost is 1540 yuan and the results indicate that the proposed method is effective.
5. Conclusion
In this paper, we have developed an effective heuristic method to solve the full load distribution scheduling problem of refined oil. Due to the limitations of this paper, some factors such as multiple products, inventory cost, etc. are not considered. So considering these factors would help the multi-period multi-compartment Vehicle Routing decision made more realistically. In addition, the sales of per hour of each gas station are random in practical problems. So the actual demand of each gas station per hour is random. That means the gas station may be out of stock under the original distribution plan.
The inadequacies of this article lie in the problem is too much simplified, such as the assumption that the volume is constant, between each gas station and depot the travel time is 1 hour, check the inventory of each gas station and make delivery to each gas station only at the whole point. And use the heuristic algorithm to solve the problem without compared to other algorithms. There is no detailed analysis of the time complexity and space complexity. In a subsequent study, we will gradually remove various simplifying assumptions, model and algorithm will be designed more in line with the actual situation.
Acknowledgements
This work was supported by the National Natural Science Foundation of China (71540028, F012408), the Funding Project of Beijing high level innovation and entrepreneurship program teaching teacher, Beijing Key Laboratory (NO: BZ0211), Beijing Intelligent Logistics System Collaborative Innovation Center and Major Research Project of Beijing Wuzi University.
References