Description
PROJECT 4 CODE STYLE
Code Style
Part of your grade will be based on the code style demonstrated by your programming. In general, all projects will involve a style component. This should not be intimidating, but it is fundamentally important to readable and maintainable code. Style grading will not be super-strict. For example, one or two bad indents or one or two subjective variable names are hardly a problem. However, if your code seems careless or confusing, or if no significant effort was made to document the code, style points will be lost. If you are confused about the style guide below, please talk with a TA.
The following items represent good coding style:
• Use effective comments to document what important variables, functions, and sections of the code are for. In general, the TA should be able to understand your logic through the comments left in the code.
• Use effective and standard indentation.
• Use descriptive names for variables. Use standard Java style for your names: ClassName, functionName, variableName for structures in your code, and ClassName.java for the file names.
Try to avoid the following stylistic problems:
• Redundant, useless comments, for example: int a = 5; //Set a to be 5 is not helpful.
• Disorganized and messy files. Poor indentation of braces ({ and }).
• Incoherent variable names. Names such as m and numberOfIndicesToCount are not use- ful. The former is too short to be descriptive, while the latter is much too descriptive and redundant.
• Slow functions. While some algorithms are more efficient than others, functions that are aggressively inefficient could be penalized even if they are otherwise correct. In general, functions should terminate in under 5 seconds for any reasonable input.
Discrete Event Simulation
Decision making requires data which often can be obtained from observation. For example, deter- mining when a restaurant is busy is possible by collecting data on the times that people arrive and depart. Based on this information, the manager of the restaurant can determine how many workers should be scheduled at different times during the day.
Hint: Try to insert comments as you program rather than adding them all in at the end. Comments should not feel like arbitrary busy work – they should be written assuming the reader is fluent in Java, yet has no idea how your program works or why you chose certain solutions.
2
PROJECT 4 INTRODUCTION TO THE PROJECT SPECIFICS
However, there are situations where information gathering like this may be very difficult or im- practical. This may be in “what if” scenarios or when determining the expected performance or load level of system or business. To assist in making decisions for situations that cannot be easily directly observed, computer modeling can be a very useful and effective approach. Using an object oriented language (like Java) together with basic data structures that we have covered so far in class, we will be applying a technique known as discrete event simulation to gather data and create a report. Discrete event simulation is based on the creation of objects that represent each of the components in the system we wish to model. Time is modeled using an agenda (or priority queue) where future events are scheduled in chronological order. As events occur, they are removed from the agenda, so only future-scheduled events reside in the agenda at any given time. The scheduled events determine the current clock time. The only time steps modeled are the time steps when an event is scheduled to occur. This keeps both the agenda and the run time required rather efficient.
Introduction to the Project Specifics
The popularity of local Bus Route 3 has increased, and now the customers are complaining about longer waits and full buses. In order to keep ridership up, the bus company has decided to run a simulation to help figure out how many buses to run, and whether they should have some buses run as “express” buses which stop at only one out of every four bus stops. The company wants to minimize the average travel time (wait time + ride time) for its riders. However, they also want to maximize the Passenger Miles Per Gallon (PMPG). The PMPG is calculated by multiplying the Miles Per Gallon of a bus by its average occupancy. Buses run at 4.3 MPG and hold 50 passengers (maximum). Buses that run at less than capacity will have a high PMPG which does not make good business sense. For example, running lots of (express and regular) buses that are almost empty, will provide a great service to the riders, but the cost in PMPG (not to mention driver salary) would be prohibitive. So, it is in everyone’s best interest that the bus company find a happy middle ground that reduced wait time to something manageable while keeping PMPG low as well.
Note: the simulation in this project will not need to do PMPG calculations.
You are tasked to create this simulation and return a report to the bus company with your findings. The Car Wash example that we acted out in lecture has many parallels to this project. You may find it helpful to use some of the code for the Car Wash example in your simulation project, and that is O.K. Specifically, you should use the priority queue (PQ.java) as-is.
Reminder: Be sure to credit any code borrowed from the posted lecture examples.
3
PROJECT 4
SETUP
Setup
We will assume the following user-adjustable system parameters:
• The number of buses on the route
• The mix of bus types used:
– regular bus: services every bus stop on the route
– express bus: services stops that are evenly divisible by 4, and downtown stops at either
end of the route (see Stop description in the Primary Classes section below)
• The average inter-arrival rate of riders at each bus stop (this will be referred to as the load). For simplicity, the arrival rates of riders at each bus stop will be the same for all stops. The inter-arrival rate (load) should be set and maintained for each simulation. The load should not vary during a simulation. The inter-arrival rate can be set low to model off-peak load, and it can be set higher to model rush-hour load.
We will assume the following system constraints:
• Riders will be passive, but they will contain data such as:
– Boarding bus stop number
– Time they arrived at the boarding stop
– Destination/stop number they want to go to
• Arrival of a rider at a bus stop will be provided by an arrival class that will generate arrivals (determined statistically, see below). You may have a single central arrival class instance that generates and then “dispatches” all rider arrivals for all the bus stops, or you may have an arrival class instance for each bus stop that generates the rider arrivals for only the bus stop to which it is associated.
• Wait/travel time will be determined by arrival time and passenger count (see below).
• If a rider cannot get onto the bus (when the bus is full) they must wait for the next bus, and
assume the rider will not go away.
Approach to This Simulation
Simulation of the system is achieved by creating classes to model the behavior of each element of the system as well as each activity (event) that occurs in the system. There is NOT an overall controller that calls for actions to happen at particular times except for a main driver loop that runs queued events until time runs out. Each element in the system models its own behavior and interactions with other elements in the system. Each NON-passive element class has an Event class associated with it. The associated event defines a run() method (as discussed in lecture) that simulates the specific behavior of that event.
4
PROJECT 4 APPROACH TO THIS SIMULATION
The Primary Classes we will use are:
• RiderEvent – one for each Rider arriving at a boarding stop
• Bus Stops (Stop) – contain the queue of Riders waiting for the bus
• BusEvent – occurs each time a Bus arrives at a stop
• PQ – priority queue instance which you should name “agenda” (provided for you) • Event – an interface for all our events (provided for you)
Let’s look at each of these components, and see what they should contain. Please note that you may need to include other information, but what is given here is considered fundamental.
RiderEvent
This is instantiable once for each Rider creation event. One RiderEvent will be made for each stop, allowing you to have some stops that are more popular than others. This will implement the Event interface similar to how the CarMaker class was implemented as described in lecture. RiderEvent will reschedule itself (using the agenda), create a Rider, decide where they want to go on the route, and place the Rider in the appropriate bus stop queue.
Stop
This is instantiable once for each bus stop on Route 3. Each location on the route will have a queue associated with it and a name and number to designate which bus stop it is. Note that Ramp B and Union Depot locations (which are at the far ends of the route) each only need to have one bus stop, since riders who arrive at those locations stops cannot go further west or east, respectively. There are exactly 16 bus stop locations along Route 3, and 30 bus stops numbered and named according to the list below.
5
PROJECT 4
APPROACH TO THIS SIMULATION
• 0-RampB
• 1 and 29 – 4th & Nicollet
• 2 and 28 – Anderson Hall
• 3 and 27 – Jones Hall
• 4 and 26 – Kasota Circle
• 5and25-Como&Eustis
• 6 and 24 – Como & Cleveland
• 7 and 23 – Como & Snelling
• 8 and 22 – Como and Hamline
• 9 and 21 – Maryland and Dale
• 10 and 20 – Maryland and Rice • 11 and 19 – Front and Lexington • 12 and 18 – Front and Dale
• 13 and 17 – Capitol
• 14 and 16 – Cedar
• 15 – Union Depot
Implementation Note: Since a bus stop location has effectively two bus stops–one for west- bound buses, and one for eastbound buses–each location (except for stops 0 and 15) can be considered as two separate stops with the buses basically circulating through 30 stops at 16 locations. Stops 1-14, and stops 16-20 give 28 stops. Then, add stops 0 and 15, for a total of 30 stops. Using this numbering, stops 0, 1, 29 and stops 14, 15, 16 are all stops that will be serviced by the express buses (in addition to stops that are evenly divisible by 4).
BusEvent
This implements the Event interface. A BusEvent is created for each time the bus pulls up to a Stop. When a bus arrives at a bus stop, the BusEvent “looks at” the riders of the associated bus to see if there are riders that wish to exit the bus at this stop. If there are, these riders are removed (and statistics are updated as the removed riders leave the system). The BusEvent will then look at riders at the bus top that want to go the direction the bus is going and board as many as will fit on this bus. Finally, the BusEvent will create a new BusEvent and schedule it (via the agenda) for the arrival at the next bus stop at a time in the future depending on the number of passengers that got off and got on. If the Bus has reached the last bus stop location in either direction (west or east–stops 1 and 15), it will start going the other direction. For example, if an eastbound bus arrives at the Union Depot Stop, it will then leave the Union Depot Stop going westbound. More simply, it will go from bus stop 15 to bus stop 16.
6
PROJECTR4ANDOMNESS, REALISM, ASSUMPTIONS, AND MAKING IT WORK
PQ
This is the priority queue. The PQ code is provided (from lecture). Do not modify it. Also, do not forget to credit the source of the PQ code to the “CSci 1933 Lecture Examples.” Use exactly one instance of PQ, and call it “agenda,” which is what we will call it in this document. Agenda will handle all the scheduled simulation events. In other words, every event that occurs in your simulation will be scheduled at some point by adding it to the agenda. Completed events will be discarded from the agenda, and only the (one) next scheduled event for each active component in the simulation will be scheduled at any time. Therefore, the agenda is a very efficient structure which will not get very big.
Statistics
Keeping track of relevant statistics will be necessary in order to derive beneficial information from the simulation. Here are some examples of statistics the simulator can provide.
• How full each bus is on average
• The maximum time a passenger spends waiting at a bus stop • The maximum queue length at a bus stop
• . . . and others that you can might choose to implement
In order to generate statistics, data needs to be collected during the simulation. Some of that information will be contained within the Rider objects. However, it is suggested that a Statistics class be written that contains aggregate statistics, statistics gathering public accessors, and final statistics calculations. By putting these entities in a designated Statistics class, the functional parts of the simulation (RiderEvent, BusEvent) will be uncluttered with the statistics gathering code.
Randomness, Realism, Assumptions, and Making It Work
You will need to use a random distribution to model the arrival of riders at each bus stop. This is determined by method calls made in the run() method for the RiderEvent. You will also need to randomly generate which bus stop each rider wants to go to. For the arrival of riders at a bus stop, you should start with an average inter-arrival rate of 1 rider at each stop every 120 seconds. But, you will want to run your model with both higher and lower demand by decreasing and increasing this inter-arrival time. To more realistically represent the pattern of arrival of riders (since in the real-world, riders will not arrive in even intervals), we will introduce some randomness according to the relative frequencies in the table below. (Example calculations are shown for a 120 second inter-arrival time.)
7
PROJECTR4ANDOMNESS, REALISM, ASSUMPTIONS, AND MAKING IT WORK
• 10 above average arrival interval (120 + 0.75 × 120) • 15 above average arrival interval (120 + 0.50 × 120) • 20 above average arrival interval (120 + 0.20 × 120) • 10% of the time: right at average arrival interval (120)
• 20 below average arrival interval (120 − 0.20 × 120) • 15 below average arrival interval (120 − 0.50 × 120) • 10 below average arrival interval (120 − 0.75 × 120)
Hint: In order to achieve the relative frequency distribution above, create an array of doubles of length 20, and initialize it to the above/below percentage amounts from the table above (.75, .5, .2, 0, −.2, −.5, −.75) according to the desired frequency of oc- curance (10, or 20%), also from the table above. For example, out of every 20 requests:
2 of 20 (or 10) will be for a .5 higher interarrival rate, 4 of 20 (or 20%) will be for a .2 higher interarrival rate, . . . and so on for the other interarrival rate adjustments.
The array of 20 above/below percentage amounts will be initialized like this:
double[] arrivalPercents = {.75, .75, .5, .5, .5, .2, .2, .2, .2, 0, 0,
-.2, -.2, -.2, -.5, -.5, -.5, -.75, -.75};
When obtaining the next arrival time, select a random integer in the range [0, 19], and use that number as an index into arrivalPercents to give the above/below percentage amount according to the relative frequency specified in the table.
One more consideration while we are talking about arrival randomness . . . Downtown stop locations (Stops 0, 1, 29, 14, 15, 16) are more popular than others; therefore, at these bus stops, passengers should arrive twice as frequently than at other bus stops. This means that if the average interarrival rate is 120 seconds for typical bus stops, the average interarrival rate at the downtown bus stops is 60 seconds. (As an aside: downtown bus stops are also two times as likely to be a destination for a rider than other bus stops.) There are 30 total bus stops, six of them have twice the likelihood of a rider (than the other 24 bus stops). To achieve this, an array similar to what was done for the interarrival rate above can be created to select the bus stop a Rider will be dispatched to, so that the downtown bus stops have twice the number of Riders arriving to take the bus.
The array for bus stop selection will have one bus stop entry for each of the non-downtown bus stops, and two bus stop entries for the 6 downtown stops. It will look like this:
8
PROJECT 4 BUS TRAVEL TIME
int[] stopSelect = {0, 0, 1, 1, 29, 29, 14, 14, 15, 15, 16, 16,
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28};
The stopSelect array will have 36 entries, so when choosing the bus stop number for a new rider, a random integer will be selected in the range [0, 35]. The value found at that index in stopSelect will be the bus stop to receive the new rider.
Rider arrivals are likely to be generated centrally for the entire group of bus stops. So, for ex- ample, if using a per stop rider inter-arrival spacing of 120 (or so) seconds based on the ran- domness described above, a new rider will need to be generated about every three to four seconds (1/120 second individual bus stop rate×36 entries in the stopSelect array = 36/120 ≈ 3.3 seconds) and dispatched to a stop based on the value randomly obtained from stopSelect[].
One additional form of randomness is in identifying where a rider will get off the bus–and which bus he will get on. Use the following rules to determine rider behavior.
Rule 1) Eastbound riders (boarding at bus stops 0-14) will only travel east.
Rule 2) Westbound riders (boarding at bus stops 15-29) will only travel west.
Rule 3) A rider’s destination will be randomly selected among the east or west options (depending on direction of travel) except that the downtown bus stops (0, 1, 29, 14, 15, 16) are twice as likely to be chosen as non-downtown destinations. For example, if a rider boards at stop 25, the only possible destination stops (since he is travelling west) are (26, 27, 28, 29, 0). But, 29 and 0 are downtown stops and are twice as likely to be chosen than the others. So, a random stop from 26, 27, 28, 29, 29, 0, 0 will be selected. Thus, one of the two downtown destinations is twice as likely to be selected as any of the other three destinations.
Rule 4) Riders will always board the first bus they can get onto, except that a rider will not board an express bus unless he wishes to go to a downtown destination or a destination stop number that is evenly divisible by 4.
Rule 5) Except for rule (4) above, riders board buses in the order they arrive at the bus stop.
Bus Travel Time
To determine the amount of time a bus will take between bus stops, we use these rules:
• A bus will take 4 minutes (240 seconds) for a bus to travel between bus stops.
• It takes a passenger 2 seconds to get off a bus and 3 seconds to get on a bus.
• A bus will wait at a bus stop for the longer of 15 seconds or the time it takes for riders to get off and get on the bus.
9
PROJECT 4 ASSUMPTIONS
Therefore, a bus will take at least 4 minutes and 15 seconds to get from one bus stop to the next bus stop, and longer depending on the number of passengers who get off and get on. Express buses will (except for downtown stops) skip over three stops, so the minimum travel time when going from say, stop 8 to stop 12 will be 4 × 240 + 15 = 975 seconds. Even if each stop isn’t necessarily the same distance from the next one, the times between each bus stop have been standardized to make the calculation simpler.
Assumptions
• Rider arrival rates, origination stop and destination stop will use the randomness methods described above.
• System load (frequency of new riders) is a simulation parameter which will be varied by the user when gathering simulation results.
• Assume that the number of buses is a simulation parameter that can be adjusted between 1–14 buses.
• Type of bus — there must be at least one regular bus, but otherwise the mix of regular and express buses is a simulation parameter that will be varied when gathering simulation results.
• Use the rules in “Bus Travel Time” above for calculating the amount of time it takes a bus to travel between each bus stop and boarding/unboarding details.
What to do
First, get the simulation system to work, but start small and verify that each feature works before proceeding to the next one. Then, make several simulation runs to gather data. With the data gathered, write a detailed report that gives a convincing presentation for what the bus company needs to do to satisfy its customers while maximizing their fuel economy. While you do not need to calculate PMPG (the bus company will do that), the results of your simulation runs should include the observed utilized bus capacity and rider wait times. Low utilization means bad PMPG, while buses running at capacity optimizes PMPG. Therefore, bus capacity utilization is a key statistic to report along with rider wait times.
In order to provide a convincing argument, you will need to collect good statistics, verify them, and present them in a clear manner.
Simulation Guidelines and Equilibrium
• Do not vary loads within a simulation. Separate simulations should be done for heavy (peak) load times and light (off-peak) load times.
• Run the simulations for long enough, but not too long. For example, a rush-hour (peak) simulation should be run for about two to four hours of simulated time, not days.
10
PROJECT 4 GRADING AND DELIVERABLES
• Determine if your simulation is at “equilibrium” before reporting results. Short simulations will not be accurate as the system takes some time “start up.” So, short runs of a few minutes will not give useful results. On the other extreme, a system that is overloaded (many riders and too few buses) will show longer and longer lines at the bus stops based on how long the simulation is run. This is indicative of a system that is not at equilibrium. Data gathered from such a simulation is not reliable because it depends on the length of the simulation. To determine is the simulation is at equilibrium, run a few of the same simulations (keeping all simulation parameters constant) but with varying simulation times. A system at equilibrium should give similar statistics for each simulation regardless of simulation time.
• Something to watch for and optionally correct when you run your simulations …If left unchecked, the buses will tend to “clump” together in some situations. While a bus passing another (as will happen with express buses) is not an issue and something that happens in real life, the clumping of buses together is best avoided as it causes long wait times at some bus stops meaning that riders at certain stops are not served well even though there are enough buses in use. To properly interpret your statistics, check to see if clumping is happening. If there is clumping, realize that wait times at some bus stops will be higher than at other bus stops. You can, optionally, try to incorporate something into the Bus class to keep a bus from getting to close to the bus in front of it. In the real world, a bus will hang out at a stop if the driver can see another bus ahead of it less than two stops away.
• This project is purposely vague in some respects so that you can decide what statistics are best gathered and determine what simulation tests you should run. But, present enough information so that the bus company can decide how many buses and what bus types it needs for various loads. Keep in mind that the bus company will want statistics for the busy times (lunch and rush hour), as well as off-peak times such as weekends and nights. A significant portion of the grading will be based on the report of your results which will include your simulation results presented in a useful format, conclusions and recommendations. This means that you will need to have a working simulator in order to have results to write about.
Grading and Deliverables
The report must be submitted as a pdf document along with the rest of your source code. 25% of the project grade will be somehow connected to the report. When deciding on statistics to maintain and the simulations to run, think about the need to support conclusions in your report. The report should be in the form of a consulting findings document that you might submit to the bus company. The report should include data such as average travel time of passengers (including wait time), queue lengths, and bus load, all summarized in a concise and readable fashion along with specific data that proves that the simulation results are correct. Please be sure that the report is concise. Do the numbers make sense? Are simulation runs at equilibrium? Certainly, some statistics are more difficult to properly calculate than others, but some of the simpler statistics to gather are the most useful. So, don’t try to everything at once. Get some statistics going, and verify them, before moving on. You may find that just the simple statistics are all that are needed to produce an effective report.
11
PROJECT 4 GRADING AND DELIVERABLES
A common expectation of large software projects is that they include a “README” file to famil- iarize the user with the project. Include a short README file along with your project; it should contain (at least) the following items, which are often included in README files for other projects:
• The project name and author information (include both partners names, and emails).
• Instructions for running your project on a new machine.
• An overview of the project organization and hierarchy.
• The data structures and algorithms used in the project, and why they are a good choice. • Any known bugs or issues associated with the project.
As this project is largely left up to student design, the intent of this README file is to familiarize your TAs with your project. A good README file will make grading the project easier.
This is a challenging project, but many find it to be the highlight of the course. Start now, and enjoy the ride!
12
