abstract: This dissertation investigates congestion mitigation during the ingress of a planned special event (PSE). PSEs would impact the regular operation of the transportation system within certain time periods due to increased travel demand or reduced capacities on certain road segments. For individual attendees, cruising for parking during a PSE could be a struggle given the severe congestion and scarcity of parking spaces in the network. With the development of smartphones-based ridesharing services such as Uber/Lyft, more and more attendees are turning to ridesharing rather than driving by themselves. This study explores congestion mitigation during a planned special event considering parking, ridesharing and network configuration from both attendees and planner’s perspectives. Parking availability (occupancy of parking facility) information is the fundamental building block for both travelers and planners to make parking-related decisions. It is highly valued by travelers and is one of the most important inputs to many parking models. This dissertation proposes a model-based practical framework to predict future occupancy from historical occupancy data alone. The framework consists of two modules: estimation of model parameters, and occupancy prediction. At the core of the predictive framework, a queuing model is employed to describe the stochastic occupancy change of a parking facility. From an attendee’s perspective, the probability of finding parking at a particular parking facility is more treasured than occupancy information for parking search. However, it is hard to estimate parking probabilities even with accurate occupancy data in a dynamic environment. In the second part of this dissertation, taking one step further, the idea of introducing learning algorithms into parking guidance and information systems that employ a central server is investigated, in order to provide estimated optimal parking searching strategies to travelers. With the help of the Markov Decision Process (MDP), the parking searching process on a network with uncertain parking availabilities can be modeled and analyzed. Finally, from a planner’s perspective, a bi-level model is proposed to generate a comprehensive PSE traffic management plan considering parking, ridesharing and route recommendations at the same time. The upper level is an optimization model aiming to minimize total travel time experienced by travelers. In the lower level, a link transmission model incorporating parking and ridesharing is used to evaluate decisions from and provide feedback to the upper level. A congestion relief algorithm is proposed and tested on a real-world network. / Dissertation/Thesis / Doctoral Dissertation Civil, Environmental and Sustainable Engineering 2019

L'émergence des téléphones mobiles et objets connectés a profondément changé notre vie quotidienne. Ces dispositifs, grâce à la multitude de capteurs qu'ils embarquent, permettent l'accès à un large spectre de services. En particulier, les capteurs de position ont contribué au développement des services de localisation tels que la navigation, le covoiturage, le suivi de la congestion en temps réel... En dépit du confort offert par ces services, la collecte et le traitement des données de localisation portent de sérieuses atteintes à la vie privée des utilisateurs. En effet, ces données peuvent renseigner les fournisseurs de services sur les points d'intérêt (domicile, lieu de travail, orientation sexuelle), les habitudes ainsi que le réseau social des utilisateurs. D'une façon générale, la protection de la vie privée des utilisateurs peut être assurée par des dispositions légales ou techniques. Même si les mesures d'ordre légal peuvent dissuader les fournisseurs de services et les individus malveillants à enfreindre le droit à la vie privée des utilisateurs, les effets de telles mesures ne sont observables que lorsque l'infraction est déjà commise et détectée. En revanche, l'utilisation des technologies renforçant la protection de la vie privée (PET) dès la phase de conception des systèmes permet de réduire le taux de réussite des attaques contre la vie privée des utilisateurs. L'objectif principal de cette thèse est de montrer la viabilité de l'utilisation des PET comme moyens de protection des données de localisation dans les services de covoiturage. Ce type de service de localisation, en aidant les conducteurs à partager les sièges vides dans les véhicules, contribue à réduire les problèmes de congestion, d'émissions et de dépendance aux combustibles fossiles. Dans cette thèse, nous étudions les problèmes de synchronisation d'itinéraires et d'appariement relatifs au covoiturage avec une prise en compte explicite des contraintes de protection des données de localisation (origine, destination). Les solutions proposées dans cette thèse combinent des algorithmes de calcul d'itinéraires multimodaux avec plusieurs techniques de protection de la vie privée telles que le chiffrement homomorphe, l'intersection sécurisée d'ensembles, le secret partagé, la comparaison sécurisée d'entier. Elles garantissent des propriétés de protection de vie privée comprenant l'anonymat, la non-chainabilité et la minimisation des données. De plus, elles sont comparées à des solutions classiques, ne protégeant pas la vie privée. Nos expérimentations indiquent que les contraintes de protection des données privées peuvent être prise en compte dans les services de covoiturage sans dégrader leurs performances. / The emergence of mobile phones and connected objects has profoundly changed our daily lives. These devices, thanks to the multitude of sensors they embark, allow access to a broad spectrum of services. In particular, position sensors have contributed to the development of location-based services such as navigation, ridesharing, real-time congestion tracking... Despite the comfort offered by these services, the collection and processing of location data seriously infringe the privacy of users. In fact, these data can inform service providers about points of interests (home, workplace, sexual orientation), habits and social network of the users. In general, the protection of users' privacy can be ensured by legal or technical provisions. While legal measures may discourage service providers and malicious individuals from infringing users' privacy rights, the effects of such measures are only observable when the offense is already committed and detected. On the other hand, the use of privacy-enhancing technologies (PET) from the design phase of systems can reduce the success rate of attacks on the privacy of users. The main objective of this thesis is to demonstrate the viability of the usage of PET as a means of location data protection in ridesharing services. This type of location-based service, by allowing drivers to share empty seats in vehicles, helps in reducing congestion, CO2 emissions and dependence on fossil fuels. In this thesis, we study the problems of synchronization of itineraries and matching in the ridesharing context, with an explicit consideration of location data (origin, destination) protection constraints. The solutions proposed in this thesis combine multimodal routing algorithms with several privacy-enhancing technologies such as homomorphic encryption, private set intersection, secret sharing, secure comparison of integers. They guarantee privacy properties including anonymity, unlinkability, and data minimization. In addition, they are compared to conventional solutions, which do not protect privacy. Our experiments indicate that location data protection constraints can be taken into account in ridesharing services without degrading their performance.

Traditionally, optimization problems in operations research have been studied in a complete information setting; the input/data is collected and made fully accessible to the user, before an algorithm is sequentially run to generate the optimal output. However, the growing magnitude of treated data and the need to make immediate decisions are increasingly shifting the focus to optimizing under incomplete information settings. The input can be partially inaccessible to the user either because it is generated continuously, contains some uncertainty, is too large and cannot be stored on a single machine, or has a hidden structure that is costly to unveil. Many problems providing a context for studying algorithms when the input is not entirely accessible emanate from the field of matching theory, where the objective is to pair clients and servers or, more generally, to group clients in disjoint sets. Examples include ride-sharing and food delivery platforms, internet advertising, combinatorial auctions, and online gaming. In this thesis, we study three different novel problems from the theory of matchings. These problems correspond to situations where the input is hidden, spread across multiple processors, or revealed in two stages with some uncertainty. In particular, we present in Chapter 1 the necessary definitions and terminology for the concepts and problems we cover. In Chapter 2, we consider a two-stage robust optimization framework that captures matching problems where one side of the input includes some future demand uncertainty. We propose two models to capture the demand uncertainty: explicit and implicit scenarios. Chapters 3 and 4 see us switch our attention to matchings in hypergraphs. In Chapter 3, we consider the problem of learning hidden hypergraph matchings through membership queries. Finally, in Chapter 4, we study the problem of finding matchings in uniform hypergraphs in the massively parallel computation (MPC) model where the data (e.g. vertices and edges) is distributed across the machines and in each round, a machine performs local computation on its fragment of data, and then sends messages to other machines for the next round.

As concerns about climate change increase, many people are calling for reductions in the use of fossil fuels and encouraging a shift to more sustainable and less polluting transportation modes. Cities and urban areas are more concerned because their population currently comprises over half of the world's population. Sustainable transportation modes such as cycling, walking, and use of public transit and electric vehicles can benefit the environment in many ways, including a reduction in toxic greenhouse gas (GHG) emissions and noise levels. In order to enhance the trend of using sustainable modes of transportation, tools, measures, and planning techniques similar to those used for vehicular transportation need to be developed. In this dissertation, we consider four problems in the context of different sustainable modes of transportation, namely, cycling, rail, public transit, and ridesharing. We develop different models to predict bike travel times for use in bike share systems (BSSs) using random forest (RF), least square boosting (LSBoost), and artificial neural network (ANN) techniques. We also use cycling Global Positioning System (GPS) data collected from 10 people (3 females and 7 males) to study cyclists' acceleration/deceleration behavior. Moreover, we develop a continuous rail transit simulator (RailSIM) intended for multi-modal energy-efficient routing applications. Finally, we propose a dynamic trip planning system that integrates ridesharing and public transit. The work done in this dissertation can help encouraging more people to move to more sustainable modes of transportation. / Doctor of Philosophy / As concerns about climate change increase, many people are calling for reductions in the use of fossil fuels and encouraging a shift to more sustainable and less polluting transportation modes. Cities and urban areas are more concerned because their population currently comprises over half of the world's population. Sustainable transportation modes such as cycling, walking, and use of public transit and electric vehicles can benefit the environment in many ways, including a reduction of toxic greenhouse gas (GHG) emissions and noise levels. In order to enhance the trend of using sustainable modes of transportation, tools, measures, and planning techniques similar to those used for vehicular transportation need to be developed. In this dissertation, we consider four problems in the context of different sustainable modes of transportation, namely, cycling, rail, public transit, and ridesharing. We develop different models to predict bike travel times in bike share systems (BSSs) using machine learning techniques. We also use cycling Global Positioning System (GPS) data collected from 10 people (3 females and 7 males) to study cyclists' acceleration/deceleration behavior. Moreover, we develop a continuous rail transit simulator (RailSIM) intended for multi-modal energy-efficient routing applications. Finally, we propose a dynamic trip planning system that integrates ridesharing and public transit. The work done in this dissertation can help encouraging more people to move to more sustainable modes of transportation.

<p dir="ltr">Ride-hailing is the frontier of transportation innovations and has become an essential component of urban mobility. Addressing the efficiency of service operations and associated challenges has significant implications for the future of transportation systems. </p><p dir="ltr">In this dissertation, we develop a series of approaches and tools to enhance the efficiency of ride-hailing systems, validate operational controls, and assess the associated risks. Through extensive numerical experiments, we demonstrate the efficacy of our methods.</p><p dir="ltr">In Chapter 2 to 4, we develop three complementary operational algorithms aimed at improving ride-hailing services' efficiency:</p><ul><li> Chapter 2 focuses on proactive vehicle repositioning using a supervised learning model to recommend optimal pickup locations for vacant vehicles. The numerical experiments suggest this strategy can reduce empty vehicle mileage and also balance driver income/utilization.</li><li>Chapter 3 presents a hub-based ride-sharing algorithm that features an efficient data structure for querying feasible vehicle schedules and employs model predictive control to account for future demand and supply uncertainties. This approach significantly outperforms baselines that do not account for future supply and demand or rely on point-wise predictions.</li><li>Chapter 4 addresses dynamic pricing in ride-hailing systems. We contribute to a rigorous definition of the problem and a reinforcement learning-based method to generate deterministic pricing policies. The numerical results suggest our approach can achieve near-optimal performance in promoting service income by effectively reducing empty vehicle mileage.</li></ul><p dir="ltr">Chapter 5 introduces METS-R SIM, an agent-based simulator that combines detailed microscopic traffic simulation models with dynamic demand-supply matching. We validate METS-R SIM against actual ride-hailing data, demonstrating its ability to accurately reproduce travel time and distance profiles and provide valuable insights for improving supply design and control strategies.</p><p dir="ltr">Finally, Chapter 6 explores the security challenges in autonomous mobility-on-demand (AMoD) systems. We develop a threat model to assess risks in the passenger-vehicle matching mechanism. Our experiments reveal that optimization-based attacks can significantly degrade service quality and increase traffic congestion, highlighting the need for extensive security analyses in autonomous ride-hailing operations.</p><p>Together, these contribute to a complete framework for improving ride-hailing systems with advanced operational algorithms, high-fidelity validation, and comprehensive risk assessments, paving the path toward a more efficient and secure ride-hailing service.</p>

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-06-02T19:19:17Z No. of bitstreams: 1 RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-06-05T19:52:50Z (GMT) No. of bitstreams: 1 RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5) / Made available in DSpace on 2017-06-05T19:52:51Z (GMT). No. of bitstreams: 1 RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5) Previous issue date: 2017-02-17 / O Problema do Caixeiro Viajante com Passageiros e Lota??o ? uma vers?o do PCV cl?ssico onde o caixeiro ? o motorista de um ve?culo que compartilha os custos de viagem com passageiros. Al?m de dividir os custos do percurso, o caixeiro pode se valer, tamb?m, dos descontos das high-occupancy vehicle lanes, que s?o faixas de tr?nsito que isentam ve?culos lotados do pagamento de ped?gio. A adi??o de passageiros ao PCV, um problema restrito ao roteamento, cria um vi?s colaborativo que ? intensificado pela considera??o das faixas especiais. Tal cen?rio confere ao problema estudado um aspecto ecol?gico, uma vez que seu estudo tem consequ?ncias diretas sobre o uso eficiente do espa?o urbano e a diminui??o da emiss?o de gases poluentes, contribuindo sobremaneira para o incremento da qualidade de vida. A pesquisa compreendeu desde a correla??o entre esse novo problema e outros constantes na literatura at? a concep??o de um conjunto de seiscentas inst?ncias artificiais e a cria??o de diversos m?todos de solu??o. Para a determina??o de ?timos, ? proposto um modelo matem?tico que suportou as solu??es por Programa??o Matem?tica e por Restri??es. Adicionalmente, ? apresentado um algoritmo branch-and-bound especificamente desenvolvido para o problema. Visando a busca por solu??es de qualidade em curto espa?o de tempo, s?o expostos cinco algoritmos experimentais com base nas abordagens heur?sticas Simulated Annealing, Variable Neighborhood Search, Coloniza??o de Abelhas e Algoritmos Gen?ticos. Diversos procedimentos auxiliares para constru??o de solu??es e execu??o de buscas locais s?o tamb?m expostos. Um experimento computacional ? realizado para compara??o entre os m?todos de solu??o. Uma amostra de cem casos teste ? utilizada para o processo estat?stico de ajuste de par?metros dos algoritmos heur?sticos, enquanto o restante das inst?ncias ? extensivamente abordado pelos m?todos. S?o determinados os ?timos para cento e cinquenta e cinco casos com tamanhos 10 e 20 cidades. Dentre os m?todos experimentais, cabe destacar a superioridade do algoritmo heur?stico que une as meta-heur?sticas Simulated Annealing e Variable Neighborhood Search. / The Traveling Salesman with Passengers and High Occupancy Problem is a version of the classic TSP where the salesman is the driver of a vehicle who shares travels? expenses with passengers. Besides shared expenses, the driver also benefits from discounts of the highoccupancy vehicle lanes, i.e. traffic lanes in which high occupancy vehicles are exempted from tolls. The addition of passengers to the TSP, a routing-only problem, creates a sharing view which is intensified by the consideration of special lanes. This scenario grants to the problem an ecological feature, since its study have direct consequences for the efficient use of urban space and the greenhouse gas emissions reduction, greatly contributing for quality of life improvement. This work addresses the study of this novel combinatorial optimization problem, going from the relationship it draws with other ones in the literature until the conception of a six hundred set of artificial test cases and the creation of many solution methods. To find optimal solutions, a mathematical model is proposed. This model supported the search for exact solutions by Mathematical and Constraint Programming. Additionally, is presented a branchand- bound algorithm specifically developed for the problem. Aiming the search for good quality solutions in short time period, five experimental algorithms based on the heuristics approaches Simulated Annealing, Variable Neighborhood Search, Bees Colony and Genetic Algorithms are introduced. Several auxiliary procedures for solutions generations and local search execution are revealed as well. A computational experiment is fulfilled to comparison between the solution methods. A sample of a hundred test cases is used for the heuristics algorithms? parameter tuning statistical process, while the rest of them are extensively addressed by the methods. The optimal solution for a hundred and fifty five test cases with sizes of 10 and 20 cities are determined. Among the experimental methods, one has to highlight the advantage of the heuristic algorithm that unites the metaheuristics Simulated Annealing and Variable Neighborhood Search.

1 The concept of carpooling, its development and recent comprehension in judicial practice Abstract This thesis focuses on the concept of carpooling, its development and understanding of this concept in commonly spoken and legal language, including the current view of the Czech and European courts. A significant part of the work addresses the legal classification of carpooling. The first part describes the development of carpooling from its inception to the present. In the recent years, carpooling was often associated with the development of modern technology which caused confusion about the exact content of the concept of carpooling. In the second part I analyse carpooling from a linguistic viewpoint, both in terms of commonly used language and from a legal point of view. This also answers the question of whether the content of the concept "carpooling" has possibly changed over time. The third chapter looks at the relationship between carpooling and commercial activity. I try to find out whether any form of carpooling may also have commercial features. I also aim to establish whether there is a certain limit to when an activity can still be considered as carpooling. The fourth chapter discusses the most important case laws in the Czech and European context which deal with the solution of unfair competitive...

Queueing theory has often been applied to study communication and service queueing systems such as call centers, hospital emergency departments and ride-sharing platforms. Unfortunately, it is complicated to analyze queueing systems. That is largely because the arrival and service processes that mainly determine a queueing system are uncertain and must be represented as stochastic processes that are difficult to analyze. In response, service providers might be able to partially capture the main characteristics of systems given partial data information and limited domain knowledge. An effective engineering response is to develop tractable approximations to approximate queueing characteristics of interest that depend on critical partial information. In this thesis, we contribute to developing high-quality approximations by studying tight bounds for the transient and the steady-state mean waiting time given partial information. We focus on single-server queues and multi-server queues with the unlimited waiting room, the first-come-first-served service discipline, and independent sequences of independent and identically distributed sequences of interarrival times and service times. We assume some partial information is known, e.g., the first two moments of inter-arrival and service time distributions. For the single-server GI/GI/1 model, we first study the tight upper bounds for the mean and higher moments of the steady-state waiting time given the first two moments of the inter-arrival time and service-time distributions. We apply the theory of Tchebycheff systems to obtain sufficient conditions for classical two-point distributions to yield the extreme values. For the tight upper bound of the transient mean waiting time, we formulate the problem as a non-convex non-linear program, derive the gradient of the transient mean waiting time over distributions with finite support, and apply classical non-linear programming theory to characterize stationary points. We then develop and apply a stochastic variant of the conditional gradient algorithm to find a stationary point for any given service-time distribution. We also establish necessary conditions and sufficient conditions for stationary points to be three-point distributions or special two-point distributions. Our studies indicate that the tight upper bound for the steady-state mean waiting time is attained asymptotically by two-point distributions as the upper mass point of the service-time distribution increases and the probability decreases, while one mass of the inter-arrival time distribution is fixed at 0. We then develop effective numerical and simulation algorithms to compute the tight upper bound. The algorithms are aided by reductions of the special queues with extremal inter-arrival time and extremal service-time distributions to D/GI/1 and GI/D/1 models. Combining these reductions yields an overall representation in terms of a D/RS(D)/1 discrete-time model involving a geometric random sum of deterministic random variables, where the two deterministic random variables have different values, so that the extremal waiting times need not have a lattice distribution. We finally evaluate the tight upper bound to show that it offers a significant improvement over established bounds. In order to understand queueing performance given only partial information, we propose determining intervals of likely performance measures given that limited information. We illustrate this approach for the steady-state waiting time distribution in the GI/GI/K queue given the first two moments of the inter-arrival time and service time distributions plus additional information about these underlying distributions, including support bounds, higher moments, and Laplace transform values. As a theoretical basis, we apply the theory of Tchebycheff systems to determine extremal models (yielding tight upper and lower bounds) on the asymptotic decay rate of the steady-state waiting-time tail probability, as in the Kingman-Lundberg bound and large deviations asymptotics. We then can use these extremal models to indicate likely intervals of other performance measures. We illustrate by constructing such intervals of likely mean waiting times. Without extra information, the extremal models involve two-point distributions, which yield a wide range for the mean. Adding constraints on the third moment and a transform value produces three-point extremal distributions, which significantly reduce the range, yielding practical levels of accuracy.