# Bus scheduling algorithm picks up the slack

##### Oct 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

Explore further: Can science eliminate extreme poverty?

## Related Stories

#### Scholar: Empower Congress to bolster separation of powers

Nov 11, 2013

Although it may not receive high marks these days as a public body, Congress should actually be empowered so it can uphold the constitutional checks and balances that help to curb overreach by the other two ...

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

May 03, 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".

#### Increasing hydropower capacity without straining the environment

Apr 29, 2013

With over 800 mini-hydroelectric plants awaiting approval in Switzerland, the biodiversity of Swiss river ecosystems could be at stake. More enlightened policies could help preserve the environment.

#### Refocusing important on and off the court, says recent study.

Feb 12, 2013

(Phys.org)—If an employee's performance drops in one area, does that mean they're slacking off?

#### A new theory on long-term unemployment

Dec 14, 2012

(Phys.org)—Com­pa­nies rank more recently unem­ployed job can­di­dates much higher than they would rank oth­er­wise qual­i­fied appli­cants who have been out of work for more than six months, ...

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

Oct 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.

## Recommended for you

#### Egypt archaeologists find ancient writer's tomb

Apr 19, 2014

Egypt's minister of antiquities says a team of Spanish archaeologists has discovered two tombs in the southern part of the country, one of them belonging to a writer and containing a trove of artifacts including reed pens ...

#### Researchers create methylation maps of Neanderthals and Denisovans, compare them to modern humans

Apr 18, 2014

(Phys.org) —A team of Israeli, Spanish and German researchers has for the first time created a map of gene expression in Neanderthals and Denisovans and has compared them with modern humans. In their paper ...

#### 3 Qs: Economist makes the case for new quasi-experiments as a way of studying environmental issues

Apr 18, 2014

How can scholars get traction on environmental problems, particularly those relating to pollution? In an essay appearing in this week's issue of the journal Science, MIT economist Michael Greenstone, along ...

#### New specimens of Yanornis indicate a digestive system of living birds

Apr 18, 2014

In a recent paper describing ten new specimens of Yanornis martini identified by the director of the Shandong Tianyu Museum of Natural History Mr. Xiaoting Zheng, an international team of scientists lead ...

#### Study finds law dramatically curbing need for speed

Apr 18, 2014

Almost seven years have passed since Ontario's street-racing legislation hit the books and, according to one Western researcher, it has succeeded in putting the brakes on the number of convictions and, more importantly, injuries ...

#### Changing dinosaur tracks spurs novel approach

Apr 17, 2014

Paleontologists are using a range of old and new techniques to map the Broome Sandstone dinosaur trackways.

## More news stories

#### Researchers create methylation maps of Neanderthals and Denisovans, compare them to modern humans

(Phys.org) —A team of Israeli, Spanish and German researchers has for the first time created a map of gene expression in Neanderthals and Denisovans and has compared them with modern humans. In their paper ...

#### Last Week's Best—Quantum mechanics breakthrough, 3-D printed human heart, and paraplegia therapy

(Phys.org) —Hello readers—we'd like to try something new here at Phys.org and Medical Xpress: offer a weekly summary every Monday highlighting what we feel are the most important stories of the past ...

#### Earliest ancestor of land herbivores discovered

New research from the University of Toronto Mississauga demonstrates how carnivores transitioned into herbivores for the first time on land.

#### Neanderthals and Cro-magnons did not coincide on the Iberian Peninsula

The meeting between a Neanderthal and one of the first humans, which we used to picture in our minds, did not happen on the Iberian Peninsula. That is the conclusion reached by an international team of researchers ...

#### Clippers and coiners in 16th-century England

In 2017 a new £1 coin will appear in our pockets with a design extremely difficult to forge. In the mid-16th century, Elizabeth I's government came up with a series of measures to deter "divers evil persons" ...

#### Making graphene in your kitchen

Graphene has been touted as a wonder material—the world's thinnest substance, but super-strong. Now scientists say it is so easy to make you could produce some in your kitchen.

#### Review: With Galaxy S5, Samsung proves less can be more

Samsung Electronics Co. has produced the most formidable rival yet to the iPhone 5S: the Galaxy S5. The device, released over the weekend, is the fifth edition of the company's successful line of Galaxy S ...

#### Bulletproof nuclei? Stem cells exhibit unusual absorption property

Stem cells – the body's master cells – demonstrate a bizarre property never before seen at a cellular level, according to a study published today from scientists at the University of Cambridge. The property ...

#### Study casts doubt on climate benefit of biofuels from corn residue

Using corn crop residue to make ethanol and other biofuels reduces soil carbon and can generate more greenhouse gases than gasoline, according to a study published today in the journal Nature Climate Change.

#### 4.5 million smartphones were lost or stolen in US in 2013

A report released Thursday said 4.5 million smartphones were lost or stolen in the U.S. last year, up from 2.8 million in 2012.