Collab II: High-performance transportation optimization through parallel and collaborative methods II

This project focuses on the research and development of new parallel optimization methods for the coordination of transport. These tools will make transportation planning more efficient by providing better plans with fewer costs in shorter time. Opposite to today's sequential methods, these new parallel approaches will be able to utilize the further hardware development in computers which is based on parallelization, and will be able to adapt to the hardware at hand. Software for automated transportation planning is becoming more and more common. This leads to improvements in form of more coordinated transport with less resource usage in combination with fewer resources spent on planning. The effect is in great part determined both by the power of the optimization method used and the computational power of the hardware at hand. For many real world applications there is still a need for more powerful optimization software. For many years optimization software benefited not only from better methods, but also from a steady increase of the CPU-frequency in computers. Due to technological reasons, this increase ended a few years ago. Computers nowadays still improve in computing power, but now by increasing the number of cores on the processor, leading to a more and more parallel architecture in modern commodity computers. In addition, cheap parallel accelerators like the graphics card have a huge theoretical computational power because they provide a large amount of cores. Traditional sequential software is not able to utilize this parallel development. In fact, sequential code will run slower on today's computers, as the CPU frequency is lower than for yesterday's sequential machines. New, parallel optimization methods are therefore needed to utilize the tremendous theoretical computational power in the computers of today and the future. Collab II is a continuation of Collab and around half of the budget is used to finance a postdoc position. ACTIVITIES AND RESULTS: We have developed a GPU based solver for the DCVRP, a variation of the vehicle routing problem (VRP), which for example is relevant for the delivery of goods to customers. Using an approximative method, the solver produces, for standard problems, solutions of similar quality as one of the most well known solvers running on the CPU, but it generates them in shorter time. The speed improvement seems to increase with the size of the problem. The solver was presented at the international conferences NOW 2015, EURO 2015, INFORMS 2016 and ROUTE 2016. An article describing the solver has been submitted to a high impact scientific journal (UHR level 2). We started developing a new VRP solver using an exact method. Such methods can guarantee to find the optimal solution, but the answering time can be long for large problems. The solver will use both the CPU and the GPU, each of them for tasks that fit well to their corresponding architecture. Key features of the method design have been implemented and early experiments are promising and confirm the assumptions the method is based on. However, there is still research needed in order to lift the approach to a competitive level. We have earlier developed a GPU based solver for the travelling salesman problem. The solver has been applied to standard test problems from the literature and gives solutions very close to the best known solutions so far. On a new standard problem consisting of the 115 475 biggest cities and places in the USA, our solver produced a solution only 0.1 % worse then the best one known so far. The computation of this solution took only 21 hours. This work was presented on the international conferences NOW 2013 in Siracusa, SOAK/NOS6 2013 in Gothenburg and VeRoLog 2014 in Oslo. We have in the project so far published 5 scientific articles in respected journals and we gave 19 presentations at international conferences. A book chapter with the description of the central themes of Collab II has been printed in the standard reference book for researchers on vehicle routing, published by the Society for Industrial and Applied Mathematics. Instead of organizing a workshop in 2014, we chose to give a tutorial about GPU-programming in optimization in combination with the international VeRoLog conference in Blindern in June 2014, see www.sintef.no/verolog2014. The group of optimization at SINTEF was the local organizer of the conference. As the result of a request by Professor Vittorio Maniezzo from the University of Bologna, one of his PhD students, Francesco Strappaveccia, visited us from February to May in 2014. During his stay he developed GPU based algorithms for the shortest path problem (SPP). Furthermore he developed a CPU based algorithm for the SPP for usage in Dynamo - SINTEF's software for multi-modal routing in dynamic networks. The work was included in Francesco's PhD thesis that he defended in spring 2015.

The effect of advanced ITS vehicle routing and optimal route finding software is largely determined by a combination of the power of the underlying optimization methods and the power of the computer. For many applications, there is still a large gap betwe en requirements and performance offered. SINTEF has developed efficient sequential methods for real-life variants of the Vehicle Routing Problem (VRP) and the Shortest Path Problem (SPP) in dynamic, multi-modal transportation networks. These methods are the basis for the Spider and Invent VRP/IRP solvers and the Dynamo SPP solver. Sequential methods cannot exploit modern, heterogeneous PC architectures that consist of multiple cores for task parallelism and one or more stream processing accelerators suc h as the GPU. In the recently finished Collab project, SINTEF, supported by 4 academic partners abroad, has developed new algorithms for the VRP that fully utilize multiple cores for task parallelism, and other algorithms that fully utilize stream process ing accelerators. Results have already been widely published and disseminated for commercial exploitation. In Collab II, we continue to collaborate with excellent research groups abroad. We extend the efforts on VRPs and aim at self-adaptable algorithms that fully utilize all processing units of modern PCs. Self-adaptation is important for scalability and automatic exploitation of future hardware developments. We also expand the scope to the SPP for multi-modal, dynamic transportation networks. This prob lem is key to dynamic fleet management, and also to route finding for goods transportation as well as personal travel. To ensure relevance we collaborate with DI AS (newspaper distribution), GdF Suez, Statoil, Tieto AS, and PetroOnline AS (maritime and l and based transportation of LNG and petroleum products), and the ongoing Norwegian personal travel portal project and ITS Norway (intermodal transportation).