How can SAS improve my city driving experience?
You’ve had that experience. You just want to pick up a snack from your local Bojangles drive-through and get back home peacefully. But they are out there. Traffic lights. You find them every few city blocks. Even if you are the only driver on the road, you still have to wait for those red traffic lights to turn green. Even the thrill of electric vehicle acceleration starts to wear off after getting caught by 2 or 3 consecutive red lights.
It’s time for us to unite and take action. But how? With SAS Optimization, of course.
In this first post of the series, I’ll use proc optmodel to find a solution for this traffic light problem. The idea is to find a way to synchronize green traffic light signals so that a vehicle traveling at the stated speed limit through the main street of a town will catch a green light at every intersection. Imagine going from one end of town to the other without having to stop while achieving epic gas mileage – no matter what you drive.
Let’s get started.
I find it helpful to first sketch out the problem on a whiteboard. Before reading on, take a minute to create your own diagram of the problem or write a list of the information needed to start solving it.
Select any image to see a larger version.
Mobile users: To view the images, select the "Full" version at the bottom of the page.
Let's see if we can even build a solution by trying to optimize the timing of green traffic light signals for just 4 intersections at various distances with a speed limit of 35 mph.
We start with traffic lights (1-4) with distances between them of (1.2, 1.02 and 1.5) miles. This gives us 3 sections of road between 4 traffic lights.
We need to know the time it takes for a traffic signal to complete a full cycle. Within a cycle, we need to know how much time it is on green. In our example, the cycle duration is the same for all 4 traffic lights, while the cycle start times can differ.
Other items to choose or calculate:
| Attribute: | Value: |
| Optimization Timer start | 0 seconds |
| Segment Travel time | (distance(mi)/mph) * 3600 |
| Signal offset from time start | |
| Cumulative distance traveled | |
| Cumulative elapsed time |
This is what I used as a Whiteboard Diagram to get into the problem:
Now that we have something to help us think through the issues, we can start planning. Our Course: Optimization Concepts for Data Science and Artificial Intelligence does a great job of teaching the proc optmodel procedure.
The intersections and distances-between-intersections can be listed in ‘sets’. Sets define the index domains for parameters, variables, and constraints. They represent collections of elements or tuples that describe the structure of the optimization model, but do not store data. This structure is useful for reusing the model for other street/speed configurations. The following sets define the index domains used later in the model.
set NODES = 1..4; /* four traffic lights */
set LINKS = 1..3; /* three links between the four traffic lights */
Next, we might define a numeric parameter such as "link_mi" indexed over the set LINKS:
num link_mi {LINKS};
and assign mileage distances to each link between traffic lights:
link_mi[1] = 1.25; /* 1 -> 2 */
link_mi[2] = 1.20; /* 2 -> 3 */
link_mi[3] = 1.50; /* 3 -> 4 */
The indices 1,2 and 3 come from the previously defined set LINKS and represent the three road segments in order.
We also need to record the traffic light cycle and how much of it is a green light. In the code provided at the end of the post, you will notice that I entered a cycle time of 90 seconds, where 30 seconds of the cycle shows green. These are parameters in the model. Each traffic light will repeat the 90 second cycle pattern, so the vehicle will not necessarily meet a signal on its first cycle. Our code will number the consecutive cycles for each traffic light (starting at 0). This will be used in the objective of our traffic problem.
Since we want to give the city planner timing information to coordinate each traffic lights’ cycle start time, we initialize the trip start time as time zero. The model optimizes an offset for each traffic light on the route, so the green signal starts exactly at the vehicle’s arrival time when it is traveling at the stated speed limit. We add decision variables to our code to account for each light's time offset and cycle.
Proc optmodel can use various solvers to find solutions. The Linear Programming (LP) solver is used when decision variables of a problem can take on continuous (and possibly fractional) values such as the weight in kilograms of a parcel being loaded on a plane. The Mixed Integer Linear Program (MILP) solver is used when a variable in the model is declared as integer or binary.
In this problem, the decision variable: cyc is defined as integer. This requires use of the MILP solver. The other decision variable phi however, can take on a continuous value. This is how those variables are defined in the code:
var phi {NODES} >= 0 <= CYCLE; /* offset in seconds */
var cyc {NODES} integer >= 0; /* cycle index */
A constraint is added to our model to align the start of green exactly at time t[i] where i refers to a traffic signal from the set NODES. The model will find an offset value that satisfies the constraint. The code for the constraint can be found in the program.
The objective for this solution is to Minimize the sum of cycles as a vehicle moves through the NODES (intersections). The solve statement puts the optimization in motion and looks for a solution. The cyc[i] parameter references the cycle number for each intersection {i in NODES}. The value of this decision variable must be an integer, while the other decision variable representing the signal timing offset can be continuous.
/*---------------------
Objective
Minimizing the sum of cycle
indices chooses the smallest feasible cycles (unique solution).
-----------------------------*/
minimize MinCycles = sum {i in NODES} cyc[i];
solve with MILP; /* Mixed Integer Linear Programming Solver being used */
A portion of the optimization results show the arrival time at each intersection at a traveling speed of 35 mph and the offset from time 0 that the green signal starts at each intersection. The Cycle index shows that by the time the vehicle gets to intersection 4, the light has completed several cycles already.
From these optimization results, I'd instruct the city planner that the optimal signal plan consists of timing the green-cycle start relative to the cycle start for intersection 1 using the offsets provided in this table for each traffic signal at their respective numbered intersections. This plan resulted in the best traffic flow along the street thereby providing vehicles with the shortest feasible travel time given the cycle time and distances.
The following plot illustrates a vehicle arriving at a traffic light starting its green phase throughout the 4 traffic lights. The numbers within the plot show the cumulative mileage traveled.
There are a few additional tricks you will notice when you look at the code provided below. The optimization objective for the model is to minimize the sum of cycle distances to choose a feasible solution.
Copy the code, change the number of intersections, distances between intersections and speed limits. Run the program in SAS Studio and make the solution your own.
Here is the program that generated the solution.
/*===============================================================
Traffic Green light alignment (PROC OPTMODEL)
----------------------
- Vehicle travels at the posted speed limit (35 mph).
- Distances between intersections range from 1.2 and 1.50 miles.
- Each signal has a fixed cycle (CYCLE) and a fixed green duration (G_DUR).
- Compute FREE-FLOW arrival times t[i] from distances and speed.
- Set each signal's offset so that the green STARTS
exactly at the vehicle's arrival time t[i].
phi[i] + cyc[i]*CYCLE = t[i]
KEY LEARNING POINTS
-------------------
- Using sets and arrays in PROC OPTMODEL (SETS, PARAMETERS).
- Integer cycle index and continuous offset alignment constraints.
===============================================================*/
options nodate nonumber;
ods listing;
/*===============================
Optimization (feasibility)
===============================*/
proc optmodel;
/*-----------------------------
Sets
-----------------------------*/
set NODES = 1..4; /* four intersections */
set LINKS = 1..3; /* three links between the four intersections */
/*-----------------------------
Parameters (global)
-----------------------------*/
num CYCLE = 90; /* seconds, common cycle length */
num G_DUR = 30; /* seconds, green duration (teaching default) */
num SPEED_MPH = 35; /* posted speed limit */
/*-----------------------------
Link distances (miles) between intersections
This could be read in from an external dataset
-----------------------------*/
num link_mi {LINKS};
link_mi[1] = 1.25; /* 1 -> 2 */
link_mi[2] = 1.20; /* 2 -> 3 */
link_mi[3] = 1.50; /* 3 -> 4 */
/*-----------------------------
Calculate arrival times and cumulative distances
t[1]=0; then accumulate by link time
Travel time (sec) = distance(mi)/mph * 3600
-----------------------------*/
num t {NODES}; /* arrival time at each intersection */
num cum_mi {NODES}; /* cumulative distance from the start */
t[1] = 0; cum_mi[1] = 0;
for {lk in LINKS} do;
t[lk+1] = t[lk] + link_mi[lk] / SPEED_MPH * 3600;
cum_mi[lk+1] = cum_mi[lk] + link_mi[lk];
end;
/*-----------------------------
Decision variables
- phi[i]: signal offset within [0, CYCLE)
- cyc[i]: which cycle the start-of-green occurs on
We align: phi[i] + cyc[i]*CYCLE = t[i].
-----------------------------*/
var phi {NODES} >= 0 <= CYCLE; /* offset in seconds */
var cyc {NODES} integer >= 0; /* cycle index */
/* Anchor the first signal at time 0 for the city planner */
fix phi[1] = 0;
fix cyc[1] = 0;
/*-----------------------------
Alignment constraints:
Start-of-green occurs exactly at t[i]
(base green start at 0, so start time = phi + cyc*CYCLE)
-----------------------------*/
con AlignStart {i in NODES}:
phi[i] + cyc[i]*CYCLE = t[i];
/*-----------------------------
Objective
Minimizing the sum of cycle
indices chooses the smallest feasible cycles (unique solution).
-----------------------------*/
minimize MinCycles = sum {i in NODES} cyc[i];
solve with MILP; /* Mixed Integer Linear Programming Solver being used */
/*-----------------------------
Output for plotting
We store:
- arrival time t[i]
- cumulative distance cum_mi[i]
- offset phi[i]
- cycle index cyc[i]
- fixed green start (0) and end (=G_DUR) relative to cycle start
-----------------------------*/
create data signal_plan
from [i]=NODES
t = t[i]
distance = cum_mi[i]
offset = phi[i]
cycle = cyc[i]
gstart0 = 0
gend0 = G_DUR;
/* Convenience: also export parameters */
create data signal_params from CYCLE G_DUR;
/* show details for exploring results */
expand;
quit;
proc print data=signal_plan noobs label;
label i='Intersection' t='Arrival (s)' distance='Distance (mi)'
offset='Offset (s)' cycle='Cycle idx' gstart0='Green start@0'
gend0='Green end@dur';
run;
Watch for my next post on this scenario . Drive safely, and be sure to check it out!
Thanks for reading!
Find more articles from SAS Global Enablement and Learning here.
