Routing engine, award winner, NSF program

The story behind Microsoft’s flexible, robust routing engine

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.

The study, “Customizable Route Planning in Road Networks,” was authored 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,” Thomas Pajor says. “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.”

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.

Olinsky receives 2015 SAS Distinguished Professor Award

Dr. Alan Olinsky, a professor of mathematics and computer information systems at Bryant University (Smithfield, R.I.) and co-director and co-founder of Bryant’s Advanced Applied Analytics Center, was named the 2015 winner of the SAS Distinguished Professor Award.

Bryant introduced one of the country’s first undergraduate applied analytics programs, and in 2014 added a joint certificate in business analytics offered through the Bryant University Graduate School of Business. These programs are overseen in collaboration with Bryant’s Advanced Applied Analytics Center, founded by Olinsky and Dr. Richard Glass, professor of computer information systems.

“Dr. Olinsky is truly an innovative leader in his field, and we are proud that he has been recognized by SAS for his achievements,” said Glenn Sulmasy, Bryant University Provost. “Analytics has emerged as a critical organizational function that is essential in today’s world, and, through Dr. Olinsky’s work and our strategic affiliation with SAS, Bryant is producing highly skilled professionals ready to answer the call of organizations around the world.”

The SAS Distinguished Professor Award is given to a professor who uses SAS software in teaching and/or research, and supports student usage in an effective way. “Dr. Olinsky has put countless students on the road to successful careers through his innovative instruction and programs,” said Jerry Oglesby, senior director for the SAS Global Academic Program and Global Certification.

Olinsky, whose research interests include statistics, management science and data mining, is past president of the Rhode Island Chapter of the American Statistical Association.

The innovative Advanced Applied Analytics Center (AAAC) at Bryant University supports the broadening of the relationship between analytics, research and the solution of real-world problems. Bryant’s AAAC is a hub for professional collaboration and the development of interdisciplinary analytics academic programs, research, training, application development and conferences and symposia focused on real-world problem-solving. For more, visit www.Bryant.edu.

New NSF program to fund service, manufacturing & operations research

The National Science Foundation (NSF) Directorate for Engineering recently announced a new program to more effectively and efficiently fund research on service and manufacturing enterprises, and foundational operations research topics, called the Service, Manufacturing and Operations Research (SMOR) program.

To create this program, Engineering is merging three existing programs within the Civil, Mechanical and Manufacturing Innovation (CMMI) Division: Operations Research (OR), Service Enterprise Systems (SES) and Manufacturing Enterprise Systems (MES).

These programs have common underlying disciplinary themes – development of innovative mathematical models, analysis and computational algorithms for decision-making. They differ in the degree to which proposed models are general-purpose and the proposed application domains.

Because of the continued convergence between service and manufacturing, NSF will implement a team-based approach to co-manage the new single program, SMOR. Two program directors will oversee the new program.

A goal of the merger is to simplify proposal preparation for an increasing number of researchers whose work fits more than one of the three programs, which we hope will result in a more efficient proposal review. The total budget for the research will remain the same.

When completed, details of the new SMOR program will be available on the Web at http://www.nsf.gov/eng/cmmi/.