Search

One of the most challenging facets of dynamic ride-sharing problems is the automated matching process, especially in large-scale networks where the number of received requests is huge. Matching users to trips is very challenging in real-time since it must happen very quickly while it must ensure high quality solutions. In this paper, we rely on an exact solving method to ensure the quality of the solution, while using AI-based techniques to limit the number of requests that we feed to the solver. More precisely, we propose a clustering method based on a new space-time shareability function to put the most shareable trips inside separate clusters. Each cluster is then managed with a proposed heuristic framework in order to solve the matching problem inside each cluster. To validate our proposal, we employ the proposed method on the network of Lyon city in France, with half-million requests in the morning peak from 6 to 10 AM. The results demonstrate that the algorithm can provide high-quality solutions in a short time for large-scale problems.

hEART 2019, 8th Symposium of the European Association for Research in Transportation, Budapest, HONGRIE, 04-/09/2019 - 06/09/2019; In recent years, intelligent transportation systems made it possible for operators to adapt in real-time the transportation supply to travel demand via new mobility services. Among these services, ride-sharing is becoming popular. The dynamic ride-sharing problem involves two sub-problems: (1) How to serve the upcoming trips (Optimal fleet management) and (2) How to accurately predict the travel times to determine vehicles availability and pick up/drop off times. In this paper, we express the optimal fleet management problem as a constrained multi objective integer linear programming. Our aim is to find the global optimal solution for the ride-sharing problem without uncertainty in demand to have a vision of these services performance in optimal situation. Then we compare the results and experiments with the exact optimal condition. We have designed an algorithm to find the exact solution for matching problem based on the branch and bound algorithm. To solve the second sub-problem, we define two different models to assess the impact of traffic conditions on the dynamic ride-sharing system performance for large-scale problems.

KES-AMSTA 2019, 13th KES International Conference Agents and Multi-agent Systems: Technologies and Applications, Saint Julian's, MALTE, 17-/06/2019 - 19/06/2019; Sharing rides can be an effective solution for traffic management in populated urban areas. Real-time ride-sharing is a dynamic and complex optimization problem. Indeed, the problem data are not known a priori in a dynamic context. However, most of the approaches in the literature consider that the missing data concerns the travelers, which are revealed online. Very few consider traffic changes during optimization or execution. More precisely, they assume that the predicted travel times used during optimization remain the same when executing the vehicle schedule, which is usually not the case in practice. In this paper, we propose a multi-agent system to solve the real-time ride-sharing problem. In this system, two models are defined to deal with dynamic traffic conditions. On the one side, the currently observed average speed in the network is used to predict travel times when calculating the optimal schedule for the ride-sharing fleet. On the other side, the traffic situation is updated every 10 seconds using a simulator as the plant model to represent the real traffic dynamics. The experimental results with real data on the city of Lyon show that the proposed multi-agent system is efficient in terms of congestion reduction, especially during peak hours and if sufficient rides are shared. The system can also reduce the providers cost with a small increase in passengers waiting time and travel time.

TRB 2019, Transportation Research Board 98th Annual Meeting, Washington DC, ETATS-UNIS, 13-/01/2019 - 17/01/2019; When assessing the dynamic ride-sharing problem, two important points should be considered. First, how the ride-sharing system serves the network demand and second, how the ride-sharing system is impacted by the network and in particular by congestion. Most of the existing approaches focus on the first point, i.e. designing the demand matching while using basic assumptions for the second point, mainly constant travel times. Furthermore, most assume that predicted travel times used for the demand-matching are observed when executing the vehicle schedule, which is usually not the case in practice. In this paper two models are defined to deal with dynamic traffic conditions: current mean speed in the network is used over the next 10 minutes to predict travel times when calculating the optimal schedule for the ride-sharing fleet. This fleet is assumed composed of autonomous cars to avoid considering constraints about the drivers. Then, cars travels are simulated and the traffic situation is updated every 10 seconds using a trip-based MFD model as the plant model to represent the traffic dynamics. Some important details are discussed: improvements in the objective functions and also traffic conditions with different values for the number of sharing, the market-rate, and pickup/drop off time window. We find out that the proposed system is really efficient in terms of reducing congestion, especially in peak hours if sufficient sharing happens. Also it can reduce the providers cost while it has small increase in passengers waiting time and travel time.

TRISTAN X, The Tenth Triennial Symposium on Transportation Analysis, Hamilton island, AUSTRALIE, 17-/06/2019 - 21/06/2019; Ride-sharing is becoming one of the most important transportation modes in many cities due to its convenience and accessibility. But it is important to assess the impact of network on the ride-sharing performance and vice versa. This paper proposes a complete framework to represent the ride-sharing system functioning. We address the problem for a city scale of 25 km2, a total market of 11,235 shareable trips over a 4 hours period with a rolling horizon of 20 minutes. Furthermore, the solutions are assessed using a dynamic trip-based macroscopic simulation to account for congestion effect and dynamic travel times that may influence the optimal solution obtained with predicted travel times. This outperforms most previous studies about optimal fleet management that usually consider constant and fully deterministic travel time functions. Then we assess the network performance under different levels of ride-sharing.