论文部分内容阅读
Abstract：This paper analyzes the uncertainties of air cargo and applies revenue management to solve the problem of air cargo capacity control.A robust capacity allocation model for a multiple-leg with multiple shipment types is established，which describe uncertainty of these parameters as a number of discrete scenarios，and obtain the optimal allocation with Mutation Particle Swarm Optimization.Simulation experiments show that this method can balance uncertainty of the model effectively and accord with actual situation.
Keywords：Capacity Inventory Control；Uncertain Optimization；Robust Optimization；MPSO
1.Introduction
The revenue management technologies have been applied to air passenger transportation management successfully.Because cargos are perishable and large fixed costs while variable costs are small in the short run，the principles of revenue management also can be applied to air cargo industry.
However，the successful methods of revenue management have not been widely applied in air cargo industry.Because of the differences between cargo transportation and passenger transportation，capacity inventory control can not be used in air cargo directly.The available cargo space of a fight is affected by many uncertain factors：
（1）Cargo has different booking behavior，and cargo is a business-to-business market.Due to the complexity of the operation of cargo industry，forecasting and overbooking all include errors；
（2）Because cargo capacity is measured in weight and volume and is dependent on the number of passengers，the amount of baggage，load factor and the amount of fuel on the plane，there are lots of differences between intending demands and actual demands.
In some articles（see：Referenc-es[2][3][4]），the solutions of model have lots of defects.Gui Yunmiao and Zhu Jinfu chosen a dynamic programming [2]approach to the problem which，although theoretically very interesting，is computationally very demanding.Amaruchkul，Cooper and Gupta presented a Markov Decision Process model for a single flight with multiple shipment types [4].Because the Markov Decision Process has a high-dimensional state space，it is not practical to compute an optimal policy.With the development of airline network，the research on more complicated network capacity control is significant.So，a static but more efficient model is proposed in this paper.
2.Multiple-leg Robust Optimization Model
Due to difficulties and inconven-ience on mathematical treatment，the uncertainty is simply ignored in many cases，and the only care of uncertainty is taken by sensitivity analysis.This is a post-optimization tool for analyzing the stability of the solution. There are some uncertain approaches which handle uncertainties directly-Expected Marginal Revenue model，Chance Constrained Programming and Dependent Chance Programming，and they can resolve some problems effectively.Expected Marginal Revenue model is widely applied on capacity inventory control.However，it is only suitable for those who do not care about risk.In fact，we do not always care about the maximization of expected marginal revenue.With the problem of uncertain system parameters，we often have to consider the reliability（or risk）.Mulvey，Vanderbei and Zenios proposed the robust mathematical programming to handle uncertainty [5].Here instead of fixed data several scenarios are considered.
In order to make the model of capacity inventory control more reasonable，robust optimization which can reflect the subjective attitude of decision maker is introduced to eliminate the inaccurate factors from forecasting errors.
2.1 Stochastic Programming Model
A multiple-leg flight consists of several legs and segments.A leg is defined as one flight between a take off and the next landing.A segment is the possible itinerary a shipment takes on a number of legs of the same flight.
（1）Notation：
：Index of leg；
：Index of segment，；
：Index of market-product；
；
：Index of agent；
：The usable volume of leg i；
：The usable weight of leg i；
：Index of revenue from selling bargain-product t of agent m；
：Index of revenue from selling retail-product t；
：Index of the average piece volume from bargain-product t of agent m；
：Index of the average piece volume from retail-product t；
：If bargain-product t of agent m use leg i，，otherwise ；
：If retail-product t use leg i，then，otherwise；
：Demand for bargain-product t of agent m；
：Demand for retail-product t；
（2）Decision variables：
：Allocation for bargain-product t of agent m；
：Allocation for retail-product t；
So before signing sales agreement，the Stochastic Programming Model can be expressed as：
（1）
The constraints of gross volume and gross weight on one leg are shown as：
（2）
2.2 Robust Optimization Model
The uncertain parameters of the model can be similarly described as a number of discrete scenarios，and a candidate solution is allowed to take care of the stability of the resulting solution and to violate the “scenario realizations” of the constraints. In this case，the stochastic programming model can be translated into the following form：
（3）
Where is the decision-making factor of venture，and are the chastening factors of feasibility，they are all non-negative values. is the probability of uncertain scenario n，，，.In the objective function， is the average absolute deviation of expected revenue and revenue，the other part is the average absolute deviation of constraints.
Because of the presence of absolute values，the calculation is complex.According to the method of linear transformation [6]，the absolute value can be further transformed into：
（4）
Proof：In the problem（4），is equivalent to the form .
Observing the constraints，we have.In other words，the minimum is .When ，the value of is 0，and.When，the value of is ，and .
Therefore，the proposition is correct.
Similarly，the programming（4）is equivalent to the programming（3）.
In the case of probability of scenarios，the model has been successfully translated into determi-nistic mathematical programming model.However，instead of being increasing of goods and the complex network，the calculation is more complex.So the application of intelligent optimization algorithm is especially important.
3.Algorithm
3.1 Mutation Particle Swarm Optim-ization
Searching from a group of initial
solutions，Particle Swarm Optimization （PSO）is easier to gain the global optimal solution.Due to the impact of individual optimal values and the global optimal value，particles have astringency.If the individual optimal values and the global optimal value remain unchanged within a period of time，the algorithm is very easy to fall into local optimal solution.So the Mutation Particle Swarm Optimization is adopted to solve the problem.
（1）Mutation method：
Based on the idea of survival of the fittest，selected a part of particles which have less individual value as the mutation of particle swarm（The proportion of the mutation of particle swarm is gradually reduced from 1.0 to 0.1）.It can improve diversity of particles and avoid falling into local optimal solution.
（2）Fitness function：
Calculate the objective function value of each particle as its fit value.If the current individual fit value is superior to the individual optimal value，then set the current position as its best previous position.If the individual optimal value is superior to the global optimal value，then set the current position as the whole best previous position. （3）Update：
Positions of mutation particles are replaced by random values.Update the velocities and positions of other particles according to the following formulas：
（5）
Whereis inertia weight within the interval，is iterative number，are learning factors. is the optimal value of particle k in dimension t.is the global optimal value.
3.2 Experimental results
On the airline of PEK（Beijing）-CTU（Chengdu）-LXA（Lasa），assume that the selling bargain-products are unchangeable，and there are six kinds of market-products and three discrete scenarios.The demands and the revenues of each scenario are known.
The size of the population is 30，and the maximum iterative time is 1000.When the optimal allocation is given as the following tables：
Table 1 Optimal allocation of segment PEK-CTU
Agent Capacity Allocation（T）
F1 F2 F3 F4 F5 F6
A-1 0.5 0.03 0.02 0 0.01 0.01
A-2 0.3 0.04 0 0.01 0 0
A-3 0.58 0.35 0 0.1 0 0
A-4 2.43 4.63 0.15 0.22 0 0
A-5 1.32 0 0 0 0.02 0
Retail 1.34 0.14 0 0.04 0 0
Table 2 Optimal allocation of segment PEK-LXA
Agent Capacity Allocation（T）
F1 F2 F3 F4 F5 F6
A-1 0.01 0.06 0.25 0 0 0
A-2 0.2 0.03 0 0.04 0 0
A-3 1.28 0.8 0.03 0.17 0.01 0.3
A-4 0.37 0.52 0 0 0 0
A-5 0.82 0.09 0 0 0 0
A-6 0.13 0.01 0 0.1 0.01 0
A-7 0.01 0.06 0.25 0 0 0
Retail 0.2 0.03 0 0.04 0 0
Table 3 Optimal allocation of segment CTU-LXA
Agent Capacity Allocation（T）
F1 F2 F3 F4
A-1 0.1 0.02 0 0
A-2 0.01 0 0 0
A-3 0.17 0.03 0 0
A-4 0.02 0.02 0 0
A-5 0.32 0 0 0
Retail 0 0 0 0
3.3 Decision-making factor of ventures
The decision-making factor of venture expresses the aversion of decision-makers for risk.With the increase of decision-making factor of venture，optimal revenue gets lower and lower.The relationship between optimal revenues and chastening factors of feasibility can be seen from the following figure：
Fig.1 The relationship between optimal revenue and decision-making factor of venture
3.4 Chastening factors of feasi-bility
The chastening factors are the negation deviations of demands.These values can be used to rectify the space allocation and to meet different demands.Decision-makers can increase a certain appointed cargo by using lower chastening factor.
4.Conclusion This paper applies revenue manag-ement technology to solve the problem of air cargo capacity Inventory control.For balancing uncertain parameters，we apply robust optimization method，which based on scenario-based description，to solve stochastic programming model and obtain the optimal allocation.From the result，we can see that，this strategy can make significant progress in air cargo management.This method may produce solutions which are not feasible for realizations of the constraints，even for the scenario ones.And the approach becomes a particular case of the robust counterpart scheme.
We only researched on single-route and single flight，and ignored the transfer of demands from different flights on different routes.We hope to explore these and other related questions in the future.
References
[1]Karaesmen I Z，Three essays on Revenue Management， Columbia University，2001.
[2]Gui Yun miao and Zhu Jin fu，Research on Dynamic Model of Air Cargo Slot Inventory Control.Forecasting，2006（6）：53-04.
[3]K.Huang and W.Hsu，Revenue Management for Air Cargo Space with Supply Uncertainty，Proceedings of the Eastern Asia Society for Transportation Studies，2005：570-580.
[4]K.Amaruchkul，W.l.Cooper，D.Gupta，Single-Leg Air-Cargo Revenue Management，Working Paper，2005（3）.
[5]Mulvey J M，Vanderbei R J and Zenios S A，Robust Optimization of Large-scale System，Operations Research，1995（38）.
[6]Li H L，An Efficient Method for Solving Linear Goal Programming Problems，Journal of Optimization Theory and Application，1996.90（2）.
[7]Li Yu and Luo Li，Research on Capacity Inventory Control Model of Air cargo Revenue Management，2008（18）：68-02.
Keywords：Capacity Inventory Control；Uncertain Optimization；Robust Optimization；MPSO
1.Introduction
The revenue management technologies have been applied to air passenger transportation management successfully.Because cargos are perishable and large fixed costs while variable costs are small in the short run，the principles of revenue management also can be applied to air cargo industry.
However，the successful methods of revenue management have not been widely applied in air cargo industry.Because of the differences between cargo transportation and passenger transportation，capacity inventory control can not be used in air cargo directly.The available cargo space of a fight is affected by many uncertain factors：
（1）Cargo has different booking behavior，and cargo is a business-to-business market.Due to the complexity of the operation of cargo industry，forecasting and overbooking all include errors；
（2）Because cargo capacity is measured in weight and volume and is dependent on the number of passengers，the amount of baggage，load factor and the amount of fuel on the plane，there are lots of differences between intending demands and actual demands.
In some articles（see：Referenc-es[2][3][4]），the solutions of model have lots of defects.Gui Yunmiao and Zhu Jinfu chosen a dynamic programming [2]approach to the problem which，although theoretically very interesting，is computationally very demanding.Amaruchkul，Cooper and Gupta presented a Markov Decision Process model for a single flight with multiple shipment types [4].Because the Markov Decision Process has a high-dimensional state space，it is not practical to compute an optimal policy.With the development of airline network，the research on more complicated network capacity control is significant.So，a static but more efficient model is proposed in this paper.
2.Multiple-leg Robust Optimization Model
Due to difficulties and inconven-ience on mathematical treatment，the uncertainty is simply ignored in many cases，and the only care of uncertainty is taken by sensitivity analysis.This is a post-optimization tool for analyzing the stability of the solution. There are some uncertain approaches which handle uncertainties directly-Expected Marginal Revenue model，Chance Constrained Programming and Dependent Chance Programming，and they can resolve some problems effectively.Expected Marginal Revenue model is widely applied on capacity inventory control.However，it is only suitable for those who do not care about risk.In fact，we do not always care about the maximization of expected marginal revenue.With the problem of uncertain system parameters，we often have to consider the reliability（or risk）.Mulvey，Vanderbei and Zenios proposed the robust mathematical programming to handle uncertainty [5].Here instead of fixed data several scenarios are considered.
In order to make the model of capacity inventory control more reasonable，robust optimization which can reflect the subjective attitude of decision maker is introduced to eliminate the inaccurate factors from forecasting errors.
2.1 Stochastic Programming Model
A multiple-leg flight consists of several legs and segments.A leg is defined as one flight between a take off and the next landing.A segment is the possible itinerary a shipment takes on a number of legs of the same flight.
（1）Notation：
：Index of leg；
：Index of segment，；
：Index of market-product；
；
：Index of agent；
：The usable volume of leg i；
：The usable weight of leg i；
：Index of revenue from selling bargain-product t of agent m；
：Index of revenue from selling retail-product t；
：Index of the average piece volume from bargain-product t of agent m；
：Index of the average piece volume from retail-product t；
：If bargain-product t of agent m use leg i，，otherwise ；
：If retail-product t use leg i，then，otherwise；
：Demand for bargain-product t of agent m；
：Demand for retail-product t；
（2）Decision variables：
：Allocation for bargain-product t of agent m；
：Allocation for retail-product t；
So before signing sales agreement，the Stochastic Programming Model can be expressed as：
（1）
The constraints of gross volume and gross weight on one leg are shown as：
（2）
2.2 Robust Optimization Model
The uncertain parameters of the model can be similarly described as a number of discrete scenarios，and a candidate solution is allowed to take care of the stability of the resulting solution and to violate the “scenario realizations” of the constraints. In this case，the stochastic programming model can be translated into the following form：
（3）
Where is the decision-making factor of venture，and are the chastening factors of feasibility，they are all non-negative values. is the probability of uncertain scenario n，，，.In the objective function， is the average absolute deviation of expected revenue and revenue，the other part is the average absolute deviation of constraints.
Because of the presence of absolute values，the calculation is complex.According to the method of linear transformation [6]，the absolute value can be further transformed into：
（4）
Proof：In the problem（4），is equivalent to the form .
Observing the constraints，we have.In other words，the minimum is .When ，the value of is 0，and.When，the value of is ，and .
Therefore，the proposition is correct.
Similarly，the programming（4）is equivalent to the programming（3）.
In the case of probability of scenarios，the model has been successfully translated into determi-nistic mathematical programming model.However，instead of being increasing of goods and the complex network，the calculation is more complex.So the application of intelligent optimization algorithm is especially important.
3.Algorithm
3.1 Mutation Particle Swarm Optim-ization
Searching from a group of initial
solutions，Particle Swarm Optimization （PSO）is easier to gain the global optimal solution.Due to the impact of individual optimal values and the global optimal value，particles have astringency.If the individual optimal values and the global optimal value remain unchanged within a period of time，the algorithm is very easy to fall into local optimal solution.So the Mutation Particle Swarm Optimization is adopted to solve the problem.
（1）Mutation method：
Based on the idea of survival of the fittest，selected a part of particles which have less individual value as the mutation of particle swarm（The proportion of the mutation of particle swarm is gradually reduced from 1.0 to 0.1）.It can improve diversity of particles and avoid falling into local optimal solution.
（2）Fitness function：
Calculate the objective function value of each particle as its fit value.If the current individual fit value is superior to the individual optimal value，then set the current position as its best previous position.If the individual optimal value is superior to the global optimal value，then set the current position as the whole best previous position. （3）Update：
Positions of mutation particles are replaced by random values.Update the velocities and positions of other particles according to the following formulas：
（5）
Whereis inertia weight within the interval，is iterative number，are learning factors. is the optimal value of particle k in dimension t.is the global optimal value.
3.2 Experimental results
On the airline of PEK（Beijing）-CTU（Chengdu）-LXA（Lasa），assume that the selling bargain-products are unchangeable，and there are six kinds of market-products and three discrete scenarios.The demands and the revenues of each scenario are known.
The size of the population is 30，and the maximum iterative time is 1000.When the optimal allocation is given as the following tables：
Table 1 Optimal allocation of segment PEK-CTU
Agent Capacity Allocation（T）
F1 F2 F3 F4 F5 F6
A-1 0.5 0.03 0.02 0 0.01 0.01
A-2 0.3 0.04 0 0.01 0 0
A-3 0.58 0.35 0 0.1 0 0
A-4 2.43 4.63 0.15 0.22 0 0
A-5 1.32 0 0 0 0.02 0
Retail 1.34 0.14 0 0.04 0 0
Table 2 Optimal allocation of segment PEK-LXA
Agent Capacity Allocation（T）
F1 F2 F3 F4 F5 F6
A-1 0.01 0.06 0.25 0 0 0
A-2 0.2 0.03 0 0.04 0 0
A-3 1.28 0.8 0.03 0.17 0.01 0.3
A-4 0.37 0.52 0 0 0 0
A-5 0.82 0.09 0 0 0 0
A-6 0.13 0.01 0 0.1 0.01 0
A-7 0.01 0.06 0.25 0 0 0
Retail 0.2 0.03 0 0.04 0 0
Table 3 Optimal allocation of segment CTU-LXA
Agent Capacity Allocation（T）
F1 F2 F3 F4
A-1 0.1 0.02 0 0
A-2 0.01 0 0 0
A-3 0.17 0.03 0 0
A-4 0.02 0.02 0 0
A-5 0.32 0 0 0
Retail 0 0 0 0
3.3 Decision-making factor of ventures
The decision-making factor of venture expresses the aversion of decision-makers for risk.With the increase of decision-making factor of venture，optimal revenue gets lower and lower.The relationship between optimal revenues and chastening factors of feasibility can be seen from the following figure：
Fig.1 The relationship between optimal revenue and decision-making factor of venture
3.4 Chastening factors of feasi-bility
The chastening factors are the negation deviations of demands.These values can be used to rectify the space allocation and to meet different demands.Decision-makers can increase a certain appointed cargo by using lower chastening factor.
4.Conclusion This paper applies revenue manag-ement technology to solve the problem of air cargo capacity Inventory control.For balancing uncertain parameters，we apply robust optimization method，which based on scenario-based description，to solve stochastic programming model and obtain the optimal allocation.From the result，we can see that，this strategy can make significant progress in air cargo management.This method may produce solutions which are not feasible for realizations of the constraints，even for the scenario ones.And the approach becomes a particular case of the robust counterpart scheme.
We only researched on single-route and single flight，and ignored the transfer of demands from different flights on different routes.We hope to explore these and other related questions in the future.
References
[1]Karaesmen I Z，Three essays on Revenue Management， Columbia University，2001.
[2]Gui Yun miao and Zhu Jin fu，Research on Dynamic Model of Air Cargo Slot Inventory Control.Forecasting，2006（6）：53-04.
[3]K.Huang and W.Hsu，Revenue Management for Air Cargo Space with Supply Uncertainty，Proceedings of the Eastern Asia Society for Transportation Studies，2005：570-580.
[4]K.Amaruchkul，W.l.Cooper，D.Gupta，Single-Leg Air-Cargo Revenue Management，Working Paper，2005（3）.
[5]Mulvey J M，Vanderbei R J and Zenios S A，Robust Optimization of Large-scale System，Operations Research，1995（38）.
[6]Li H L，An Efficient Method for Solving Linear Goal Programming Problems，Journal of Optimization Theory and Application，1996.90（2）.
[7]Li Yu and Luo Li，Research on Capacity Inventory Control Model of Air cargo Revenue Management，2008（18）：68-02.