Outstanding Master of Engineering Projects Win Silent Hoist and Crane Materials Handling Prizes
Projects dealing with design of telecommunications networks, redistribution of farm topsoil, and scheduling of railroad crews won prizes at the ORIE Master of Engineering Graduation Ceremony in May. The cash prizes in the competition open to all students in the College of Engineering have been endowed by the Silent Hoist and Crane Company and were distributed to members of the project teams, nearly all from ORIE.
|Global Capacity team members Aayush Mahendru, Kasthuri Rangan Prabharkaran, left, and Christian Doppler, right, with Professor Jack Muckstadt at graduation. Not present: Tonghe Shen.|
photo: University Photography
Access Network Design Optimization
The top prize was awarded to the team working with a company called Global Capacity that designs networks composed of leased telecommunications links in order to serve an array of geographically distributed customers. In keeping with the prize's materials handling theme, the company calls itself "industry's first telecom logistics team." The ORIE team, comprised of Christian Doppler, Kasthuri Rangan Prabhakaran, Aayush Mahendru and Tonghe Shen, was given the problem of economically connecting 1506 customers of a client in France to a backbone network. The team worked under the guidance of Professor David Williamson.
|Network designed prior to the project. Lines are clustered around a few "points of presence."|
Before the project started, Global Capacity had designed a network costing 962,774€ per month to serve these customers. The team formulated an integer programming model, used commercial solver software called CPLEX (developed by ORIE alumnus Robert Bixby), and added heuristic methods in order to come up with an improved solution that cost 722,204€ , an improvement of 20%. According to Andrew Berquist of Global Capacity, the company had been working with heuristic algorithms for years, but "due to the continual pressure to deliver results, we had too little time to review the approach we were taking to see if there were [possible] improvements."
|The network designed by the team, costing 20% less. Note the increased number of points of presence.|
Berquist confirms the 20% savings. The team provided "a turn-key solution that we can use directly in our analyses which will deliver value to the business directly," according to Berquist. "We would highly recommend sponsoring a Cornell OR MEng project to any company with complex analysis needs," Berquist said.
Farm Yield Optimization - Topsoil Redistribution and Travel Paths
Second prize in the competition went to a team working on a very different problem, though attacked with similar computational tools. Shaan Qamar, Tahla Omer, Kevin Jin Ho Ham and Anshuman Bhairavbhat worked with Cornell Ph.D. student Clay Mitchell, who with his family grows corn and soybeans on a traditional farm using leading edge techniques. Mitchell asked whether there is an economical way to redistribute topsoil that has shifted due to erosion, so as to increase crop yield. He provided the team with data showing the variation in yield across a field, from which the team was able to deduce the variations in the level of topsoil. They built an integer programming model designed to optimize the redistribution, and used CPLEX to arrive at the path that a tractor should follow in accomplishing the redistribution, by scraping the topsoil and redepositing it.
|In these maps of the farm, light green represents excessive topsoil, with darker green and red representing lesser and lesser amounts. Proposed tractor routes show as black lines. The result of the redistribution is on the right.|
For the case worked by the students, a one time expenditure of less than $1000 in scraping incrased potential yield from $178,000 to $187,000 per year, until erosion results in the need to repeat the procedure. However the estimated cost does not include the cost of acquiring the software (nor the capital cost of the equipment, which is assumed to be already on hand). Hence a follow-on team is currently developing special-purpose software that can compute tractor trajectories to accomplish the redistribution.
In commenting on the project in a story in the Cornell Chronicle, project advisor Professor Huseyin Topaloglu emphasized the unusual nature of the project. "We are looking at something that's not really a traditional business problem, but if it pays off, it could make changes in people's lives," he said.
Crew Scheduling: Measuring Stability and Optimality for CN
Third prize in the competition went to a team with four ORIE students: Mikhail Chrestkha, Christian Klar, Abhas Sinha, and Betsy Wang, as well as Systems Engineering student Daniel Wu and Computer Science student Beibei Zhu. The team worked on the problem of scheduling work crews in the freight rail industry. The project, the second in two years for Canadian National Railway (CN), was sponsored by consulting company Axon. It was advised by Professors Peter Jackson and Leslie Trotter. The team also prepared a video demonstration of the software they developed.
|Christian Klar, John Talio (Axon), Len Podgurny (CN), Mihail Chrestkha, Betsy Wang, Professor Peter Jackson, Beibei Zhu and Daniel Wu in the CN train yard in Montreal, Canada|
The student team addressed the problem of pairing employees with trains on their routes over a period of 72 hours, during which crews move from train to train according to their skills, home base, specific requirements, and union work rules and regulations. Here, too, the students developed an integer programming formulation but used open source software, Symphony, developed by Cornell Ph.D. alumnus Ted Ralphs, which was well-suited to the implementation of their approach. For a realistic test problem with 60 trains and 100 employees in a 5 station network, they were able to reduce the number of assigned by employees needed to fulfill requirements by 40%, while satisfying all union rules and regulations.
However in actuality CN crew members are entitled to take a certain number of rest periods, which they can do at essentially random times and which result in delays and revisions to the schedule. Therefore the team developed a Monte Carlo simulation to determine the impact of such rest periods on the durability of the recommended schedule, i.e. how long it can be used before revisions are required or train delays occur. For the test problem they determined that the recommended schedule met a specified durability standard for the first 50 of the 72 hour scheduling time period. CN's Len Podgurny commented that "this group did a fantastic job working towards the deliverables and meeting and exceeding my expectations." He noted that the project results provide "a strong basis from which we can work."
The Silent Hoist and Crane Company Prize has a long tradition in ORIE since its establishment in 1950 for the purpose of "stimulating the thinking of engineering students with aptitude or special interest in the Art and Science of Material Handling." In the ensuing years, the Brooklyn-based company that endowed the prize (and awards at the University of Buffalo and the Massachusetts Institute of Technology) was dissolved, its line of fork lift vehicles was taken over by Hoist Liftruck of Bedford Park, Illinois, and material handling has been recognized as an industry requirement extending well beyond the movement of goods in plants and warehouses. For this year's Silent Hoist and Crane Prize winners, the handled "materials" included information, topsoil, and train crews.