Mathematical models for the design and planning of transportation on demand in urban logistics networks

Resumen

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.