DIMACS

Center for Discrete Mathematics & Theoretical Computer Science

DIMACS EDUCATIONAL MODULE SERIES

MODULE 04-2 Modeling Traffic Jams with Cellular Automata

Date prepared: September 13, 2004

Stephanie Edwards University of Dayton Dayton, OH 45469-2316 email: sedwards@udayton.edu

Mark Ginn Appalachian State University Boone, NC 28608-2092 email: ginnmc@appstate.edu

John Harris Furman University Greenville, SC 29613 email: john.harris@furman.edu

Gregory Rhoads Appalachian State University Boone, NC 28608-2092 email: rhoadsgs@appstate.edu

DIMACS Center, CoRE Bldg., Rutgers University, 96 Frelinghuysen Road, Piscataway, NJ 08854-8018

TEL: 732-445-5928 • FAX: 732-445-5932 • EMAIL: center@dimacs.rutgers.edu

                         Web: http://dimacs.rutgers.edu/

Founded as a National Science Foundation Science and Technology Center and a Joint Project of Rutgers University, Princeton University, AT&T Labs - Research, Bell Labs, NEC Laboratories America and Telcordia Technologies with affiliated members Avaya Labs, HP Labs, IBM Research, Microsoft Research.

Module Description Information

• Title:

Modelling Traffic Jams with Cellular Automata

• Authors:

Stephanie Edwards, University of Dayton Mark Ginn, Appalachian State University John Harris, Furman University Gregory Rhoads, Appalachian State University

• Abstract:

The module touches on several topics of mathematical interest. Mathematical modeling in general is discussed briefly at the start, and then some details regarding traffic models are given. Cellular automata (CA), both deterministic and probabilistic, are introduced as a method for modeling traffic flow. The software package Mirek’s Cellebration (MCell) is presented as a way of handling the long-run forecasting of different CAs.

• Informal Description:

The concept of cellular automata is motivated by easy-to-follow examples. While much of the material in the module concerns simple deterministic CAs, there is a section at the end on probabilistic CAs. Instructors could spend as much or as little time as desired on each type. MCell is a software package that is available for free download, and students will enjoy trying out its many interesting features. Regarding traffic, students can easily experiment with initial densities and other features that affect the way traffic flows. There are plenty of exercises throughout the module that give students the opportunity to solidify the concepts for themselves.

• Target Audience:

This module is designed for advanced high school students and lower level college students. It would be a good module for a liberal arts mathematics class.

• Prerequisites:

This module assumes some familiarity with computers and downloading software from the internet. It assumes that the students have had high school algebra.

• Mathematical Field:

Probability, Discrete Mathematics, Cellular Automata

• Applications Areas:

This module uses cellular automata and technology to model traffic jams.

• Mathematics Subject Classification:

Primary: 37B15 Secondary: 60K30 • Contact Information:

Stephanie Edwards University of Dayton Dayton, OH 45469-2316 email: sedwards@udayton.edu

Mark Ginn Appalachian State University Boone, NC, 28608-2092 email: ginnmc@appstate.edu

John Harris Furman University Greeneville, SC, 29613 email: john.harris@furman.edu

Gregory Rhoads Appalachian State University Boone, NC, 28608-2092 email: rhoadsgs@appstate.edu

• Other DIMACS modules related to this module:

04-1: Probability and Chip Firing Games