00001
00002
00003
00004
00005 #include <assert.h>
00006
00007 #include <iostream>
00008
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
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
00136
00137
00138
00139
00140 const double PRICE_OVER_DENIED_COST = 0.5;
00141
00142
00143
00144
00145
00146 const double MAX_BOOKING_LIMIT = 180;
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158 const double SERVICE_LEVEL1 = 0.0001;
00159
00160
00161 const double SERVICE_LEVEL2 = 0.0001;
00162 const int SERVICE_LEVEL_TYPE = 2;
00163
00164
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175 const double CANCELLATIONS_DEVIATION = 0.05;
00176
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
00205
00206
00207 FldDistributionParameters Overbooking::calculateHeuristic() const {
00208 FldDistributionParameters resultOBPercentage;
00209
00210 const double lCancellationsPercentage =
00211 _remainingCancellationDistributionParameters.getMean()
00212 * _netBookings / _capacity;
00213
00214
00215 const double lNoShow = _noShowDistributionParameters.getMean();
00216 const double lOBMean = (lNoShow + lCancellationsPercentage)
00217 / (1 - (lNoShow + lCancellationsPercentage));
00218 resultOBPercentage.setMean (lOBMean);
00219
00220
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
00236
00237
00238 FldDistributionParameters Overbooking::calculateRiskBased() const {
00239 FldDistributionParameters resultOBPercentage;
00240
00241
00242
00243 resultOBPercentage = calculateHeuristic();
00244
00245
00246
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
00256
00257 FldDistributionParameters Overbooking::calculateServiceLevel() const {
00258 FldDistributionParameters resultOBPercentage;
00259
00260
00261 const double lNoShowMean = _noShowDistributionParameters.getMean();
00262
00263
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
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
00286 resultOBPercentage.setStandardDeviation (0);
00287
00288 return resultOBPercentage;
00289 }
00290
00291
00292
00293 FldDistributionParameters Overbooking::calculateHybridPolicy() const {
00294 FldDistributionParameters resultOBPercentage;
00295
00296 FldDistributionParameters resultOBPercentage_1 = calculateRiskBased();
00297 FldDistributionParameters resultOBPercentage_2 = calculateServiceLevel();
00298
00299
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
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
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329
00330 double Overbooking::calculateBookingLimit () const {
00331 double resultBookingLimit = _capacity;
00332
00333
00334 const double lDemandMean = _demandDistributionParameters.getMean();
00335 const double lDemandStdDev =
00336 _demandDistributionParameters.getStandardDeviation();
00337
00338
00339 double pNormal =
00340 gsl_cdf_gaussian_Q (_capacity - lDemandMean, lDemandStdDev);
00341
00342
00343
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
00355
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
00377
00378 assert (_capacity > 1);
00379 assert (b - _capacity + 1 > 0);
00380
00381
00382
00383
00384
00385 lProbability += (1+pNormal)
00386 * lNoShowMean * gsl_ran_binomial_pdf (_capacity-1, lNoShowMean, b);
00387
00388 }
00389 return resultBookingLimit;
00390 }
00391
00392
00393
00394
00395
00396
00397
00398
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
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
00424
00425
00426
00427
00429
00430
00431
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
00454
00455
00456
00457
00458
00459
00460
00461
00462
00463
00464