CECS552-Programming Assignment 3 Solved

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.

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

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.

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.