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

Research output: ThesisDoctoral ThesisCollection of Articles

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.
Translated title of the contributionMalleja ja algoritmeja ajoneuvon reititykseen, resurssien allokointiin, sekä monijaksoiseen päätöksentekoon epävarmuuden alla
Original languageEnglish
QualificationDoctor's degree
Awarding Institution
  • Aalto University
Supervisors/Advisors
  • Salo, Ahti, Supervising Professor
  • Bartolini, Enrico, Thesis Advisor
  • Pinheiro de Oliveira, Fabricio, Thesis Advisor
  • Liesiö, Juuso, Thesis Advisor
  • Salo, Ahti, Thesis Advisor
Publisher
Print ISBNs978-952-64-0417-2
Electronic ISBNs978-952-64-0418-9
Publication statusPublished - 2021
MoE publication typeG5 Doctoral dissertation (article)

Keywords

  • optimization
  • vehicle routing
  • resource allocation
  • decision-making under uncertainty

Fingerprint

Dive into the research topics of 'Models and algorithms for vehicle routing, resource allocation, and multi-stage decision-making under uncertainty'. Together they form a unique fingerprint.

Cite this