Tag Archives: network

Better Traffic Networks Through Vehicle and Signal Coordination

My friend Phil Spadaro pointed me to two interesting articles on traffic management techniques being studied by BMW and Audi here and here. The idea is to allow traffic lights and cars to communicate, which would yield better traffic flow, reducing time spent at red lights and, as a consequence, reducing fuel consumption. From the Audi article:

The results obtained during the first travolution project in 2006 were immediate and dramatic: reduced waiting times at traffic signals cut fuel consumption by 17 percent…The secret of this success: the traffic signals in Ingolstadt are controlled by a new, adaptive computing algorithm that Audi developed in cooperation with partners at colleges of advanced engineering and in business and industry. Audi has now developed travolution still further, by enabling vehicles to communicate directly with traffic light systems, using wireless LAN and UMTS links…The traffic signals transmit data that are processed into graphic form and shown on the car’s driver information display screen. The graphics tell the driver for instance what speed to adopt so that the next traffic light changes to green before the car reaches it. This speed, which keeps the traffic flowing as smoothly as possible, can then be selected at the adaptive cruise control (ACC) – but the driver can also delegate this task to the car’s control system.

The savings are significant:

When the car is part of a network in this way, the driver can reduce the amount of time spent at a standstill and cut fuel consumption by 0.02 of a litre for every traffic-light stop and subsequent acceleration phase that can be avoided. The potential is enormous: if this new technology were applied throughout Germany, exhaust emissions could be lowered by about two million tonnes of CO2 annually, equivalent to a reduction of approximately 15 percent in CO2 from motor vehicles in urban traffic.

I am sure that there are many parts of this whole coordination process that involve some OR. It must be really cool to work on a project like this. On a different, but related, note I also believe that a lot of traffic jams have psychological reasons. People’s curiosity and lack of advance planning can severely influence their driving behavior. One great example of this is the Golden Glades fork here in Miami:

People going north on I-95 (traffic pattern on the right, going upward in the picture) have to decide among one of three directions: taking the Turnpike (letter A in the picture), continuing on I-95 (letter B), or taking the rightmost exit (letter C). It just so happens that most drivers realize that they have to change lanes at the last minute and this fork is constantly congested (even without accidents). There’s a very simple simulation experiment I always wanted to run but never had the time to: simulate the traffic flow when most people decide to change lanes very close to the fork versus the situation when people change lanes at uniformly distributed points way ahead of the fork. I bet you’d see much better flow in the second case. I hope that one day, when computers can drive for us, the driving algorithms will take care of these issues.

Leave a comment

Filed under Applications, Network Flows, Research, Traffic Management

Twilight Network Flow

CAUTION: Spoiler Alert!

Part of a professor’s job is to come up with new exam questions each year. That may be a time-consuming (and sometimes tedious) task. You want the question to be just right: not too easy, not too difficult, and capable of testing whether or not the students understood a given concept. This year, I figured I might as well have some fun while doing it. Inspired by Laura McLay’s insightful (and very popular) post on vampire populations, I decided to create a Twilight-themed network flow question:

Alice is in charge of planning Edward and Bella’s wedding and she ordered 2000 roses to be delivered to three locations as shown in the network below. The Cullen’s house (node 2) needs 1000 roses, Charlie’s house (node 4) needs 800 roses, and Billy’s house (node 7) is supposed to get 200 roses (just to tease Jacob). The numbers next to the arcs of the network represent shipping costs per rose (in cents); they’re proportional to the distance between each node. The roses are coming from two local growers in Forks (nodes 1 and 3). Each of them can supply 1000 roses. Arrows with two heads indicate that shipments can be made in both directions.

Write down the supply and/or demand values next to each node and write a linear programming model to determine the shipment plan that minimizes the total cost of delivering all the roses (include all the necessary constraints). (Note: Alice already knows whether you’re going to get the right answer.)

The second half of the fun is to see if any students react to it. In fact, I got a couple of interesting written comments: “How dare you incorporate Twilight into Management Science?”, and a Harry Potter enthusiast wrote “Team Harry!”, while at the same time substituting the names of Hermione, Harry, Ginny and Malfoy for Alice, Edward, Bella, and Jacob.

4 Comments

Filed under Exam Fun, Linear Programming, Modeling, Network Flows, Teaching