Project 2: One Way Street

When visiting Japan many years ago, I was impressed when I noticed that between some train stations there was only a single track. Trains in both directions were managed using a very tight schedule that allowed the one-way segments to be used alternately in opposite directions. Stations had multiple tracks, allowing trains to pass by each other. (In fact, the scheduling problem was even more impressive because there were both local and express trains in each direction, and express trains overtook local trains while they were waiting in the station.) A similar situation occurs during roadworks, where one lane of a road is closed, and traffic is routed on the other lane by a road crew. Automobile ferries have similar behavior in creating one-way-at-a-time traffic. There are short segments of mountain roads in Australia that are single lane, where downhill traffic is expected to wait for uphill traffic.

This project aims to efficiently transport vehicles on a single-lane road network separated by parking lots that can hold a given number of vehicles. In this network, all vehicles move at 20m/s. It therefore takes 10 seconds for a vehicle to traverse a 200-meter road segment. Vehicles are 5m long, and must be separated by 5m, so that the maximum throughput for a road is 2 vehicles/second. Vehicles traveling in opposite directions should never be on a common road segment at any time. (Why?)

While the general network problem is complex (and we might think about it if we have time) we'll focus for this project on a linear network. A linear network has two endpoints that are parking lots with unlimited capacity. Vehicles appear at one endpoint, and need to make their way to the other endpoint (at which time they disappear from the simulation). The difference in time between when vehicles appear and disappear is used to calculate the score (see below).

In a linear network, parking lots are ordered from left to right. Intermediate parking lots (i.e., not the endpoints) have a finite capacity, and are connected to their two neighboring parking lots by exactly one road segment. Each road segment has an integer length that is divisible by 5, measured in meters. The number of parking lots, their capacities, and the road segment lengths are specified in a map file that is read in by the simulator at the start of the simulation.

Your player sets the traffic signals at the ends of each road segment to control entry; exit is uncontrolled. A green signal means that vehicles may enter that road segment, while a red signal prevents vehicles from entering the road segment. You probably want to avoid having green signals at both ends. (Why? Would it make sense to sometimes have red signals at both ends?)

Vehicles arriving at a parking lot join the queue. Parking lots can contain vehicles traveling in both directions; vehicles remember which way they are traveling. For each direction, parking lots are first-in first-out queues. Vehicles in the parking lot have the first opportunity to enter a road segment. The simulator will send them on their way if (a) the light is green, and (b) there is sufficient separation from the previous vehicle. A vehicle may arrive at a parking lot with an empty queue and depart on the same turn if the conditions permit. The simulator works in quarter-second units of time, the time taken for a vehicle to advance exactly one vehicle length.

Your player will fail if any of the following happens:

If you manage to complete the simulation (i.e., do not fail) then all vehicles will have reached their destination. Your score will be calculated based on the distribution of latencies encountered by the vehicles. The minimum possible latency m is the total length of all road segments divided by 20. Drivers that achieve a latency of m are perfectly happy, and add zero penalty to your score. (The goal is to minimize your score.) Drivers tend to be relatively tolerant of small latencies, but disproportionally dislike long latencies. Thus, the penalty associated with a latency of L is $L\log L - m\log m$, which is superlinear in L.

On each time unit, the simulator will ask your player how to set the traffic lights. Your player has access to all of the current state information, including the queues at each parking lot, and the positions and starting times of all active vehicles. The player does not have access to information about when vehicles will first appear at the end-points, or how many total vehicles are to be processed. Your programs will be given a limited amount of compute time on each cycle, say one CPU-second.

The simulator reads the vehicle counts and timing information from a timing file. The timing file should be generated in advance, either manually, or with the aid of a program. (The format of the timing file will be provided later.) Hopefully we'll be able to explore a variety of timing patterns, including both uniform and nonuniform patterns.

Some things to think about:

Ken Ross 2013-09-17