Optimization and Allocation in Some Decision Problems with Several Agents or with Stochastic Elements

Abstract

[Abstract] This dissertation addresses sorne decision problems that arise in project management, cooperative game theory and vehicle route optimization. We start with the problem of allocating the delay costs of a project. In a stochastic context in which we assume that activity durations are random variables, we propose and study an allocation rule based on the Shapley value. In addition, we present an R package that allows a comprehensive control of the project, including the new rule. We propose and characterize new egalitarian solutions in the context of cooperative games with a coalitional structure. Also, using a necessary player property we introduce a new value for cooperative games, which we later extend and characterize within the framework of cooperative games with a coalitional structure. Finally, we present a two-step algorithm for solving multi-compartment vehicle route problems with stochastic demands. This algorithm obtains an initial solution through a constructive heuristic and then uses a tabu search to improve the solution. Using real data, we evaluate the performance of the algorithm.

[Resumo] Nesta memoria abórdanse diversos problemas de decisión que xorden na xestión de proxectos, na teoría de xogos cooperativos e na optimización de rutas de vehículos. Empezamos estudando o problema da repartición dos custos de demora nun proxecto. Nun contexto estocástico no que supoñemos que as duracións das actividades son variables aleatorias, propoñemos e estudamos unha regra de repartición baseada no valor de Shapley. Ademais, presentamos un paquete de R que permite un control integral do proxecto, incluíndo a nova regra de repartición. A continuación, propoñemos e caracterizamos axiomaticamente novas solucións igualitarias no contexto dos xogos cooperativos cunha estrutura coalicional. E introducimos un novo valor, utilizando unha propiedade de xogadores necesarios, para xogos cooperativos, que posteriormente estendemos e caracterizamos dentro do marco dos xogos cooperativos cunha estrutura coalicional. Por último, presentamos un algoritmo en dous pasos para resolver problemas de rutas de vehículos con multi-compartimentos e demandas estocásticas. Este algoritmo obtén unha solución inicial mediante unha heurística construtiva e, a continuación, utiliza unha búsqueda tabú para mellorar a solución. Utilizando datos reais, levamos a cabo unha análise do comportamento do algoritmo.

[Resumen] En esta memoria se abordan diversos problemas de decisión que surgen en la gestión de proyectos, en la teoría de juegos cooperativos y en la optimización de rutas de vehículos. Empezamos estudiando el problema del reparto de los costes de demora en un proyecto. En un contexto estocástico en el que suponemos que las duraciones de las actividades son variables aleatorias, proponemos y estudiamos una regla de reparto basada en el valor de Shapley. Además, presentamos un paquete de R que permite un control integral del proyecto, incluyendo la nueva regla de reparto. A continuación, proponemos y caracterizamos axiomáticamente nuevas soluciones igualitarias en el contexto de los juegos cooperativos con una estructura coalicional. E introducimos un nuevo valor, utilizando una propiedad de jugadores necesarios, para juegos cooperativos, que posteriormente extendemos y caracterizamos dentro del marco de los juegos cooperativos con una estructura coalicional. Por último, presentamos un algoritmo en dos pasos para resolver problemas de rutas de vehículos con multi-compartimentos y demandas estocásticas. Este algoritmo obtiene una solución inicial mediante una heurística constructiva y, a continuación, utiliza una búsqueda tabú para mejorar la solución. Utilizando datos reales, llevamos a cabo un análisis del comportamiento del algoritmo.