Received 2 February 2016; accepted 16 April 2016; published 19 April 2016
Among traditional energy, human beings have used oil widely for only 100 years. However, with the development of modern society, oil, as a kind of strategic resources, has a great influence on the development of politics, economy and society. Crude oil cannot be used directly before refining. Petrol or some other fuel can be produced in refinery. Petrol consumption is the main form of oil consumption. It is also the most closely part related to the end of industrial chain  .
Petrol distribution can be divided into primary distribution and secondary distribution (Figure 1). The process of petrol transportation from refineries to depots is called primary distribution and the process of petrol transportation from depots to petrol stations or other terminal customers is called secondary distribution. The main participants of petrol secondary distribution are dispatching center, depots, carriers and petrol stations. As shown in Figure 2, dispatching center forecasts the replenishment quantity every day based on the sales data received from petrol stations, then base on the information of depots and vehicles, the dispatching plan is generated which would be executed by carriers.
Being the end of the petrol supply chain, the petrol sold by petrol stations is of great significance to the social and economic operation and development. Series of loses will be caused when stock out appeared in a petrol station. At the same time, when the petrol supply is less than the demand of all petrol stations, some petrol stations can’t avoid stock out and produce shortage costs. In this case, managers of the dispatching center have to consider the problem: how to make an appropriate dispatching plan so as to minimize the total cost including transportation cost and shortage cost?
Due to the different economic and social environment each petrol station confronts, the unit shortage cost of each petrol station is also different. People in the urban area have higher incomes than those in the suburban and countryside, so the unit shortage cost of petrol stations in the urban area is larger than that in the suburban and countryside. For example, enterprise would lose 20 Yuan when 1 L out of stock happened within 1 hour in the urban district, but 5 Yuan in the suburban. Therefore, beside the transportation cost, manager must take the shortage cost into consideration.
Because the unit shortage cost of different petrol station is different, when the supply is insufficient, dispatching plan should firstly meet the demand of petrol stations whose unit shortage cost are larger. Since the duration of shortage is another remarkable influential factor, so the time point of stock out need to be considered in making the dispatching plan. The earlier time point of stock out is, the longer duration of shortage and the more cost of shortage is. Conversely, the later time point of stock out is, the shorter duration of shortage and the less cost of shortage is. Generally, the time point of stock out can be calculated according to the inventory levels every morning and the sales rate of each petrol station.
All kinds of petrol sold by petrol station is stored in the oil tanks, each oil tank has an inventory holding capacity. There are two constraints to be satisfied when calculating the replenish quantity. The first is to ensure that the petrol station can avoid stock out, the second is to ensure that the petrol station has enough empty tank capacity to accommodate the replenishment quantity. The minimum replenishment quantity that can avoid stock out is called the lower bound. The maximum replenishment quantity that the petrol station’s tank can accom-
Figure 1. Primary distribution and secondary distribution.
Figure 2. Procedure of secondary distribution.
modate is called the upper bound. The reality replenishment quantity cannot be less than the lower bound to guarantee no shortage and cannot be exceed the upper bound for the inventory capacity limit. When the sales rate is a constant, the upper bound minus the lower bound exactly equals the inventory holding capacity.
Because petrol is highly combustible and hazardous, special compartment transport vehicle need to be used in the secondary distribution. During the delivery process, compartment vehicle must be fully loaded to avoid the dangerous caused by the fluid shake.
Beside the transportation cost, shortage cost and full loaded requirement also need to be taken into consideration. Therefore, the petrol secondary distribution problem is different from the traditional transportation problem   where no full loaded requirement included and the shortage cost is not considered. In traditional transportation problem, the objective function is to minimized the total transportation cost, while in petrol secondary distribution problem, the objective function is to minimized the total cost including transportation cost and shortage cost. In recent years, scholars have studied the expansion of traditional transport problems. Yuan et al.  took loading capacity constraints into consideration when studying the traditional transportation problem. Liu et al.  provided a method to solve the transportation problem with punishment fee. A method for solving the minimum cost transportation problem with time limited was provided by Li et al.   . Zeng  made the demand, delivery price and supply quantity as interregional number for the uncertainty. Han  transferred the transportation problem to a kind of linear integer programing and proved it theoretically. Hu  introduced and modeled satisfaction optimization transportation problem aiming at maximizing the relative equalities among the members. Wu  discussed the multi-objective fuzzy transportation problem with three types of transshipment. Rani  proposed a method to solve the fully fuzzy unbalanced transportation problem in which the total availability production is more than the total demand. Aizemberg  proposed a column generation-based heuristic to find good feasible solutions of a crude oil transportation problem by tankers. Object functions and constrains of these patulous transportation problems are not same as the problem in this paper, so we cannot use the models and methods directly to solve petrol secondary distribution problem.
Although many researchers have focused on traditional transportation problem, they have paid little attention on the petrol secondary distribution problem with considering shortage cost. In practical, because the demand quantity of each oil station is random and the supply quantity of each oil depot is limited, insufficient supply of oil depots often happens. However, there are few methods to deal with this problem in the feel management information system or dispatching system. So investigating the models and algorithms of this problem is important.
In this paper, the petrol secondary distribution problem with insufficient supply is studied. A mathematical model to minimize the total cost is established, and relational simulation is done on an example. The remainder of this paper is organized as follows. Section 2 describes the problem and formulates it into a mathematical model. The simulation on an example is given in section 3. Section 4 contains the conclusions of this work.
2. Mathematical Model of the Petrol Secondary Distribution Problem
2.1. Problem Description
Assume that there are n petrol stations in an area whose petrol is delivered from m depots. The available inventory of each depot, the upper and lower bounds of each station’ soil tank are known. Assume that the petrol must be delivered from depots to petrol stations by full loaded compartment vehicles, and the petrol in one compartment must be fully unloaded into one oil tank rather than separated to multiple oil tanks. There are k kinds of vehicles whose compartments capacity are known, each kind of vehicles are sufficient. The time point of stock out, the unit shortage cost of each station and the unit transportation cost from each depot to every station are known. The question is how to arrange the transportation plan so as to minimize the total cost.
2.2. Mixed Integer Programming Model
To establish the mathematical model of the problem, some symbols and variables are defined as follows, where:
: unit transportation cost from depot i to station j;
: compartment capacity of vehicle type r;
: unit shortage cost of station j;
: time point of stock out of station j;
: upper bound of replenishment quantity in station j;
: lower bound of replenishment quantity in station j;
: available supply of depot i;
: shortage volume of station j;
: number of vehicles of type r transport from depot i to station j.
Similar to other transportation problem, petrol secondary distribution problem can be formulated into the following mixed integer programing model:
Object function (1) minimizes the total cost of the petrol secondary distribution. In the objective function, the first item represents the total transportation cost and the second item is the total shortage cost where is the shortage duration of station j.
Constraints (2) ensure that the total petrol departed from depot i cannot exceed the supply capacity of it. Constraints (3) mean that the sum of oil transported to oil station j plus the shortage volume of oil station j is no less than the lower bound of station j. Constraints (4) guarantee that the sum of oil transported to oil station j is no more than the upper bound of station j. Constrains (5) and (6) are the illustrations of variables.
2.3. Solving Method
There are many methods to solve traditional transportation problem. Generally, the simplex method and some special methods like table dispatching method, shortest path algorithm and minimum cost max-flow method can be used to solve the standard transportation problem  . There are some improved methods to solve the extended transportation problem. All the methods are not suitable to solve the model in this paper.
Since the standard transportation problem is a linear programming (LP), while the model of petrol secondary transportation is a mixed integer programing, whose objective function and constraints are more complexity than those of standard transportation problem. Since the model of this paper is more complexity, it is coded on Lingo 11.0 and solved directly. All the experiments are completed on the same computer. The main configurations of the computer are given in Table 1.
3. Simulation Results
In this section, we do simulation on an example to validate the model and obtain an optimal dispatching plan.
3.1. Example Description
There is a company selling petrol 92# in an area. The petrol is stored in 3 depots and sold by 4 petrol stations. Each depot has only one oil tank to store the petrol. Current inventory and safety inventory of each depot are
Table 1. Main configurations of the computer.
listed in Table 2, where the available inventory of each depot equals current inventory minus safety inventory. Each station has multiple oil tanks whose sales rates are constants and the average sale quantity of each oil tank per day is known. The time point of stock out in each oil tank can be calculated by known parameters. The inventory capacity and pump-stop inventory (which cannot be used for selling) of each oil tank are known and the lower bounds of replenishment can be calculated by the following formulation:
Based on the lower bounds calculated above, the upper bounds can be obtained by the following expression:
The information of each oil tank in every station is listed in Table 3.
There are 3 types of compartment vehicles delivering petrol from depots to stations, the compartment capacity of each type of vehicles are listed in Table 4. The number of each type of compartment vehicle is sufficient.
The unit transportation costs from each depot to every station are listed in Table 5. In this paper, we assume that the unit shortage cost equals the profit of selling one-liter petrol, which is 2.5 Yuan per liter per hour.
3.2. Simulation Results
Base on the information above, we build the mathematical model of the problem and solve it by Lingo 11.0 software. The computation results are shown in Table 6. The third column represents from which oil depot, using what kind of compartment vehicles, loading how many compartments petrol, deliver for the target station’s oil tank. For instance, 2/2/1 in the last row means that 1 compartment’s petrol of the compartment vehicle type 2 is delivered from depot 2 to oil tank 2 of station 4. The shortage quantity of each oil tank after having executed dispatching plan is listed in the last column.
Because the total available supply is less than the sum of replenishment lower bounds, shortage might happen in some petrol stations. The time point of stock-out instation 1 is later than others, so no delivery to station 1 in the optimal dispatching plan. Notice that the shortage volumes are disequilibrium and stock-out mostly happened in petrol stations which have less sales. Due to the Equation (7), less sales means less lower bounds. Therefore, the dispatching plan tries to ensure the demands of petrol stations which have a larger market other than the less sales ones. Because of the insufficient supply, among the stations which receive replenishment, the actual replenishment amount does not exceed the lower bound of replenishment lot. The actual amount of replenishment in the optimal dispatching plan is to meet the minimum replenishment quantity. The total cost of the plan in this instance is 171,000.00 Yuan.
With the development of economy, the demand of petrol will increase. But the scarcity of resources will lead to short supply. In this case, a reasonable dispatching plan should be made to reduce the total cost. In this paper we study the petrol secondary distribution problem as a special instance of transportation problem considering deliver cost and shortage cost. Considering the full loading requirement, a mixed integer programing model is built. Through a concrete example, simulation for validation of the model is done and a reasonable dispatching plan is obtained. Results show that the optimal plan can reduce the total cost.
Transportation problem with insufficient supply and compartment full loading constraints is an extension of the standard transport problem, which meet the petrol secondary distribution problem. Actually, the reality problem is more complex than our model since it has much more constrains. In this paper, dimensionality reduc-
Table 2. Depot’s information (L).
Table 3. Information of oil tank in each station (L).
Table 4. Compartment capacity (L).
Table 5. Unit transportation cost (Yuan/L).
Table 6. Computation results.
tion methods are used to simplify the problem. For instance, some constraints such as vehicle number limits and traffic capacity of each station are ignored. Also in the computation experiment, the profit of selling one-liter petrol is used as the unit shortage cost of each station, which might cause errors. In the future, we will consider the vehicle number limits, analyze the unit shortage cost, and further consider the problem with stochastic demand, in order to design an ideal algorithm for solving the large-scale petrol secondary transportation problem.
This work was supported by the National Natural Science Foundation of China (11131009, 71540028, F012408), the Funding Project for Academic Human Resources Development in Institutions of Higher Learning under the Jurisdiction of Beijing Municipality (CIT&TCD20130327), Beijing Key Laboratory (No: BZ0211), Beijing Intelligent Logistics System Collaborative Innovation Center and Major Research Project of Beijing Wuzi University.
 Hitchcock, FL. (1941) The Distribution of a Product from Several Sources to Numerous Locations. Journal of Mathematics and Physics, 20, 224-230. http://dx.doi.org/10.1002/sapm1941201224
 Zeng, J., Zhang, X. and Ye, J. (2008) An Interval Programming Model and Algorithm for Transportation Problem. Journal of Sichuan University of Science & Engineering (Natural Science Edition), 21, 30-32.
 Rani, D., Gulati, T.R. and Kumar, A. (2014) A Method for Unbalanced Transportation Problems in Fuzzy Environment. Indian Academy of Sciences, 39, 573-581. http://dx.doi.org/10.1007/s12046-014-0243-8
 Aizemberg, L., Kramer, H., Pessoa, A. and Uchoa, E. (2014) Formulations for a Problem of Petroleum Transportation. European Journal of Operational Research, 39, 573-581.