CS177 Assignment 2 Spring 2003

A Moving Sidewalk Network for Campus

Due: 11:59pm Sunday May 18

I. Summary

Help the university's planning department evaluate the idea of installing a network of moving sidewalks between major building entrances and parking lots, by creating a model of pedestrian traffic flow around campus using CSIM.

II. Input Data

Note that your program does not need to have any kind of a graphical interface, such as a campus map augmented with the location(s) of the proposed moving sidewalks, or an animation to show the flow of pedestrian traffic around campus with or without the moving sidewalks. Instead, you only need to be able to read an abstract graph theoretic description of a simplified campus map from an input file (such as the sample here), which consists of the following:

The number of vertices, V, followed by a list of vertices, each representing an important location on campus such as the entrance to a major building or parking lot, or an intersection point between multiple paths. For each vertex, the file contains the following information on one line:

a sequence number from 1 to V,
the (x, y) coordinates of its location (in feet, relative to an arbitrary origin point),
whether it is an intersection point (Y or N),
and its name.

(Note: the location is provided for your convenience, in case you want to add some sort of graphical input or output to your program, and is not used within the specifications of the model -- except for "sanity checking" of the input data, to verify that the input length for each path is never shorter than the Euclidean distance between its two endpoints.)

The number of existing paths, followed by a list of edges, each representing an available direct path between two vertices. For each edge, the file contains the following information on one line:

the vertex numbers of its two endpoints,
its width (in feet),
and its length (in feet).

(Note: the path length may be significantly longer than the Euclidean distance between the two endpoints if the path does not follow a straight line.)

The number of moving sidewalks, followed by a list of moving sidewalks. For each moving sidewalk, the file will contains the following informationon one line:

the vertex numbers of its starting point and ending point,
its width (in feet),
its length (in feet),
and the speed at which it moves (in miles per hour).

(Note: each moving sidewalk entry is assumed to be unidirectional, so you need to include two entries in the file with the starting and ending points reversed, to create a bidirectional link between its two endpoints.)

You will also need to provide your program with a description of the pattern of movements for the pedestrians. Clearly, this pattern changes as a function of time-of-day, with greater numbers of people entring campus from the parking lots in the morning, greater numbers of people leaving campus in the afternoon, and increasing numbers of people moving from one building to another when classes end at the top of each hour. Rather than trying to represent all of this time-dependence in a single run of your program, you should instead study each of these different types of activity through a separate run. Thus, you should read the description of the traffic pattern from a separate input file (such as the example here), to make it easy to study the same campus model at different times of day. The traffic file will have the following format:

A V×V matrix R whose (i, j)th entry gives the exponential rate (in pedestrians per second) at which pedestrians leave from vertex i to reach a destination of vertex j. (Note: only buildings and parking lots should be used as a source or destination vertex, since it makes no sense for the intersection between paths to either magically create new people out of thin air or to make them disappear.)

III. Representation of Traffic Flow

Pedestrians will be represented by separate CSIM processes, each with the following set of attributes:

source and destination vertices, randomly generated according to the matrix R. The easiest way to do this is to create a separate traffic generator process for each non-zero entry in matrix R at program startup. Each call to the traffic generator function includes the required source, destination and rate as parameters, so after each invocation of the function splits off to run as a separate process after the create() statement it will only need to handle a fixed pair of source and destination vertices. Pedestrians will always follow the shortest (i.e., fastest) route between the source and destination.
desired walking speed, which is a uniform uniform random value between 2 mph and 4 mph.
laziness, which is true with probability 0.6 and false with probability 0.4. A lazy person will just stand on a moving sidwalk, whereas a non-lazy person will attempt to continue walking at his/her normal speed.

Movement of pedestrians along an existing path or moving sidewalk will be modelled in the same way. In other words, an existing path is just a special case of a moving sidewalk with its speed set to zero.

If there were no other pedestrians around to cause congestion, the pedestrian flow would be very simple to describe. Once the pedestrian enters the start of a path, it simply waits for enough time to elapse for it to move forward by the length of the path while travelling at some fixed speed, and then declares itself have arrived at the other end of the path. The "fixed speed" will be its desired walking speed, if it is following an existing path. However, it is using a moving sidewalk the "fixed speed" will be either: (a) the speed of the moving sidewalk, if the pedestrian is lazy; or (b) the sum of its desired walking speed and the speed of the moving sidewalk, if the pedestrian is not lazy.

However, if multiple pedestrians are travelling along the same path or moving sidewalk at the same time, congestion can occur if a (group of) faster traveller(s) catches up to a (group of) slower traveller(s) travelling in the same direction who entered the same path or moving sidewalk in front of it. To simplify the problem, we assume that congestion causes the two (groups of) travellers to merge into a single group which moves at the slower of the two speeds (i.e., the one in front); we do not consider the case where the faster travellers pass the slower ones, and thereafter continue at their previous (i.e., higher) speed.

Since the existing paths are (obviously) bi-directional, pedestrians also experience some congestion caused by travellers moving in the opposite direction. To model this effect, we will require pedestrians who wish to enter an existing path (i, j) from vertex i to compete with the stream of "reverse travellers" who have just completed the journey in the opposite direction for the right to pass through this exit point. In addition, we will assume that every pedestrian who is travelling along the same path in the opposite direction at the moment we calculate our our transit time at step 1 (below) will delay us by an additional 2 seconds.

In this case, the transit time for each existing path or moving sidewalk can be modelled very simply with the following set of rules:

Before entering an existing path, each pedestrian must first spend 3 seconds inside the same CSIM storage that is used to model congestion at the output point for reverse traffic on the same path (see item 4, below).
Pedestrians go through the entrance point to the path or moving sidewalk, one at a time, under the control of a CSIM facility. The purpose of the facility is to allow each pedestrian to briefly see a picture of the congestion ahead of it along this path or moving sidewalk, from which it can calculate the time at which it reaches the exit point at the other end. Thus, the exit time for a moving sidewalk will be the maximum of:
1. its transit time in the uncongested case, where it covers the whole distance at its desired "fixed speed" defined above; or
2. the exit time for the previous pedestrian, plus 2 seconds.
To obtain the exit time for an existing path, we apply the same formula as the moving sidewalk, plus an additional 2 seconds for every pedestrian travelling in the opposite direction who has already reached the entrance facility (described above) but has not yet completed its stay in the exit point storage (described below).
Thereafter, the pedestrian simply "sleeps" until its calculated exit time. If this time is greater than the uncongested case, then at some point along the way we know it must have caught up with some slower travellers, but we really don't need to worry about the exact history of events during its trip.
Once the pedestrian "wakes up" at the exit point, it must pass through a CSIM storage which models the congestion occurs as people try to move away from the exit point. We will used a constant service time of 3 seconds to represent this process. Since multiple people can exit from a wide sidewalk at the same time, the total capacity of the storage should be the width divided by 3 feet.
If the exit point is a crossroads where multiple paths and/or moving sidewalks meet, rather than the entrance to a building or parking lot, then the pedestrians must make their way through this crossroads area to the entrance point of the next path or moving sidewalk along their journey. Since moving through the crossroads becomes more difficult as it gets crowded, we will model each crossroads location as a CSIM storage, with a capacity of 50 people. In addition, the time each pedestrian spends at a crossroads location will be exponentially distributed with a mean of 20 seconds plus an additional 0.5 seconds for every other person already present in the crossroads when it wakes up from the 3-second exit delay period described in step 4. Note that our system would have a major safety problem if any pedestrians arriving from a moving sidewalk are blocked from entering the crossroads location because of the 50-person limit. Your program must be able to detect and report this problem, if it occurs.

IV. Measurements

Design your program so that, for the given combination of a campus description file and a traffic rate file, it outputs the mean and 95% confidence intervals for:

the average travelling time between each source-destination pair for which R(i, j) is positive.
the average utilization of every moving sidewalk
the maximum number of people within each crossroads location at any time
the average amount of time that each pedestrian is delayed because of the non-overtaking rule.

V. Questions

Prove the correctness of the max-based exit time calculation that is given within rule one.
In the real world, (groups of) faster pedestrians can overtake slower ones who are in front of them, as long as the number of people in the slower group is small enough to prevent it from blocking the the entire width of the path or moving sidewalk. Briefly explain how this feature could be incorporated into the model without resorting to the drastic strategy of breaking each path into a sequence of small segments that the pedestrians must cross one after the other.
Requiring all pedestrians to follow a single, fixed path between a given source and destination may be inefficient if there are several paths available which are almost equally good. In the real world, pedestrians would soon learn to distribute themselves across all available paths to minimize their travelling times. How could you incorporate this feature into your model?