# Bus scheduling algorithm picks up the slack

##### October 23, 2007

A prizewinning paper by a USC Viterbi School engineer elegantly solves a basic transit scheduling problem, potentially meaning shorter waits and faster trips for riders.

The question: how much slack should schedulers of a bus or tram line add to keep operations from bunching up? Maged Dessouky, a professor in the Viterbi School's Daniel J. Epstein department of Industrial and Systems engineering joined with two colleagues to analyze this problem.

Slack time is extra time built into a bus schedule to accommodate unexpected delays. The paper published in November 2006 issue of Transportation Science notes, "if slack time is insufficient, buses are unlikely to be able to catch up with the schedule when they fall behind, deteriorating reliability. But too much slack time reduces service frequency, which may inconvenience passengers."

For the simplest case, a single vehicle traveling in a loop, the algorithm published in the paper gives an exact number, based on the size of the loop and the distribution of the of the travel time delay. The analysis also provides a way to approximate the effect of adding more busses to the loop.

The calculations are not simple. The effects that the equations have to model involve human behavior that is easy to describe, but hard to quantify. For example, if trains or buses are spaced close together (less than 10 minutes apart, typically), travelers tend not to consult schedules or expect vehicles to arrive exactly on time, and buses can leave early without upsetting travel plans. If buses are an hour apart, this isn't true.

And delays tend to be cumulative. "Buses on frequent lines have a tendency to bunch … when a bus falls slightly behind schedule it tends to pick up more passengers, causing it to slow further."

While not all effects like this can be modeled, a surprising amount of the dynamics can be captured by abstracting and making simplifying assumptions, according to the paper by Dessouky and co-authors Jiamin Zhao and T.S. Bukkapatnam, both formerly at USC as graduate student and assistant professor respectively. The paper won a "Best Paper for 2007" award from the Institute For Operations Research and Management Science (INFORMS) Transportation Science and Logistics (TSL) Society

The work comes off of empirical studies published by Dessouky in 1999 analyzing bus operations at the Los Angeles Metropolitan Transit District. At the time Dessouky measured an average slack time ratio of .25 on three MTA lines - that is, a bus trip scheduled to take an hour generally was accomplished in 45 minutes, with the extra fifteen minutes in the schedule built in to accommodate possible delays.

But was the 15 minutes more than necessary" Dessouky later worked with the MTA to incorporate these delay measurements into more effective scheduling, while continuing to try to build the dynamics he found into equations to find out what the optimal level might be.

The 2006 paper uses the equations to create curves to correlate average levels of delay and slack time ratios and, by further transpositions, with resulting waiting time for passengers, leading to an approximation of how much slack time is optimal, depending on total round trip travel time. The bottom line — build in between 15 and 20 percent slack, more for longer trips.

Dessouky says no transit system is yet using the new algorithms to schedule operations but "our next step which is to make the agencies aware of our approach instead of the current method of using rules of thumb."

Dessouky will receive his award November 5, at the INFORMS 2007 Annual Meeting at the Sheraton Seattle Hotel in Seattle, WA.

Source: University of Southern California

## Related Stories

#### Paper: Young workers hit hardest by slow hiring during recessions

May 17, 2016

The saying "Youth is wasted on the young" may ring hollow to young workers who were unable to find work or begin building a career during the Great Recession. When hiring slows during recessions, the brunt of job losses is ...

#### Rising levels of 'underemployed', according to new research paper

May 3, 2013

More and more people want to work longer hours – but can't because there isn't a demand for their services. Meet the "underemployed".

#### Evolution of moral outrage: I'll punish your bad behavior to make me look good

February 25, 2016

What makes human morality unique? One important answer is that we care when other people are harmed. While many animals retaliate when directly mistreated, humans also get outraged at transgressions against others. And this ...

#### Mother's little helpers let her relax

October 24, 2012

Having relations around to help look after the kids lets mothers ease off and save energy for the next lot, a study of Australian cooperative birds shows.

#### Tiny RNA has big impact on lung cancer tumors

December 7, 2009

Researchers from Yale University and Mirna Therapeutics, Inc., reversed the growth of lung tumors in mice using a naturally occurring tumor suppressor microRNA. The study reveals that a tiny bit of RNA may one day play a ...

#### Biologist describes optimized cellular replication as a systems engineering problem

February 17, 2015

(Phys.org)—Biologist Rami Pugatch of Princeton's Simons Center for Systems Biology has characterized the self-replication process of Escherichia coli according to a scheduling policy model derived from industrial processes. ...

## Recommended for you

#### Sudden extinction of Neanderthals followed population peak

July 26, 2016

Neanderthals once populated the entire European continent. Around 45,000 years ago, Homo neanderthalensis was the predominant human species in Europe. Archaeological findings show that there were also several settlements ...

#### DNA analyses reveal genetic identities of world's first farmers

July 25, 2016

Conducting the first large-scale, genome-wide analyses of ancient human remains from the Near East, an international team led by Harvard Medical School has illuminated the genetic identities and population dynamics of the ...

#### First discovery from 'New Riversleigh'—a new extinct carnivorous marsupial

July 25, 2016

A new species of extinct flesh-eating marsupial that terrorised Australia's drying forests about 5 million years ago has been identified from a fossil discovered in remote northwestern Queensland.

#### Ancient feces provides earliest evidence of infectious disease being carried on Silk Road

July 21, 2016

An ancient latrine near a desert in north-western China has revealed the first archaeological evidence that travellers along the Silk Road were responsible for the spread of infectious diseases along huge distances of the ...

#### Mathematicians may have found an answer to the longstanding puzzle as to why we have evolved to cooperate

July 19, 2016

Why do we feel good about giving to charity when there is no direct benefit to ourselves, and feel bad about cheating the system? Mathematicians may have found an answer to the longstanding puzzle as to why we have evolved ...

#### How a little mathematics can help create some beautiful music

July 21, 2016

Since the time of Pythagoras around 500 BCE, music and mathematics have had an intimate and mutually supportive relationship.