## Description

Ride Sharing in Squaresville with Lynx

The streets and avenues of the city of Squaresville consist of twenty streets (1st through 20th) that

run east-west, along with twenty avenues (again, 1st through 20th) that run north-south. Each

intersection between a street s and avenue a is denoted by the coordinates (s, a). Also, Near each

intersection are designated pick-up and drop-off stations for a privately owned and city-sponsored

ride-sharing business called Lynx. To use Lynx, a potential rider uses an app to reserve a ride by

providing the following information: i) pick-up coordinates, ii) drop-off coordinates, iii) number of

passengers (1-4), and iv) whether or not the party wants to carpool with other passengers. Currently,

the system only handles reservations for immediate travel, and so the ideal pick-up time is equal to

the time the reservation is established.

Lynx prides itself in reliability and quality, and guarantees that i) a party will be picked-up no later

than 15 minutes after its reservation was made, and ii) whenever a carpooling party experiences an

intermediate stop (i.e. pick-ups or drop-offs of fellow carpool passengers), the location of that stop

is always closer to the party’s final destination than any of the previous intermediate stops, and the

initial pick-up location. In other words, intermediate stops are, in some sense, ”on the way”. If either

guarantee is not met, then the party rides for free.

Registered Lynx drivers can join the current drivers pool at any time. Drivers receive a variable-rate

percentage of the fare paid by each party that the driver has transported. Moreover, the rate declines

when the supply of drivers exceeds the rider demand, and increases when there is a perceived driver

shortage. Note also that a driver is still paid (so long as he or she is not at fault) for transporting

a party that traveled for free due to a breach in reliability or quality. Therefore, it is important for

Lynx to have enough drivers at any time, but not too many to where drivers find themselves idle

much of the time.

1

Lynx Needs Your Help

Lynx has hired you to answer the following question: assuming a fixed number of drivers over a

given two-hour time period, what is the least number of drivers needed so that the probabiity p

that “no more than 5% of passengers ride free” is at least 0.90? where 0.90 is the left endpoint of a

95% confidence interval for p. To answer this question they want you to design the best algorithm

possible for assigning party reservations to each driver. Moreover, they want you to prove concept by

simulating use of the algorithm over the two-hour time period. Note that a percentage of passengers

is calculated, as opposed to a percentage of reservations.

System Modeling

Probability Distributions

Over a given two-hour period, reservations are randomly made at a rate of 2 reservations per minute,

with the time between successive reservations following an exponential distribution. All reservations

are assumed independent.

The following table shows the percentage of reservations that are for a given size, and the percentage

of those reservations that request carpooling.

Number in Party Percent of Reservations Percent that Carpools

1 60% 50%

2 25% 65%

3 10% 45%

4 5% 30%

Furthermore, if (S1, A1) denotes the pick-up coordinates of a reservation, while (S2, A2) denotes

the drop-off coordinates, then S1, S2, and A1 are assumed independent and uniformly distributed

over {1, 2, . . . , 20}. However, due to the time of day, 75% of all drop-off A2 values uniformly lie in

{4, 8, 12, 16}, while the other 25% uniformly lie in {1, 2, . . . , 20} − {4, 8, 12, 16}. This is because most

government and retail buildings are located at the multiple-of-four avenues.

For any pair of adjacent intersections, the time needed to travel from one to the other is normally

distributed with a mean of one minute, and a standard deviation of 20 seconds. Note that this time

includes time waiting at stop lights and stopping for passengers.

The passenger capacity of a vehicle is determined at random before the start of simulation by using

the following table

2

Vehicle Passenger Capacity Probability

1 0.05

2 0.05

3 0.40

4 0.30

5 0.15

6 0.5

Note that vehicles are independently and randomly assigned a capacity based on the abofe distribution.

Events

The following is a list of the events that change the system state.

Reservation A party has made a reservation.

Reservation Assignment A driver has been assigned a reservation.

Intersection Arrival A driver has arrived at an intersection.

Pick Up A driver has picked-up a reservation.

Drop Off A driver has dropped off the party associated with a reservation.

Idle Arrival A driver with no assigned reservations has arrived at the intersection where she is to

wait for her next assigned reservation.

System Initialization

1. The system clock is initialized to T = 0.

2. The future event list is initialized with all Reservation events that will occur over the two-hour

period.

3. Each driver is randomly placed at an intersection, where she is parked until receiving her first

assigned reservation.

4. Drivers initially have no assigned reservations.

3

Program Options

1. Allow the user to input i) a vehicle capacity and location ii) pick-up and drop off locations

for a reservation, iii) reservation party size, and iv) a list of locations of potential intermediate

stops. The program then simulates driving to the pick-up location, then driving to the dropoff location, while making as many intermediate stops as possible without sacrificing quality.

The program should print a list of intersections visited, along with the elapsed time (seconds

rounded to the nearest integer) to travel between each adjacent pair of intersections.

4