Back to search


Discrete Optimization Methods in Maritime and Road-based Transport II

Awarded: NOK 10.7 mill.

The core members of DOMinant II have achieved considerable research results in developing models and methods for discrete optimization problems within maritime and road-based transportation. We have focused on 1) inventory routing problems (IRP) and 2) fleet size and mix vehicle routing problems (FSMVRP). We have got 60 papers accepted/published (where 28 are on UHR level 2) and have given 115 international presentations. DOMinant II researchers received the award for the best paper in Networks in 2013 on IRP-research. A. Hemmati defended his PhD thesis in September 2015 and received very good feedback from the opponents. K. Thun has extended his period as PhD candidate until 1. April 2016 to contribute in the teaching at NTNU. L. M. Hvattum and H. Andersson have been found competent as professors within the project period. The main focus in the research has been on IRPs. We have developed new models that are close to the convex hull of integer points. The models are decomposed in new and innovative ways. Uncertainty is considered in models in new ways and results in more robust routes. The group has developed new and effective tight formulations, column generation methods and metaheuristics. Exact solution methods are combined with heuristics and resulted in hybrid methods or matheuristics. These make it possible to solve large instances close to optimality. We have also developed important test instances used for benchmark studies. DOMinant contributed considerably to the development of the solution methods in SAMs (Sintef ICT, Applied mathematics) IRP-solver INVENT. This DSS has demonstrated considerable savings within LNG transportation. Improvements of the solution methods are done in DOMinant II. DOMinant II have performed basic research within transport optimization for the "Mixed Capacitated General Routing Problem (MCGRP)", "Vehicle routing problems" (VRP) and "Travelling Salesman Problem" (TSP). These are often subproblems in IRP and FSMVRP. Together with University of Aarhus, we have developed the first method for finding lower bounds on the MCGRP. In cooperation with UNIMORE, we have developed a solution method resulting in world records on 59 of the 67 large test instances from the MCGRP literature and touch the record on 7 out of the remaining 8. We have worked on GPU-based parallelization of solution methods for TSP and VRP. The group has also developed new cooperative parallel solvers for various large routing problems. The methods give high quality solutions within short running time by use of several processors. Computational resources from NOTUR are utilized. The group has achieved good results within multi-criteria optimization for rich VRPs. Within FSMVRP, DOMinant II has completed several work packages. Several metaheuristics are developed. We expect that the methods can be used in future software and that considerable savings in driving distances, energy consumption, and emission of gases can be achieved. The group has developed new models and solution methods for liner network design where fleet size and mix are considered. Furthermore, we have developed models and methods to decide the size and mix of the ship fleet responsible for maintenance of offshore wind farms. The results will become important for further development of the planned offshore wind farms, such as Doggerbank. Finally, we have developed models and methods for optimizing the fleet composition for supply ships in the North Sea. The DOMinant II - group has extended its international network, and 34 of the publications have international co-authors. The most important international partners come from Australia, Canada, Denmark, Italy, The Netherlands, Portugal, and Spain. DOMinant II organized the conference VeRoLog (Vehicle Routing and Logistics Optimization) in Oslo in June 2014 with 170 participants from 27 countries. In addition, MUC and DOMinant II organized the conference LOT (Logistics-Optimization-Transportation) in September 2014, in memory of Arne Løkketangen. Annually, we have participated in committees of international conferences and organized sessions and streams at conferences. Results from DOMinant II are emphasized in a debate contribution about transportation research in Aftenposten 21.8.2014. G. Hasle was interviewed about transport optimization in NRKs Siffer (10:10). Furthermore, interviews about route optimization is published in Gemini and "Under Dusken", and at and the web pages of RCN. The project participants in Molde have presented and demonstrated software for solving route planning problems for pupils at high schools. We have collaborated with several industry actors, such as Statoil, Tine, Statkraft, DNV, MARINTEK, GDF SUEZ, Tieto, PetroOnline and Distribution Innovation. DOMinant II research is presented in classes at MUC and NTNU. 27 students have written their master thesis within DOMinant II research.

Transport typically represents 10-20% of the final cost of goods. Transport has serious environmental impacts. CO2 emission from seaborne transport is estimated at 1 billion tons annually. Use of discrete optimization in logistics has been a huge success. Studies refer to potential savings of 5-20% in costs and 14% in fuel consumption. The eVITA project DOMinant has led to improved models and optimization algorithms for important transport problems. As one of the results, SINTEF's inventory routing solv er INVENT has already demonstrated large savings in the LNG business. There is still a gap between the research frontier and industrial needs. In DOMinant II, we will significantly reduce this gap by developing models and efficient solution algorithms fo r computationally hard discrete optimization problems (DOPs) in transport. NTNU, Molde University College (MUC), and SINTEF Applied Mathematics (SAM) shall work closely together. We shall develop formulations of critical DOPs. We will extend the inventor y routing problem and the fleet composition problem to satisfy industrial needs that have not been studied yet. NTNU will focus on exact solution methods, relaxations, and bounds. Metaheuristics and hybrid methods for industrial sized problems will be dev eloped in collaboration. Parallel and collaborative methods will be designed by MUC and SAM. Extensive computational experiments are integral to the project. To speed up development, we shall utilize supercomputers including the NOTUR infrastructure. Thr ough DOMinant II, we shall further strengthen and integrate the work of the groups. 2 PhDs and 2 postdocs will be recruited. The groups have wide international networks that will be strengthened through workshops, visiting researchers, and joint publicati on. We have close cooperation with CIRRELT and GERAD, Canada (routing problems); INRIA, France (parallel and heterogeneous optimization); CIDMA, Portugal (stochastic optimization and exact methods).

Publications from Cristin

No publications found

Funding scheme: