Project3: Where's My Bus?

Have you heard the term ``bus bunching''? Have you experienced it? Bus bunching occurs on long bus routes, where buses seem to come in bunches, with large gaps between the bunches.

Why does it happen? Suppose we start with a collection of equally spaced buses on the route. Due to random fluctuations, some of the gaps will get a little bit bigger and some will be a little bit smaller. A smaller gap means fewer passengers to pick up, which means the bus will progress faster, which means the gap gets smaller. Similarly, a larger gap means more passengers, which means slower progress and the gap gets bigger. In the end, the small gaps shrink to zero, causing buses to bunch, while the big gaps get bigger.

I hear you saying ``What can I do about it?'' I'm glad you asked.

You are in control of the M4444 bus route. There are many stops on this route, and passengers show up at stops in a random, statistically generated way. You have a certain number of buses, and you need to direct them in order to minimize the average time taken to get passengers to their destinations. We will assume that the bus operates on a long, straight two-way street, and that each bus-stop serves buses going in either direction. The route is a simple linear route, with $n$ equally spaced stops, where $n$ is a parameter. The terminus is stop number 1, with stop number $n$ being the other endpoint.

You have a variety of weapons in your arsenal. You have fine-level control over each bus on the route. You may instruct a bus to:

• Start a route. Only a parked bus may start a route, and intially all buses are parked at the terminus. Note that a bus parked along the route may start the route in either direction. A bus that starts a route immediately begins to take on passengers from the current stop.
• Designate that a parked bus is an express bus that does not stop at certain stops. You get to choose the stops for each bus, but once chosen they can't be changed until the bus is parked again. A passenger who wishes to get to a stop not visited will always get on the bus; that passenger will get off at the last stop before his/her desired stop, to wait for the next bus. Both stop 1 and stop $n$ must be among the stops of every bus.
• Move to the next bus stop. The movement takes time proportional to the distance to the stop, plus a randomized component corresponding to the number of red lights encountered. The stop itself will take time proportional to the number of passengers getting on and getting off. You can add time to the stop if you wish. A bus cannot skip a stop unless it's been designated an express bus not stopping at that stop. When a bus reaches an endpoint (stop 1 or stop $n$) it automatically becomes parked.
• Park a bus at a stop. This can be done when the bus has passengers; all passengers get off and have to take the next bus. You get an ``inconvenience point'' for each passenger who is affected.
• Zap a parked bus to another bus stop. This is equivalent to sending the bus empty along the route, not stopping along the way. It takes time proportional to the distance travelled, plus the randomized component for red lights. At the final location, the bus will again be parked, ready for further instructions.

The bus has fixed capacity, and cannot take more passengers than its capacity. Passengers wait in a FIFO queue at each stop.

We will provide a simulator for the bus system, and your program will interact with the simulator to direct the buses. You do not have access to information about how many passengers are waiting at each stop, nor do you have information about how full each bus is. However, thanks to GPS technology, you do know the position of each bus at each time point. The position is a floating point number between 1 and $n$. For example, a position of $1.75$ means that the bus is three quarters of the way from stop 1 to stop 2 (or one quarter of the way from stop 2 to stop 1). You also know whether a bus is parked, and in what direction the bus is moving.

Your goal is to minimize the average waiting time of all passengers. That statistic will be measured by the simulator, and returned at the end of the simulation. The simulator also keeps track of inconvenience points. Feel free to consider strategies that might reduce average waiting time even if they increase the number of inconvenience points. (We'll discuss in class how to trade-off inconvenience points for time.)