event_driven_rideshare_sim

The main method in RideShareDispatchSimulator should be run to initiate the simulation. Current application requires the user to input the number of drivers and customers for the simulation. Additionally, parameters including the upper bound of randomly generated distance, the driver’s driving speed and the events time span can be modified by changing the constant variables in SimDirector class.

The project implements an event-driven simulation for a rideshare scenario. The project is implemented based on the MVC framework. It adopted the Abstract Factory creation pattern, the Visitor behavior pattern and the Composite structure pattern to facilitate a modular design.

The current design implemented three Priority Queues in form of Abstract Data Structure (ADT), a Mediator, a Visitor, a Factory and several utility classes.

1. Event queue
   An Event priority queue is used to manage a series of events dynamically, and process the events based on the time when they occur. The two types of events, RideRequestedEvent and RideFinishedEvent, are ordered by the eventTime attribute, which represents the creation time for RideRequestEvent and finish time for RideFinishedEvent. In the simulation main loop, at each iteration, the event that has the earliest eventTime will be dequeued for processing.

2. Customer request queue
   A Request event priority queue is implemented so that when a ride request event is dequeued from the event queue, the request event is added to the request queue. However, this request event priority queue is an ArrayList that contains 4 individual priority queues. It can only contain RideRequestedEvent and its subtypes. Priority queue at index 0 to 3 contains requests for rides of different priorities. Within each priority queue, a combination of Shortest Job First (SJF) and First Come First Served (FCFS) scheduling method is used. The ride request with a shorter distance has a higher priority. For rides request with the same distance, earlier request time yields higher priority. In addition, a weighted Round Robin (RR) method is used to prevent lower priority queue from starving by rotating the queues. Each priority queue is assigned with a specific service quantum. In order to preserve the rule that higher priority queue should get more resources, the queue with higher priority is assigned with a higher quantum and vice-versa. This makes sure that the higher priority queue has a higher probability of being served.

3. Driver queue
   The driver queue is implemented as a normal queue. At each iteration of the main loop, if both the driver queue and the request event queue are not empty, then a request event and a driver will be dequeue. With the help of the Visitor class, a new RideFinishedEvent will be created using the information encapsulated in the two objects. This RideFinishedEvent will be added back to the event queue.

4. Event queue and Visitor
   The event queue contains the two subtypes of the Event class a uniform way of processing each event is needed so that the down-casting can be avoided. The Visitor pattern is used to solve this problem. Because the event queue contains objects of subtypes of Event, Visitor uses overloaded method to process different types of Event object in runtime. This promotes loose coupling and avoids unsafe down casting. When a RideRequestedEvent is dequeued from the event queue, the request event is added to the request queue. If there are available drivers in the driver queue, a ride finished event is created using a request is dequeued from the request queue and a driver is dequeued from a driver queue. The ride finished event is then added back to the event queue. When a RideFinishedEvent is dequeued from the event queue, a Ride object is created based on information encapsulated in the finished event and stored into the list of finished rides. The driver assigned to the finished event is then added back to the driver queue, with the numberOfRidesFinished attribute incremented by one. Then, if there are request in the request queue and available drivers in the driver queue, a new ride finished event is created using a request is dequeued from the request queue and a driver is dequeued from a driver queue. The ride finished event is then added back to the event queue.

5. Abstract Factory
   As the Ride object is composed of multiple components, and each component can have different subtypes, an efficient way of creating Ride objects is needed to promote loose coupling between classes. The Abstract Factory pattern is used to solve this problem. An Abstract Factory method is used in this project. Each concrete subclass of the abstract factory creates a concrete type of Ride. Each factory creates a Customer, a Driver, and a Ride. All factories implement a RideGenerator interface, which allow each factory to generate a Ride object as needed. The factories are created and maintained by the Mediator. Each type of factory will only be created once. The Visitor uses this factory to create a finished Ride object when a RideFinishedEvent occurs and stores the Ride object into a list for later use. This approach allows flexible combination of different Ride components and promotes expansibility.

6. Mediator The simulation process involves various interactions between different stakeholders, the project needs an efficient way to organize these interactions and minimize the coupling between classes. A Mediator, SimDirector, is created as the director of the simulation. The mediator is in charge of running the main loop and coordinating the behaviors between different objects. It creates all the data structures needed for the simulation, then coordinates the interaction between Event, Visitor and Factory in order to maintain the event queue and produces expected results. The major steps of the simulation regulated by the Mediator are as follows:

   1. Initializes Event queue, RequestEvent queue, Driver queue, RideFactories (HashMap with key as Integer representing RideType and value as corresponding RideFactory) and list for finished ride object.
   2. Populates the Event queue with random generated eventTime, the total number of events generated depends on the user input for the total number of customers. Populates the driver queue with random drivers, the total number of Drivers generated also depends on user input.
   3. Begins the main loop. While either the Event queue and the RequestEvent queue is not empty, the loop continues. For each iteration, if the event queue is not empty, then the event with the highest priority is dequeued, and the Visitor is called to visit the event and carry out corresponding process. Based on the type of the event, one of the two pipelines will be carried out by the Visitor:
      If the event is a RideRequestedEvent, it is added to the request queue. Then, if the driver queue is not empty, a Driver will be dequeued from the driver queue and a RideRequestEvent will be dequeued form the request event queue. A RideFinishedEvent will be created using the information in the RideRequestedEvent and the Driver. Then the newly created RideFinishedEvent is added back to the event queue. If the event is a RideFinishedEvent, a new driver is created with the driver information from the RideFinishedEvent and the driver’s number of finished rides is incremented by 1. Then the driver is added back to the driver queue. Meanwhile, the RideFactory is used by the Visitor to create a Ride object representing a finished ride, this Ride object will be stored in the list of finished rides. After these operation, if both the driver queue and the request event queue are not empty, a new driver and a new request event will be dequeued, and a new RideFinishedEvent will be created and added back to the event queue. The departure time for this newly dequeued event will be the eventTime (finish time) of the last RideFinishedEvent.
   4. If the event queue and the request event queue are both not empty, continue step 3.

Reference

Gamma, E., Helm, R., Johnson, R., & Vlissides, J. (1994). Design Patterns: Elements of Reusable Object-Oriented Software. Westford, Massachusetts, United States: Addison-Wesley.