RMOL Logo Get Revenue Management Optimisation Library at SourceForge.net. Fast, secure and Free Open Source software downloads

Overbooking.cpp

Go to the documentation of this file.
00001 // //////////////////////////////////////////////////////////////////////
00002 // Import section
00003 // //////////////////////////////////////////////////////////////////////
00004 // C
00005 #include <assert.h>
00006 // STL
00007 #include <iostream>
00008 // GSL
00009 #include <gsl/gsl_sys.h>
00010 #include <gsl/gsl_math.h>
00011 #include <gsl/gsl_sf.h>
00012 #include <gsl/gsl_randist.h>
00013 #include <gsl/gsl_cdf.h>
00014 // RMOL
00015 #include <rmol/basic/BasConst_Overbooking.hpp>
00016 #include <rmol/bom/Overbooking.hpp>
00017 
00018 namespace RMOL {
00019 
00020   // //////////////////////////////////////////////////////////////////////
00021   Overbooking::Overbooking () :
00022     _overbookingPercentage (DEFAULT_OVERBOOKING_OVERBOOKING_PERCENTAGE),
00023     _capacity (DEFAULT_OVERBOOKING_CAPACITY), 
00024     _netBookings (DEFAULT_OVERBOOKING_NET_BOOKINGS),
00025     _loadFactor (DEFAULT_OVERBOOKING_LOAD_FACTOR),
00026     _noShowDistributionParameters (FldDistributionParameters (DEFAULT_OVERBOOKING_MEAN, 
00027                                                               DEFAULT_OVERBOOKING_STANDARD_DEVIATION)),
00028     _cancellationDistributionParameters (FldDistributionParameters (DEFAULT_OVERBOOKING_MEAN, 
00029                                                                     DEFAULT_OVERBOOKING_STANDARD_DEVIATION)),
00030     _remainingCancellationDistributionParameters (FldDistributionParameters (DEFAULT_OVERBOOKING_MEAN, 
00031                                                                              DEFAULT_OVERBOOKING_STANDARD_DEVIATION)),
00032     _demandDistributionParameters (FldDistributionParameters (DEFAULT_OVERBOOKING_MEAN, 
00033                                                               DEFAULT_OVERBOOKING_STANDARD_DEVIATION)) {
00034   }
00035 
00036   // //////////////////////////////////////////////////////////////////////
00037   Overbooking::Overbooking (const Overbooking& iOverbooking) :
00038     _overbookingPercentage (DEFAULT_OVERBOOKING_OVERBOOKING_PERCENTAGE),
00039     _capacity (DEFAULT_OVERBOOKING_CAPACITY), 
00040     _netBookings (DEFAULT_OVERBOOKING_NET_BOOKINGS),
00041     _loadFactor (DEFAULT_OVERBOOKING_LOAD_FACTOR),
00042     _noShowDistributionParameters (FldDistributionParameters (DEFAULT_OVERBOOKING_MEAN, 
00043                                                               DEFAULT_OVERBOOKING_STANDARD_DEVIATION)),
00044     _cancellationDistributionParameters (FldDistributionParameters (DEFAULT_OVERBOOKING_MEAN, 
00045                                                                     DEFAULT_OVERBOOKING_STANDARD_DEVIATION)),
00046     _remainingCancellationDistributionParameters (FldDistributionParameters (DEFAULT_OVERBOOKING_MEAN, 
00047                                                                              DEFAULT_OVERBOOKING_STANDARD_DEVIATION)),
00048     _demandDistributionParameters (FldDistributionParameters (DEFAULT_OVERBOOKING_MEAN, 
00049                                                               DEFAULT_OVERBOOKING_STANDARD_DEVIATION)) {
00050   }
00051 
00052   // //////////////////////////////////////////////////////////////////////
00053   Overbooking::Overbooking (const FldOverbookingPolicy& iPolicy) :
00054     _policy (iPolicy),
00055     _overbookingPercentage (DEFAULT_OVERBOOKING_OVERBOOKING_PERCENTAGE),
00056     _capacity (DEFAULT_OVERBOOKING_CAPACITY), 
00057     _netBookings (DEFAULT_OVERBOOKING_NET_BOOKINGS),
00058     _loadFactor (DEFAULT_OVERBOOKING_LOAD_FACTOR),
00059     _noShowDistributionParameters (FldDistributionParameters (DEFAULT_OVERBOOKING_MEAN, 
00060                                                               DEFAULT_OVERBOOKING_STANDARD_DEVIATION)),
00061     _cancellationDistributionParameters (FldDistributionParameters (DEFAULT_OVERBOOKING_MEAN, 
00062                                                                     DEFAULT_OVERBOOKING_STANDARD_DEVIATION)),
00063     _remainingCancellationDistributionParameters (FldDistributionParameters (DEFAULT_OVERBOOKING_MEAN, 
00064                                                                              DEFAULT_OVERBOOKING_STANDARD_DEVIATION)),
00065     _demandDistributionParameters (FldDistributionParameters (DEFAULT_OVERBOOKING_MEAN, 
00066                                                               DEFAULT_OVERBOOKING_STANDARD_DEVIATION)) {
00067   }
00068 
00069   // //////////////////////////////////////////////////////////////////////
00070   Overbooking::~Overbooking() {
00071   }
00072 
00073   // //////////////////////////////////////////////////////////////////////
00074   const std::string Overbooking::describeShortKey() const {
00075     std::ostringstream oStr;
00076     oStr << _policy;
00077     return oStr.str();
00078   }
00079   
00080   // //////////////////////////////////////////////////////////////////////
00081   const std::string Overbooking::describeKey() const {
00082     return describeShortKey();
00083   }
00084 
00085   // //////////////////////////////////////////////////////////////////////
00086   std::string Overbooking::toString() const {
00087     std::ostringstream oStr;
00088     oStr << describeShortKey()
00089          << ", " << _policy << ", " << _overbookingPercentage
00090          << ", " << _capacity  << ", " << _netBookings
00091          << ", " << _loadFactor
00092          << ", " << _noShowDistributionParameters
00093          << ", " << _cancellationDistributionParameters
00094          << ", " << _remainingCancellationDistributionParameters
00095          << ", " << _demandDistributionParameters
00096          << std::endl;
00097     
00098     return oStr.str();
00099   }   
00100 
00101   // //////////////////////////////////////////////////////////////////////
00102   void Overbooking::toStream (std::ostream& ioOut) const {
00103     ioOut << toString();
00104   }
00105   
00106   // //////////////////////////////////////////////////////////////////////
00107   void Overbooking::fromStream (std::istream& ioIn) {
00108   }
00109   
00110   // //////////////////////////////////////////////////////////////////////
00111   const std::string Overbooking::shortDisplay() const {
00112     std::ostringstream oStr;
00113     oStr << describeKey();
00114     return oStr.str();
00115   }
00116   
00117   // //////////////////////////////////////////////////////////////////////
00118   const std::string Overbooking::display() const {
00119     std::ostringstream oStr;
00120     oStr << shortDisplay();
00121     oStr << "Policy = " << _policy
00122          << "; OB% = " << _overbookingPercentage
00123          << "; Capacity = " << _capacity
00124          << "; Net Bookings = " << _netBookings
00125          << "; Load Factor (LF) = " << _loadFactor
00126          << "; No-Show Distrib. Params = " << _noShowDistributionParameters
00127          << "; Cx Distrib. Params = " << _cancellationDistributionParameters
00128          << "; Rem. Cx Distrib. Params = " << _remainingCancellationDistributionParameters
00129          << "; Demand Distrib. Params = " << _demandDistributionParameters
00130          << std::endl;
00131     return oStr.str();
00132   }
00133 
00134 
00135   // ////////////// TODO: REMOVE THOSE CONSTANTS //////////
00136   //Parameters given by RMS User , for the prototype we set at
00137   //predefined values
00138 
00139   // = 0.5; to check the influence of this parameter , actually has 1 problem
00140   const double PRICE_OVER_DENIED_COST = 0.5;
00141 
00142   // = 150; 
00143   // const unsigned int CAPACITY = 150;
00144 
00145   // = CAPACITY*1.2;
00146   const double MAX_BOOKING_LIMIT = 180;
00147 
00148   // 0.8; // il faut calculer ro dans la requete
00149   // const double SHOW_RATE = 0.9 ;
00150 
00151   // 120;
00152   // const unsigned int NET_BOOKINGS = 120;
00153   // const int OVERBOOKING_METHOD_TYPE = 0;
00154         
00155         
00156   // service level parameters
00157   //pSHOW_RATEbability that we have to deny one or more passengers = 1/10.000
00158   const double SERVICE_LEVEL1 = 0.0001; 
00159 
00160   //the fraction of passengers who will be denied to board = 1 over 10.000
00161   const double SERVICE_LEVEL2 = 0.0001; 
00162   const int SERVICE_LEVEL_TYPE = 2;
00163         
00164   //parameters fSHOW_RATEm Forecaster 
00165   //demand average and deviation for a flight date
00166   // const double DEMAND_AVERAGE = 135;
00167 
00168   //100,10
00169   // const double DEMAND_DEVIATION = 10; 
00170   // const double NS_PERCENTAGE = 0.1;
00171   //10,2
00172   // const double NS_DEVIATION = 0.02;  
00173   // const double REMAINING_CANCELLATIONS_PERCENTAGE = 0.2;
00174   //20,5
00175   const double CANCELLATIONS_DEVIATION = 0.05;
00176   // ////////////// END OF TODO: REMOVE THOSE CONSTANTS //////////
00177 
00178   // //////////////////////////////////////////////////////////////////////
00179   FldDistributionParameters Overbooking::getOverbookingCalculation () const {
00180     FldDistributionParameters resultOBPercentage;
00181     
00182     const FldOverbookingPolicy::EN_Policy lPolicy = _policy.getPolicy();
00183 
00184     switch (lPolicy) {
00185     case FldOverbookingPolicy::HEUR: 
00186       resultOBPercentage = calculateHeuristic(); 
00187       break;
00188     case FldOverbookingPolicy::RISK:  
00189       resultOBPercentage = calculateRiskBased();
00190       break;
00191     case FldOverbookingPolicy::SL1: 
00192       resultOBPercentage = calculateServiceLevel();
00193       break;
00194     case FldOverbookingPolicy::HYBRID: 
00195       resultOBPercentage = calculateHybridPolicy();
00196       break;
00197     default: 
00198       resultOBPercentage = calculateHeuristic(); 
00199       break;
00200     }
00201     return resultOBPercentage;  
00202   }
00203 
00204   // 0 :  Method Heuristic take No show and cancellations infor 
00205   //to calculate the Overbooking percentage and deviation
00206   // //////////////////////////////////////////////////////////////////////
00207   FldDistributionParameters Overbooking::calculateHeuristic() const {
00208     FldDistributionParameters resultOBPercentage;
00209 
00210     const double lCancellationsPercentage = 
00211       _remainingCancellationDistributionParameters.getMean()
00212       * _netBookings / _capacity;
00213 
00214     // Overbooking average percentage
00215     const double lNoShow = _noShowDistributionParameters.getMean();
00216     const double lOBMean = (lNoShow + lCancellationsPercentage)
00217       / (1 - (lNoShow + lCancellationsPercentage));
00218     resultOBPercentage.setMean (lOBMean);
00219 
00220     // Overbooking deviation (heuristic)
00221     const double lNSStdDev = 
00222       _noShowDistributionParameters.getStandardDeviation();
00223     const double lNSVariance = lNSStdDev * lNSStdDev;
00224 
00225     const double lCxStdDev = 
00226       _cancellationDistributionParameters.getStandardDeviation();
00227     const double lCxVariance = lCxStdDev * lCxStdDev;
00228 
00229     const double lOBStdDev = sqrt (lNSVariance + lCxVariance);
00230     resultOBPercentage.setStandardDeviation (lOBStdDev);
00231 
00232     return resultOBPercentage ;
00233   }
00234         
00235   // 1 : Method Risk based  take No show and cancellations infor 
00236   //to calculate the Overbooking percentage and deviation
00237   // //////////////////////////////////////////////////////////////////////
00238   FldDistributionParameters Overbooking::calculateRiskBased() const {
00239     FldDistributionParameters resultOBPercentage;
00240                         
00241     // take the Overbooking average and deviation by Heuristic method
00242     // in order to calculate some parameters ? show rate par exemple
00243     resultOBPercentage = calculateHeuristic();
00244 
00245     //Calculation SHOW_RATE : Shows rate = shows/net booking;
00246     //Calculation booking limit
00247     const double lBookingLimit = calculateBookingLimit ();
00248 
00249     const double lOBMean = lBookingLimit / _capacity - 1.0;
00250     resultOBPercentage.setMean (lOBMean);
00251         
00252     return resultOBPercentage;
00253   }
00254 
00255   //  2 : Service level policy  
00256   // //////////////////////////////////////////////////////////////////////
00257   FldDistributionParameters Overbooking::calculateServiceLevel() const {
00258     FldDistributionParameters resultOBPercentage;
00259 
00260     // No-Show Rate
00261     const double lNoShowMean = _noShowDistributionParameters.getMean();
00262     
00263     //  service level 1
00264     unsigned int b = _capacity;
00265     switch (SERVICE_LEVEL_TYPE){
00266     case 1: default: {
00267       double test = serviceLevel1 (lNoShowMean, b, _capacity);
00268       while (test < SERVICE_LEVEL1) {
00269         b++; 
00270         test = serviceLevel1 (lNoShowMean, b, _capacity);
00271       }
00272       break;
00273     }
00274     case 2: {
00275       // service level 2
00276       double test = fractionServiceLevel2 (lNoShowMean, b, _capacity);
00277       while (test < SERVICE_LEVEL2){
00278         b++;
00279         test = fractionServiceLevel2 (lNoShowMean, b, _capacity);
00280       }
00281       break;            
00282     }   
00283     }
00284     resultOBPercentage.setMean (static_cast<double>(b) / _capacity - 1.0);
00285     // TODO: To be altered
00286     resultOBPercentage.setStandardDeviation (0);
00287 
00288     return resultOBPercentage;
00289   }
00290         
00291   //    3 : Hybrid policy
00292   // //////////////////////////////////////////////////////////////////////
00293   FldDistributionParameters Overbooking::calculateHybridPolicy() const {
00294     FldDistributionParameters resultOBPercentage;
00295     
00296     FldDistributionParameters resultOBPercentage_1 = calculateRiskBased();
00297     FldDistributionParameters resultOBPercentage_2 = calculateServiceLevel();
00298     
00299     //intermediate step to calculate the OB%
00300     const double lMean1 = resultOBPercentage_1.getMean();
00301     const double lMean2 = resultOBPercentage_2.getMean();
00302     const double lSDeviation1 = resultOBPercentage_1.getStandardDeviation();
00303     const double lSDeviation2 = resultOBPercentage_2.getStandardDeviation();
00304     
00305     //The hybrid method gets the minimum value
00306     if (lMean1 > lMean2)      {
00307       resultOBPercentage.setMean (lMean2);
00308       resultOBPercentage.setStandardDeviation (lSDeviation2);
00309       return resultOBPercentage;
00310     }
00311     assert (lMean1 <= lMean2);
00312 
00313     resultOBPercentage.setMean (lMean1);
00314     resultOBPercentage.setStandardDeviation (lSDeviation1);
00315 
00316     return resultOBPercentage;
00317   }
00318         
00319   //Distribution
00320   //binomial distribution, normal distribution
00321         
00322   // Service level 
00323   // in the Service Level policy method we can switch between service
00324   // level 1 and 2 in the Hybrid policy, because they are constraints
00325   // so we can choose one or the other or the two
00326 
00327         
00328   // useful functions
00329   // //////////////////////////////////////////////////////////////////////
00330   double Overbooking::calculateBookingLimit () const {
00331     double resultBookingLimit = _capacity;
00332 
00333     // Demand Distribution Parameters
00334     const double lDemandMean = _demandDistributionParameters.getMean();
00335     const double lDemandStdDev =
00336       _demandDistributionParameters.getStandardDeviation();
00337     
00338     // Algorithm
00339     double pNormal = 
00340       gsl_cdf_gaussian_Q (_capacity - lDemandMean, lDemandStdDev);
00341 
00342     //  double pNormal = probabilityNormal (CAPACITY, DEMAND_AVERAGE, 
00343     //                                  DEMAND_DEVIATION);
00344 
00345     if  (PRICE_OVER_DENIED_COST >= 1 - pNormal) {
00346       resultBookingLimit = MAX_BOOKING_LIMIT;
00347       return resultBookingLimit; 
00348     }
00349     assert (PRICE_OVER_DENIED_COST < 1 - pNormal);
00350 
00351     pNormal = gsl_cdf_gaussian_Q (_capacity - 1 - lDemandMean, 
00352                                   lDemandStdDev);
00353 
00354     //    pNormal = probabilityNormal (CAPACITY-1, DEMAND_AVERAGE, 
00355     //                           DEMAND_DEVIATION);
00356 
00357     const double lNoShowMean = _noShowDistributionParameters.getMean();
00358     
00359     double lProbability = (1 - pNormal)
00360       * gsl_sf_pow_int (lNoShowMean, _capacity);
00361 
00362     int counter = 1;
00363     while ((lProbability < PRICE_OVER_DENIED_COST) && (counter < 100)) {
00364       counter++;
00365       if (resultBookingLimit >= MAX_BOOKING_LIMIT) {
00366         return resultBookingLimit;
00367 
00368       } else {
00369         resultBookingLimit += 1.0; 
00370       }
00371 
00372       const unsigned int b = static_cast<unsigned int> (resultBookingLimit);
00373 
00374       pNormal = gsl_cdf_gaussian_Q (b + 1 - lDemandMean, lDemandStdDev);
00375 
00376       //  pNormal = probabilityNormal (b+1, DEMAND_AVERAGE, DEMAND_DEVIATION);
00377 
00378       assert (_capacity > 1);
00379       assert (b - _capacity + 1 > 0);
00380       // assert (b >= 0); (derived from the other two)
00381 
00382 
00383       // The cumulated probability that the number of shows exceeds
00384       // the leg/cabin physical capacity
00385       lProbability += (1+pNormal)
00386         * lNoShowMean * gsl_ran_binomial_pdf (_capacity-1, lNoShowMean, b);
00387       
00388     }
00389     return resultBookingLimit;
00390   }
00391         
00392 
00393   // Private useful functions, some of them are to be replaced by gsl
00394   // library's functions
00395 
00396   // //////////////////////////////////////////////////////////////////////
00397   //to be deleted, already available in gsl lib
00398   //cumulated binomial probability
00399   double Overbooking::probabilityNormal (const int b, const double average, 
00400                                          const double sdeviation) const {
00401     double resultCdf = 0.0;
00402 
00403     for (int i=0; i < b+1 ; i++) {
00404       resultCdf += 1 /( sqrt(2 * M_PI) )
00405         * gsl_sf_exp (-1* (gsl_sf_pow_int(i-average, 2)) / (2*sdeviation));
00406     }
00407     return resultCdf;
00408   }
00409         
00410   // //////////////////////////////////////////////////////////////////////
00411 
00412   // to be deleted, already available in gsl lib, gsl_ran_binomial_pdf(unsigned int k, double SHOW_RATE, unsigned int b)
00413   double Overbooking::binomialProbability_F_b_s (const double iShowRate, 
00414                                                  const int b, 
00415                                                  const int k) const {
00416     double Factorials = gsl_sf_fact(b)/gsl_sf_fact(k)/gsl_sf_fact(b-k);
00417     double f = Factorials*
00418       gsl_sf_pow_int(iShowRate, k)*gsl_sf_pow_int(1-iShowRate, b-k) ;
00419 
00420     return f;
00421   } 
00422 
00423   // pSHOW_RATEbability to deny one or more services
00424   // //////////////////////////////////////////////////////////////////////
00425 
00426 
00427 
00429 
00430   // service level 1 : cumulated probability of having no-shows
00431   //the constant SHOW_RATE can be changed in local variable in this function
00432 
00433   // //////////////////////////////////////////////////////////////////////
00434   double Overbooking::serviceLevel1 (const double iShowRate, 
00435                                      const int b, const int C) const {
00436     double resultProbability = 1.0;
00437     for (int i = 1; i<=C; i++) {
00438       resultProbability -= gsl_ran_binomial_pdf (i, iShowRate, b);}
00439     return resultProbability;
00440   }
00441 
00443   double Overbooking::fractionServiceLevel2 (const double iShowRate, 
00444                                              const int b, const int C) const {
00445     double resultFraction = serviceLevel1 (iShowRate, b-1, _capacity-1) 
00446       - C / b / iShowRate * serviceLevel1 (iShowRate, b, _capacity);
00447 
00448     return resultFraction;
00449   } 
00450 }
00451  
00452   
00453   /* where can I move this main function ?*/
00454   // int main(){
00455     //tester = a supprimer
00456   // double []test; 
00457   // overBookingCalculation tester = new overBookingCalculation("AY", "831");
00458   // test = tester.getOverbookingCalculation(2);
00459 
00460   // System.out.println("OB % = " + test[0]);
00461   // System.out.println("OB deviation = " + test[1]);
00462                
00463   
00464  
SourceForge Logo

Generated on Fri Sep 11 06:31:59 2009 for RMOL by Doxygen 1.5.8