# Using math to speed up school buses

##### June 8, 2011 By Nicolas Guérin

(PhysOrg.com) -- Optimizing school bus routes is a lot more complicated than one might think. The International School of Geneva handed their problem over to a group of EPFL mathematicians.

“Our student population is increasing rapidly,” observes Michel Chinal, Director General of the International School of Geneva. And the rising number of parents picking up and dropping off their children is creating traffic problems in the village of Founex, just outside Geneva. The bus service offered by the school is too slow. “Parents often say that they would like to sign their children up, but the bus ride is too long.” The buses pick up students in an area bounded by Morges, Geneva and neighboring France. So how can they improve the routes of 11 different buses carrying a total of 283 students to and from school? That’s the problem that was given to the in EPFL’s Discrete Optimization Group.

EPFL chemist Rainer Beck, whose child attends the school, offered to optimize the service during a meeting of the parent’s association. He asked his mathematical colleague Friedrich Eisenbrand to tackle the problem. “Coming up with a simple arithmetic algorithm is not difficult. But that’s not an efficient approach -- due to the enormous number of possible itineraries, the calculations are painfully slow. We needed to develop an algorithm that quickly rejected most routes, so that the computation could be completed before the end of the Universe,” explains Eisenbrand. With the assistance of his PhD student Adrian Bock, the mathematician came up with a solution for this complex problem. Using a few clever techniques, the calculations only take half a day to complete.

The researchers modeled student and parent satisfaction using specific parameters, such as “regret” (also called “opportunity loss”), a term used in decision theory. For this case, the regret was the difference between the ideal direct route – in a car – and the route taken by the bus. This parameter enabled the mathematicians to determine the threshold that would convince more students to take the bus. Once the calculations were finished, the gain was impressive: the largest discrepancies between the bus and car routes were cut by 25%.

Optimization is a technique that can be taken well beyond the problem of ferrying kids back and forth from school. The mathematicians are collaborating not only with world leaders in the telecommunications and airline industries to improve communications devices, but also with insurance companies to streamline their lengthy computations. Thus, in everyday life, as soon as we tap into a network, such as the Internet, we are benefiting from all the optimization work that is hidden behind it.

In addition to its evident economic advantages, this research can also help meet objectives for reducing environmental impact. “Our school is seriously concerned with pollution, and we are trying to find responsible solutions,” adds Chinal.

Explore further: The kids are alright

## Related Stories

#### The kids are alright

May 26, 2011

Children should be seen and not heard... who says? A Philosophy academic at The University of Nottingham is challenging the adage by teaching primary school children to argue properly.

#### When robots learn from our mistakes

May 26, 2011

(PhysOrg.com) -- Robots typically acquire new capacities by imitation. Now, EPFL scientists are doing the inverse -- developing machines that can learn more rapidly and outperform humans by starting from failed or inaccurate ...

#### How a hike led to a math 'Eureka!'

February 23, 2011

Where do “eureka” moments come from? Emory mathematician Ken Ono found his on a hiking trail in north Georgia.

#### Computer scientists make progress on math puzzle

October 28, 2010

(PhysOrg.com) -- Two UT Dallas computer scientists have made progress on a nearly 4-decade-old mathematical puzzle, producing a proof that renowned Stanford computer scientist Don Knuth called "amazing" in his communication ...

#### Whole child taken into account with new study

February 4, 2011

If you’ve ever wondered where your children go when they leave the house, just ask Jason Gilliland.

#### Schools lose records; English learners pay

April 11, 2011

(PhysOrg.com) -- Poor recordkeeping keeps California schools from getting all of the funding that they have coming, a failing that especially hurts English learners, according to research from the University of California, ...

## Recommended for you

#### Money can buy happiness but it's costly to bank on that without measuring debt

October 26, 2016

Yes, money can lead to happiness, but how much debt one has should also be considered in the money-happiness equation, according to a new a study from Purdue University.

#### Ancient parrot fossil found in Siberia

October 26, 2016

(Phys.org)—A Russian paleontologist has discovered a parrot fossil uncovered in Siberia several years ago—the first evidence of parrots living in Asia. In his paper published in Biology Letters, Nikita Zelenkov describes ...

#### Upper Paleolithic humans may have hunted cave lions for their pelts

October 26, 2016

Upper Paleolithic humans may have hunted cave lions for their pelts, perhaps contributing to their extinction, according to a study published October 26, 2016 in the open-access journal PLOS ONE by Marián Cueto from the ...

#### Ancient burials suggestive of blood feuds

October 24, 2016

There is significant variation in how different cultures over time have dealt with the dead. Yet, at a very basic level, funerals in the Sonoran Desert thousands of years ago were similar to what they are today. Bodies of ...

#### Dinosaurs of a feather flock and die together?

October 24, 2016

In the paleontology popularity contest, studying the social life of dinosaurs is on the rise.

#### Model helps explore how changing certainty in belief of one statement can lead to changings belief in truth of others

October 21, 2016

A small team of researchers with members from the U.S., the Netherlands, Russia and Italy has developed a new model that illuminates how changing the degree of certainty a person holds for a given belief can lead to changes ...