Search

25th International Conference on Urban Transport and the Environment, Urban Transport 2019; Aveiro; Portugal; 25 June 2019 through 27 June 2019; Code 155807 In recent years, the growth of fossil fuel use and greenhouse gases emissions (GHGs) has been promoted by the population increase and development of the industry sector. Due to the increasing attention towards the effects of climate changes on quality of life, recent researches on pollutant formation processes have been developed in different sectors, especially in transportation. The last emission standards on pollutants impose limits on the dimensions and on the particle number of the particulate matter emissions, because of the highly dangerous effect on human health. To fight high concentrations of particulate matter (PM) emissions, a wide number of studies are addressed towards the definition of the most important parameters in effective production of particulate matter, especially in spark ignition engines. Physical processes such as mixture formation, engine operating parameters and fuel chemical properties strongly affect the soot formation in gasoline engines. The heat transfer process between the piston hot surface and the fuel gasoline during the post-injection phase is a key aspect of soot emissions for an engine. This paper is devoted to analyzing the fundamental parameters that are responsible for pollutant formation in the transport sector and the actual experimental and numerical techniques used to predict the environmental impact of engines.

In many transit systems, operators use skip–stop strategies to reduce travel time of particular train services by not stopping (skipping) at less densely populated stations. This decision of omitting some stops reduces the travel time for the users within the vehicle and increases the speed of operation, favouring the provision of new transit services where are more necessary. In this work, the best A/B stop–skip patterns for a set of transit services along a railway corridor are determined by means a three-phase methodology that includes the formulation of a nonlinear integer programming inspired in the multiple knapsack problem and the application of a heuristic algorithm based on mathematical properties (matheuristic). Ministerio de Economía y Competitividad MTM2015-67706-P Ministerio de Economía y Competitividad MTM2016-74983-C2-1-R

Railway systems in metropolitan areas support a high density of daily traffic that is exposed to different types of disturbances in the service. An interesting topic in the literature is to obtain action protocols in the presence of contingencies which can affect the system operation, avoiding the propagation of perturbation and minimizing its negative consequences. Assume that, with a small margin of time (e.g. one day), the decision-maker of the transportation network is knowing that a part of the train fleet will become inoperative temporarily along a specific transit line and none additional vehicle will be able to restore the affected services. The decision to be taken in consequence will require to reschedule the existing services by possibly reducing the number of expeditions (line runs). This will affect travellers who regularly use the transit system to get around. Consider that the decision-maker aims to lose the least number of passengers as a consequence of having introduced changes into the transit line. A strategy that could be applied in this context is to remove those line runs which are historically less used by travellers without affecting the remaining services. Another alternative strategy might be to reschedule the timetables of the available units, taking into account the pattern of arrivals of users to the boarding stations and the user behavior during waiting times (announced in situ). The aim of this work consists of assessing the strategy of train rescheduling along the current transportation line when the supply must be reduced in order to reinforce the service of another line, exploited by the same public operator, which has suffered an incidence or emergency. Ministerio de Economía y Competitividad Fondo Europeo de Desarrollo Regional

In this paper we consider a trip covering location model in a mixed planar-network space. An embed- ded network in the plane represents an alternative transportation system in which traveling is fasterthan traveling within the plane. We assume that the demand to be covered is given by a set of origin- destination pairs in the plane, with some traffic between them. An origin-destination pair is covered bytwo facility points on the network (or transfer points), if the travel time from the origin to destinationby using the network through such points is not higher than a given acceptance level related to the traveltime without using the network. The facility location problems studied in this work consist of locatingone or two transfer points on the network such that, under several objective functions, the traffic throughthe network is maximized. Due to the continuous nature of these problems, a general approach is pro- posed for discretizing them. Since the non-convexity of the distance function on cyclic networks alsoimplies the absence of convexity of the mixed distance function, such an approach is based on a decom- position process which leads to a collection of subproblems whose solution set can be found by adaptingthe general strategy to each problem considered. Ministerio de Economía y Competitividad MTM2012-37048 Ministerio de Economía y Competitividad MTM2015-67706-P Junta de Andalucía P10-FQM-5849

Los autores exponen los cambios metodológicos que implica la nueva definición de crédito establecida por el RD 1125/2003, como consecuencia del proceso de adaptación al EEES. El grupo de noveles expone la experiencia desarrollada en las asignaturas "Derecho Financiero I" y "Fiscalidad Internacional", señalando los resultados obtenidos, así como las ventajas y dificultades del nuevo sistema. Las nuevas técnicas se concentraron en el análisis de la jurisprudencia constitucional, la resolución de casos prácticos, el establecimiento de un programa de tutorías que resultara atractivo a los alumnos y la implantación de las nuevas tecnologías (página web del Departamento, lista de distribución de correo electrónico y tutorías online) The authors explain the changes in the teaching methodology that imply the new concept of credit included in the RD 1125/2003, approved to adapt the Spanish regulation to the European Higher Education Area. The lerner lectures group describes its pilot experience in the subjects "Tax Law I" and "International Tax Law", and exposes the results, the advantages and the problems of the new system. The group has tested with the students the analysis os the constitutional jurisprudence and cases, an attractive program of supervision and monitoring, and the use of new technologies (the creation of a site web and a mailing list, and the online tutorship)

The problem of coordinating transfers consists of determining timetables which ensure the transfer of passengers between trains from different line runs at interchange stations. Two strategies can be considered: (1) Forcing the line runs to be synchronized; that is, a solution can be accepted only if there exists a connection between them, while the goal is minimizing travel times for passengers by using the minimum number of vehicles needed. (2) Minimizing an objective function that penalizes the lack of synchronization between line runs. The problem of transfer coordination turns out to be NP-hard even in the simple case of periodic timetables. Therefore, the problem is usually treated sequentially in two stages: first, determine the frequency of service according to the rate of demand, and then solve the problem of coordination by means of heuristics. This chapter considers a transit line where a train fleet circulates and stops at the stations according to a predetermined timetable which is known by the users. At any instant, passengers arrive at different stations in order to board these vehicles according to an assumed deterministic model of arrivals. In this scenario, a service rescheduling forced by an incidence is determined in order to minimize the loss of passengers who require transfers between different lines at the interchange stations. A case study consisting of a railway line with several equi-spaced stations, where it is possible a connection to other lines at intermediate stations is analyzed for different scenarios where the loss of transfers is penalized. Ministerio de Economía y Competitividad MTM2010-19576-C02-01 Ministerio de Economía y Competitividad MTM2012-37048 Junta de Andalucía P09-TEP-5022 Junta de Andalucía FQM-5849 Junta de Andalucía P10-FQM-5849

In this paper we consider a set of origin-destination pairs in a mixed model in which a network embedded in the plane represents an alternative high-speed transportation system, and study a trip covering problem which consists on locating two points in the network which maximize the number of covered pairs, that is, the number of pairs which use the network by acceding and exiting through such points. To deal with the absence of convexity of this mixed distance function we propose a decomposition method based on formulating a collection of subproblems and solving each of them via discretization of the solution set. Ministerio de Educación, Ciencia e Innovación MTM2009-14243 Ministerio de Economía y Competitividad MTM2012-37048 Junta de Andalucía P09-TEP-5022 Junta de Andalucía P10-FQM-5849

In this paper, the concept of the ordered weighted averaging operator is applied to define a model which unifies and generalizes several inequality measures. For a location x, the value of the new objective function is the ordered weighted average of the absolute deviations from the average distance from the facilities to the location x. Several kinds of networks are studied: cyclic, tree and path networks and, for each of them, the properties of the objective function are analyzed in order to identify a finite dominating set for optimal locations. Polynomial-time algorithms are proposed for these problems, and the corresponding complexity is discussed. Future and Emerging Technologies Unit (European Commission) Ministerio de Educación y Ciencia

A waste pipeline, considered as an undesirable facility, is to be located in a coastal region. Two criteria are taken into account, the Euclidean distance from a given set of protected areas (coral reefs and sandbanks) and a utility function related to the pipe length, both to be maximized. The paper describes a methodology to obtain an efficient set of points where the extreme of a marine pipeline should be located. Since the formulation of the model is based on the zone Voronoi diagram, the computational complexity of the solving procedure is low.

En este trabajo se presenta un procedimiento heurístico GRASP para el problema del diseño de redes rápidas de transito (Rapid Transit Network Design Problem, RTNDP). El problema RTNDP consiste en determinar las líneas y la localización en ella de las estaciones de una red de tránsito rápido. Para establecer el diseño óptimo se tienen en cuenta algunos criterios relevantes como el coste de la inversión necesaria o el uso futuro de la red. Las alternativas se analizan a partir de la demanda de trayectos, de la distribución de trayetos, de los modelos de elección de los usuarios y del equilibrio del trá co. La metaheurística GRASP proporciona las pautas para diseñar un proceso constructivo adaptativo para obtener las líneas que forman la red. La heurística es contrastada frente a la aplicación de un optimizador comercial basado en su formulación como un problema de programación lineal entera Ministerio de Educación y Ciencia BFM2003-04062/MATE Ministerio de Fomento 2003/1360

Extensive facility location models on graphs deal with the location of a special type of subgraphs such as paths, trees or cycles and can be considered as extensions of classical point location models. Variance is one of the measures applied in models in which some equality requirement is imposed. In this paper the problem of locating a minimum variance path in a tree network is addressed, and an O(n2 log n) time algorithm is proposed. Ministerio de Ciencia y Tecnología BFM2000-1052-C02-01

The Rapid Transit System Network Design Problem consists of two intertwined location problems: the determination of alignments and that of the stations. The underlying space, a network or a region of the plane, mainly depends on the place in which the system is being constructed, at grade or elevated, or underground, respectively. For solving the problem some relevant criteria, among them cost and future utilisation, are applied. Urban planners and engineering consulting usually select a small number of corridors to be combined and then analysed. The way of selecting and comparing these alternatives is performed by the application of the four-stage transit planning model. Due to the complexity of the overall problem, during last ten years some efforts have been dedicated to modelling some aspects as optimisation problems and to provide Operations Research methods for solving them. This approach leads to the consideration of a higher number of candidates than that of the classic corridor analysis. The main aim of this paper is to integrate the steps of the transit planning model (trip attraction and generation, trip distribution, mode choice and traffic equilibrium) into an optimisation process. Ministerio de Ciencia y Tecnología BFM2003-04062/MATE Ministerio de Fomento 2003/1360

The k-Centrum problem consists in finding a point that minimises the sum of the distances to the k farthest points out of a set of given points. It encloses as particular cases to two of the most known problems in Location Analysis: the center, also named as the minimum enclosing circle, and the median. In this paper the k-Centrum criteria is applied to obtaining a straight line-shaped facility. A reduced finite dominant set is determined and an algorithm with lower complexity than the previous one obtained. Ministerio de Ciencia y Tecnología

Ministerio de Ciencia y Tecnología

Most location problems on networks consider discrete nodal demand. However, for many problems, demands are better represented by continuous functions along the edges, in addition to nodal demands. Several papers consider the optimal location problem of one or more facilities when demands are continuously distributed along the network, and the objective function dealt with is the median one. Nevertheless, in location of public services it is desirable to use an equity criterion. One of the latter is variance of distance distribution which has been studied only for discrete nodal demands. In this paper the variance problem has been generalized to the case where one allows the demand to arise discretely on the nodes as well as continuously along the edges. Properties and behaviour of the objective function are studied. Likewise we present an exact algorithm for solving this problem in a network, which reduces the complexity of the exhaustive procedure. Spanish Research Council (DGICYT)

A central question when planning rapid transit systems is the determination of alignments and stations. Operational research methods can help solve these problems and they are also useful for the assessment of the network characteristics. This survey article reviews the main available methods. Canadian Natural Sciences and Engineering Research Council OGP0039682 Ministerio de Educación y Ciencia PB-95-1237-C03-01

El problema de diseño de redes de tránsito rápido (metros, cercanías, autobuses en plataforma reservada y cerrada, etc) consiste en, conocida una demanda de movilidad en una zona urbana o metropolitana, determinar las estaciones y las conexiones entre las mismas. El tema suele ser muy complejo, ya que intervienen distintos especialistas (ingenieros, economistas, geólogos, etc.), autoridades y grupos sociales. Los distintos agentes que intervienen en la planificación se pueden agrupar en tres categorías: agencias de transporte, usuarios y empresas (constructoras y explotadoras). Esta gama de agentes a menudo implica la necesidad de tener en cuenta distintos criterios que deben coexistir dentro de un mismo proyecto. Las expectativas son distintas: así como las autoridades representadas por las agencias de transporte desean que la utilidad de las redes sea lo más amplia posible, los usuarios buscan minimizar el tiempo dedicado al viaje, y las empresas tienen como prioridad la optimización de costes de construcción y de operación para maximizar sus beneficios. El método empleado por las constructoras para localizar el trazado de una línea de tránsito rápido consiste en determinar corredores por los que circula el tráfico, unirlos y considerar un pequeño número de alternativas para posteriormente compararlas desde distintos puntos de vista. Los modelos de programación matemática permiten considerar un gran número de opciones y, en particular, algunas que no reproducen los patrones de movilidad existentes pero que resultan ventajosos a los usuarios. En el diseño de redes de metro hay que tener en cuenta que el modo de transito rápido va a competir con otros modos de transporte como son los medios privados y públicos. Normalmente, el usuario escoge el medio que le reporte mayor utilidad, dentro de la cual se pueden considerar distintos atributos: el precio, la seguridad o el confort. No obstante, debido a que el usuario suele realizar el mismo viaje diario, el más importante suele ser el tiempo de recorrido. Por tanto, los problemas de diseño de redes de tránsito rápido son muy complejos al intervenir tanto distintos agentes como la conducta de los usuarios, dando lugar a problemas NP-duros desde el punto de vista computacional. Por otra parte, la construcción de líneas de metro supone un coste muy elevado y no siempre es posible satisfacer completamente la demanda por lo que, incluso recién inauguradas, sufren la congestión y el amontonamiento de pasajeros. Los modelos matemáticos considerados hasta el momento asumen la competencia con otros modos de transporte en condiciones de no congestión. De hecho, la demanda real captada puede variar al degradarse la utilidad de los posibles usuarios debido a la congestión. En este sentido, se pueden clasificar en cuatro grupos los motivos de degradación de la utilidad esperada: i) congestión y amontonamiento en los accesos o en los andenes ii) espera de un segundo, tercer o sucesivos trenes iii) tiempos de parada en las estaciones mayores que los nominales debido a la gran afluencia de viajeros iv) sobreocupación en los vagones. Los efectos de estos motivos suelen aparecer en horas punta, con ocasión de eventos especiales, y cuando ocurren perturbaciones a la operativa nominal. Por otra parte, el intervalo entre dos trenes consecutivos y el tamaño de estos tiene una cota inferior (dos o tres minutos en el mejor de los casos, y de seis a diez vagones), por lo que las condiciones técnicas no permiten una ampliación de la capacidad por hora de la línea. Sin embargo, puede ser interesante, a la hora de realizar un análisis coste/beneficio, efectuar un estudio de la sensibilidad sobre la pérdida de usuarios respecto a la variación en la frecuencia. En áreas metropolitanas densamente pobladas, los estudios empíricos han determinado que la sobreocupación dentro de los vehículos de tránsito ha empeorado cada vez más en los últimos años. El hacinamiento crónico dentro de los vehículos no sólo es causado por la falta de infraestructura física, sino también por la provisión inadecuada de servicios o por una planificación basada en un modelo matemático inadecuado. 2 En este trabajo se va a considerar el problema de la localización del trazado de una línea de tránsito rápido que maximice el número de viajes captados, teniendo en cuenta los distintos efectos de la sobreocupación. A la hora de diseñar la localización de la línea, se van a tener en cuenta los condicionantes anteriormente descritos. El principal objetivo de un sistema de tránsito rápido es mejorar la movilidad de la población. Idealmente, una red debe estar diseñada para proporcionar tiempos de viaje cortos a un elevado número de pasajeros, respetando restricciones técnicas, legislativas y presupuestarias. Para ello, se van a introducir funciones que modelen cada uno de esos efectos. El modelado se va a efectuar mediante programación matemática entera mixta y, dada la complejidad computacional, se realizará una experiencia numérica de tamaño pequeño. The design problem for rapid transit networks (metros, commuter trains, buses on a reserved and closed platform, etc.) consists of knowing a demand for mobility in an urban or metropolitan area, determining the stations and the connections between them. The issue is usually very complex, since different specialists (engineers, economists, geologists, etc.), authorities and social groups are involved. The different agents involved in planning can be grouped into three categories: transport agencies, users and companies (builders and operators). This range of agents often implies the need to take into account different criteria that must coexist within the same project. The expectations are different: just as the authorities represented by the transport agencies want the usefulness of the networks to be as wide as possible, the users seek to minimize the time spent on the journey, and the companies have the optimization of construction and operating costs as a priority to maximize the profits. The method used by construction companies to locate the layout of a rapid transit line consists of determining corridors through which traffic circulates, joining them and considering a small number of alternatives to later compare them from different points of view. Mathematical programming models allow us to consider a large number of options and, in particular, some that do not reproduce existing mobility patterns but are advantageous to users. In the design of metro networks, it must be taken into account that the rapid transit methods will compete with other modes of transportation such as private and public means. Normally, the user chooses the mode that provides the greatest utility, within which different attributes can be considered: price, safety or comfort. However, since the user usually makes the same daily trip, the most important is usually the travel time. Therefore, rapid transit network design problems are very complex, as different agents and user behavior intervene, giving rise to NP-hard models from the computational point of view. On the other hand, the construction of metro lines entails a very high cost and it is not always possible to fully satisfy the demand, which is why, even just inaugurated, they suffer from congestion and overcrowding of passengers. The models considered so far assume competition with other transportation modes under non-congested conditions. In fact, the real demand captured can vary as the usefulness of potential users is degraded due to congestion. In this sense, the reasons for the degradation of the expected utility can be classified into four groups: i) congestion and crowding at the entrances or on the platforms ii) waiting for a second, third or successive trains iii) stop times at the stations greater than nominal due to the large flow of travelers iv) overcrowding in wagons. The effects of these reasons usually appear at peak times, on the occasion of special events, and when disturbances to nominal operations occur. On the other hand, the interval between two consecutive trains and the size of these has a lower limit (two or three minutes in the best of cases, and from six to ten wagons), so the technical conditions do not allow an extension of the hourly capacity of the line. However, it may be interesting, when carrying out a cost/benefit analysis, to carry out a study of the sensitivity of the loss of users with respect to the variation in frequency. In densely populated metropolitan areas, empirical studies have found that overcrowding within transit vehicles has gotten worse in recent years. Chronic overcrowding inside vehicles is not only caused by the lack of physical infrastructure, but also by the inadequate provision of services or by planning based on an inadequate mathematical model. In this work, the problem of locating the layout of a rapid transit line that maximizes the number of trips captured, taking into account the different effects of overcrowding, will be considered. When designing the location of the line, the conditions described above will be taken into account. The 4 main objective of a rapid transit system is to improve the mobility of the population. Ideally, a network should be designed to provide short travel times to a high number of passengers, while respecting technical, legislative and budgetary constraints. To do this, functions that model each of these effects will be introduced. The modeling will be done through integer or mixed-integer mathematical programming and, given the computational complexity, a small numerical experiment will be carried out. Universidad de Sevilla. Doble Máster en MAES-Máster Universitario en Matemáticas (MAES-MUM)

La aparición del Covid-19 en nuestras vidas ha influido en todos los ámbitos de nuestro quehacer diario, como el trabajo, estudios, ocio, viajes, movilidad, etc. La demanda en el metro de Sevilla ha variado durante y después de la pandemia a causa del Covid-19, respecto a la que ya existía antes, en el periodo pre-pandemia. En la primera parte del trabajo presento una introducción donde detallo las características demográficas de la ciudad y de su metro, además de una breve presentación de las fórmulas más usadas para la previsión de demanda y el reparto modal. En la segunda expongo todo lo relacionado con la demanda del metro el año anterior al Covid, es decir, el 2019. Se comentan y analizan aspectos como la demanda, viajeros por estación, porcentaje de ocupación en horas punta, etc. En la tercera se comenta cómo la pandemia ha afectado a la demanda del metro en este último año, además de un pequeño análisis de la evolución que ha tenido y que tendrá en los próximos años. En la penúltima parte se muestran los distintos factores que afectan a la demanda y un análisis de cómo han cambiado respecto a años anteriores a causa del virus. Finalmente, se plantean las hipótesis y el modelo de utilidad esperada el cual está considerado como el más exacto para este tipo de estudio, con las variaciones como consecuencia de la pandemia Covid-19. The appearance of Covid-19 in our lives has influenced all areas of our daily work, such as work, studies, leisure, travel, mobility, etc. The demand in the Seville metro has varied during and after the pandemic caused by Covid-19, compared to what already existed before, in the pre-pandemic period. In the first part of the work, I present an introduction where I detail the demographic characteristics of the city and its metro, as well as a brief presentation of the most used formulas for demand forecasting and modal split. In the second I present everything related to the demand for the subway the year before the Covid, that is, 2019. Aspects such as demand, passengers per station, percentage of occupancy at peak hours, etc are discussed and analyzed. The third section contains a discussion on how the pandemic has affected the demand for the subway in the last year, in addition to a small analysis of the evolution that it has had and that it will have in the coming years. The penultimate part shows the different factors that affect demand and an analysis of how they have changed compared to previous years due to the virus. Finally, the hypotheses and the expected utility model are raised, which is considered the most accurate for this type of study, with variations as a consequence of the Covid-19 pandemic. Universidad de Sevilla. Grado en Ingeniería de Tecnologías Industriales

During last decades, it has been taken an interest in the modeling of complex systems that could not be represented by classical graph theory. Such systems are characterized by a structure that cannot be reduced or simplified to a simple network, even by projection, without loss of information. This would be the case, for example, of the transportation network that is established in a certain city, where different means of transport (metro, bus, tram, ...) can coexist with different natures. There are many complex representation models, but in this paper we are going to focus on multilayer graphs. A multilayer graph is a pairM = (G, C) where G = fGa; a 2 Mg (with M = f1, . . . ,mg being the layer’s index subset of M) is a family of (directed or undirected, weighted or unweighted) graphs Ga = (Va, Ea), called layers ofM, and C = fEab Va Vb; a, b 2 M, a 6= bg is the set of interconnections between nodes of different layers Ga y Gb with a 6= b. In this structure we will study two types of location problems. On the one hand, we will see the network design problems where we have origin-destination demand pairs we must satisfy according to different imposed and objective conditions. We will provide a formulation of the three possibly most studied location problems: the Median Problem, the Center Problem and the Coverage Problem. On the other hand, we will see the point location problems, where we are not going to have origin-destination pairs to satisfy, but we will consider different objectives taking into account the nodes of the network, without distinguishing whether a node is the origin or the destination of a pair or not. In both types, we will see how beyond the most basic cases of the problem, the multilayer structure is required. Thus, it is not possible to make a projection of the multilayer network to transform it into a graph with the classic topology where to solve it, but a different topology of the problem is required. Durante las últimas décadas, se ha puesto un especial interés en el modelado de sistemas complejos que no han podido ser representados mediante la teoría de grafos clásica. Dichos sistemas se caracterizan por tener una estructura que no puede ser reducida o simplificada a un grafo simple, ni siquiera mediante una proyección, sin que eso conlleve pérdida de información. Éste sería el caso, por ejemplo, de la red de transporte que está establecida en una cierta ciudad, donde pueden coexistir distintos medios de transporte (metro, autobús, tranvía, ...) con distintas naturalezas. Existen multitud de sistemas complejos, pero en el presente trabajo vamos a centrarnos en los grafos multicapa. Una red multicapa es un par M = (G, C) donde G = fGa; a 2 Mg (con M = f1, . . . ,mg el conjunto de indices de las capas de M) es una familia de grafos (dirigidos o no, ponderados o no) Ga = (Va, Ea), llamados las capas deM, siendo C = fEab Va Vb; a, b 2 M, a 6= bg el conjunto de interconexiones entre nodos de diferentes capas Ga y Gb con a 6= b. En esta estructura estudiaremos dos tipo de problemas de localización. Por un lado, veremos los problemas de diseño de redes en los que tenemos pares origen-destino que debemos satisfacer atendiendo a diferentes condiciones impuestas y objetivos. Proporcionaremos una formulación de los tres problemas de localización posiblemente más estudiados: el Problema de la mediana, el del centro y el de cobertura. Por otro lado, veremos los problemas puntuales de localización, en los que ya no habra pares origen-destino que satisfacer, sino que consideraremos diferentes objetivos teniendo en cuenta los nodos del grafo, sin distinguir si un nodo es origen o destino de algún par. Tanto de un tipo como de otro, veremos como más allá de los casos más básicos del problema, se requiere de la estructura multicapa, no pudiéndose realizar una proyección del grafo multicapa para transformarlo en un grafo unicapa, donde resolverlo, sino requeriendo una topología del problema diferente. Universidad de Sevilla. Doble Máster en Profesorado de Educación Secundaria Obligatoria y Bachillerato, Formación Profesional y Enseñanzas de Idiomas y Máster Universitario en Matemáticas

En esta tesis se analiza, en primer lugar, el problema de localización de un servicio sobre alguno de los vértices de una red general. También se implementa un algoritmo que ha sido utilizado para llevar a cabo una amplia comparación empírica entre trece medidas de igualdad y la mediana, que ha permitido agruparlas en función de los valores de cuatro indicadores. A continuación, se ha estudiado el comportamiento de las funciones "Coeficiente de Variación" e "Índice de Schutz" cuando se emplean como criterios para la localización de un servicio sobre un punto cualquiera de una red general, proporcionando sendos algoritmos. Se prosigue con un amplio estudio comparativo de los criterios "Varianza", "Desviación Absoluta Media", "Coeficiente de Variación" e "Índice de Schutz", que viene a confirmar la estrecha relación entre las medidas absolutas y las medidas relativas y que suministra unos índices que pueden ayudar a la hora de tomar decisiones sobre el empleo de unos u otros criterios. El comportamiento de la "Función Desviación Absoluta Media" para la localización de p servicios se analiza sobre una red general, y se demuestra que es NP-duro, proporcionado un algortimo para el caso p=2. Finalmente, se han estudiado las funciones "Varianza" y "Coeficiente de Variación" para la localización de caminos con extremos libres sobre redes árbol, proporcionando e implementando algoritmos para su obtención. Asimismo, se han obtenido, para el criterio de minimizar la varianza, relaciones entre el problema de localización puntual y el problema de localización de servicios extensos tipo camino.

This dissertation studies in depth the structure of the Discrete Ordered Median Problem (DOMP), to define new formulations and resolution algorithms. Furthermore we analyze an interesting extension for DOMP, namely MDOMP (Monotone Discrete Ordered Median Problem). This thesis is structured in three main parts.First, a widely theoretical and computational study is reported. It presents several new formulations for the Discrete Ordered Median Problem (DOMP) based on its similarity with some scheduling problems. Some of the new formulations present a considerably smaller number of constraints to define the problem with respect to some previously known formulations. Furthermore, the lower bounds provided by their linear relaxations improve the ones obtained with previous formulations in the literature even when strengthening is not applied. We also present a polyhedral study of the assignment polytope of our tightest formulation showing its proximity to the convex hull of the integer solutions of the problem. Several resolution approaches, among which we mention a branch and cut algorithm, are compared. Extensive computational results on two families of instances, namely randomly generated and from Beasley's OR-library, show the power of our methods for solving DOMP. One of the achievements of the new formulation consists in its tighter LP-bound. Secondly, DOMP is addressed with a new set partitioning formulation using an exponential number of variables. This chapter develops a new formulation in which each variable corresponds to a set of demand points allocated to the same facility with the information of the sorting position of their corresponding distances. We use a column generation approach to solve the continuous relaxation of this model. Then, we apply a branch-cut-and-price algorithm to solve to optimality small to moderate size of DOMP in competitive computational time.To finish, the third contribution of this dissertation is to analyze and compare formulations for the monotone discrete ordered median problem. These formulations combine different ways to represent ordered weighted averages of elements by using linear programs together with the p-median polytope. This approach gives rise to two efficient formulations for DOMP under a hypothesis of monotonicity in the lambda vectors. These formulations are theoretically compared and also compared with some other formulations valid for the case of general lambda vector. In addition, it is also developed another new formulation, for the general case, that exploits the efficiency of the rationale of monotonicity. This representation allows to solve very efficiently some DOMP instances where the monotonicity is only slightly lost. Detailed computational tests on all these formulations is reported in the dissertation. They show that specialized formulations allow to solve to optimality instances with sizes that are far beyond the limits of those that can solve in the general case., Cette dissertation étudie en profondeur la structure du "Discrete Ordered Median Problem" (DOMP), afin de proposer de nouvelles formulations et de nouveaux algorithmes de résolution. De plus, une extension intéressante du DOMP nommée MDOMP ("Monotone Discrete Ordered Median Problem") a été étudiée.Cette thèse a été structurée en trois grandes parties.La première partie présente une étude riche aux niveaux théorique et expérimentale. Elle développe plusieurs formulations pour le DOMP qui sont basées sur des problèmes d'ordonnancement largement étudiés dans la littérature. Plusieurs d'entres elles nécessitent un nombre réduit de contraintes pour définir le problème en ce qui concerne certaines formulations connues antérieurement. Les bornes inférieures, qui sont obtenues par la résolution de la relaxation linéaire, donnent de meilleurs résultats que les formulations précédentes et ceci même avec tout processus de renforcement désactivé. S'ensuit une étude du polyhèdre de notre formulation la plus forte qui montre sa proximité entre l'enveloppe convexe des solutions entières de notre problème. Un algorithme de branch and cut et d'autres méthodes de résolution sont ensuite comparés. Les expérimentations qui montrent la puissance de nos méthodes s'appuient sur deux grandes familles d'instances. Les premières sont générées aléatoirement et les secondes proviennent de Beasley's OR-library. Ces expérimentations mettent en valeur la qualité de la borne obtenue par notre formulation.La seconde partie propose une formulation "set partitioning" avec un nombre exponentiel de variables. Dans ce chapitre, la formulation comporte des variables associées à un ensemble de demandes affectées à la même facilité selon l'ordre établi sur leurs distances correspondantes. Nous avons alors développé un algorithme de génération de colonnes pour la résolution de la relaxation continue de notre modèle mathématique. Cet algorithme est ensuite déployé au sein d'un Branch-and-Cut-and-Price afin de résoudre des instances de petites et moyennes tailles avec des temps compétitifs.La troisième partie présente l'analyse et la comparaison des différentes formulations du problème DOMP Monotone. Ces formulations combinent plusieurs manières de formuler l'ordre des éléments selon les moyennes pondérées en utilisant plusieurs programmes linéaires du polytope du p-median. Cette approche donne lieu à deux formulations performantes du DOMP sous l'hypothèse de monotonie des vecteurs lambda. Ces formulations sont comparées de manière théorique puis comparées à d'autres formulations valides pour le cas général du vecteur lambda. Une autre formulation est également proposée, elle exploite l'efficacité du caractère rationnel de la monotonie. Cette dernière permet de résoudre efficacement quelques instances où la monotonie a légèrement disparue. Ces formulations ont fait l'objet de plusieurs expérimentations dècrites dans ce manuscrit de thèse. Elles montrent que les formulations spécifiques permettent de résoudre des instances plus importantes que pour le cas général., Este trabajo estudia en profundidad la estructura del problema disctreto de la mediana ordenada (DOMP, por su acrónimo en inglés) con el objetivo de definir nuevas formulaciones y algoritmos de resolución. Además, analizamos una interesante extensión del DOMP conocida como el problema monótono discreto de la mediana ordenada (MDOMP, de su acrónimo en inglés).Esta tesis se compone de tres grandes bloques.En primer lugar, se desarrolla un detallado estudio teórico y computacional. Se presentan varias formulaciones nuevas para el problema discreto de la mediana ordenada (DOMP) basadas en su similaridad con algunos problemas de secuenciación. Algunas de estas formulaciones requieren de un cosiderable menor número de restricciones para definir el problema respecto a algunas de las formulaciones previamente conocidas. Además, las cotas inferiores proporcionadas por las relajaciones lineales mejoran a las obtenidas con formulaciones previas de la literatura incluso sin reforzar la nueva formulación. También presentamos un estudio poliédrico del politopo de asignación de nuestra formulación más compacta mostrando su proximidad con la envolvente convexa de las soluciones enteras del problema. Se comparan algunos procedimientos de resolución, entre los que destacamos un algoritmo de ramificación y corte. Amplios resultados computacionales sobre dos familias de instancias -aleatoriamente generadas y utilizando la Beasley's OR-library- muestran la potencia de nuestros métodos para resolver el DOMP.En el segundo bloque, el problema discreto de la mediana ordenada es abordado con una formulación de particiones de conjuntos empleando un número exponencial de variables. Este capítulo desarrolla una nueva formulación en la que cada variable corresponde a un conjunto de puntos de demanda asignados al mismo servidor con la información de la posición obtenida de ordenar las distancias correspondientes. Utilizamos generación de columnas para resolver la relajación continua del modelo. Después, empleamos un algoritmo de ramificación, acotación y "pricing" para resolver a optimalidad tamaños moderados del DOMP en un tiempo computacional competitivo.Por último, el tercer bloque de este trabajo se dedica a analizar y comparar formulaciones para el problema monótono discreto de la mediana ordenada. Estas formulaciones combinan diferentes maneras de representar medidas de pesos ordenados de elementos utilizando programación lineal junto con el politopo de la $p$-mediana. Este enfoque da lugar a dos formulaciones eficientes para el DOMP bajo la hipótesis de monotonía en su vector $lambda$. Se comparan teóricamente las formulaciones entre sí y frente a algunas de las formulaciones válidas para el caso general. Adicionalmente, se desarrolla otra formulación válida para el caso general que explota la eficiencia de las ideas de la monotonicidad. Esta representación permite resolver eficientemente algunos ejemplos donde la monotonía se pierde ligeramente. Finalmente, llevamos a cabo un detallado estudio computacional, en el que se aprecia que las formulaciones ad hoc permiten resolver a optimalidad ejemplos cuyo tamaño supera los límites marcados en al caso general., Doctorat en Sciences, info:eu-repo/semantics/nonPublished

En este trabajo se considera el problema de localizar tanto estaciones bases de telefonía móvil como wifi para proporcionar cobertura a un sistema con una estructura de tipo red. El sistema mallado se representa sobre un plano en el cual se conoce la ubicación de un conjunto de coordenadas que representan los puntos de inicio y final de caminos o carreteras. Estos puntos se codifican mediante dos matrices origen-destino que representan las coordenadas en los ejes cartesianos del plano y generan una red de segmentos en los que existe una demanda de servicios telefónicos. A partir de esta demanda de servicios el operador le asigna una prioridad dentro del sistema. El objetivo del trabajo es la implementación en MATLAB de un algoritmo heurístico que localice un conjunto de estaciones base sobre el plano para satisfacer la demanda de servicios. Para ello, se genera un conjunto de puntos de forma simétrica que cubra el área del plano, puntos que servirán de lugares potenciales para la instalación de antenas. El algoritmo consiste en fijar las antenas a colocar, de forma secuencial buscando maximizar la cobertura proporcionada por las antenas. Este algoritmo tiene en cuenta el solapamiento entre las áreas de cobertura de las antenas y proporciona a la operadora flexibilidad al respecto. Permite decidir si se incentiva o penaliza el solapamiento mediante la asignación de pesos a los diferentes tipos de cobertura, diferenciando entre cobertura simple, doble o triple, que corresponden a la cobertura proporcionada por una, dos y tres o más antenas respectivamente. Este modelo no tiene en cuenta el entorno, puesto que el alcance o cobertura que proporciona una antena depende de los obstáculos que estén entre el teléfono y la antena, la altura de esta, las interferencias, reflexiones...etc. Además de la posibilidad de que no se pueda instalar una antena en el lugar donde nos indique el programa debido a licencias, permiso de los propietarios del terreno o que la compensación económica al colocar una antena en ese lugar, bien a los dueños del terreno o a quienes se vean afectados por la instalación sea demasiado elevada. Por ello, aunque este algoritmo proporciona una buena primera aproximación al problema, será necesario un estudio posterior sobre la viabilidad de la instalación de las antenas en los lugares propuestos. This paper considers the problem of locating both mobile base stations and Wi-Fi routers to provide coverage to a system with a network-like structure. The system is represented on a plane in which the location of a set of coordinates that represent the points of start and end of roads or highways are known. These points are encoded by two origin-destination matrices that represent Cartesian coordinates in the plane and generate a network of segments in which there is a demand for telephone services. Then the operator assigns a priority to each segment based on their demands. The aim of this work is the implementation in MATLAB of a heuristic algorithm to locate a set of base stations on the plane to supply the demand for services. To do this, a set of points are located covering the total area of the plane, this points serve as potential sites for the installation of antennas. The algorithm fix the antennas to be placed and then sequentially seeks to maximize the coverage provided for each one. This algorithm takes into account the overlap between the coverage areas of the antennas and provides the operator flexibility about it. It allows decide whether incentives or penalizes overlap by assigning weights to the different types of coverage, differentiating between single coverage, double or triple, corresponding to the coverage provided by one, two and three or more antennas respectively. This model does not considers environment issues, since the scope or coverage provided by an antenna depends on the obstacles that are between the phone and the antenna, the height of the antenna, interference, reflections ... etc. In addition to the possibility that it may can not be installed on where the program tell us to because of licensing, permission from the owners of the land or because the financial compensation to those affected by the installation is too high. Therefore, although this algorithm provides a good first solution to the problem, further study on the feasibility of installing the antennas in the proposed locations will be necessary. Universidad de Sevilla. Grado en Ingeniería de las Tecnologías de Telecomunicación

En este trabajo se considera el problema de localizar estaciones en una red representada mediante un grafo empotrado en el plano euclídeo. Asumiremos que viajar por la red es más rápido que viajar a través del plano de acuerdo a la distancia euclídea. En el plano se conoce la ubicación de un conjunto de puntos, que pueden representar pueblos, ciudades o zonas de transporte, entre los cuales existe una demanda de viaje codificada mediante una matriz origen-destino. Se supone que los viajeros disponen de un medio alternativo y que seleccionan el medio de transporte de acuerdo con el tiempo de viaje. Los viajeros comparan el tiempo de viaje en el modo alternativo con el del modo combinado que utiliza la red de alta velocidad y eligen el de menor tiempo. En este trabajo, de forma genérica, hemos fijado unos tiempos máximos para que el viajero escoja la red de alta velocidad El objetivo del trabajo es localizar dos estaciones sobre la red de forma que se maximize la captura o cobetura total de pares de demanda por parte del modo combinado. Grado en Ingeniería de Tecnologías Industriales

El sector del transporte es un factor clave en una sociedad en evolución continua. El transporte proporciona movilidad de personas y bienes, acceso a empleos, desarrollo y mejora el bienestar de una sociedad. Un transporte eficiente hace accesible regiones aisladas y fácil la vida cotidiana. Inmersos en un mundo de constante evolución es difícil pensar en un futuro sin un transporte eficiente y ecológico. La investigación operativa es una herramienta fundamental en los procesos de planificación del transporte y su gestión. Los problemas que surgen en el contexto del transporte son generalmente descritos y analizados por medio de modelos de programación matemática. Estos problemas son de naturaleza compleja y difíciles de resolver. A través de modelos y métodos matemáticos adecuados, este tipo de problemas puede resolverse en un tiempo razonable. Esta tesis se centra en el desarrollo de modelos matemáticos en el contexto de sistemas de transporte rápido así como en técnicas eficientes para su resolución. Los sistemas de transportes rápidos comprenden sistemas de metro, autobuses con carril especial, metro ligero, monorail, etc. Tradicionalmente, el proceso de planificación de transporte rápido en el contexto de ferrocarriles, se ha descompuesto en una sucesión de etapas: diseño de redes, diseño de líneas, horarios, gestión del material rodante y planificación del personal. Sin embargo, en los últimos años puede observarse una fuerte tendencia a integrar etapas. La integración de varias etapas en los procesos de planificación lleva a sistemas más difíciles de resolver pero de mejores resultados. Así, una de las propuestas de esta tesis es desarrollar un modelo matemático general que integre las etapas de diseño de redes y planificación de líneas. Concretamente, estamos interesados en determinar, simultáneamente la red de infraestructura, la planificación de líneas, la capacidad del tren de cada línea y la inversión de la flota requerida y del personal. Asimismo, incorporamos el procedimiento de asignación de tráfico en el proceso de optimización y un modo de transporte compitiendo con la red que estamos diseñando. También proponemos un algoritmo para resolver este problema a escala real. Otra importante contribución de esta tesis es el tratamiento realista del problema hecho que, en ocasiones, la investigación olvida. Bajo esta perspectiva, presentamos un análisis riguroso para la calibración de todos los aspectos que aparecen como consecuencia de integración de etapas. Por otra parte, en una situación realista, varios datos de entrada como matrices origen-destino, tiempos de viajes y costes, pueden presentar incertidumbre o son desconocidos de antemano, llevando así a sistemas que no se adaptan a la realidad. Por lo tanto, es necesario desarrollar modelos matemáticos robustos y hacer uso de la optimización robusta. En esta tesis hemos estudiado este tipo de problemas teniendo en cuenta la presencia de incertidumbre en los datos de demanda. Otro aspecto innovador a destacar es la aplicación de la teoría de hipergrafos en el campo del transporte. En los últimos años, el estudio de redes complejas ha atraído a muchos investigadores. En particular, el fenómeno "small-world" fue introducido en 1998 por los matemáticos Duncan Watts y Steven Strogatz. Watts y Strogatz mostraron que las redes complejas podían clasificarse por medio de dos medidas conocidas como "coeficiente de agrupación" y "longitud del camino característico". Este tipo de redes son robustas ante ataques intencionados y vulnerables a fallos aleatorios. Sin embargo, más tarde se mostró que estas medidas no son aplicables a ciertas redes. Medidas tales como "eficiencia global y local" fueron introducidas y analizadas para describir este tipo de redes complejas. En esta tesis nos hemos interesado en todas estas medidas así como en medidas de robustez. Como consecuencia de la revisión y adaptación de estas medidas a redes de transportes se han estudiado propiedades de las mismas. Motivados por clasificar las redes de transportes como redes complejas, según la definición propuesta por Watts y Strogatz, hemos ido un paso más, representando, a través de la estructura de hipergrafos, redes de transporte colectivo. Esta estructura permite describir y analizar las redes de transporte desde diferentes niveles de abstracción.

El Capítulo 1 se dedica a la descripción y estimación de distancias de viaje en una red plana. Especial relevancia tiene el concepto de p-sesgo y su aplicación en la noción de preferencia.... 39;Times New Roman','serif'; font-size: 12pt">En el Capítulo 2 se estable la relación entre un calibrador plano y un par de funciones lp y lq, donde p ϵ [1,2) y q ϵ (0,1], encontrándose una expresión algebraica, que asocia los valores de p y q. Se concluye el capítulo con el estudio del error de aproximación. Se comprueba en el capítulo 3 que la relación entre el índicep ϵ [1,2) y el ángulo ɸ(p) se generaliza a RN, obteniéndose las correspondientes fórmulas de aproximación. El Capítulo 4 se dedica a la creación de una metodología de estimación que relaciones regresión cuadrática y aproximación con normas bloque y normas lp. Las muestras se estratificarán para conseguir estimadores parciales que, posteriormente, se mezclarán bajo hipótesis de uniformidad. Una nueva hipótesis sobre la distribución poblacional de los sesgos se efectuará, comprobándose empíricamente su adecuación. En el Capítulo 5 se analiza el problema variacional que da lugar a que el diseño óptimo, para conectar dos puntos mediante poligonales y un solo codo, tenga un desvío de trayectoria de ángulo ɸ(p). Completando el capítulo, se establecen algoritmos para la determinación de redes regulares con sesgos prefijados en la familial p, p ϵ(0,2). Un método exacto que proporciona una solución aproximada al problema de Webwe generalizado se detalla en el capítulo 6 tras analizar el algoritmo de Weiszfeld para normaslp, p ϵ(1,2). Este método, basado en programación lineal, consigue una rápida convergencia hacia la solución óptima en las primeras iteraciones, para después inmovilizarse en un entorno cercano a dicho óptimo.