联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> Algorithm 算法作业Algorithm 算法作业

日期:2021-01-08 11:09

4.1. THEORY – THE CARPARK MODEL 39

ith booking made on the system B

i may be written as

(4.1)

where tb is the booking time, ta the arrival time and td is the departure time.

In order to keep track of all bookings made over time and their effect on the number of cars in

the car park, and also the revenue generated by the bookings, we split the problem into discrete

time steps. Take the interval in time t > a,

In this project we set the basic unit of time to be a day, and ?t

1 represents a time period of one

day.

This function f ?B? simply describes the fact that a car is regarded as being in a car park for a full

day if it either arrives during that day, leaves during that day, or arrives on a previous day and

leaves on a later day.

This is useful in our model as the price paid will be linked to the duration of stay.

Now let the price per day for a booking B

i be given by a pricing function p?D

i

? where D is

the duration of stay.

? (4.8)

4.1.1 Generating events from a Poisson Process

To generate the set of bookings we suppose that bookings are generated by a Poisson process,

i.e. they are generated independently and continuously at some average rate λb bookings per

day. For such a process, the time between subsequent bookings is given by an exponential distribution.

If u

n

is an independent random draw from a uniform distribution (0 @ u

n B 1) then the

function to generate the time of the next event t

n of a Poisson process with intensity λb,

(4.9)

4.1.2 Generating a Booking

Given that we have generated the time of the next booking, we need to know when the customer

will arrive in the car park and how long they will stay. Note that if the arrival intensity is given by

λ, then the average time of the next event will be 1

λ

. So if we wish to have a process where the

average time between booking and arrival is say, 28 days, and the average time between arrival

and departure is 7 days, then we may use Poisson processes with intensity λa

1

28 and λd

1

7

for

the arrival and departure times respectively.

Put simply, given three random draws from a uniform distribution and the time the previous

booking was made t

i

b we may generate the next booking as:

0). The sequence of booking times tb is generated

by a Poisson process with rate λb. For each booking, the time between booking and arrival, and

the time between arrival and departure, are each exponentially distributed with mean 1~λa and

1~λb respectively. Note that this booking model is not very realistic, but it is very easy to generate,

and could easily be extended to allow the intensity parameters to become functions of time to

capture weekly or seasonal effects.

4.1.3 Calculated expected values of car park measures

We can use the random bookings that we generate as input to our car park model in section 4.1,

and in doing so evaluate various measures of our car park, such as the revenue, and occupancy

(number of cars in the car park) for a given day. These values will depend on the parameters

intrinsic to the car park model (for example, the size of the car park, and the pricing function), but

4.1. THEORY – THE CARPARK MODEL 41

will also depend on the particular booking times chosen by our random booking process. To study

the effect of car park parameters (size, pricing function etc.) on our measurements (of revenue,

occupancy, etc.) we would like these measurements to be independent of the randomness in the

booking times. To do this by taking the expected value, or average, of our measurement over all

the possible random bookings. For very simple measurements it may be possible to calculate this

expected value algebraically, for most measurements we will need to calculate these expected

values numerically, using a so-called Monte Carlo technique.

The idea behind Monte Carlo methods is very straightforward. Suppose we wish to measure

the expected value of R

k

, the revenue of the car park on the kth day. The expected value of the revenue is approximated by the mean of

these samples,(4.11)

When N is large this expected value ER

k

is approximately normally distributed (from the central

limit theorem), (4.12)

This standard deviation decreases with increasing N, so by choosing sufficiently large N our expected

value becomes relatively insensitive to the particular random booking times.

Note that we cannot take N arbitrarily large – it may take too long to simulate the car park

model a very large number of times – so the choice of N is a compromise between program run

time and accuracy.

4.1.4 Optimal Revenue Management

The explanation of Revenue Management in this project will be brief but we will lay out the basics

relevant to our simplified model. This project focuses on the problem of capacity allocation.

The problem arises when the same product (a space in a car park) is sold to different customers

at different prices, so the question arises of how many bookings we should allow the low-price

customers to make when there is a possibility that high-price customers may arrive later on.

In our car park model, we assume that there exists a set of low price customers that take advantage

of the discount for staying in the car park for a long period. (By discount we mean that,

while the total price of a long stay is greater than that of a short stay (4.7), the price per day of

a long stay is less than that of a short stay (4.6).) They tend to book into the car park online in

advance, and are typically leisure passengers. In contrast, we assume that there exists a set of

high-price customers who turn up and pay a high price to stay for only a day or two. They are typically

business passengers, and do not book trips in advance, and therefore neither do they book

their parking in advance. In this model we do not assume that different customers are subject to

different prices, just that they will receive a discount the longer they stay in the car park. Price is

assumed to be given as a function of duration of stay as in equation (4.6) with positive constants

4.2. EXERCISES 42

α and β.

At first we will decide whether to reject bookings by simply assigning a constant proportion

of the car park to each set of customers. By varying this proportion we can then investigate when

the maximum revenue is generated, and thus find the optimal proportion to assign to each set of

customers.

4.2 Exercises

4.2.1 The Customers class

? Create a function that returns the time of the next event for a Poisson process with intensity

λ. You may use the internal C++ random number generator rand() to generate samples

from a uniform distribution. Alternatively, look at the Mersenne Twister code provided for

the Gillespie Algorithm project in this booklet. Make sure that you enforce the constraint

u

n A 0 by excluding the case where rand() generates a value of 0.

? Enter the following data structure for bookings into your code:

class Booking

{

public:

double bookingTime;

double arrivalTime;

double departureTime;

};

// compare for sort algorithms

bool operator<(const Booking &x,const Booking &y);

(Recall that a struct is simply a class with all members public by default.) Complete the implementationfor

the “less than” operator < so that bookings may be ordered by bookingTime

. You may also wish to overload stream outputs using operator<<.

? Now create a class (similar to the MVector) to store all of the bookings for one class of customer.

class Customers

{

private:

std::vector<Booking> vectorBookings;

public:

// generate a set of bookings

void generateBookings(double bookingRate,double arrivalRate,

double departureRate,double startTime,double finishTime);

};

Complete the implementation for the generateBookings method. The first three arguments

should be the intensity parameters for the Poisson process. Using startTime as

4.2. EXERCISES 43

your initial time, keep generating bookings until you reach finishTime. See section 4.1.2

for information on how to generate bookings.

? Complete the class by writing member functions to allow access to vectorBookings and

also to return the number of bookings (see MVector for how we did this with double as

the data type.

? Generate bookings using λb

5, λa

1~14, and λd

1~7 with tb > 0,

150 and write them

to screen. These will be the low-price leisure customers. (Note that although we restrict

tb B 150, we may have bookings where ta A 150 and/or td A 150).

? Generate bookings using λb

25, λa

1, and λd

2 with tb > 0,

150 and compare them to

the previous booking set. These will be the high-price business customers.

? Write a member function of Customers to add bookings from another Customers class.

The function signature should look like:

void addBookings(Customers &C);

Complete the implementation. Try adding the business and leisure customers together to

form one single set of ordered bookings.

You can sort a vector using the std::sort function, in the <algorithm> include library.

For a std::vector vectorBookings we write

std::sort(vectorBookings.begin(),vectorBookings.end());

which sorts the vector by booking time, so long as the less than operator has been overloaded

correctly. Display your bookings to screen, and check that the sets have combined

correctly.

4.2.2 The Car Park Class

? By writing a class, or otherwise, create storage for the number of cars present in the car park

in each period k and also the revenue they generate (you could combine both using your

own data structure).

? Now create a function CarsPresent that takes as input:

– a list of bookings stored in a Customers class

– the start time

– the number of days

and gives as output

– a vector containing the number of cars present in the car park for each day.

You will need to use equation (4.3) to calculate the cars present in the car park for each day

from the booking times. (Is there a faster way to calculate D

i

than simply summing over f

as in (4.4)?)

4.2. EXERCISES 44

? What is the expected number of cars in the car park at t

150 using either of the sets of

customers? Choose what you think is a sensible number of simulations N when calculating

the expected value, and give your answer to an appropriate number of digits.

? Write in a price function of the form shown in equation (4.6) with α

10 and β

5 and use

it to calculate the revenues generated at each day, and also the total revenue.

? Now modify your car park class to include a capacity (number of spaces in the car park).

Write a function that takes a booking and checks if space is available in the car park for the

entire duration of that booking. Use this in your CarsPresent function to reject bookings

if there is no space.

? Using a combined set of both customer types, what is the expected time that a car park

with 50 spaces will first reach capacity? As before, think about how many simulations N

you should run when calculating the expectation.

4.2.3 Revenue management with a fixed allocation strategy

? For the combined set of customers, calculate the total expected revenue for car parks with

capacity 10, 20, 30, . . . , 100.

? Now create two different car parks for each set of customers so that the sum of the capacity

of each car park is equal to capacity of the combined car park. Investigate what is the optimal

proportion of the car park to reserve for each set of customers. For example, you could

create a plot of the optimal proportion as a function of total car park size. Optionally, can

you estimate the error in your calculation of the optimal proportion?

? You may wish to extend this idea by generating a contour plot of the revenue as a function

of both the car park size and the proportion allocated to business/leisure customers.

? How does the optimal proportion of the car park to allocate vary with the booking rates λb

for each type of customer?

4.2.4 Booking rejection strategies

So far we have used a very simple strategy for rejecting bookings, by allocating a fixed proportion

of the car park to each type of customer. Alternatively, we could generate a rejection rule based

on the number of spaces left in the car park, the price per period of the booking, and the time

remaining the period in question. We should reject a booking only if the total revenue generated

from the booking is less than the expectedrevenuefromfuture bookings that the car will displace

over all periods it is present. For example, imagine that it is Friday and we have one space left in

the car park on Monday and one space left for Tuesday. A booking is requested on the system that

will stay both days, and if we generate our price from (4.6) with α

10 and β

5 the the booking

will pay a rate of £10 per day. Now if we know that the probability that a someone will turn up and

stay for one day on Monday and Tuesday and pay £15 per period is 0.8, then we can say that the

net contribution from the booking is ?10  15  0.8?  ?10  15  0.8?

£4. This means we should

4.3. REPORT 45

reject the booking and take our chances that the high-price customers will arrive. Alternatively

if the car park had 100 spaces left, then the car park is unlikely to fill, the value of the spaces

displaced is low (zero if there is no chance that the car park will fill up) and we should accept the

booking. How we should calculate the notional value of the space that is displaced is left for you

to discover.

Investigate booking rejection strategies of this type. The most interesting cases are likely to

be found for car parks that are large enough that they will not usually be filled by the highestpaying

customers alone, but small enough that some customers cannot be accommodated. Can

you design a method that improves on the optimal revenue generated when a fixed proportion

of the car park is allocated to each type of customer?

4.3 Report

Write your report as a connected piece of prose. Read the Guidelines section at the start of this

documentfor other instructions on theformat of the report. Some questions have marks in square

brackets, indicating the 30 marks available for correct numerical results and code. The other 30

marks are awarded for the overall quality of validation, analysis and the write-up, as detailed in

the grading criteria provided in the guidelines.

? Detail any classes that you have used in the problem. [3]

? Show some test cases to demonstrate that your car park model is working as expected. (For

example, you could generate a few bookings manually and check that the number of cars

in the car park for each day is as you expect, both for unlimited capacity and when the car

park is small enough that some bookings are rejected.) [4]

? For the unlimited capacity case, analyse the expected number of cars in the car park, and

also the expected revenue. [5]

? After including capacity to the problem, analyse the expected time that a car park with 50

spaces will first reach capacity. [6]

? Analyse of the optimal proportion of the car park that should be reserved for the business

customers, as described in §4.2.3 [6]

? Describe your investigation of new booking strategies in §4.2.4, including numerical results

from the strategies you chose. (If you did not have time to complete this part of the project,

discuss what you think might be good strategies). Do your new rejection strategies generate

higher revenue than that when an (optimal) fixed proportion of the car park is allocated

to each type of customer? [6]


版权所有:留学生编程辅导网 2018 All Rights Reserved 联系方式:QQ:99515681 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。