Knapsack models applied to the solution of complex problems in transport planning

Abstract

This thesis has been developed during the competitive research projects aimed at promoting the use of mathematical optimization models for decision-making in complex contexts where there are often conflicting interests (such as those of users, transportation companies, and administration), multiple constraints (due to limited capacity, required availability of time windows to perform the offered service, or distance limitations to ensure service coverage), and exogenous variables (such as the user’s non-deterministic behavior in decision-making, traffic congestion episodes during peak hours, and the possibility of using intermodality in travels). Planning transportation within such complex contexts requires innovative formulations, which may be initially based on those that have proven effective and efficient in similar contexts, using both exact and heuristic models (including metaheuristics and matheuristics). Location and transportation problems share a common origin in mathematical optimization, characterized by the use of variables of different nature (continuous, integer, or binary) to construct compatible objective functions, preferably with linear behavior. The versatility provided by the introduced decision variables allows representing the characteristic constraints present in such optimization models through algebraic manipulation. In addition to constraints, possible strategies to be followed by the involved agents (individual users, administration, or companies) can also be described through suitable algebraic expressions of those variables. A paradigmatic optimization model due to its versatility to adapt to a large number of real contexts and its possibilities of extension (by adding new lines of constraint for solution searching, incorporating complementary levels of optimality and/or modifying the linearity of algebraic expressions) is the so-called knapsack problem (KP). In most of the proposed solutions to the analyzed problems in this thesis, the knapsack problems have been a useful tool for their formulation. This is why the thesis references this combinatorial optimization problem. Regarding the real contexts analyzed from the perspective of mathematical optimization, we must admit that the academic center where the Ph.D. student has been trained (Department of Applied Mathematics of the Technical School of Architecture at the University of Seville) has had an undeniable influence: - The design of fast transit lines has been approached from a novel perspective of acquiring a higher level of territorial cohesion, minimizing the need for mobility due to forced displacements caused by territorial imbalances. - The search for solutions for the effective location of waste containers and the efficient deployment of selective collection routes has been complemented by the additional consideration of solidarity behavior by the user who, suitably motivated, could be willing to deposit their waste collection demand at a point different from the nearest one. - The planning of non-habitual waste collection services through itinerant containers with multiple compartments (ecopoints) has been analyzed in a separate chapter, where optimization models have been formulated for different resolution strategies that have been compared in terms of efficiency. - The deployment of electric charging stations based on the prior existence of a network of conventional gas stations is another problem addressed in this thesis, in which the perspective of the government administration has been contributed as a novelty, which requires that the number of charging points provide reinforced coverage to users who undertake a journey throughout the territory, and the business interests, selecting the most promising locations due to the flow of travel that passes through them. - The restrictions on accessibility to current urban centers in private motor vehicles have been dealt with in another chapter of the thesis, providing a decision model for the optimal choice of a park-and-ride facility that combines criteria of distance to destination, travel times subject to traffic flow, possibility of using intermodality, and availability of free parking spaces. - Finally, the management of waiting time for users at transport network nodes can generate interesting strategies for optimizing travel times, both in global terms (reducing the number of intermediate stops to favor the travel time of most passengers), and individual terms (waiting at a node for the arc that provides the exit from the node to be passable in a significantly shorter time).