Abstract

In the last years the steady development of autonomous driving technology has enabled the deployment of more mature autonomous vehicles. These vehicles have been applied in several pilot projects worldwide, most commonly in the form of small buses. At the same time, the amount of people traveling in especially urban areas is continuously growing, resulting in more trips in the transportation system. An efficient transportation system is therefore required to serve the growing passenger demand. Autonomous buses (AB) are assumed to have lower operational costs and with that public transport (PT) systems can potentially be designed more efficiently to facilitate the increased demand better. In this study, an AB specific simulation-based optimization framework is proposed which allows analyzing the impacts AB have on line-based PT systems. The thesis focuses on the transition from existing PT systems towards line-based PT systems operated partially or exclusively by AB. Existing work on PT service design is extended so that realistic AB systems can be investigated. This is achieved by (i) using AB specific operator cost formulations, (ii) integrating infrastructure costs required for AB operations, (iii) utilizing a dynamic, stochastic and schedule-based passenger assignment model for the simulation of PT networks and by (iv) formulating a multi-objective optimization problem allowing to investigate the stakeholder-specific impacts of AB. In Paper I the effects of AB, concerning service frequency and vehicle capacity, on fixed-line PT networks are investigated. Among other metrics, the changes are evaluated based on differences in level of service and passenger flow. Additionally, the sequential introduction of AB in existing PT systems is studied. The framework addresses a case study in Kista, Sweden. The study confirmed the initial hypothesis that the deployment of AB leads to an increase in service frequency and a marginal reduction in vehicle capacity. Furthermore, it could be seen that the deployment of AB increases the passenger load on AB lines and that passengers can shift from other PT modes towards the AB services. Paper II incorporates a multi-objective heuristic optimization algorithm in the simulation framework. The study investigates changes in transport network design based on the deployment of AB. The differences in user-focused and operator-focused network design are analyzed and the impact of AB on these is quantified. This study is applied to a case study in Barkarby, Sweden where a full-sized, line-based PT network is designed to exclusively operate AB. Among other findings, we show that the autonomous technology reduces the number of served bus stops and reduces the total PT network size. Additionally, average passenger waiting time can be reduced when deploying AB on user-focused PT networks, which in turn leads to a further reduction of user cost. De senaste årens framsteg inom autonom körteknik har lett till mer mogna autonoma fordon. Dessa fordon har setts tillämpas i flera pilotprojekt över hela världen, oftast i form av små bussar. Samtidigt växer mängden människor som reser, särskilt i stadsområden, kontinuerligt vilket resulterar i fler resor i transportsystemet. Därför krävs ett effektivt transportsystem för att tillgodose det växande antalet passagerare. Autonoma bussar (AB) antas ha lägre driftskostnader och därmed kan system för kollektivtrafik (public transport, PT) potentiellt utformas mer effektivt för att underlätta den ökade efterfrågan bättre. I denna studie föreslås ett AB-specifikt simuleringsbaserat optimeringsramverk som gör det möjligt att analysera effekterna AB har på linjebaserade PT-system. Avhandlingen fokuserar på övergången från befintliga PT-system till linjebaserade PT-system som delvis eller uteslutande drivs av AB. Befintligt arbete med PT-tjänstdesign utvidgas så att realistiska AB-system kan undersökas. Detta uppnås genom att (i) använda AB-specifika operatörskostnadsformuleringar, (ii) integrera infrastrukturkostnader som krävs för AB-verksamhet, (iii) använda en dynamisk, stokastisk och schemabaserad modell för att tilldela passagerare vid simulering av PT-nät samt genom att (iv) formulera ett multifunktionellt optimeringsproblem som gör det möjligt att undersöka AB: s intressespecifika effekter. I artikel I undersöks effekterna av AB, med avseende på servicefrekvens och fordonskapacitet, på fasta linjer i PT-nät. Förändringar utvärderas bland annat utifrån skillnader i servicenivå och passagerarflöde. Dessutom studeras den sekventiella introduktionen av AB i befintliga PT-system. Det föreslagna ramverket tillämpas på en fallstudie i Kista, Sverige. Studien bekräftade den initiala hypotesen att utplaceringen av AB leder till en ökning av servicefrekvensen och en marginell minskning av fordonens kapacitet. Vidare kunde man se att utplaceringen av AB ökar passagerarbelastningen på AB-linjer och att passagerare kan skifta från andra PT-former mot AB-tjänsterna. Artikel II integrerar en multifunktionell heuristisk optimeringsalgoritm i ramverket för simuleringen. Studien undersöker förändringar i transportnätverkets design baserat på implementeringen av AB. Skillnaderna i användarfokuserad och operatörsfokuserad nätverksdesign analyseras och AB: s inverkan på dessa kvantifieras. Denna studie tillämpas på en fallstudie i Barkarby, Sverige, där ett fullstort linjebaserat PT-nät är utformat för att exklusivt driva AB. Vi visar bland annat att den autonoma tekniken reducerar antalet använda busshållplatser och reducerar den totala PT-nätstorleken. Dessutom kan implementeringen av AB på användarfokuserade PT-nät ytterligare förbättra servicenivån främst genom att minska den genomsnittliga väntetiden per passagerare.

Abstract

International audience; Switched Ethernet networks rely on the Spanning Tree Protocol (STP) to ensure a cycle-free connectivity between nodes, by reducing the topology of the network to a spanning tree. The Multiple Spanning Tree Protocol (MSTP) allows for the providers to partition the traffic in the network and assign it to different virtual local area networks, each satisfying the STP. In this manner, it is possible to make a more efficient use of the physical resources in the network. In this paper we consider the traffic engineering problem of finding optimal designs of switched Ethernet networks implementing the MSTP, such that the worst-case link utilization is minimized. We show that this problem is N P-hard. We propose three mixed-integer linear programming formulations for this problem. Through a large set of computational experiments, we compare the performance of these formulations. Until now, the problem was almost exclusively solved with heuristics. Our objective here is provide a first comparison of different models that can be used in exact methods.

Abstract

This thesis develops mathematical programming models which integrate network design (ND) and line frequency setting (LFS) phases. These appear in transport planning studies that extend an existing urban public transportation system (UPTS) and are suitable for underground and rapid transit systems. The ND phase extends the working UPTS, taking as inputs the locations of candidate stretches and stations on the new lines, as well as construction costs which cannot exceed the available infrastructure budget. Regarding the LFS phase, frequencies and vehicles are assigned to functioning and newly built lines, providing that they do not exceed resource capacities and the time horizon. The developed models take into account the type of service patterns that may operate on the lines of the transport system. They include local services, where vehicles halt at every node in the line, and express services, in which vehicles halt at only a subset of nodes in the line. A passenger assignment model allows solving, simultaneously, the ND and LFS phases under a system optimum point of view. The combined model has two variants: one which deals with inelastic demand and another which faces elasticities in demand. The latter originates from changes in the modal choice proportions of travelers and may result from modifications in the public transport system. The former does not take into account competition among several modes of transportation and it is formulated as a mixed-integer linear programming problem. In contrast, the latter allows passengers to travel via two modes of transportation: public transport and private car. It is formulated as a mixed-integer linear bi-level programming problem (MILBP) with discrete variables only in the upper level. In both models, a complementary network is used to model transfers among lines and to reach the passenger¿s origin and/or destination nodes when the constructed UPTS does not cover them. The model with inelastic demand is initially solved by means of the commercial solver CPLEX under three different mathematical formulations for the ND phase. The first two are exact approaches based on extensions of Traveling Salesman Problem formulations for dynamic and static treatment of the line¿s subtours, whereas the last one is an approximation inspired by constrained k-shortest path algorithms. In order to deal with large-sized networks, a quasi-exact solution framework is employed. It consists of three solving blocks: the corridor generation algorithm (CGA), the line splitting algorithm (LSA), and a specialized Benders decomposition (SBD). The LSA and CGA are heuristic techniques that allow skipping some of the non-polynomial properties. They are related to the number of lines under construction and the number of feasible corridors that can be generated. As for the SBD, it is an exact method that splits the original mathematical programming problem into a series of resolutions, composed of two mathematical problems which are easier to solve. Regarding the elastic demand variant, it is solved under the same framework as the specialized Benders decomposition adaptation for solving MILBP, which results from this variant formulation. The inelastic demand variant is applied to two test cases based on underground network models for the cities of Seville and Santiago de Chile. Origin destination trip matrices and other parameters required by the models have been set to likely values using maps and published studies. The purpose of these networks is to test the models and algorithms on realistic scenarios, as well as to show their potentialities. Reported results show that the quasi-exact approach is comparable to approximate techniques in terms of performance. Regarding the elastic demand variant, the model is more complex and can be applied only to smaller networks. Finally, some further lines of research for both modeling and algorithmic issues are discussed.

Abstract

n important problem in the assessment of reliability benefits of transport projects is that link level improvements must be translated to network level, so that they can be economically valued based on users’ trips from origins to destinations. For intermodal transport, shipments follow a chain with more than one mode. Generally, this requires aggregation of travel time distributions that are not additive. We propose an approach that estimates the change in transport time reliability of an intermodal transport chain based on the changes for links of that chain. We demonstrate the framework of reliability assessment for a case study of network improvement for rail-truck intermodal transport in China. Also, we demonstrate the application in a cost-benefit analysis context with user valuations of transport reliabilities from the case at hand. The application leads to the result that projects for the renovation and expansion of the transshipment terminal perform better compared with project that improve rail haulage speed. Another finding is that the effect of reliability improvement projects can be super-additive at network level. In comparison with traditional methods, we conclude that the proposed method can better estimate transport time reliability benefits when the distribution of link travel times is highly skewed. Also, it opens new possibilities for further research for measuring correlated reliability measures within networks and for performing network resilience analysis.

Abstract

The evaluation of dynamic Traffic Engineering (TE) algorithms is usually carried out using some specific network(s), traffic pattern(s) and traffic engineering objective(s). As the behavior of a TE algorithm is a consequence of the interactions between the network, the traffic demand and the algorithm itself, the relevance of TE may depend on several network design aspects. In this paper, we evaluate well-known TE algorithms using real-world and generated network topologies and traffic demands. By re-scaling observed traffic demands, we are able to observe the behavior of TE algorithms under a variety of situations, which may not be observable in reality. We identify distinct network load regimes that correspond to different behaviors of the TE algorithms. We also study the impact of several network design aspects, like network provisioning and redundancy, on the relevance of TE algorithms. We find that there are specific situations under which TE algorithms are useful. These situations depend highly on shortcomings in the network provisioning as well as on the availability of alternative paths in the network.

Abstract

With automated vehicles (AVs), reversible lanes could be a sustainable transportation solution once there is vehicle-to-infrastructure connectivity informing AVs about the lane configuration changes. This paper introduced the reversible lane network design problem (RL-NDP), formulated in mixed-integer non-linear mathematical programming&mdash both the traffic assignment and the reversible lane decisions were embedded. The model was applied on an hourly basis in the case study of the city of Delft, the Netherlands. Reversible lanes are examined under no traffic equilibrium (former paths are maintained) user-equilibrium (UE) assignment (AVs decide their own paths) and system-optimum (SO) traffic assignment (AVs are forced to follow SO paths). We found out that reversible lanes reduce congested roads, total travel times, and delays up to 36%, 9%, and 22%, respectively. The SO scenario was revealed to be beneficial in reducing the total travel time and congested roads in peak hours, whereas UE is equally optimal in the remaining hours. A dual-scenario mixing SO and UE throughout the day reduced congested roads, total travel times, and delay up to 40%, 8%, and 19%, respectively, yet increased 1% in travel distance. The spatial analysis suggested a substantial lane variability in the suburbs, yet a strong presence of reversible lanes in the city center. Document type: Article