Search

In this paper, we propose a new approach for including quay crane travel and setup times in the berth allocation and quay crane assignment problem. We first develop a new mixed integer linear programming model (MILP) for the problem without setups (BACASP), in which berthing positions and times are considered as continuous variables. Several groups of valid inequalities are also set forth. Then, for the BACASP with crane travel and setup times, which we denote as BACASP-S, we propose two MILPs: the first is based on the previous BACASP formulation and the second on routing formulations. Due to the complexity of the BACASP-S, we also propose a genetic algorithm and an exact approach which combines various MILPs with the genetic algorithm. All methods and valid inequalities are computationally tested over two different sets of randomly generated instances. According to the results, the models and algorithms can optimally solve, in less than one hour, BACASP-S instances of up to 40 vessels within a quay one kilometer long and a time horizon of one week. Additionally, extensive experiments were conducted on a new large set of instances to assess the effect of various BACASP-S input parameters on the computation effort required to solve the problem. Ceteris paribus, the computational effort required seems to increase with decreasing number of cranes, while vessel processing times and crane setup times seem not to affect it.

This article deals with one of the types of “Satellite Range Scheduling” problems arising in Earth Observation Satellite operations, Antenna-Satellite Scheduling. Given a set of satellites, a set of available antennas and a time horizon, the problem consists of designing an operational plan that assigns satellites to antennas in an optimal fashion. Extending a previous integer linear programming (ILP) model (shortening model, with only integer variables), we propose a mixed ILP (MILP) (shaving model, which includes both continuous and integer variables), to more efficiently solve this problem. After computing the passes generated by the satellites' windows of visibility from the antennas, the optimal planner is able to cancel a pass, move it to another antenna, or shorten its duration, in order to avoid scheduling conflicts. In contrast to the shortening model, which used intersections between passes to determine the best schedule, the shortening operation is now referred to as shaving, since the shaving model can arbitrarily adjust the duration of a pass in a razor-like fashion, giving the model its name. Computational results obtained in tests over realistic scenarios prove that the shaving model outperforms the shortening model, producing fewer cancellations, smaller shaved times, and a fairer distribution of cancelled passes among satellites, with much shorter preprocessing times.

El propósito de este proyecto consiste en crear un modelo de programación lineal entera mixta que pueda ser utilizado por los equipos de Fórmula 1 para determinar la mejor estrategia de carrera. El modelo considerará varios parámetros, como la degradación de los neumáticos basada en datos de tiempos por vuelta de la temporada 2020/2021 de la Fórmula 1, y también el reglamento actual de la Federación Internacional del Automóvil (FIA). Aunque el modelo no tendrá en cuenta la presencia de otros competidores, determinará cuándo debe ingresar el coche a boxes para completar la carrera en el menor tiempo posible. Para evaluar la precisión del modelo, se compararán sus resultados con los de carreras reales., The goal of this project is to build a mixed integer linear programming model that can be used by Formula 1 teams to determine the optimal race strategy in the presence of a number of parameters that influence it. The model takes into account tyre degradation, based on lap time data observed during 2020/2021 Formula 1 season, and also the current FIA (Federation Internationale de l’Automobile) regulations. No other competitors are considered in the model, but we will determine which laps the car should enter to finish the race in the shortest time possible. The results will be compared with the results of real races to see the differences.

El diseño de un modelo matemático exacto para la planificación de redes de tránsito rápido en una ciudad es posible, pero no es una tarea sencilla debido a la complejidad y la cantidad de variables involucradas. Como se ha introducido anteriormente, requiere una planificación cuidadosa y una consideración de varios factores, como las necesidades de transporte de la ciudad, el crecimiento futuro, las características topográficas y la demanda de transporte. El uso de modelos matemáticos en el diseño de una red de tránsito rápido en una ciudad es cada vez más común. Los modelos matemáticos pueden ayudar a los planificadores de transporte a analizar diferentes opciones de rutas, evaluar la demanda de pasajeros y determinar la capacidad necesaria para el sistema. Por otro lado, los modelos matemáticos también pueden ayudar a optimizar la ubicación de las estaciones, la frecuencia de los trenes y otros aspectosimportantes del diseño de la red de tránsito rápido. Además, estos modelos pueden ser útiles para simular diferentes escenarios y evaluar el impacto de posibles cambios en la red en términos de tiempos de viaje, capacidad, costes, y otros aspectos. No obstante, los modelos matemáticos avanzados que se han desarrollado para la planificación de redes de transporte son de alto coste, y requieren una cantidad significativa de recursos y tiempo para desarrollarse y mantenerse actualizados. Adicionalmente, la utilización de modelos matemáticos en el diseño de una red de tránsito rápido depende en gran medida de la disponibilidad de datos precisos y actualizados, así como de los recursos financieros y técnicos necesarios para llevar a cabo la planificación y construcción del sistema. Esto hace, que se dificulte su aplicación matemática, dado que es importante tener en cuenta las limitaciones y posibilidades de los solvers que resuelven los modelos matemáticos en función de las condiciones específicas de cada proyecto. Es por esta razón, que a lo largo de este capítulo se e

Machine scheduling problems arise in many production processes, and are something that needs to be consider when optimizing the supply chain. Among them, flowshop scheduling problems happen when a number of jobs have to be sequentially processed by a number of machines. This paper addressees, for the first time, the Permutation Flowshop Scheduling problem with additional Resources during Setups (PFSR-S). In this problem, in addition to the standard permutation flowshop constraints, each machine requires a setup between the processing of two consecutive jobs. A number of additional and scarce resources, e.g. operators, are needed to carry out each setup. Two Mixed Integer Linear Programming formulations and an exact algorithm are proposed to solve the PFSR-S. Due to its complexity, these approaches can only solve instances of small size to optimality. Therefore, a GRASP metaheuristic is also proposed which provides solutions for much larger instances. All the methods designed for the PFSR-S in this paper are computationally tested over a benchmark of instances adapted from the literature. The results obtained show that the GRASP metaheuristic finds good quality solutions in short computational times.

Firms’ growth, the darling measure of investors, comes from higher revenues. Thus, sales and marketing departments make extreme efforts to accept as many customer orders as possible. Unfortunately, not all orders contribute equally to profits, and some orders may even reduce net profits. Thus, saying no (i.e., not accepting an order) may be a necessary condition for net profits growth. For understanding the impact of rejecting orders on profitability, we propose an order acceptance and scheduling problem (OAS). Although the OAS has extensively been studied in the literature, there is still some gap between these papers and real-life problems in industry. In an attempt to close that gap, the OAS we propose considers orders revenues, machines costs, holding costs and tardiness costs. We develop a mixed integer linear programming (MILP) model for solving this problem. Since the complexity of the problem makes it impossible for the MILP to solver large-scale instances, we also propose a metaheuristic algorithm. Numerical experiments show that the metaheuristic finds good quality solutions in short computational times. In the last part of the paper we confirm some managerial insights: higher holding and tardiness costs imply a lower acceptance of orders, forcing production has a concave negative impact on net profits, and accurately estimating costs is essential for good planning.

As a consequence of globalization, interactions among countries, companies, people, etc, have been increased during recent decades. The basic mathematical support structure for modeling such interactions is a network. Thus, Network Design plays an important role for facilitating the interactions. Nevertheless, %Network Design Problems have been studied since the interest of modelling the interaction between a set of individuals became to gain importance. Nevertheless, the majority of Network Design problems are difficult to solve. Our goal is to study them from the Combinatorial Optimization point of view to find exact and metaheuristic \mbox{approaches} that improve the process of getting optimal ,or at least good, solutions for practical applications. In this thesis, we study some Network Design problems, which can be grouped into two large classes detailed below, according to the main feature of each one. In all the problems it is considered that the demand is given by a set of pairs of origin-destination points. That is, each demand has to move from an origin-node to a destination-node. Another feature in common is the existence of an alternative network that can be used by the demand set. In this situation, the possible existing competition between the network to be designed and the already actual alternative network has been highlighted. On the one hand, Chapters 2, 3 and 4 deal with Covering Network Design \mbox{problems}. These problems seek to design a network in such a way that the proportion of demand covered is maximized or exceeds a certain percentage of the total. Particularly, the third chapter shows a practical application for Network Design in the transportation area. On the other hand, Chapter 5 extends the existing notions in Facility Location Theory of $\lambda$-Cent-Dian and Generalized-Center to the area of Network Design. The problems in this chapter are focused on designing a network that minimizes the maximum distance of a known set of origi, Doctorat en Sciences, info:eu-repo/semantics/nonPublished

The aim of this paper is to introduce the Flexible Periodic Vehicle Routing Problem with Heterogeneous Fleet, a variant of the Periodic Vehicle Routing Problem. Flexibility is introduced in service schedules and delivered quantities, heterogeneity comes from different vehicles capacities and speeds. Three Mixed-Integer Linear Programming formulations and a matheuristic, based on Kernel Search, are proposed. Computational tests are made to evaluate the performance of the three formulations and to assess the quality of the solutions provided by the matheuristic.

[ES] En el presente trabajo se aborda la optimización de la secuenciación de la producción en una empresa del sector de los aerosoles; concretamente, de su línea de productos para el hogar. Se trata de una situación real y no de un caso de estudio. La empresa necesita planificar la secuenciación de las órdenes de producción que se reciben diariamente, de modo que se reduzcan los tiempos de transición. El trabajo comprende tanto la modelización matemática del problema como la elaboración de una solución informática que permita obtener una secuencia de producción óptima. Asimismo, se evalúa la eficiencia y el ahorro de coste de esta metodología comparando los resultados que esta ofrece frente a datos reales de producción. Por último, se evalúa la capacidad de la solución informática desarrollada para abordar problemas de mayor tamaño, desde el punto de vista de la cantidad de trabajos a secuenciar., [EN] In this Project, production sequencing optimization in an aerosol sector company is approached, specifically in its home care products line. It is actually a real case found during my internship at a company, not a study case. The company needs to plan the sequence of the production orders daily received, in a way that transition times are reduced. The project involves mathematical modelling as well as the development of a software solution that enables to obtain an optimal production sequence. Moreover, the efficiency and cost saving of this methodology is evaluated comparing the results it offers with the real production data. Finally, the capacity of the software solution developed is evaluated for bigger size problems, from a number of jobs to sequence point of view.

[ES] En esta tesis doctoral se estudia el problema de secuenciación de máquinas paralelas no relacionadas con necesidad de ajustes y recursos adicionales asignados en los ajustes. En este problema, se tiene un grupo de tareas (también llamadas trabajos), donde cada una debe ser procesada en una de las máquinas paralelas disponibles. Para procesar una tarea después de otra en la misma máquina, se debe hacer un ajuste en la máquina. Se asume que estos ajustes deben ser realizados por un recurso adicional limitado (por ejemplo, operarios). En esta tesis doctoral se estudian dos variantes del problema planteado: 1) considerando el problema con el único objetivo de minimizar el tiempo máximo de finalización de todos los trabajos (makespan), y 2) considerando el problema multi-objetivo minimizando simultáneamente el makespan y el consumo máximo de recursos adicionales. Inicialmente, se realiza una completa revisión bibliográfica sobre estudios relacionados con el problema planteado. En esta revisión se detecta que, a pesar de existir numerosos estudios de secuenciación de máquinas paralelas, no muchos de estos estudios tienen en cuenta recursos adicionales. Posteriormente, para introducir el problema a estudiar antes de plantear métodos de resolución, se realiza una breve explicación de los principales problemas de secuenciación de máquinas paralelas. El problema de un solo objetivo está clasificado como NP-Hard. Por ello, para abordar su resolución se han diseñado e implementado heurísticas y metaheurísticas siguiendo dos enfoques diferentes. Para el primer enfoque, que ignora la información sobre el consumo de recursos adicionales en la fase constructiva, se adaptan dos de los mejores algoritmos existentes en la literatura para el problema de máquinas paralelas con ajustes sin necesidad de recursos adicionales. En el segundo enfoque, que sí tiene en cuenta la información sobre el consumo de recursos adicionales en la fase constructiva, se proponen nuevos algoritmos heur, [CAT] En aquesta tesi doctoral s'estudia el problema de seqüenciació de màquines paral·leles no relacionades amb necessitat d'ajustos i recursos addicionals assignats en els ajustos. En aquest problema, es tenen un grup de tasques (també anomenades treballs), on cadascuna ha de ser processada en una de les màquines paral·leles disponibles. Per processar una tasca després d'una altra en la mateixa màquina, s'ha de fer un ajustament en la màquina. S'assumeix que aquests ajustos en les màquines per a processar una tasca després del processament d'una altra, han de ser realitzats per un recurs addicional limitat (per exemple, operaris). En aquesta tesi doctoral s'estudien dos variants al problema plantejat: 1) considerant el problema com l'únic objectiu de minimitzar el temps màxim de finalització de tots els treballs (makespan), i 2) considerant el problema multi-objectiu minimitzant simultàniament el makespan i el consum màxim de recursos addicionals. Inicialment, es realitza una completa revisió bibliogràfica sobre estudis relacionats amb el problema plantejat. En esta revisió es detecta que, tot i existir nombrosos estudis de seqüenciació de màquines paral·leles, hi ha molts pocs que tenen en compte recursos addicionals. Posteriorment, per introduir el problema a estudiar abans de plantejar mètodes de resolució, es realitza una breu explicació dels principals problemes de seqüenciació de màquines paral·leles. El problema d'un sol objectiu està classificat com NP-Hard. Per això, per abordar la seua resolució s'han dissenyat i implementat heurístiques y metaheurístiques seguint dos enfocs diferents. El primer enfoc ignora la informació sobre el consum de recursos en la fase constructiva, adaptant dos dels millors algoritmes existents en la literatura per al problema de seqüenciació de màquines paral·leles amb ajustaments sense necessitat de recursos. Per al segon enfoc si es té en compte la informació sobre el consum de recursos en la fase constructiva. Després d'anal, [EN] In this thesis we study the unrelated parallel machine scheduling problem with setup times and additional limited resources in the setups. In this problem, we have a group of tasks (also called jobs), where each one must be processed on one of the available parallel machines. To process one job after another on the same machine, a setup must be made on the machine. It is assumed that these setups on machines must be made by a limited additional resource (eg, operators). In this thesis two variants of the problem are studied: 1) considering the problem with the objective of minimizing the maximum completion time of all jobs (makespan), and 2) considering the multi-objective problem, minimizing the makespan and the maximum consumption of additional resources. Initially, a complete literature review is carried out on studies related to the problem addressed in this thesis. This review finds that despite numerous parallel machine scheduling studies, there are very few that take into account additional resources. Subsequently, to introduce the problem addressed before proposing resolution methods, a brief explanation of the main parallel machines scheduling problems is made. The problem with a single objective is classified as NP-Hard. Therefore, to solve it, heuristics and metaheuristics have been designed and implemented following two different approaches. For the first approach, which ignores the information on the consumption of resources in the construction phase, two of the best algorithms existing in the literature for the problem of parallel machines with setups without additional resources are adapted. For the second approach, which does take into account information on the consumption of resources in the construction phase, new heuristic and metaheuristic algorithms are proposed to solve the problem. Following the results of the computational experiments, we conclude that there are differences between the two approaches, the approach that takes into accoun

[ES] En este trabajo se pretende resolver el problema de secuenciación de máquinas paralelas no relacionadas con ajustes entre trabajos y recursos limitados adicionales. El objetivo del problema es minimizar el tiempo de finalización del último trabajo en ser procesado (makespan). Este makespan puede ser determinante para cualquier empresa con una cadena de producción a la hora de cumplir plazos de entrega o mejorar la productividad. Para abordar este problema se diseñarán e implementarán heurísticas que estarán formadas por dos fases: una fase constructiva donde se obtendrá una primera solución del problema, y una fase de reparación donde se arreglará la solución obtenida en la fase anterior si se supera el número de recursos permitidos. Además, para conseguir una mayor diversidad de soluciones, se aleatorizará parte de la fase constructiva, convirtiendo las heurísticas en metaheurísticas. Más adelante se realizará una extensa fase de experimentos y posterior análisis, en el que se probarán diferentes versiones de las heurísticas y metaheurísticas variando diferentes factores. A continuación, se compararán los resultados obtenidos por los algoritmos propuestos, con los logrados previamente para el mismo problema por un modelo de programación lineal entera (MILP, por sus siglas en inglés Mixed Integer Linear Program). La conclusión principal de estos experimentos es que, con un tiempo de proceso muy inferior, se pueden casi igualar y en algunos casos mejorar los resultados de este modelo utilizando los algoritmos heurísticos y metaheurísticos propuestos., [EN] This project aims to solve the unrelated parallel machines scheduling problem with adjustments between jobs and additional limited resources. The goal of this problem is to minimize the completion time of the last job (makespan). This makespan can be decisive for any business with production chains when it comes to respect deadlines or improving productivity. To engage this problem, design and implementation of heuristics and metaheuristics will be done, and they will be split in two phases: a constructive phase where a first solution will be obtained, and a repair phase where this solution will be fixed in case of exceeding the resources limit. Furthermore, to achieve a major diversity of solutions, part of the construction phase will be randomized, transforming heuristics into metaheuristics. Later, an extensive experiments phase will be done with a proper analysis, where different versions of the heuristics and metaheuristics will be tested varying different factors. Next, the results obtained will be compared with the ones achieved for the same problem by an integer linear programming model (MILP). The main conclusion of these experiments is that, with much less processing time, the results obtained with the model are similar or in some instances even worse, compared to the ones achieved with the proposed heuristic and metaheuristic algorithms., [CA] En aquest treball es tracta de resoldre el problema de seqüenciació de màquines paral·leles no relacionades amb ajustos entre treballs i recursos limitats adicionals. L’objectiu del problema es minimitzar el temps de finalització de l’últim treball a ser processat (makespan). Este makespan pot ser determinant per a qualsevol empresa amb una cadena de producció a l’hora de complir terminis de lliurament o millorar la productivitat. Per a abordar aquest problema es dissenyaran e implementaran heurístiques que estaran formades per dues fases: una fase constructiva on s’obtindrà una primera solució del problema, i una fase de reparació on s’arreglarà la solució obtinguda en la fase anterior si es supera el nombre de recursos permitits. A més, per a aconseguir una major diversitat de solucions, s’aleatoritzarà part de la fase construcitva, convertint les heurístiques en metaheurístiques. Més endavant es realitzarà una extensa fase d’experiments i posterior anàlisi, en el qual es provaran diferents versions de les heurístiques i metaheurístiques variant diferents factors. A continuació, es compararan els resultats obtinguts pels algorismes proposats, amb els reeixits prèviament per al mateix problema obtinguts amb un model de programació lineal sencera (MILP, per les seues sigles en anglés Mixed Integer Linear Program). La conclusió principal d’aquests experiments és que, amb un temps de procés molt inferior, es poden quasi igualar i en alguns casos millorar els resultats d’aquest model utilitzant els algorismes heurístics i metaheurístics proposats.

[EN] In this paper we analyze the computational complexity of transportation infrastructure network design problems, in the presence of a competing transportation mode. Some of these problems have previously been introduced in the literature. All problems studied have a common objective: the maximization of the number of travelers using the new network to be built. The differences between them are due to two factors. The first one is the constraints that the new network should satisfy: (1) budget constraint, (2) no-cycle constraint, (3) both constraints. The second factor is the topology of the network formed by the feasible links and stations: (1) a general network, (2) a forest. By combining these two factors, in total we analyze six problems, five of them are shown to be NP-hard, the sixth being trivial. Due to the NP-hardness of these problems, a genetic algorithm is proposed. Computational experiments show the applicability of this algorithm.

[EN] This paper provides practitioners with new approaches for solving realistic scheduling problems that consider additional resources, which can be implemented on expert and intelligent systems and help decision making in realistic settings. More specifically, we study the unrelated parallel machine scheduling problem with setup times and additional limited resources in the setups (UPMSR-S), with makespan minimization criterion. This is a more realistic extension of the traditional problem, in which the setups are assumed to be done without using additional resources (e.g. workers). We propose three metaheuristics following two approaches: a first approach that ignores the information about additional resources in the constructive phase, and a second approach that takes into account this information about the resources. Computational experiments are carried out over a benchmark of small and large instances. After the computational analysis we conclude that the second approach shows an excellent performance, overcoming the first approach.

[EN] This paper introduces a row and column generation algorithm for finding the nucleolus, based on a linear programming model proposed in an earlier research. Since this approach cannot return an allocation for large games, we also propose a heuristic approach, which is based on sampling the coalitions space. Experiments over medium sized games show that the proposed heuristic finds allocations which are close to the true nucleolus, in a reasonable amount of time. Experiments over 100-player games show that the proposed heuristic can be applied to games of large size.

[EN] Parallel machine scheduling problems have many practical and industrial applications. In this paper we study a generalization which is the unrelated parallel machine scheduling problem with machine and job sequence setup times (UPMS) with makespan minimization criterion. We propose new mixed integer linear programs and a mathematical programming based algorithm. These new models and algorithms are tested and compared with the existing ones in an extensive and comprehensive computational campaign. The performance of two popular commercial solvers (CPLEX and Gurobi) is also compared in the experiments. Results show that the proposed methods significantly improve on existing methods and are able to obtain solutions for extremely large instances of up to 1000 jobs and eight machines with relative deviations from lower bounds below 0.8%.

El problema presentado es bien conocido en la literatura, y está clasificado como NP-duro. Por ello, se hacen necesarios algoritmos eficientes para su resolución. En este trabajo se proponen diferentes algoritmos matheurísticos, que combinan técnicas heurísticas con un modelo de programación lineal entera propuesto en una investigación anterior. Se realizarán experimentos computacionales para validar la calidad de la solución obtenida, así como la eficiencia de los algoritmos propuestos.

[EN] In this paper, we characterize minimax and Pareto-optimal security payoff vectors for general multicriteria zero-sum matrix games, using properties similar to the ones that have been used in the single criterion case. Our results show that these two solution concepts are rather similar, since they can be characterized with nearly the same sets of properties. Their main difference is the form of consistency that each solution concept satisfies. We also prove that both solution concepts can transform into each other, in their corresponding domains. (C) 2017 Elsevier Inc. All rights reserved.

En este trabajo el alumno aborda un problema de secuenciación de máquinas paralelas no relacionadas con tiempos de ajuste entre trabajos. Los tiempos de ajuste dependen tanto de la máquina como de la secuencia de trabajos procesados. Además, dichos ajustes necesitan utilizar una cantidad de recursos adicionales, que también depende tanto de la máquina como de la secuencia. Este recurso es limitado y renovable. Este problema apenas ha sido tratado en la literatura científica, y se puede clasificar como NP-difícil. Dado la complejidad del problema, se propondrán técnicas metaheurísticas para su resolución en un tiempo de computación razonable. La calidad de la solución obtenida se comparará con aquélla que se obtenga mediante un modelo de programación lineal entera, para instancias de tamaño pequeño.

[EN] The problem studied in this paper takes as input data a set of lines forming a railway network, and an origin¿destination (OD) matrix. The OD pairs may use either the railway network or an alternative transportation mode. The objective is to determine the frequency/headway of each line as well as its number of carriages, so that the net profit of the railway network is maximized. We propose a mixed integer non-linear programming formulation for this problem. Because of the computational intractability of this model, we develop four algorithms: a mixed integer linear programming (MIP) model, a MIP-based iterative algorithm, a shortest-path based algorithm, and a local search. These four algorithms are tested and compared over a set of randomly generated instances. An application over a case study shows that only the local search heuristic is capable of dealing with large instances.

El diseño de redes de ferrocarril en competencia con modos de transporte alternativo (RND por sus siglas en inglés) se puede modelar como un problema de optimización combinatoria sobre un grafo dirigido. El objetivo del RND es diseñar una red de ferrocarril que atraiga al mayor número de pasajeros posible, suponiendo una restricción presupuestaria. Estudios previos han demostrado que este problema es NP-duro. Además de esa justificación teórica, trabajos publicados en la literatura científica han demostrado que los modelos matemáticos para el RND no son aplicables a instancias de este problema de tamaño real. Por todo ello, la investigación sobre algoritmos que ofrezcan una solución en un tiempo de cómputo razonable está justificada. En este trabajo se propondrán nuevos algoritmos metaheurísticos para una resolución eficiente del RND. Dichos algoritmos se compararán con otros propuestos con anterioridad en la literatura científica mediante la resolución de instancias del RND.

[EN] In this paper we analyze a parallel machine scheduling problem in which the processing of jobs on the machines requires a number of units of a scarce resource. This number depends both on the job and on the machine. The availability of resources is limited and fixed throughout the production horizon. The ob- jective considered is the minimization of the makespan. We model this problem by means of two integer linear programming problems. One of them is based on a model previously proposed in the literature. The other one, which is based on the resemblance to strip packing problems, is an original contribution of this paper. As the models presented are incapable of solving medium-sized instances to optimality, we propose three matheuristic strategies for each of these two models. The algorithms proposed are tested over an extensive computational experience. Results show that the matheuristic strategies significantly outperform the mathematical models.

[EN] This work presents an unrelated parallel machine problem, solved by an ILP model with 5 contraint sets, which is compared to a model that uses lagrangian relaxation on one of its constraints, in this case, the resource constraints which indicates there is a limited resource which is needed for the jobs process., [ES] El trabajo presenta un problema de máquinas paralelas no relacionadas resuelto con un modelo ILP con cinco sets de restricciones, el cual es comprobado con un modelo que utiliza relajación lagrangiana en una de sus restricciones, en este caso,la restricción relajada corresponde a un recurso limitado que es necesario para el proceso de los trabajos.

Refereeing of this contribution was handled by T. Vladimirova, [EN] This paper deals with the swath acquisition planning problem for multisatellite Earth observation missions. Given a set of satellites and a mission time frame, the problem we solve consists of selecting a set of acquisitions from the satellites in order to cover a given region of interest during the requested time frame, optimizing a certain objective function. We show that the planning problem can be modeled as a set covering problem, using basic tools of mathematical programming. The formulation of the model requires the solution of a complex computational geometry problem, and therefore the use of heuristics and metaheuristics applies. In this paper, we discuss the efficiency of the constructive phase of a greedy randomized adaptive search procedure algorithm. Computational results comparing the heuristic algorithms with the exact approach are presented.

[ES] El trabajo pretende analizar los efectos sobre la economía de los países o zonas en las que se ha empleado esta política de expansión monetaria, mediante un análisis estadístico de los cambios producidos sobre determinados indicadores tanto macro (PIB, IPC, Paro, Dinero en Circulación ... ), y una posterior extrapolación de estos efectos observados a distintos sectores de la economía, con el objetivo de estimar las posibles consecuencias de esta medida de política económica en cada uno de ellos. Para ello se estudiarán los posibles efectos sobre la base del modelo macroeconómico modelo ISLM. Se analizará el marco conceptual y de funcionamiento de los bancos centrales. Asimismo se describirá el desarrollo de las diferentes expansiones cuantitativas en los países en los que con anterioridad se ha aplicado esta medida y se efectuará un análisis estadístico de los efectos de la expansión sobre variables clave de la economía, así como un análisis del impacto de estas variables sobre distintos sectores de la economía.

[EN] In this work, a problem consisting of locating two or more stations over a high-speed railway network is proposed and solved. A competing transportation mode is also considered., [ES] En este trabajo se modela y resuelve el problema de localizar dos o más estaciones de tren en una red de alta velocidad, en presencia de otro medio de transporte.

[EN] In this work genetic algorithms applied to select neural networks The neural networks then used to predict store customers position., [ES] En este trabajo se aplicarán algoritmos genéticos para seleccionar redes neuronales. Las redes neuronales diseñadas se utilizarán para la predicción de posicionamientos de clientes en tiendas.

The railway planning problem consists of several consecutive phases: network design, line plan- ning, timetabling, personnel assignment and rolling stocks planning. In this paper we will focus on the line planning process. Traditionally, the line planning problem consists of determining a set of lines and their frequencies optimizing a certain objective. In this work we will focus on the line planning problem context taking into account aspects related to rolling stock and crew operating costs. We assume that the number of possible vehicles is limited, that is, the problem that we are considering is a capacitated problem and the line network can be a crowding net- work. The main novelty in this paper is the consideration of the size of vehicles and frequencies as variables as well as the inclusion of a congestion function measuring the level of in-vehicle crowding. Concretely, we present the problem and an algorithm to solve it, which are tested via a computational experience.

In this paper the following facility location problem in a mixed planarnetwork space is considered: We assume that traveling along a given network is faster than traveling within the plane according to the Euclidean distance. A pair of points (Ai,Aj ) is called covered if the time to access the network from Ai plus the time for traveling along the network plus the time for reaching Aj is lower than, or equal to, a given acceptance level related to the travel time without using the network. The objective is to find facilities (i.e. entry and exit points) on the network that maximize the number of covered pairs. We present a reformulation of the problem using convex covering sets and use this formulation to derive a finite dominating set and an algorithm for locating two facilities on a tree network. Moreover, we adapt a geometric branch and bound approach to the discrete nature of the problem and suggest a procedure for locating more than two facilities on a single line, which is evaluated numerically.

In this paper we study the problem of locating a new station on an existing rail corridor and a new junction on an existing road network, and connecting them with a new road segment under a budget constraint. We consider three objective functions and the corresponding optimization problems, which are modeled by means of mixed integer non-linear programs. For small instances, the models can be solved directly by a standard solver. For large instances, an enumerative algorithm based on a discretization of the problem is proposed. Computational experiments show that the latter approach yields high quality solutions within short computing times.

Every day, ground stations need to manage numerous requests for allocation of antenna time slots by customers operating satellites. For multi-antenna, multi-site ground networks serving numerous satellite operators, oftentimes these requests yield conflicts, which arise when two or more satellites request overlapping time slots on the same antenna. Deconflicting is performed by moving passes to other antennas, shortening their duration, or canceling them, and has frequently been done manually. However, when many conflicts are present, deconflicting becomes a complex and time-consuming when done manually. We propose an automated tool that solves the problem by means of Integer Linear Programming. The models include operational constraints and mimic the manual process but consider the problem globally, thus being able to improve the quality of the solution. A simplified shortening model is also included to avoid excessive computation times, which is crucial given that the general problem has been reported NP-complete. Priorities are taken into account by tuning the cost function according to specifications of the requesting clients. Experiments with real-data scenarios using open-source software show that our tool is able to solve the Antenna Satellite assignment problem for a large number of passes in a short amount of time, thus enormously improving manual scheduling operations, even when performed by a skilled operator.

In this paper we show a new method for calculating the nucleolus by solving a unique minimization linear program with O(4n) constraints whose coeffi- cients belong to {−1, 0, 1}. We discuss the need of having all these constraints and empirically prove that they can be reduced to O(kmax2 n), where kmax is a positive integer comparable with the number of players. A computational experience shows the applicability of our method over (pseudo)random transferable utility cooperative games with up to 18 players.

This paper discusses and extends some competitive aspects of the games proposed in an earlier work, where a robust railway network design problem was proposed as a non-cooperative zero-sum game in normal form between a designer/operator and an attacker. Due to the importance of the order of play and the information available to the players at the moment of their decisions, we here extend those previous models by proposing a formulation of this situation as a dynamic game. Besides, we propose a new mathematical programming model that optimizes both the network design and the allocation of security resources over the network. The paper also proposes a model to distribute security resources over an already existing railway network in order to minimize the negative effects of an intentional attack. For the sake of readability, all concepts are introduced with the help of an illustrative example.

In this paper we show a new method for calculating the nucleolus by solving a unique minimization linear program with Oð4n Þ constraints whose coefficients belong to f−1; 0; 1g. We discuss the need of having all these constraints and empirically prove that they can be reduced to Oðkmax2n Þ, where kmax is a positive integer comparable with the number of players. A computational experience shows the applicability of our method over (pseudo)random transferable utility cooperative games with up to 18 players

This paper discusses and extends some competitive aspects of the games proposed in an earlier work, where a robust railway network design problem was proposed as a non-cooperative zero-sum game in normal form between a designer/operator and an attacker. Due to the importance of the order of play and the information available to the players at the moment of their decisions, we here extend those previous models by proposing a formulation of this situation as a dynamic game. Besides, we propose a new mathematical programming model that optimizes both the network design and the allocation of security resources over the network. The paper also proposes a model to distribute security resources over an already existing railway network in order to minimize the negative effects of an intentional attack. For the sake of readability, all concepts are introduced with the help of an illustrative example.

In this paper we will show how hypergraphs and some measures related to them can help in extracting information about Collective Transportation Line Networks. We will also prove that these measures satisfy certain properties that validate their use to compare the connectivity of different networks. © 2013 EDP Sciences and Springer.

In this paper we introduce and analyze new classes of cooperative games related to facility location models. The players are the customers (demand points) in the location problem and the characteristic value of a coalition is the cost of serving its members. Specifically, the cost in our games is the service diameter of the coalition. We study the existence of core allocations for these games, focusing on network spaces, i.e., finite metric spaces induced by undirected graphs and positive edge lengths.

This paper deals with cooperation situations in linear production problems in which a set of goods are to be produced from a set of resources so that a certain benefit function is maximized, assuming that resources not used in the production plan have no value by themselves. The Owen set is a well-know solution rule for the class of linear production processes. Despite their stability properties, Owen allocations might give null payoff to players that are necessary for optimal production plans. This paper shows that, in general, the aforementioned drawback cannot be avoided allowing only allocations within the core of the cooperative game associated to the original linear production process. In this paper a new solution set named EOwen is introduced. For any player whose resources are needed in at least one optimal production plan, the EOwen set contains at least one allocation that assigns a strictly positive payoff to such player.

This paper deals with cooperation situations in linear production problems in which a set of goods are to be produced from a set of resources so that a certain benefit function is maximized, assuming that resources not used in the production plan have no value by themselves. The Owen set is a well-known solution rule for the class of linear production processes. Despite their stability properties, Owen allocations might give null payoff to players that are necessary for optimal production plans. This paper shows that, in general, the aforementioned drawback cannot be avoided allowing only allocations within the core of the cooperative game associated to the original linear production process, and therefore a new solution set named EOwen is introduced. For any player whose resources are needed in at least one optimal production plan, the EOwen set contains at least one allocation that assigns a strictly positive payoff to such player. © 2012 Elsevier B.V. All rights reserved.

[EN] In this paper the following facility location problem in a mixed planar-network space is considered: We assume that traveling along a given network is faster than traveling within the plane according to the Euclidean distance. A pair of points (A i, A j) is called covered if the time to access the network from A i plus the time for traveling along the network plus the time for reaching A j is lower than, or equal to, a given acceptance level related to the travel time without using the network. The objective is to find facilities (i.e. entry and exit points) on the network that maximize the number of covered pairs. We present a reformulation of the problem using convex covering sets and use this formulation to derive a finite dominating set and an algorithm for locating two facilities on a tree network. Moreover, we adapt a geometric branch and bound approach to the discrete nature of the problem and suggest a procedure for locating more than two facilities on a single line, which is evaluated numerically. © 2012 Sociedad de Estadística e Investigación Operativa.

In this paper we introduce and analyze new classes of cooperative games related to facility location models defined on general metric spaces. The players are the customers (demand points) in the location problem and the characteristic value of a coalition is the cost of serving its members. Specifically, the cost in our games is the service radius of the coalition. We study the existence of core allocations and the existence of polynomial representations of the cores of these games, focusing on network spaces, i.e., finite metric spaces induced by undirected graphs and positive edge lengths, and on the ℓp metric spaces defined over Rd.

Rapid transit construction projects are major endeavours that require long-term planning by several players, including politicians, urban planners, engineers, management consultants, and citizen groups. Traditionally, operations research methods have not played a major role at the planning level but several tools developed in recent years can assist the decision process and help produce tentative network designs that can be submitted to the planners for further evaluation. This article reviews some indices for the quality of a rapid transit network, as well as mathematical models and heuristics that can be used to design networks.

[EN] Rapid transit construction projects are major endeavours that require long-term planning by several players, including politicians, urban planners, engineers, management consultants, and citizen groups. Traditionally, operations research methods have not played a major role at the planning level but several tools developed in recent years can assist the decision process and help produce tentative network designs that can be submitted to the planners for further evaluation. This article reviews some indices for the quality of a rapid transit network, as well as mathematical models and heuristics that can be used to design networks. © 2011 Elsevier Ltd.

In this paper we introduce and analyze new classes of cooperative games related to facility location models defined on general metric spaces. The players are the customers (demand points) in the location problem and the characteristic value of a coalition is the cost of serving its members. Specifically, the cost in our games is the service radius of the coalition. We call these games the Minimum Radius Location Games (MRLG). We study the existence of core allocations and the existence of polynomial representations of the cores of these games, focusing on network spaces, i.e., finite metric spaces induced by undirected graphs and positive edge lengths, and on the ¿ p metric spaces defined over R d. © 2011 Elsevier B.V. All rights reserved.

This paper analyzes the solvability of a railway network design problem and its robust version. These problems are modeled as integer linear programming problems with binary variables, and their solutions provide topological railway networks maximizing the trip coverage in the presence of a competing mode, both assuming that the network works fine and that links can fail, respectively. Since these problems are computationally intractable for realistic sizes, GRASP heuristics are proposed for finding good feasible solutions. The results obtained in a computational experience indicate that our GRASP algorithms are suitable for railway network design problems. © 2011 Springer Science+Business Media, LLC.

In this paper we introduce and analyze new classes of cooperative games related to facility location models. The players are the customers (demand points) in the location problem and the characteristic value of a coalition is the cost of serving its members. Specifically, the cost in our games is the service diameter of the coalition. We study the existence of core allocations for these games, focusing on network spaces, i.e., finite metric spaces induced by undirected graphs and positive edge lengths.

[EN] The multidimensional assignment (MDA) problem is a combinatorial optimization problem arising in many applications, for instance multitarget tracking (MTT). The objective of an MDA problem of dimension $d\in\Bbb{N}$ is to match groups of $d$ objects in such a way that each measurement is associated with at most one track and each track is associated with at most one measurement from each list, optimizing a certain objective function. It is well known that the MDA problem is NP-hard for $d\geq3$. In this paper five new polynomial time heuristics to solve the MDA problem arising in MTT are presented. They are all based on the semi-greedy approach introduced in earlier research. Experimental results on the accuracy and speed of the proposed algorithms in MTT problems are provided. © 2006 IEEE.

En esta tesis se estudia la posible cooperación en procesos de decisión en los que intervienen varios agentes. Las principales contribuciones de este trabajo son:- Exten sión del concepto de solución de Owen para juegos de producción lineal, superando ciertos problemas de justicia que dicho concepto de solución presenta.- Introducción y estudio de una nueva clase de juegos cooperativos que surge de un problema particular de distribución, juegos de cadenas de abastecimiento.- Introducción y estudio de una nueva clase de juegos cooperativos, juegos de diámetro, sobre grafos tipo árbol. Se estudian sus propiedades y el cálculo de reglas de reparto de forma eficiente.- Introducción de los juegos de asignación multidimensional, una extensión de los clásicos juegos de asignación. Se estudian sus propiedades y se combina el uso de algoritmos de aproximación con la búsqueda de buenas reglas de reparto.