Design and Experimental Analysis of Novel Integrated Optimization Methods

Effektiv transport og logistikk er viktig i dagens samfunn. Godstransport står for rundt 10% av verdens CO2-utslipp, og det er ikke uvanlig at transport står for mer enn 10% av produktkostnadene. En nøkkel til mer effektiv logistikk er å velge ressurser og fastsette tider til oppgavene på best mulig måte, der ressursene er begrensede. Operasjonsanalyse er den vitenskapelige disiplin som studerer kvantitative metoder for slike oppgaver. Matematisk optimering er det viktigste verktøyet. Beslutningsstøtteverktøy for planlegging fører i dag til betydelig mer effektiv transport og logistikk. I AXIOM har sterke forskergrupper ved NTNU, Høgskolen i Molde og SINTEF samarbeidet om å løse komplekse diskrete optimeringsproblem ved å designe integrerte metoder som kombinerer elementer fra eksakte optimeringsmetoder, avanserte heuristikker og heterogene beregninger. Hovedfokuset i prosjektet har vært å studere det meget komplekse optimeringsproblemet kjent som det lagerstyrte ruteproblemet. På grunn av kompleksiteten er dette velegnet for den type design og analyser som er gjennomført i AXIOM. Problemet er også meget relevant industrielt ettersom det integrerer beslutningsprosessene transportruting og lagerstyring, som tradisjonelt er styrt separat. Nåværende optimeringsmetoder er ikke tilstrekkelige for å løse virkelige industrianvendelser. Gjennom AXIOM, har nye integrerte metoder innen matematisk optimering blitt utviklet, noe som gir et grunnlag for kraftigere beslutningsstøtteverktøy. I AXIOM har tre stipendiater og en postdoktor jobbet fulltid med å utvikle nye integrerte løsningsmetoder basert på matematisk programmering, hovedsakelig rettet mot å løse lagerstyrte ruteproblemer. Metodene utviklet i AXIOM har ført til «verdensrekorder» på 8 probleminstanser av ruteproblemer med begrenset kjøretøyskapasitet, på mer enn 200 probleminstanser fra litteraturen på det lagerstyrte ruteproblemet og på mer enn 400 probleminstanser av det mer generelle produksjon- og lagerstyrte ruteproblemet. Videre har et nytt sett av probleminstanser for det lagerstyre ruteproblemet blitt utviklet, noe som gjør at forskere kan sammenligne metodene sine på et mer variert grunnlag enn det som tidligere har vært tilgjengelig. Prosjektet har resultert i mer enn 35 artikler i internasjonalt anerkjente tidsskrift, hvorav 16 er på UHR nivå 2. Arbeidet i prosjektet er også fremført i over 25 foredrag på vitenskapelige konferanser over hele verden. For brukere i både industri og offentlig sektor, vil bruken av optimeringsmetodene utviklet i AXIOM føre til mer effektiv planlegging innad i en verdikjede. Dette gjelder spesielt for de verdikjedene som består av lagerstyring og distribusjon via kjøretøy. Flere detaljer om prosjektet og dets medlemmer, samt oversikt over publikasjoner og resultat kan finnes på prosjektets hjemmeside: http://axiomresearchproject.com/

Through AXIOM, NTNU, HIMOLDE and SINTEF have strengthened their already strong expertise on combinatorial optimization, in particular on rich vehicle routing problems, such as the inventory routing problem (IRP) and the production routing problem. AXIOM designed new, very powerful, solution methods for many variants of the Vehicle Routing Problem. These methods will benefit the research community as the methods developed has raised the bar for the solution quality obtainable by optimization methods for these problems. Further, a new set of benchmark instances for the IRP that will enable researchers to benchmark their methods on a richer and more varied instance set for the problem. When exploited by users in industry and the public sector, the optimization methods developed in AXIOM will lead to better efficiency and timeliness in the management of supply chains, and especially those who mix inventory management with distribution by vehicles.

Our main goal is to move the research frontier considerably in design of novel integrated methods for solving complex discrete optimization problems. The cornerstones are the partners' deep knowledge in exact methods, metaheuristics, and heterogeneous computing. The expected results are innovative methods combining elements from these areas. AXIOM has four workpackages (WPs). WP1 starts from exact methods and analyzes how these methods can be extended and improved using heuristics. WP2 investigates how exact methods are best utilized within a metaheuristic framework. WP3 develops algorithms that fully utilize all processing elements of modern PCs and are flexible and scalable. In WP4 experimental data are collected, analyzed, and synthesized into new knowledge and understanding. The expected methods will be generic, but the inventory routing problem (IRP) is our main case. The IRP is a very complex and challenging problem with many degrees of freedom, which makes it suitable for the type of analyses and developments in AXIOM. It is also highly relevant industrially, as it merges decision processes that traditionally are managed separately. Current methods are not sufficient to solve real-life applications. To increase the benefits of decision support systems, richer problems must be analyzed and solved more efficiently by new methods. The groups at NTNU, Molde University College and SINTEF have a long track record of developing advanced methods to solve real-life optimization problems. They have collaborated in several successful research projects and organized international conferences together. The partners are already world leaders in operations research within maritime transport and form a nationally outstanding group on discrete optimization. Through AXIOM, we shall further strengthen and integrate our work. 3 PhDs and 1 postdoc will be recruited. International networks will be enhanced through workshops, visiting researchers, and joint publication.