INFORMS journal: Microsoft algorithm improves directions in large networks for Bing Maps

Faster processing, more accurate information on lengthy trips, traffic snarls

2015-06-09

(Press-News.org) Did the cross-country drive that you planned using an online mapping service take twice as long as expected? In a new study published in the Articles in Advance section of Transportation Science, a journal of the Institute for Operations Research and the Management Sciences (INFORMS), Microsoft researchers working on a project for Bing Maps explain how they developed the first routing engine that satisfies a large number of algorithmic requirements that overcome barriers to generating directions on multi-stage trips like coast-to-coast drives. Customizable Route Planning (CRP), according to the researchers, brings far greater speed and accuracy to planning routes with many stages, and more accurately estimates the time needed for turns, U-turns, road closures, and traffic snarls. The research also provides more accurate information for walking and bicycle routes, and identifies more reliable alternate routes. Surprisingly, the research culminates interest in a classic algorithm published in 1959 by Edsger Dijkstra that was thought to perform too slowly to calculate online map routes. The study, Customizable Route Planning in Road Networks, is by Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck, all employed by Microsoft when the research was submitted for publication. "CRP incorporates traffic data and new personal preferences much faster - orders of magnitude faster," says Thomas Pajor. "The resulting routing engine is a flexible and practical solution to many real-life variants of the problem, making it a perfect fit for Bing Maps." Microsoft started using CRP for Bing Maps in 2012. A key ingredient of modern online map applications is a routing engine that can find best routes between two given locations of a road network. Beneath the map that online viewers see, algorithms find point-to-point shortest paths in a graph representing the road network. Since the introduction of online maps, considerable research has gone into algorithms with two phases: (1) preprocessing portions of routes that can be used again and again, and (2) providing answers to pinpoint queries that are generated in a millisecond or less. The authors write that a modern real-world routing engine must satisfy several requirements. It must incorporate every last detail of a road network - previous work often neglected time lost in making turns and observing traffic restrictions due, for example, to road repairs. The authors found that most methods have a significant "performance penalty," often due to the way that turns are represented. Also, a practical algorithm must calculate travel times while also factoring in shortest distance, walking, biking, avoiding U-turns, height and weight restrictions - and other problems that pop up. These new metrics must be calculated fast enough to match real-time traffic information with information about the roads. Updates to the time lost on road closures, for example, should be handled even more efficiently. The engine should support not only the calculation of point-to-point shortest paths but also suggest several alternate routes. The authors found that no previous technique met all the requirements. By combining new concepts - using separator-based methods rather than the traditional methods that exploit the hierarchical structure of roads - with careful engineering, they significantly improved the performance in their approach, easily enabling interactive applications. Another innovation - the explicit separation of metric customization from metric-independent preprocessing - allows Bing Maps to answer arbitrary questions about a trip in milliseconds. In Round-Based Public Transit Routing, a paper published in 2014 by Transportation Science, authors Delling, Pajor, and Werneck, solved similar problems facing bus and train systems in London and other major metropolitan areas. All product and company names herein may be trademarks of their registered owners.

INFORMATION:

About INFORMS INFORMS is the leading international association for professionals in analytics and operations research (O.R.). INFORMS advances research, and develops and promotes best practices in analytics and O.R. through collaboration, knowledge sharing, and professional development. INFORMS helps business, government, and other organization professionals make better decisions to drive value to their organizations and society. Our certification program (CAP®), highly cited publications, educational meetings and conferences, continuing education, industry and process focused networking communities, competitions, and recognition provide professionals with the knowledge and connections they need to achieve ever greater value for their organizations. Further information about INFORMS, analytics, and operations research is at http://www.informs.org or @informs. END

ELSE PRESS RELEASES FROM THIS DATE:

Are the data underlying the US dietary guidelines flawed?

2015-06-09

Rochester, MN, June 9, 2015 - U.S. government-issued dietary recommendations continue to evolve over time. In a special article published in Mayo Clinic Proceedings, an obesity theorist and cardiovascular health researchers claim that the main source of dietary information used by the U.S. Government's 2015 Dietary Guidelines Advisory Committee (DGAC) is scientifically flawed because the underlying data are primarily informed by memory-based dietary assessment methods (M-BMs) (eg, interviews and surveys). In an editorial response nutrition experts suggest that the purported ...

Keep calm and carry on -- for the sake of your long-term health

2015-06-09

Reacting positively to stressful situations may play a key role in long-term health, according to researchers. In a study measuring adults' reactions to stress and how it affects their bodies, researchers found that adults who fail to maintain positive moods such as cheerfulness or calm when faced with the minor stressors of everyday life appear to have elevated levels of inflammation. Furthermore, women can be at heightened risk. Inflammatory responses are part of the body's ability to protect itself via the immune system. However, chronic -- long-term -- inflammation ...

Insomnia leads to decreased empathy in health care workers

2015-06-09

DARIEN, IL - A new study suggests that insomnia decreases empathy in health care workers and may lead to adverse clinical outcomes and medical errors. Results show that subjects with an Insomnia Severity Index ISI of greater than 8, scored significantly higher across all four subscales of empathy. "Insomnia affects empathy in health care workers which can lead to adverse clinical outcomes," said lead author Venkatesh Basappa Krishnamurthy, MD, assistant professor, Sleep Research and Treatment Center, department of psychiatry, Penn State College of Medicine in Hershey, ...

Mean light timing may influence body mass index and body fat

2015-06-09

DARIEN, IL - A new study suggests that the timing of exposure to moderate levels of light may influence body mass index (BMI) and body fat. Results show that people with more exposure to moderate or higher intensity light earlier in the day had lower body mass index and percent body fat than those with more of their moderate or higher intensity light exposure later in the day. "These results emphasize the importance of getting the majority of your exposure to moderate or higher intensity light during the morning and provide further support that changes to environmental ...

Study: Juvenile incarceration yields less schooling, more crime

2015-06-09

Teenagers who are incarcerated tend to have substantially worse outcomes later in life than those who avoid serving time for similar offenses, according to a distinctive new study co-authored by an MIT scholar. "We find that kids who go into juvenile detention are much less likely to graduate from high school and much more likely to end up in prison as adults," says Joseph Doyle, an economist at the MIT Sloan School of Management and co-author of a new paper detailing the results of the study. Indeed, the research project, which studied the long-term outcomes of ...

Can not having enough to eat lead to poor diabetes management?

2015-06-09

BOSTON (June 9, 2015) - Latinos who worry about having enough food to eat -- so-called food insecurity -- report having a poorer diet and exhibit worse glycemic control than those who aren't worried about having sufficient food to survive, according to a study presented at the American Diabetes Association's 75th Scientific Sessions. The findings suggest that food insecurity should be a factor considered in overall diabetes management. Approximately 24 percent of Latino households in the U.S. were food insecure in 2013, compared to 14 percent for Americans overall, according ...

Are offspring of obese moms pre-programmed for obesity and metabolic disease?

2015-06-09

BOSTON (June 9, 2015) - The evidence is clear that the children of obese parents are prone to obesity themselves, placing them at higher risk for type 2 diabetes, but how and why this occurs remains under investigation. A study being presented at the American Diabetes Association's 75th Scientific Sessions found evidence suggesting that the in utero environment in obese mothers may program a child's cells to accumulate extra fat or develop differences in metabolism that could lead to insulin resistance. "One of the questions that needs to be explored is how children ...

GLP-1 alters how the brain responds to food

2015-06-09

BOSTON (June 9, 2015) - Gut hormone-based medications used to treat diabetes, such as GLP-1 receptor agonists, have also been shown to reduce body weight. Researchers have been working to understand how. This study, presented today at the American Diabetes Association's 75th Scientific Sessions, sheds light on how GLP-1 receptor agonists alter the brain's response to food, possibly reducing cravings and increasing satisfaction while eating. Previous studies have shown that the brains of obese people have a greater response to pictures of food than those of lean people, ...

Filming the film: Scientists observe photographic exposure live at the nanoscale

2015-06-09

Photoinduced chemical reactions are responsible for many fundamental processes and technologies, from energy conversion in nature to micro fabrication by photo-lithography. One process that is known from everyday's life and can be observed by the naked eye, is the exposure of photographic film. At DESY's X-ray light source PETRA III, scientists have now monitored the chemical processes during a photographic exposure at the level of individual nanoscale grains in real-time. The advanced experimental method enables the investigation of a broad variety of chemical and physical ...

'Alzheimer's protein' plays role in maintaining eye health and muscle strength

2015-06-09

Amyloid precursor protein (APP), a key protein implicated in the development Alzheimer's disease, may play an important role in eye and muscle health. In a new report published in the June 2015 issue of The FASEB Journal, scientists have discovered that when proteins that bind to the APP, called FE65 and FE65L1, are deleted, they cause cataracts and muscle weakness in mice. Additionally, this study demonstrates that the expression of laminin, a protein pivotal for the interaction between lens epithelial cells and the lens capsule, is severely altered in mice lenses missing ...

INFORMS journal: Microsoft algorithm improves directions in large networks for Bing Maps

ELSE PRESS RELEASES FROM THIS DATE:

LAST 30 PRESS RELEASES: