Models and algorithms for vehicle routing, resource allocation, and multi-stage decision-making under uncertainty

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
School of Science | Doctoral thesis (article-based) | Defence date: 2021-07-23
Date
2021
Major/Subject
Mcode
Degree programme
Language
en
Pages
58 + app. 100
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 82/2021
Abstract
In difficult optimization problems, strong formulations and algorithmic techniques that exploit the problem structure are often invaluable in designing efficient solution methods. Although microprocessors and generic solvers have reduced solution times, these tools are often not enough to solve hard problems of realistic size. To overcome these challenges, the standard practice has typically been to develop tailored, problem-specific algorithms. This summary chapter introduces efficient formulations and algorithms for three different optimization problems, each of which either serves as a basis for future extensions or unifies previous approaches under one framework. First, two algorithms are developed for the green vehicle routing problem. Both algorithms rely on a novel multigraph reformulation that transforms refueling nodes into non-dominated refuel paths between customers. This transformation allows combining routing and refueling decisions with negligible overhead. Both algorithms serve as building blocks for developing new solution methods for generalizations of the problem. The effectiveness of the multigraph and the developed algorithms are demonstrated through computational evaluation. Second, a new framework for centralized allocation of resources to a portfolio of decision-making units is developed. This framework can handle multiple objectives with incomplete preferences and compute all non-dominated portfolios satisfying these preferences. Each portfolio corresponds to a Pareto-optimal allocation of resources among the decision-making units that maximizes portfolio-level efficiency. The framework unifies several previous models that compute single solutions from the efficient frontier, possibly involving non-linear utilities and many kinds of production possibility sets. It also demonstrates that relying on conventional efficiency scores in guiding resource allocation decisions may lead to inefficiencies at the portfolio level. Third, a novel Decision Programming approach is developed that contributes towards unifying stochastic programming and decision analysis within a single framework and relaxes two common assumptions in decision analysis: (i) perfect recall where all prior decisions are known when making a decision and (ii) regularity that assumes a total temporal order for decision variables. Decision Programming relies on a mixed-integer linear programming formulation that can handle both endogenous and exogenous uncertainties and can also optimize problems involving simultaneous decisions by agents unable to communicate with each other. The Decision Programming framework can be extended to incorporate deterministic and chance constraints, and it can be harnessed to compute all non-dominated solutions in presence of multiple value functions. Most importantly, it contributes towards approaches that can solve problems from both decision analysis and stochastic programming, and may thus facilitate collaboration between these two sub-disciplines in the future.

Vaikeita optimointiongelmia ratkottaessa vahvat formulaatiot ja ongelman rakennetta hyödyntävät ratkaisutekniikat ovat usein keskeisiä. Vaikka mikroprosessorit ja yleiset ratkaisuohjelmat ovat nopeutuneet huomattavasti lyhyen ajan sisällä, ne eivät usein pysty yksinään ratkaisemaan isoja reaalimaailman ongelmia. Tyypillisesti ainoa vaihtoehto on ollut ongelmakohtaisten algoritmien kehittäminen jokaiselle ongelmalle erikseen. Tämä väitöskirjan tiivistelmä esittää tehokkaita malleja ja ratkaisumenetelmiä kolmelle optimointiongelmalle, jotka joko toimivat pohjana uusille laajennuksille, tai yhdistävät useita eri menetelmiä isommaksi viitekehykseksi. Ensiksi on kehitetty kaksi algoritmia vihreälle ajoneuvon reititysongelmalle. Molemmat algoritmit hyödyntävät uutta monigraafi-reformulaatiota, mikä muuttaa tankkausasemia kuvaavat solmut ei-dominoiduksi energiapoluiksi asiakkaiden välillä. Tämä muunnos mahdollistaa sekä reititys- että tankkauspäätösten tekemisen samanaikaisesti ilman merkittävää laskennallista haittaa. Molemmat algoritmit toimivat myös rakennuspalikoina uusien ratkaisumenetelmien kehittämiseen ongelman laajennuksille. Monigraafi-reformulaatio sekä molemmat algoritmit ovat osoittautuneet tehokkaiksi laskennallisten testien avulla. Toiseksi on kehitetty viitekehys keskitettyyn resurssien jakamiseen portfoliolle päätöksentekoyksiköitä. Tämä viitekehys pystyy käsittelemään useita päätösfunktioita ottamalla huomioon epätarkat preferenssit ja laskemaan kaikki ei-dominoidut portfoliot, mitkä toteuttavat kyseiset preferenssit. Jokainen ei-dominoitu portfolio vastaa Pareto-optimaalista resurssien jakoa päätöksentekoyksiköiden kesken, mikä maksimoi portfolion tehokkuuden. Kehitetty viitekehys yhdistää useita eri malleja, jotka itsekseen tuottavat yksittäisiä ratkaisuja tehokkaalta rintamalta, mahdollisesti sisältäen epälineaarisia hyötyfunktioita, sekä monenlaisia tuotantomahdollisuus- joukkoja. Viitekehys myös osoittaa, että perinteisillä tehokkuusluvuilla ei voida luotettavasti ohjata resurssien allokointipäätöksiä maksimoidessa portfoliotason tehokkuutta. Kolmanneksi on kehitetty Decision Programming menetelmä, mikä edistää stokastisen optimoinnin ja päätösanalyysin yhdistämistä samaan viitekehykseen, sekä relaksoi kaksi yleistä päätösanalyysiin liittyvää oletusta: (i) täydellinen muisti, missä aikaisemmat päätökset tiedetään uusia tehdessä, sekä (ii) säännöllisyys (engl. regularity), missä päätökset noudattavat lineaarista järjestystä. Menetelmä hyödyntää sekalukuista lineaarista optimointimallia, mikä pystyy käsittelemään sekä endo-, että eksogeenisia epävarmuuksia, ja ratkaisemaan ongelmia missä joukko agentteja, jotka eivät pysty kommunikoimaan keskenään, tekevät samanaikaisesti päätöksiä. Menetelmä voidaan yleistää huomioimaan deterministisiä- ja satunnaisrajoitteita, sekä laskemaan kaikki ei-dominoidut ratkaisut usealle tavoitefunktiolle. Mikä tärkeintä, se antaa edellytyksiä sille, että päätösanalyysin ja stokastisen optimoinnin asiantuntijat voivat tehdä yhteistyötä tulevaisuudessa.
Description
Defence is held on 23 July 2021 at 10. Zoom link: https://aalto.zoom.us/j/63059713880
Supervising professor
Salo, Ahti, Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland
Thesis advisor
Bartolini, Enrico, Dr., RWTH Aachen University, Germany
Oliveira, Fabricio, Asst. Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland
Liesiö, Juuso, Asst. Prof., Aalto University, Department of Information and Service Management, Finland
Salo, Ahti, Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland
Keywords
optimization, vehicle routing, resource allocation, decision-making under uncertainty, optimointi, ajoneuvon reititys, resurssien allokointi, monijaksoinen päätöksenteko
Other note
Parts
  • [Publication 1]: I Juho Andelmin and Enrico Bartolini. An exact algorithm for the green vehicle routing problem. Transportation Science, 51(4), 1288-1303, July 2017.
    DOI: 10.1287/trsc.2016.0734 View at publisher
  • [Publication 2]: II Juho Andelmin and Enrico Bartolini. A multi-start local search heuristic for the green vehicle routing problem based on a multigraph reformulation. Computers and Operations Research, vol. 109, no. September 2019, pp. 43-63.
    Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-201906033432
    DOI: 10.1016/j.cor.2019.04.018 View at publisher
  • [Publication 3]: III Juuso Liesio, Juho Andelmin, and Ahti Salo. Efficient allocation of resources to a portfolio of decision making units. European Journal of Operational Research, vol. 286, no. 2, pp. 619-636, October 2020.
    Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-202004032694
    DOI: 10.1016/j.ejor.2020.03.031 View at publisher
  • [Publication 4]: IV Ahti Salo, Juho Andelmin, and Fabricio Oliveira. Decision Programming for mixed-integer multi-stage optimization under uncertainty.Submitted Manuscript, August 2020.
Citation