In this study, we formulate positive and negative externalities caused by changes in the supply of shared vehicles as ride sharing games. The study aims to understand the price of anarchy (PoA) and its improvement via a coordination technique in ride sharing games. A critical question is whether ride sharing games exhibit a pure Nash equilibrium (pNE) since the PoA bound assumes it. Our result shows a sufficient condition for a ride sharing game to have a finite improvement property and a pNE similar to potential games. This is the first step to analyze PoA bound and its improvement by coordination in ride sharing games. We also show an example of coordinating players in ride sharing games using signaling and evaluate the improvement in the PoA.
According to a review of sharing studies in transportation areas @cite_14 , there are few game theory studies on externalities and coordination of players' moves in vehicle sharing problems. Traditional studies on sharing include the optimization of vehicle routes for picking up all passengers (the Dial-a-ride problem ), problems of splitting passengers' fares according to their riding distances, optimization of locations of carpool stations, and problems of relocation of carpool vehicles among stations. Those studies mainly focus on optimization problems under given moves (origins and destinations) of passengers and fixed drivers of vehicles, and therefore, do not analyze the PoA when passengers strategically choose their moves in response to the moves of other passengers and vehicles. The review states that there are no studies on coordination of players' moves to improve the efficiency of sharing or reduce the PoA.
@cite_14
2031128290
Ride-sharing services are transforming urban mobility by providing timely and convenient transportation to anybody, anywhere, and anytime. These services present enormous potential for positive societ al impacts with respect to pollution, energy consumption, congestion, etc. Current mathematical models, however, do not fully address the potential of ride-sharing. Recently, a large-scale study highlighted some of the benefits of car pooling but was limited to static routes with two riders per vehicle (optimally) or three (with heuristics). We present a more general mathematical model for real-time high-capacity ride-sharing that ( i ) scales to large numbers of passengers and trips and ( ii ) dynamically generates optimal routes with respect to online demand and vehicle locations. The algorithm starts from a greedy assignment and improves it through a constrained optimization, quickly returning solutions of good quality and converging to the optimal assignment over time. We quantify experimentally the tradeoff between fleet size, capacity, waiting time, travel delay, and operational costs for low- to medium-capacity vehicles, such as taxis and van shuttles. The algorithm is validated with ∼3 million rides extracted from the New York City taxicab public dataset. Our experimental study considers ride-sharing with rider capacity of up to 10 simultaneous passengers per vehicle. The algorithm applies to fleets of autonomous vehicles and also incorporates rebalancing of idling vehicles to areas of high demand. This framework is general and can be used for many real-time multivehicle, multitask assignment problems. In the dial-a-ride problem, users formulate requests for transportation from a specific origin to a specific destination. Transportation is carried out by vehicles providing a shared service. The problem consists of designing a set of minimum-cost vehicle routes satisfying capacity, duration, time window, pairing, precedence, and ride-time constraints. This paper introduces a mixed-integer programming formulation of the problem and a branch-and-cut algorithm. The algorithm uses new valid inequalities for the dial-a-ride problem as well as known valid inequalities for the traveling salesman, the vehicle routing, and the pick-up and delivery problems. Computational experiments performed on randomly generated instances show that the proposed approach can be used to solve small to medium-size instances. This paper is the second part of a comprehensive survey on routing problems involving pickups and deliveries. Basically, two problem classes can be distinguished. The first part dealt with the transportation of goods from the depot to linehaul customers and from backhaul customers to the depot. The second part now considers all those problems where goods are transported between pickup and delivery locations, denoted as Vehicle Routing Problems with Pickups and Deliveries (VRPPD). These are the Pickup and Delivery Vehicle Routing Problem (PDVRP – unpaired pickup and delivery points), the classical Pickup and Delivery Problem (PDP – paired pickup and delivery points), and the Dial-A-Ride Problem (DARP – passenger transportation between paired pickup and delivery points and user inconvenience taken into consideration). Single as well as multi vehicle mathematical problem formulations for all three VRPPD types are given, and the respective exact, heuristic, and metaheuristic solution methods are discussed. This study examines how conversing with passengers in a vehicle differs from conversing on a cell phone while driving. We compared how well drivers were able to deal with the demands of driving when conversing on a cell phone, conversing with a passenger, and when driving without any distraction. In the conversation conditions, participants were instructed to converse with a friend about past experiences in which their life was threatened. The results show that the number of driving errors was highest in the cell phone condition; in passenger conversations more references were made to traffic, and the production rate of the driver and the complexity of speech of both interlocutors dropped in response to an increase in the demand of the traffic. The results indicate that passenger conversations differ from cell phone conversations because the surrounding traffic not only becomes a topic of the conversation, helping driver and passenger to share situation awareness, but the driving condition also has a direct influence on the complexity of the conversation, thereby mitigating the potential negative effects of a conversation on driving. We proposed and developed a taxi-sharing system that accepts taxi passengers’ real-time ride requests sent from smartphones and schedules proper taxis to pick up them via ridesharing, subject to time, capacity, and monetary constraints. The monetary constraints provide incentives for both passengers and taxi drivers: passengers will not pay more compared with no ridesharing and get compensated if their travel time is lengthened due to ridesharing; taxi drivers will make money for all the detour distance due to ridesharing. While such a system is of significant social and environmental benefit, e.g., saving energy consumption and satisfying people's commute, real-time taxi-sharing has not been well studied yet. To this end, we devise a mobile-cloud architecture based taxi-sharing system. Taxi riders and taxi drivers use the taxi-sharing service provided by the system via a smart phone App. The Cloud first finds candidate taxis quickly for a taxi ride request using a taxi searching algorithm supported by a spatio-temporal index. A scheduling process is then performed in the cloud to select a taxi that satisfies the request with minimum increase in travel distance. We built an experimental platform using the GPS trajectories generated by over 33,000 taxis over a period of three months. A ride request generator is developed (available at http: cs.uic.edu ∼sma ridesharing) in terms of the stochastic process modelling real ride requests learned from the data set. Tested on this platform with extensive experiments, our proposed system demonstrated its efficiency, effectiveness and scalability. For example, when the ratio of the number of ride requests to the number of taxis is 6, our proposed system serves three times as many taxi riders as that when no ridesharing is performed while saving 11 percent in total travel distance and 7 percent taxi fare per rider. The Dial-a-Ride Problem (DARP) consists of designing vehicle routes and schedules for n users who specify pick-up and drop-off requests between origins and destinations. The aim is to plan a set of m minimum cost vehicle routes capable of accommodating as many users as possible, under a set of constraints. The most common example arises in door-to-door transportation for elderly or disabled people. The purpose of this article is to review the scientific literature on the DARP. The main features of the problem are described and classified and some modeling issues are discussed. A summary of the most important algorithms is provided. The k-forest problem is a common generalization of both the k-MST and the dense-k-subgraph problems. Formally, given a metric space on n vertices V, with m demand pairs ⊆ V × V and a "target" k ≤ m, the goal is to find a minimum cost subgraph that connects at least k demand pairs. In this paper, we give an O(min √n,√k )- approximation algorithm for k-forest, improving on the previous best ratio of O(min n2 3,√m log n) by Segev and Segev [20]. We then apply our algorithm for k-forest to obtain approximation algorithms for several Dial-a-Ride problems. The basic Dial-a-Ride problem is the following: given an n point metric space with m objects each with its own source and destination, and a vehicle capable of carrying at most k objects at any time, find the minimum length tour that uses this vehicle to move each object from its source to destination. We prove that an a-approximation algorithm for the k-forest problem implies an O(αċlog2 n)-approximation algorithm for Dial-a-Ride. Using our results for k-forest, we get an O(min √n,√k ċlog2 n)-approximation algorithm for Dial-a-Ride. The only previous result known for Dial-a-Ride was an O(√k log n)-approximation by Charikar and Raghavachari [5]; our results give a different proof of a similar approximation guarantee-- in fact, when the vehicle capacity k is large, we give a slight improvement on their results. The reduction from Dial-a-Ride to the k-forest problem is fairly robust, and allows us to obtain approximation algorithms (with the same guarantee) for the following generalizations: (i) Non-uniform Dial-a-Ride, where the cost of traversing each edge is an arbitrary nondecreasing function of the number of objects in the vehicle; and (ii) Weighted Diala-Ride, where demands are allowed to have different weights. The reduction is essential, as it is unclear how to extend the techniques of Charikar and Raghavachari to these Dial-a-Ride generalizations. Certain “Bus Problems” are defined as generalizations of the traveling salesman problem. The simplest result concerns the length of the tour required by a single bus to pick up and deliver n passengers from random locations to random destinations in a bounded region of the plane. It is shown that the length of the tour divided by the square root of n converges almost surely to the square root of slightly more than twice the area of the region as n goes to infinity. When several buses are available, the length of the tour is simply divided by the number of buses. The bus problems have been motivated by the practical problem of scheduling dial-a-ride transportation systems. Abstract This paper explores the likely behaviours of train passengers in an emergency evacuation and examines four crucial theoretical issues on the passengers’ evacuation, including reactive vs. proactive behaviours, cooperative vs. competitive behaviours, symmetry breaking, and route exit choice. A survey of 1134 train passengers shows that respondents are not homogeneous in their likely behaviours. Overall, they are more likely to be reactive (e.g., wait for instruction from station staff) than proactive (e.g., move to exit) in an emergency situation. We also find that people are more likely to be co-operative (e.g., helping other people) than competitive (e.g., push other passengers). Although passengers are likely to show herding or symmetry breaking behaviour (e.g., following other passengers) than symmetric behaviour (e.g., choose least crowded exit), the degree of symmetry breaking behaviour is not as high as assumed in previous mathematical models. They are also unlikely to use escalators, lifts and train tunnels in their exit route choice during an emergency escape. In terms of demographic differences in behaviours, results from the ordered logit models demonstrate that there are significant differences in the evacuation behaviours between males and females but not among the different age groups. Besides providing valuable information for developing mathematical models intended to simulate passengers’ evacuation in a train station, our findings can assist managers of emergency response in developing appropriate strategies and training, and in designing solutions and education campaigns for effective evacuation. Car manufacturers are investing heavily in Autonomous Vehicles (AVs) because of their increasing popularity. AVs employ a combination of high-tech sensors and innovative algorithms to detect and respond to their surroundings, including radar, laser light, GPS, odometer, drive-by-wire control systems, and computer vision. When a user requests for a ride share or rent, the responding AV IoT device does not have the sufficient capability to store, process, or verify each other. Currently, every AV IoT device typically needs to rely on a trusted third party, which invokes another trust issue. If the trusted third party is rogue or loses credibility, the whole system will collapse. This paper introduces Chained of Things Framework and develops a blockchain-based secure ride-sharing service between passengers and autonomous vehicles. We implement an initial prototype and provide our initial results based on a proposed protocol. Optimizing shared vehicle systems (bike-sharing car-sharing ride-sharing) is more challenging compared to traditional resource allocation settings due to the presence of complex network externalities. In particular, changes in the demand supply at any location (via dynamic pricing, rebalancing of empty vehicles, etc.) affect future supply throughout the system within short timescales. Such externalities are well captured by steady-state Markovian models, which are therefore widely used to analyze and design shared vehicle systems. However, using such models to design pricing control policies is computationally difficult since the resulting optimization problems are high-dimensional and non-convex. To this end, we develop a general approximation framework for designing pricing policies in shared vehicle systems, based on a novel convex relaxation which we term elevated flow relaxation. Our approach provides the first efficient algorithms with rigorous approximation guarantees for a wide range of objective functions (throughput, revenue, welfare). For any shared vehicle system with @math stations and m vehicles, our framework provides a pricing policy with an approximation ratio of 1+(n-1) m. This guarantee is particularly meaningful when m n, the average number of vehicles per station is large, as is often the case in practice. Further, the simplicity of our approach allows us to extend it to more complex settings. Apart from pricing, shared vehicle systems enable other control levers for modulating demand and supply, e.g. rebalancing empty vehicles, redirecting riders to nearby vehicles, etc. Our approach yields efficient algorithms with the same approximation guarantees for all these problems, and in the process, obtains as special cases several existing heuristics and asymptotic guarantees. We also extend our approach to obtain bi-criterion guarantees in multi-objective settings; we illustrate this with the example of Ramsey pricing. From a technical perspective, our work develops a new approach for obtaining control policies with approximation guarantees in steady-state Markovian models. Our approach can be distilled into the following three-step program: (i) construct an upper bound via a relaxation to the original problem that encodes essential conservation laws of the system, (ii) identify a family of control policies inducing known steady-state distributions that achieve the value of the relaxed solution in an appropriate scaling limit (in our case, state-independent policies in the limit m++), and (iii) characterize the performance loss between the finite system (i.e. fixed m) and the scaling limit. This technique may be of independent interest for other settings. Vehicles equipped with GPS localizers are an important sensory device for examining people’s movements and activities. Taxis equipped with GPS localizers serve the transportation needs of a large number of people driven by diverse needs; their traces can tell us where passengers were picked up and dropped off, which route was taken, and what steps the driver took to find a new passenger. In this article, we provide an exhaustive survey of the work on mining these traces. We first provide a formalization of the data sets, along with an overview of different mechanisms for preprocessing the data. We then classify the existing work into three main categories: social dynamics, traffic dynamics and operational dynamics. Social dynamics refers to the study of the collective behaviour of a city’s population, based on their observed movements; Traffic dynamics studies the resulting flow of the movement through the road network; Operational dynamics refers to the study and analysis of taxi driver’s modus operandi. We discuss the different problems currently being researched, the various approaches proposed, and suggest new avenues of research. Finally, we present a historical overview of the research work in this field and discuss which areas hold most promise for future research. Taxi services are a vital part of urban transportation, and a considerable contributor to traffic congestion and air pollution causing substantial adverse effects on human health. Sharing taxi trips is a possible way of reducing the negative impact of taxi services on cities, but this comes at the expense of passenger discomfort quantifiable in terms of a longer travel time. Due to computational challenges, taxi sharing has traditionally been approached on small scales, such as within airport perimeters, or with dynamical ad hoc heuristics. However, a mathematical framework for the systematic understanding of the tradeoff between collective benefits of sharing and individual passenger discomfort is lacking. Here we introduce the notion of shareability network, which allows us to model the collective benefits of sharing as a function of passenger inconvenience, and to efficiently compute optimal sharing strategies on massive datasets. We apply this framework to a dataset of millions of taxi trips taken in New York City, showing that with increasing but still relatively low passenger discomfort, cumulative trip length can be cut by 40 or more. This benefit comes with reductions in service cost, emissions, and with split fares, hinting toward a wide passenger acceptance of such a shared service. Simulation of a realistic online system demonstrates the feasibility of a shareable taxi service in New York City. Shareability as a function of trip density saturates fast, suggesting effectiveness of the taxi sharing system also in cities with much sparser taxi fleets or when willingness to share is low. The ubiquitous deployment of mobile and sensor technologies has led to both the capacity to observe human behavior in physical (offline) settings as well as to record it. This provides researchers with a new lens to study and better understand the individual decision processes that were previously unobserved. In this paper, we study decision making behavior of 11,196 taxi drivers in a large Asian city using a rich data set consisting of 10.6 million fine-grained GPS trip records. These records include detailed taxi GPS trajectories, taxi occupancy data (i.e., whether a taxi was occupied with a passenger or was vacant) and taxi drivers’ daily incomes. This capacity to use data where occupancy of the taxi is known is a distinctive feature of our data set and sets this work apart from prior work which has attempted to study driver behavior. The specific decision we focus on pertains to actions drivers take to find new passengers after they have dropped off their current passengers. In particular, we study the role of information derivable from the GPS trace data (e.g., where passengers are dropped off, where passengers are picked up, longitudinal taxicab travel history with fine-grained time stamps) observable by or made available to drivers in enabling them to learn the distribution of demand for their services over space and time. We conduct our study using a heterogeneous Bayesian learning model. We find strong heterogeneity in individual learning behavior and driving decisions, which is significantly associated with individual economic outcomes. Drivers with higher incomes benefit significantly from their ability to learn from not only demand information directly observable in the local market, but also aggregate information on demand flows across markets. Interestingly, our policy simulations indicate information that is noisy at the individual level becomes valuable after being aggregated across various spatial and temporal dimensions. Moreover, the value of information does not increase monotonically with the scale and frequency of information sharing. Finally, our study has important welfare implications in that efficient information sharing leads to an income increase among all drivers, instead of a redistribution of income between different types of drivers. Our work allows us not only to explain driver decision making behavior using these detailed behavioral traces, but also to prescribe information sharing strategy for the firm in order to improve the overall market efficiency. The capability to use a moving sensor to detect moving objects and predict their future path enables both collision warning systems and autonomous navigation. This paper describes a system that combines linear feature extraction, tracking and a motion evaluator to accurately estimate motion of vehicles and pedestrians with a low rate of false motion reports. The tracker was used in a prototype collision warning system that was tested on two transit buses during 7000 km of regular passenger service Smartphone technology enables dynamic ride-sharing systems that bring together people with similar itineraries and time schedules to share rides on short-notice. This paper considers the problem of matching drivers and riders in this dynamic setting. We develop optimization-based approaches that aim at minimizing the total system-wide vehicle miles incurred by system users, and their individual travel costs. To assess the merits of our methods we present a simulation study based on 2008 travel demand data from metropolitan Atlanta. The simulation results indicate that the use of sophisticated optimization methods instead of simple greedy matching rules substantially improve the performance of ride-sharing systems. Furthermore, even with relatively low participation rates, it appears that sustainable populations of dynamic ride-sharing participants may be possible even in relatively sprawling urban areas with many employment centers. Artificial intelligence research is ushering in a new era of sophisticated, mass-market transportation technology. While computers can already fly a passenger jet better than a trained human pilot, people are still faced with the dangerous yet tedious task of driving automobiles. Intelligent Transportation Systems (ITS) is the field that focuses on integrating information technology with vehicles and transportation infrastructure to make transportation safer, cheaper, and more efficient. Recent advances in ITS point to a future in which vehicles themselves handle the vast majority of the driving task. Once autonomous vehicles become popular, autonomous interactions amongst multiple vehicles will be possible. Current methods of vehicle coordination, which are all designed to work with human drivers, will be outdated. The bottleneck for roadway efficiency will no longer be the drivers, but rather the mechanism by which those drivers' actions are coordinated. While open-road driving is a well-studied and more-or-less-solved problem, urban traffic scenarios, especially intersections, are much more challenging. We believe current methods for controlling traffic, specifically at intersections, will not be able to take advantage of the increased sensitivity and precision of autonomous vehicles as compared to human drivers. In this article, we suggest an alternative mechanism for coordinating the movement of autonomous vehicles through intersections. Drivers and intersections in this mechanism are treated as autonomous agents in a multiagent system. In this multiagent system, intersections use a new reservation-based approach built around a detailed communication protocol, which we also present. We demonstrate in simulation that our new mechanism has the potential to significantly outperform current intersection control technology--traffic lights and stop signs. Because our mechanism can emulate a traffic light or stop sign, it subsumes the most popular current methods of intersection control. This article also presents two extensions to the mechanism. The first extension allows the system to control human-driven vehicles in addition to autonomous vehicles. The second gives priority to emergency vehicles without significant cost to civilian vehicles. The mechanism, including both extensions, is implemented and tested in simulation, and we present experimental results that strongly attest to the efficacy of this approach. Vehicle-to-Grid (V2G) is that the energy stored in the batteries of electric vehicles can be utilized to send back to the power grid. And then, the energy in the batteries of electric vehicles can move with electric vehicles (EVs). Based on above characteristics, this paper introduces the concept of a mobile electrical grid and discusses the energy routing problem. It focuses on the optimization problem of how to find routes from the energy sources to charge stations, especially, when some paths are clogged by traffic jam. A bipartite graph model is used to analyze the route problem and two algorithms are presented to compute minimal energy metric route. Both of algorithms are tested by real-world transporting data in Manhattan and the Pioneer Valley Transit Authority(PVTA). Simulations show that the method is efficient. The prospect of driverless cars wide-scale deployment is imminent owing to the advances in robotics, computational power, communications, and sensor technologies. This promises highway fatality reductions and improvements in traffic and fuel efficiency. Our understanding of the effects arising from commuting in autonomous cars is still limited. The novel concept of the loss of driver controllability is introduced here. It requires a reassessment of vehicle's comfort criteria. In this review paper, traditional comfort measures are examined and autonomous passenger awareness factors are proposed. We categorize path-planning methods in light of the offered factors. The objective of the review presented in this article is to highlight the gap in path planning from a passenger comfort perspective and propose some research solutions. It is expected that this investigation will generate more research interest and bring innovative solutions into this field. This paper proposes an optimization method of train scheduling for metro lines with a train dwell time model according to passenger demand. An optimization problem of train scheduling is established with constraints of a headway equation, passenger equation, and train dwell time equation, where the train dwell time is modeled as a function of boarding and alighting passenger volumes. The aim of the optimization problem is to minimize the waiting time of passengers and train operation cost. Lagrangian duality theory is adopted to solve this optimization problem with high dimensionality. Finally, simulation results illustrate that this method is efficient to generate the train schedule, which meets the passengers' exchanging requirements between trains and platforms. The contribution of this paper is that a dwell time model is introduced in train schedule optimization, which provides the possibility of reducing the operation cost in the precondition that the exchanging time of passengers between platforms and trains is assured.