Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 12
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Revisiting a game theoretic framework for the robust railway network design against intentional attacks

  • Perea Rojas Marcos, Federico
  • Puerto Albandoz, Justo
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., The research activities of the authors have been supported by the projects FQM-5849 (Junta de Andalucia\FEDER) and MTM2010-19576-C02-01 (MICINN, Spain). Special thanks are due to two anonymous referees for their valuable comments and suggestions.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Avoiding unfairness of Owen allocations in linear production processes

  • Perea Rojas Marcos, Federico
  • Puerto Albandoz, Justo
  • Fernández García, Francisco Ramón
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., The authors want to thank the Spanish Ministry of Science and Technology for providing financial support under Grants MTM200767433 and MTM201019576, and the Junta de Andalucia/Feder (Spain) under Grant FQM5849. Special thanks are due to two anonymous referees for their valuable comments and suggestions.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

A cooperative location game based on the 1-center location problem

  • Puerto Albandoz, Justo
  • Tamir, Arie
  • Perea Rojas Marcos, Federico
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., The research of the authors is partially supported by Spanish grants MTM2007-67433, MTM2010-19576-C02-01 and Junta Andalucia/FEDER grant FQM-5849.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

The mixed general routing polyhedron

  • Corberán, Angel
  • Romero Rozalén, Antonio
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In Arc Routing Problems, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the associated polyhedron and some large families of facet-inducing inequalities are described. A preliminary cutting-plane algorithm has produced very good lower bounds over a set of 100 randomly generated instances of the Mixed Rural Postman Problem. Finally, applications of this study to other known routing problems are described., The authors wish to thank the Ministerio de Innovación y Ciencia/FEDER of Spain (projects MTM2009-14039-C06-02, MTM2010-19576-C02-02 and DE2009-0057) and Junta de Andalucía/FEDER (grant number FQM-5849) for its support. They also thank two anonymous referees for their careful reading of the manuscript and for their many suggestions and comments that have helped to improve the contents and readability of the paper.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

A maximum trip covering location problem with an alternative mode of transportation on tree networks and segments

  • Koerner, Mark-Christoph
  • Mesa, Juan A.
  • Perea Rojas Marcos, Federico
  • Schoebel, Anita
  • Scholz, Daniel
[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., This work was partially supported by the Future and Emerging Technologies Unit of EC (IST priority-6th FP), under contract no. FP6-021235-2 (project ARRIVAL), by Ministerio de Educacion, Ciencia e Innovacion (Spain)/FEDER under project MTM2009-14243 and by Junta de Andalucia (Spain)/FEDER under excellence projects P09-TEP-5022 and FQM-5849.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Resolution of an Antenna–Satellite assignment problem by means of Integer Linear Programming

  • Vazquez, Rafael
  • Perea Rojas Marcos, Federico
  • Galán Vioque, Jorge
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., The authors gratefully acknowledge the cooperation of Taitus Software (http://www.taitussoftware.com) and its team, and in particular its founder and CEO (Felipe Martin Crespo), which introduced this problem to us and provided integration with its orbital mechanics visual software SaVoir. We also acknowledge the cooperation of Kongsberg Satellite Services AS (KSAT). Jorge Galan acknowledges financial support through grants MTM2012-31821 and P12-FQM-1658. Federico Perea acknowledges financial support through grants FQM-5849 and P09-TEP-5022 (Junta de Andalucia and FEDER) and MTM2010-19576-C02-01 and MTM2013-46962-C2-1 (MICINN, Spain). Special thanks are due to three anonymous referees for their valuable comments.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

A branch-and-cut algorithm for the maximum benefit Chinese postman problem

  • Corberán, Angel
  • Plana, Isaac
  • Rodríguez-Chía, Antonio Manuel
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] The Maximum Benefit Chinese Postman Problem (MBCPP) is an NP-hard problem that considers several benefits associated with each edge, one for each time the edge is traversed with a service. The objective is to find a closed walk with maximum benefit.We propose an IP formulation for the undirected MBCPP and, based on the description of its associated polyhedron, we propose a branch-and-cut algorithm and present computational results on instances with up to 1,000 vertices and 3,000 edges., The authors wish to thank the Ministerio de Innovacion y Ciencia/FEDER of Spain (projects MTM2009-14039-C06-02, MTM2010-19576-C02-02 and DE2009-0057) and Junta de Andalucia/FEDER (grant number FQM-5849) for its support. They also thank two anonymous referees for their careful reading of the manuscript and for their many suggestions and comments that have helped to improve the contents and readability of the paper.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Cooperative location games based on the minimum diameter spanning Steiner subgraph problem

  • Puerto Albandoz, Justo
  • Tamir, Arie
  • Perea Rojas Marcos, Federico
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 research has been supported by the Spanish Ministry of Science and Innovation under grants MTM200767433 and MTM201019576, and by the Junta de Andalucia (Spain)/FEDER under grant FQM5849. Special thanks are due to two anonymous referees for their valuable comments and suggestions.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Swath-Acquisition Planning in Multiple-Satellite Missions: An Exact and Heuristic Approach

  • Perea Rojas Marcos, Federico
  • Vázquez, Rafael
  • Galán-Vioque, Jorge
[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., JGV acknowledges financial support from grant MTM2012-31821 and P12-FQM-1658, and FP from grants FQM-5849, P09-TEP-5022, and MTM2010-19576-C02-01.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

The Railway Line Frequency and Size Setting Problem

  • De-Los-Santos, Alicia
  • Laporte, Gilbert
  • Mesa, Juan A.
  • Perea Rojas Marcos, Federico
[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., This research was partly funded by the Canadian Natural Sciences and Engineering Research Council under Grant 2015-06189, by the Ministerio de Economía y Competitividad (Spain)/FEDER under projects MTM2012-37048, MTM2015-67706-P and DPI2012-36243-C02-01, and by Junta de Andalucía (Spain)/FEDER under excellence project P10-FQM-5849. Part of this research was done while Federico Perea was enjoying a research visit to CIRRELT, funded by the Universitat Politècnica de València, under program PAID-00-15. This support is gratefully acknowledged. Thanks are due to the referees for their valuable comments.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Finding the nucleolus of any n-person cooperative game by a single linear program

  • Puerto Albandoz, Justo
  • Perea Rojas Marcos, Federico
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, The authors want to thank Javier Arin, Safae El Haj Ben Ali, Guillermo Owen and Johannes H. Reijnierse for their useful and valuable help. The research of the authors has been partially supported by the projects FQM-5849 (Junta de Andalucia \ FEDER), and by the project MTM2010-19576-C02-01 (MICINN, Spain). This paper was written while the second author was enjoying a grant for a short postdoctoral research visit at the Instituto Universitario de Investigacion de Matematicas de la Universidad de Sevilla (IMUS). Special thanks are due to one anonymous referee for his/her valuable comments.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

On minimax and Pareto optimal security payoffs in multicriteria games

  • Puerto Albandoz, Justo
  • Perea Rojas Marcos, Federico
[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., We would like to thank Dr. Francisco R. Fernandez for his useful comments on earlier versions of this paper. The authors also want to acknowledge the financial support from grants FQM-5849 (Junta de Andalucia\FEDER) and MTM2016-74983-C02-01, MTM2013-46962-C02-01 (MICINN, Spain).