 |
Performance
of 50 Completed ATP Projects
Status
Report - Number 2
NIST SP 950-2
Chapter
5 - Information Technology
|
|
Union
Switch and Signal, Inc.
On Time with Rail-Traffic
Optimization Technology
|
| Over
80 percent of raw materials and goods travel by rail at some point
during shipment. Rail transport is prone to unexpected delays caused
by routing conflicts, accidents, and power outages that inconvenience
passengers and impair shipments between suppliers, manufacturers,
and retailers. These delays play havoc with just-in-time delivery
that manufacturers and distributors use to keep inventories low, and
can increase costs. Punctuality is equally important for passenger
trains: delays are a primary barrier to increasing ridership. And
because passenger and freight trains share 95 percent of the same
track miles, any delay can affect much of the rail system. |
COMPOSITE
PERFORMANCE SCORE
(Based on a four star rating.)
|
Problems with Existing Optimization Approaches
Traditional optimization software employs a linear decisionmaking process
whereby a single solution is reached. Traditional optimization techniques
generally seek a single solution, such as maximizing profit or reducing
cost. Each change in the environment (e.g., train delays or equipment
fault) triggers the optimization system to start again from scratch to
search for a new solution. This approach is both time-consuming and unrealistic
for effective use in planning real-time train movement. In contrast, standard
planning of train movement requires several objectives to be addressed
simultaneously, e.g., minimizing the cost of crews and minimizing lateness.
 |
| Better tools
for railway traffic planning could improve the rate of on-time arrivals. |
Union Switch and Signal
Company Sees Opportunity in University Research
Prior to applying to the ATP, Union Switch and Signal, Inc. (US&S),
a leading supplier of equipment to the
railroad industry, was working with a Carnegie Mellon University (CMU)
research team on technology for improving the safety and viability of
railroad equipment. In that process, US&S became familiar with optimization
research that was going on at CMU. US&S saw an opportunity to build
on the research by CMU to break through the technical challenges of optimization
for rail traffic scheduling. The optimization research underway at Carnegie
Mellon was referred to as the “Asynchronous Teams, or A_Teams technology.”
Shortly after discovering the A_Teams work at Carnegie Mellon, US&S
invited Sarosh Talukdar, a CMU professor of electrical and computer engineering,
to its offices to learn about potential applications of A_Teams technology
to rail traffic planning. A-Teams offered a number of attractive features
over traditional optimization approaches.
A_Teams technology
employs multiple software agents. The agents are autonomous pieces of
software that incorporate decisionmaking programs, memory, and the ability
to communicate with each other. These agents work together as a team,
each contributing its individual problem-solving expertise to provide
solutions. The agents operate on a population of solutions, continuously
improving the population by altering the solutions and then evaluating
each solution against the rest of the population.
One advantage of A_Teams
is that it allows optimization to be divided up into many subtasks—each
of which is addressed by teams of agents, allowing for alternative schedules
to be determined more rapidly. The flexibility of operations and adaptable
architecture help to break up the optimization problem into agent subtasks.
Thus, the A_Teams technology enables the handling of more complex problems
than the existing technology can handle. In
the case of railroads, this might include routing more trains over more
tracks, whereas traditional movement planning systems are able to plan
the movement of only one train at a time.
Another advantage
of A_Teams is that it enables more rapid adaptation to alternative schedules
because of changes in the environment (e.g., a track blocked by an accident)
and does not require a total reassessment. Teams of agents react to local
changes and make appropriate adjustments, testing the new solution by
comparing it with the existing pool of solutions. In addition, the A_Teams
is a modular approach, which allows networks to be upgraded and modified
merely by changing the population of agents. This is important because
incompatibility between different generations of software has been a particularly
troublesome problem for railway decision-support software: upgrading has
meant the complete replacement of software systems.
The university’s
modular problem-solving software appeared to offer potential for railroad
routing, but not without additional research. US&S wanted to exploit
the opportunity, but lacked the internal resources to mount the required
research effort alone.
With ATP’s Support,
US&S Adapts and Extends the A_Teams Approach
In 1995, the Advanced Technology Group (ATG), an R&D unit of US&S,
proposed a research project to adapt and extend the A_Teams approach to
make it suitable for rail traffic planning. The proposal scored high in
technical and economic merit, and US&S received a $2 million award
for research from ATP. The company contributed a cost share of $967,000
to the project.
The technical goals
of the project centered on developing a distributed optimization approach
to railroad routing, and adapted and extended Carnegie Mellon’s A_Teams
modular problem-solving approach. The research had three major components:
1) decomposing a scheduling problem into subtasks to be pursued by agents,
2) developing a messaging protocol for communication among subtasks, and
3) specifying programming agents to respond to information received.
Technical Goals Reached
Researchers at US&S made substantial progress in developing the necessary
infrastructure. They developed the basic tools and knowledge needed to
construct better A_Teams systems, including libraries of code needed for
agent construction, mathematical optimization models, system components,
and application interfaces to allow components of the system to work together.
Researchers at Carnegie
Mellon University were contracted to investigate potential organizational
designs for individual A_Teams software agents and groups of agents. In
addition, they provided expert advice on how the system could be designed
to allow software agents to communicate with each other in real time.
Pilot Testing on Trains
Efforts by US&S to commercialize work on the optimized traffic planner
are focused on two applications. The “Real-time Central Traffic Controller”
is software for real-time movement planning that is intended to provide
optimized routing plans to central office controllers. The “Offline
Railroad Operations Planner” is simulation software that will allow
railroads to evaluate alternative track layouts and routing plans. It
provides recommendations that can increase the capacity and throughput
of a railroad line. For example, it might identify a bottleneck in a railway
line and suggest laying double track to increase throughput at this trouble
spot.
Toward the end of
the project, funding was secured from a class 1 railroad (one of the six
largest North American railroads) to pilot-test the technology. US&S
researchers performed simulations of real-time movement planning using
data from the railroad, including typical schedules, track layout, speed
limits, and patterns of movement (e.g., periods of acceleration and deceleration).
The simulations demonstrated a 50 percent improvement in the rate of on-time
arrivals, a key performance goal, when compared to the performance of
traditional command-and-control software.
Unfortunately, the
railroad company that was supporting the pilot-testing was acquired by
another railroad company, and its new management, preoccupied with consolidation,
discontinued support for the project. The company’s management has
since reconsidered its decision, and, at the time of this study, was negotiating
a new arrangement with US&S. In addition, US&S at that time was
seeking to form cooperative development alliances with other class 1 railroads.
|
Project
Highlights
|
|
PROJECT:
To adapt and extend a distributed multiagent-based optimization
technology developed by Carnegie Mellon University (CMU) for use
in railway traffic planning.
Duration: 1/15/95-1/14/97
ATP Number: 94-01-0063
FUNDING (in
thousands):
| ATP |
$2,000
|
67%
|
| Company |
967
|
33%
|
| Total |
$2,967
|
|
ACCOMPLISHMENTS:
US&S researchers, working closely with university researchers
at CMU, adapted and extended a technology to simulate real-time
movement planning for railroads. The project:
- developed
the basic tools and knowledge needed to construct and implement
a better optimization system for railroad use;
- developed
two different software programs which implement the technology:
Real-time Central Traffic Controller, a real-time movement planning
software; and Offline Railroad Operations Planner, software allowing
railroads to evaluate alternative track layouts and routing plans;
- secured funding
from a class 1 railroad (one of the six largest North American
railroads) to pilot-test the technology; and
- achieved
a potential 50 percent improvement in rate of on-time arrivals
over the use of traditional command-and-control software.
|
COMMERCIALIZATION
STATUS:
Efforts by US&S to commercialize work on the optimized traffic
planner were focused on two software packages, each with specialized
applications: the Real-time Central Traffic Controller and the Offline
Railroad Operations Planner. The Real-time Central Traffic Controller
is intended to provide optimized routing plans to central office
controllers. The Offline Railroad Operations Planner provides recommendations
that can increase the capacity and throughput of a railroad line,
e.g., it can identify a bottleneck in a railway line and suggest
solutions to increase throughput at the trouble spot. The software
has performed well in pilot tests conducted in collaboration with
a railroad, but had not been commercialized as of the time of the
study.
OUTLOOK:
The commercialization of the two software packages is contingent
on the ability of US&S to enter into cooperative development
arrangements with prospective railroad customers. These customers
can provide necessary data to perform additional tests and funding
to support continued development
of the software. There are several factors supporting a favorable
outlook for commercialization: two software programs have been developed;
the initial test results were strong; and the railroad companies
have demonstrated interest. At the time of the study, however, uncertainties
remained about the willingness of the railroad companies to provide
the necessary follow-through support for commercialization.
Composite
Performance Score:
COMPANY:
Union Switch and Signal, Inc.
1000 Technology Drive
Pittsburgh, PA 15219
(Parent Company:
Ansaldo Signal, the Netherlands)
Contact:
Dr. Frank Boyle
Phone: (412) 688-2400 x3511
Subcontractor: Carnegie Mellon University
|
Return to Table
of Contents or go to next section.
Date created: April
2002
Last updated:
April 12, 2005
|
