Shipping companies optimize their truck transport schedules and, hence, their costs by means of special software. As a matter of fact, however, calculation of optimum routes requires high processing power, and single-core computers may well take several hours to achieve good results. KIT researchers now have succeeded in parallelizing a popular sequential transport planning software. Parallelization on a 24-core computer reduces the time typically needed to optimize real data from 1.5 hours to only five minutes.
Multicore systems integrating several processor cores in one chip allow parallel processing of different tasks, thus increasing considerably both processing power and speed. To be able to tap full potentials, sequential software processing the tasks sequentially on one processor core must be rewritten, i.e. parallelized. KIT computer scientists Professor Walter F. Tichy and Dr. Victor Pankratius have succeeded in doing so using a commercial transport scheduling application provided by SAP. They have introduced their different parallelization approaches in the journal “it – Information Technology”.
The software “Vehicle Scheduling and Routing Optimizer” is a module of SAP’s “Business Suite”. It serves to calculate the most cost-efficient routes while allocating shipments to the vehicles, considering truck loading instructions, and scheduling stops for reloading. The software is based on an evolutionary algorithm copying the principles of biological evolution in the computer. According to specifications by SAP, this algorithm, instead of being replaced, was rewritten from sequential into parallel while cleverly splitting and synchronizing the different individual tasks. “It has been important to ensure that each thread of execution reverts to its own data,” explains Victor Pankratius who heads the Young Investigator Group “Multicore Software Engineering” at KIT.
Pankratius and Tichy have calculated experimentally the adequate parallelization approach using also real data from shipping companies. Pankratius points out that “it has turned out that theoretical textbook-style approaches do not work in practice because the time and effort it takes to juggle data is greater, ultimately, than the benefit achieved by parallelization.”
Victor Pankratius, Walter F. Tichy: Truck Scheduling on Multicore, it – Information Technology; 53 (2011) 2/DOI 10.1524/itit.2011.0626.
www.oldenbourg-link.com/doi/pdf/10.1524/itit.2011.0626
IT at KIT: Highlights of the Year
At this year’s CeBIT in Hannover, 6 to 10 March, 2012, KIT will present current research from its focuses COMMputation as well as Anthropomatics and Robotics (Hall 9, Stand G33). At the annual reception on 22th March attended by numerous partners from industry and science again information technology will be main topic. The first German Department of Informatics will celebrate its 40th anniversary at KIT in autumn.
Information technology at Karlsruhe Institute of Technology is bundled into two focuses. The KIT Focus COMMputation integrates communication and computation for development of devices with capabilities to interact, to perceive their environment, and to adapt to dynamically changing requirements. Researchers from the fields of informatics, electrical engineering, information technology, and economics cooperate to develop new concepts, architectures, methods, tools, and applications for the relevant complex systems.
The KIT Anthropomatics and Robotics Focus intends to improve the quality of life of humans. Using methods of informatics, mechanical engineering, electrical engineering, information technology, social sciences, and humanities, symbiotic systems are developed after the models of human anatomy, motor functions, perception, and behavior. The research topics range from machine intelligence, human-centered robotics, multimodal interaction and robot technology through to industrial robotics.
Being “The Research University in the Helmholtz Association”, KIT creates and imparts knowledge for the society and the environment. It is the objective to make significant contributions to the global challenges in the fields of energy, mobility, and information. For this, about 10,000 employees cooperate in a broad range of disciplines in natural sciences, engineering sciences, economics, and the humanities and social sciences. KIT prepares its 22,800 students for responsible tasks in society, industry, and science by offering research-based study programs. Innovation efforts at KIT build a bridge between important scientific findings and their application for the benefit of society, economic prosperity, and the preservation of our natural basis of life. KIT is one of the German universities of excellence.