High-performance transportation optimization through parallel and collaborative methods (Collab)

Collab is a researcher project funded by the SMARTRANS Programme of the Research Council of Norway. The goal is to develop parallel and collaborative methods in transportation optimization. The Collab project started in March 2009 and ended in July 2012. 

The Research Council of Norway granted a continuation project (Collab II), which started in April 2013 and will run until December 2016.

 

Summary

Advanced vehicle routing tools are increasingly being used for more efficient transportation. Their effect 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 between performance requirements and the performance offered by tools.

In collaboration with research groups abroad, SINTEF has developed highly competitive methods for rich, industrial variants of the Vehicle Routing Problem. The methods have been implemented in vehicle routing tools, e.g., the Spider technology, and disseminated to industry through vendors. Hence, they improve transportation efficiency in many organizations.

Until recently, the performance of transportation optimization software has increased rapidly through a combination of research based improvement of optimization methods and the general increase of CPU clock frequency. The latter has stagnated due to technological limits. Increasing processor power is now instead offered through an increasing number of cores. Graphics processors (GPUs) become more programmable and show a drastic increase of performance for data-parallel computing. In the near future, commodity processors will be heterogeneous and combine a high number of cores and programmable GPUs.

To exploit these developments, it is now absolutely necessary that new and parallelized transportation optimization methods are developed. In Collab, we will develop parallel and collaborative optimization methods, starting from existing, high performance methods. The new methods will be able to fully utilize the performance increase of future multi-core and heterogeneous hardware platforms.

Partners

The Collab project partnership consists of:

The project is funded by the SMARTRANS Programme of the Research Council of Norway.

Project Manager

Geir Hasle, SINTEF ICT.

Postdoc fellow

SINTEF ICT engaged PhD Christian Schulz as the Collab postdoctoral researcher for the period January 1 2010 until June 30 2012. As of July 1 2012, Christian holds a permanent Research Scientist position at SINTEF.  

News

2013

  • 2013.03.20. The papers Brodtkorb A. R., Hagen T. R., Schulz C., Hasle G.: GPU Computing in Discrete Optimization Part I: Introduction to the GPU and Schulz C., Hasle G., Brodtkorb A. R., Hagen T. R.: GPU Computing in Discrete Optimization Part II: Survey Focused on Routing Problems were accepted  for publication in special issue “Vehicle Routing” of EURO Journal of Transportation and Logistics. See "Publications". 
  • 2013.03.12. The grant proposal for Collab II (2013-2016) was accepted, including a postdoctoral fellowship.

2012

  • 2012.07.01. Christian Schulz got a permanent Research Scientist position at SINTEF.
  • 2012.06.30. The Collab project officially ended.
  • 2012.06.18-20. Olli Bräysy and Geir Hasle presented the two talks "The Gap between Theory and Practice" and "Commercial Vehicle Routing" during VeRoLog 2012 - First Conference of the EURO Working Group on Vehicle Routing and Logistics Optimization. Bologna, Italy.
  • 2012.05.04. The manuscript "Graphics processing unit (GPU) programming strategies and trends in GPU computing" by Brodtkorb A. R., T. R. Hagen, M. L. Sætra was accepted for the Journal of Parallel and Distributed Computing, special issue Metaheuristics on GPU and made available online. ISSN 0743-7315, 10.1016/j.jpdc.2012.04.003.
  • 2012.03.12. Christian Schulz' manuscript "Efficient local search on the GPU—Investigations on the vehicle routing problem" was accepted for the Journal of Parallel and Distributed Computing, Special issue Metaheuristics on GPU and made available online. ISSN 0743-7315, 10.1016/j.jpdc.2012.02.020.
  • 2012.03.12. Geir Hasle gave the Day 1 lectures "Vehicle Routing in Practice" at the 5 day international PhD Course "Local Distribution (DRL 018)" at Molde University College Specialized University in Logistics, Molde, Norway.


2011

  • 2011.07.06. Geir Hasle gave the seminar "How to program efficient optimization algorithms on Graphics Processing Units - The Vehicle Routing Problem as a case study" at the University of Newcastle, Australia.
  • 2011.05.31-06.04. Geir Hasle participated in ROUTE2011 with the invited talk "Neighborhood Evaluation on GPU for the DCVRP Discrete optimization needs heterogeneous computing" (with Christian Schulz).
  • 2011.05.10-12 The 3rd Collab Workshop took place at Holmenkollen Park Hotel, Oslo, Norway. See here for details. 
  • 2011.05.03. The deadline for papers to the special issue of the Journal of Parallel and Distributed Computing: "Metaheuristics on GPU" edited by Profs. El-Ghazali Talbi, INRIA and Geir Hasle, SINTEF has been extended to May 31 2011.  You find the call text here. 
  • 2011.03.16. Geir Hasle gave the seminar “The Beach Law does not hold any more - Discrete optimization needs heterogeneous computing" at CORAL, Aarhus School of Business and Social Sciences, Aarhus, Denmark.
  • 2011.02.17. The 3rd Collab workshop will take place May 10-12, 2011 at Holmenkollen Park Hotel in Oslo.
  • 2011.02.16. SINTEF Applied Mathematics organizes the invited session Industrial applications of scheduling and routing in stream Transportation at IFORS 2011. 10 abstracts have been accepted.
  • 2011.02.03 A call for papers to a special issue of the Journal of Parallel and Distributed Computing: "Metaheuristics on GPU" edited by Profs. El-Ghazali Talbi, INRIA and Geir Hasle, SINTEF has been issued.  You find the call text here. The deadline is April 15, 2011.
  • 2011.01.26-28. A SINTEF-internal Collab workshop takes place in Geilo.

2010

  • 2010.10.28. The 2nd Collab workshop takes place in connection with the META'10 conference. 
  • 2010.10.28. The special session "Metaheuristics on graphics hardware" organized by SINTEF Applied Mathematics takes place during the 10th International Conference on Metaheuristics and Nature Inspired Computing - META'10. 
  • 2010.06.20-25. The Seventh Triennial Symposium on Transportation Analysis - TRISTAN VII - organized by NTNU, Høgskolen i Molde, EPFL, and SINTEF ICT takes place in Tromsø, Norway with more than 250 participants.
  • 2010.04.06.  The 1st Collab workshop takes place at Holmen fjordhotel outside Oslo April 11-13. For more information, see here.

2009

  • 2009.12.23.  Dr. Christian Schulz, formerly affiliated with the Centre of Mathematics for Applications centre of excellence at the University of Oslo, joins the Group of Optimization in January 2010. Christian will primarily work with parallel and heterogeneous methods in transportation optimization in the Collab project.
  • 2009.12.23. SINTEF is co-organizing the international conference TRISTAN VII  (Seventh Triennial Symposium on Transportation Analysis) on transportation analysis and transportation optimization. The conference takes place in Tromsø June 20-25 2010.