Programming assignment 2

A group simulation project

Discuss at http://guzdial.cc.gatech.edu:8080/cs2390.23

The Problem

In this project, you will design routes for a subway, trading off costs between laying track and buying trains. Your goal is to optimize (a) maximally the number of people you can get through your system and (b) minimally the average total time people are in the system.

The city you are building for is built on a grid. There are five stations to be placed on this grid:

[Grid graphic]

Step One: Design the Subway System

Your total budget for designing the subway system is $600,000.

Your first task is to lay track to connect these stations. You may lay tracks along the grid lines. These segments of track cost you $10,000. For example, to connect (1,1) to (2,2), you can lay track (1,1) to (1,2) to (2,2). However, you

directly connect (1,1) and (2,2), but those segments of track cost you $20,000. Each segment of track includes two lines for bi-directional travel on that segment.

Your second task is to buy trains. Each train costs you $50,000.

Your program does not have to dynamically design the layout! Rather, you design it then you implement your solution design.

Step Two: Design the Routes

Once you lay out your subway system, you can open for business! (In other words, you cannot dynamically lay track once people have started arriving!)

Each train holds 30 people. You may define whatever route you would like for your trains (though, of course, they can only travel on the track you've laid!). A train can start on any track. The train takes (Normal mean: 2 deviation: 1) minutes to travel each segment of track. The train takes a random amount of time at a station, on a probability distribution of (Normal mean: 5 deviation: 2). (You don't have to worry about more than one train on a segment of track at a time - each segment is actually multiple lines and the linespeople make sure that the trains don't crash.)

Every five minutes, fifteen people arrive into your subway system. They arrive at a random station drawn from the SampleSpace: #('TimesSquare' 'TimesSquare' 'Midtown' 'Midtown' 'Midtown' 'Rosslyn' 'Kendall' 'Oakland' 'CentralSquare' 'CentralSquare' 'CentralSquare') . They want to go to a random station drawn from the SampleSpace (but subtracting off the arrival station!): #('TimesSquare' 'Midtown' 'Rosslyn' 'Rosslyn' 'Kendall' 'Oakland' 'Oakland' 'CentralSquare' 'CentralSquare') .

When the train gets to the station, it can load up to 30 people. (If more people arrive while the train is at the station, you can load them in, too!) The train cannot wait until filled with 30 people. You can have at most two trains in a station at a time. (Other trains wanting to enter the station must wait until a train berth is available in the station.)

It's perfectly reasonable to allow passengers to transfer at a station, but wait time accrues at the waiting point.

Your Goal: Get as many people to their destinations in six (simulation) hours of running your system, and do it in as little as (simulation) time as possible.

The Assignment

You are to work in a team of students (two to four members per team) to create a solution to this problem in two weeks. You must work in a team. Not working on a team is an automatic reduction of 15 points on your project grade. Teams offer the opportunity to get the problem done easier through collaboration, but you have to collaborate well for that to work. Teams offer the opportunity for better learning through discussion, but you have to meet to discuss. You create your own teams.

ON FEBRUARY 12, you are to hand me a piece of paper with the names, email, and student numbers of all the members of your team.

We will call your program by executing: 

	SubwaySimulation demo

Your simulation should then (a) lay out the subway (you don't have to compute where to lay track -- you can figure it out by hand -- but it's okay if you want to do the planning algorithm yourself) and (b) run the simulated subway system for six hours of simulation time. At the end of that time, you should output (and hand in!). NOTE! YOU MUST HAND IN PIECES OF PAPER WITH ALL OF THESE PIECES EXPLICIT! "It's in the code" IS NOT AN ACCEPTABLE RESPONSE!

  1. Where you laid track, how many trains you purchased, and the total cost of your subway. (Hint: It should be less than $600,000.)
  2. The route of each of the trains. List all the segments on which you've laid track.
  3. The number of people who got to their stations in the six hours.
  4. The average time of those who got to their stations from entering the subway system to arriving at their station ("system time").
  5. The histogram of system time.
  6. A histogram for each train of the train's system time (i.e., the system time for each passenger who arrives at his/her final destination on the given train -- Note: In the case of transfers, the passenger's system time only applies to the final train).

Graphical User Interface

Displaying a graphical user interface during the simulation is problematic. As you'll discover when using the SimPkg, individual simulation object's tasks are in separate processes. When things are working, it's hard for the display process to keep up with all that's happening. (Related note: If you ever get an error box with nothing in it while using the SimPkg, hit Control-C. That will stop the current process, and it will allow the display process an opportunity to draw the error box.)

But you can provide a user interface to review the system performance after the run! Provide a user interface that allows the user to review the performance of each of the trains. Clicking on a train's button should display the histogram of that train's system time.

[GUI graphic]

EXTRA CREDIT!

Resources and Details

News Page | CS2390 Win'98 Home Page | CS2390 CoWeb | STABLE | BOOST
Questions/comments/concerns to guzdial@cc.gatech.edu
Page last updated 2/16/98; 2:55:54 PM