Search

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 deñir 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 deñir 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-librarymuestran 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 _. Se comparan tepó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.

Falta palabras clave Esta tesis presenta el estudio de dos familias de coeficientes: los coeficientes del pletismo y los coeficientes de Kronecker. Ambas familias emergen de la teoría de representaciones y la teoría de funciones simétricas. Por un lado, en 1950, Foulkes observó varias propiedades de estabilidad en sucesiones de coeficientes del pletismo dependientes de un parámetro n: las sucesiones son eventualmente constantes para n suficientemente grande. Estas propiedades fueron probadas en los 90 por Carré y Thibon, usando operadores vertex y otros argumentos combinatorios de funciones simétricas, y por Brion para grupos algebraicos en general (no solo para el grupo general linear) y usando herramientas geométricas de la teoría de representaciones. Incluimos una prueba detallada de los resultados probados por Carré y Thibon con el fin de obtener las cotas para las que dichos coeficientes son constantes. También presentamos una interpretación combinatoria de otros coeficientes del pletismo, los h–coeficientes del pletismo, definidos a partir de la base de funciones homogéneas. Estos coeficientes están relacionados directamente con los coeficientes del pletismo usuales mediante la fórmula de Jacobi–Trudi. Esta interpretación combinatoria de los h–coeficientes del pletismo los describe como el número de puntos enteros en un polítopo que depende de las particiones que indexan los coeficientes. Esta nueva interpretación nos permite dar una demostración combinatoria de las propiedades de estabilidad de Brion, Carré y Thibon. Por otro lado, en 1938, Murnaghan observó un fenómeno de estabilidad en los coeficientes de Kronecker: la sucesión de coeficientes de Kronecker, cuyas particiones asociadas tienen una primera parte creciente, son eventualmente constantes. Los coeficientes de Kronecker reducidos se pueden definir como el valor estable de estas sucesiones de coeficientes de Kronecker. Los coeficientes de Kronecker reducidos son objetos interesantes en sí mismos, y podemos recuperar los coeficientes de Kronecker a partir de ellos. Nosotros investigamos qué ocurre cuando añadimos cajas a las filas y columnas de las particiones que indexan los coeficientes de Kronecker reducidos. Presentamos un estudio de cuatro familias. Para la primera familia de coeficientes de Kronecker reducidos damos fórmulas explícitas de los quasipolinomios lineales de periodo 2 a trozos que los definen, dependiendo de las particiones asociadas. Las otras tres familias tienen en común que una de las particiones que las indexan tiene una sola parte, y que las otras dos particiones son arbitrariamente grandes. Para estas tres familias, presentamos un estudio completo: la función generatriz de los coeficientes de Kronecker reducidos y dos descripciones combinatorias, una en términos de particiones planas en un rectángulo y otra como quasipolinomios, especificando el periodo y el grado de los mismos. Además, comprobamos que la hipótesis de saturación se satisface para los coeficientes de Kronecker reducidos de estas tres familias. Otro enfoque interesante para los coeficientes de Kronecker reducidos son los operadores vertex. Incluimos una prueba del teorema de Murnaghan usando operadores vertex. Esta prueba nos proporciona una descripción de los coeficientes de Kronecker reducidos obtenida por Brion. Los operadores vertex también son usados para dar una descripción de los coeficientes de Kronecker reducidos con una partición asociada de una sola parte en términos de los coeficientes de Littlewood–Richardson.

Falta palabras clave The freight-transport industry has made enormous progress in the development and application of logistics techniques that has transformed its operation, giving raise to impressive productivity gains and improved responsiveness to its consumers. While the separation of passenger and freight traffic is a relatively new concept in historic terms, recent approaches point out that most freight-logistics techniques are transferable to the passenger-transport industry. In this sense, passenger logistics can be understood as the application of logistics techniques in urban contexts to the passenger-transport industry. The design of an urban logistic network integrates decisions about the emplacement, number and capacities of the facilities that will be located, the flows between them, demand patterns and cost structures that will validate the profitability of the process. This strategic decision settles conditions and constraints of latter tactical and operative decisions. In addition, different criteria are involved during the whole process so, in general terms, it is essential an exhaustive analysis, from the mathematical point of view, of the decision problem. The optimization models resulting from this analysis require techniques and mathematical algorithms in constant development and evolution. Such methods demand more and more a higher number of interrelated elements due to the increase of scale used in the current logistics and transportation problems. This PhD dissertation explores different topics related to Mathematical models for the design and planning of transportation on demand in urban logistics networks. The contributions are divided into six main chapters since and, in addition, Chapter 0 offers a basic background for the contents that are presented in the remaining six chapters. Chapter 1 deals with the Transit Network Timetabling and Scheduling Problem (TNTSP) in a public transit line. The TNTSP aims at determining optimal timetables for each line in a transit network by establishing departure and arrival times of each vehicle at each station. We assume that customers know departure times of line runs offered by the system. However, each user, traveling later of before their desired travel time, will give rise to an inconvenience cost, or a penalty cost if that user cannot be served according to the scheduled timetable. The provided formulation allocates each user to the best possible timetable considering capacity constraints. The problem is formulated using a p-median based approach and solved using a clustering technique. Computational results that show useful applications of this methodology are also included. Chapter 2 deals with the TNTSP in a public transit network integrating in the model the passengers' routings. The current models for planning timetables and vehicle schedules use the knowledge of passengers' routings from the results of a previous phase. However, the actual route a passenger will take strongly depends on the timetable, which is not yet known a priori. The provided formulation guarantees that each user is allocated to the best possible timetable ensuring capacity constraints. Chapter 3 deals with the rescheduling problem in a transit line that has suffered a eet size reduction. We present different modelling possibilities depending on the assumptions that need to be included in the modelization and we show that the problem can be solved rapidly by using a constrained maxcost- ow problem whose coe_cient matrix we prove is totally unimodular. We test our results in a testbed of random instances outperforming previous results in the literature. An experimental study, based on a line segment of the Madrid Regional Railway network, shows that the proposed approach provides optimal reassignment decisions within computation times compatible with real-time use. In Chapter 4 we discuss the multi-criteria p-facility median location problem on networks with positive and negative weights. We assume that the demand is located at the nodes and can be different for each criterion under consideration. The goal is to obtain the set of Pareto-optimal locations in the graph and the corresponding set of non-dominated objective values. To that end, we first characterize the linearity domains of the distance functions on the graph and compute the image of each linearity domain in the objective space. The lower envelope of a transformation of all these images then gives us the set of all non-dominated points in the objective space and its preimage corresponds to the set of all Pareto-optimal solutions on the graph. For the bicriteria 2-facility case we present a low order polynomial time algorithm. Also for the general case we propose an efficient algorithm, which is polynomial if the number of facilities and criteria is fixed. In Chapter 5, Ordered Weighted Average optimization problems are studied from a modeling point of view. Alternative integer programming formulations for such problems are presented and their respective domains studied and compared. In addition, their associated polyhedra are studied and some families of facets and new families of valid inequalities presented. The proposed formulations are particularized for two well-known combinatorial optimization problems, namely, shortest path and minimum cost perfect matching, and the results of computational experiments presented and analyzed. These results indicate that the new formulations reinforced with appropriate constraints can be effective for efficiently solving medium to large size instances. In Chapter 6, the multiobjective Minimum cost Spanning Tree Problem (MST) is studied from a modeling point of view. In particular, we use the ordered median objective function as an averaging operator to aggregate the vector of objective values of feasible solutions. This leads to the Ordered Weighted Average Spanning Tree Problem (OWASTP), which we study in this work. To solve the problem, we propose different integer programming formulations based in the most relevant MST formulations and in a new one. We analyze several enhancements for these formulations and we test their performance over a testbed of random instances. Finally we show that an appropriate choice will allow us to solve larger instances with more objectives than those previously solved in the literature. Premio Extraordinario de Doctorado US

Texto completo descargado desde Teseo In this thesis we present a series of result that are framed in the theory of Matrix Orthogonal Polynomials, a branch of the very celebrated subject of Orthogonal Polynomials. In particular we study families of matrix valued orthogonal polynomials satisfying differential, difference or q-difference equations. The search for examples of matrix polynomials which are also eigenfunctions of certain matrix operators is a rather dificult issue. This dificulty is due to several reasons. The most important of these reasons is the increase of the difficulties in the computations related with the non-commutativity of the matrix product, and the existence of singular matrices. However, having a wide set of examples of matrix orthogonal polynomials has shown to be decisive in the study and discovery of new phenomena happening in the matrix orthogonality. This has been the case with the examples of matrix orthogonal polynomials satisfying differential equations. An example of the increasing knowledge about these families of orthogonal polynomials is shown in the last chapter of this memory. There, lot of tools developed in the last decades are used to build and study in deep an interesting family of matrix orthogonal polynomials satisfying second order differential equations. Moreover, these families are shown to satisfy first order differential equations as well. In the case of matrix orthogonal polynomials satisfying difference equations, very little was known. Apart from some examples in size 2x2 (and some others reducible to the scalar case) there were no examples of such matrix orthogonal polynomials. With this thesis this lack of examples starts to be solved. Moreover, we introduce a method to construct examples of matrix orthogonal polynomials satisfying second order difference equations, and by making use of it we give a variety of examples. Having such a method is of the main importance, because we skip the complexity in the computations that made the search of examples so difficult, and now dealing with matrix orthogonal polynomials and matrix difference equations becomes much easier to handle. The method profits of the factorization of a weight matrix and the symmetry equations for a discrete weight matrix and a difference operator. These symmetry equations are the starting point to develop the method. By making use of the examples obtained by this method, we explore new features and properties satisfied by this objects. For the case of matrix orthogonal polynomials satisfying q-difference equations, even less was known. In this thesis we establish the symmetry equations for the q-difference case, and we adapt the method developed for the difference case to obtain the first non-trivial examples of matrix orthogonal polynomials satisfying second order q-difference operator. That emphasizes the power of the method to build examples for the difference case. With our method we construct an example of matrix orthogonal polynomials satisfying q-difference equations, but this method can easily be used to get a wider class of examples and to explore their properties. With the content of this thesis we get a more complete view of the theory of matrix orthog- onal polynomials, and many questions can now be tackled, such as those concerning limiting relations among matrix orthogonal polynomials satisfying second order difference equations (or q-difference) and matrix orthogonal polynomials satisfying second order differential equa- tions.