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

Juho Andelmin

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

Julkaisun otsikon käännös: Malleja ja algoritmeja ajoneuvon reititykseen, resurssien allokointiin, sekä monijaksoiseen päätöksentekoon epävarmuuden alla

Juho Andelmin

Matematiikan ja systeemianalyysin laitos

Tutkimustuotos: Doctoral Thesis › Collection of Articles

Abstrakti

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.

Julkaisun otsikon käännös	Malleja ja algoritmeja ajoneuvon reititykseen, resurssien allokointiin, sekä monijaksoiseen päätöksentekoon epävarmuuden alla
Alkuperäiskieli	Englanti
Pätevyys	Tohtorintutkinto
Myöntävä instituutio	Aalto-yliopisto
Valvoja/neuvonantaja	Salo, Ahti, Vastuuprofessori Bartolini, Enrico, Ohjaaja Pinheiro de Oliveira, Fabricio, Ohjaaja Liesiö, Juuso, Ohjaaja Salo, Ahti, Ohjaaja
Kustantaja	Aalto University
Painoksen ISBN	978-952-64-0417-2
Sähköinen ISBN	978-952-64-0418-9
Tila	Julkaistu - 2021
OKM-julkaisutyyppi	G5 Tohtorinväitöskirja (artikkeli)

Tutkimusalat

optimointi
ajoneuvon reititys
resurssien allokointi
monijaksoinen päätöksenteko

Pääsy asiakirjaan

http://urn.fi/URN:ISBN:978-952-64-0418-9

OpenUrl-saatavuus

Koko teksti

Siteeraa tätä

@phdthesis{a228c5ad89b145e79e468eda6c93552d,

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

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.",

keywords = "optimization, vehicle routing, resource allocation, decision-making under uncertainty, optimointi, ajoneuvon reititys, resurssien allokointi, monijaksoinen p{\"a}{\"a}t{\"o}ksenteko, optimization, vehicle routing, resource allocation, decision-making under uncertainty",

author = "Juho Andelmin",

year = "2021",

language = "English",

isbn = "978-952-64-0417-2",

series = "Aalto University publication series DOCTORAL DISSERTATIONS",

publisher = "Aalto University",

number = "82",

address = "Finland",

school = "Aalto University",

}

TY - THES

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

AU - Andelmin, Juho

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - optimization

KW - vehicle routing

KW - resource allocation

KW - decision-making under uncertainty

KW - optimointi

KW - ajoneuvon reititys

KW - resurssien allokointi

KW - monijaksoinen päätöksenteko

KW - optimization

KW - vehicle routing

KW - resource allocation

KW - decision-making under uncertainty

M3 - Doctoral Thesis

SN - 978-952-64-0417-2

T3 - Aalto University publication series DOCTORAL DISSERTATIONS

PB - Aalto University

ER -

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

Abstrakti

Tutkimusalat

Pääsy asiakirjaan

OpenUrl-saatavuus

Sormenjälki

Siteeraa tätä