Multimodal commuter ride sharing with flexible interchanges and return trip planning

Abstract In suburban areas, commuters frequently use cars to get to work. Even those who commute by public transport often need a car to reach the nearest train station. This inefficient use of vehicles, which can lead to traffic congestion and overcrowded parking facilities near popular interchanges, could be mitigated by improving vehicle occupancy rates. In a ride sharing system, drivers who are willing to take on passengers can announce their planned trips in advance. Similarly, prospective passengers can enter their desired itinerary and be matched to drivers with compatible schedules and routes. The system can then find suitable meeting and interchange locations and optimizes the joint routes. We describe an algorithm for matching passengers to drivers and planning their joint routes. Given a set of itineraries for drivers and passengers, each with potentially multiple paths (via different interchanges) to their final destination, we match passengers to drivers according to schedule compatibility and proximity along these paths, find concrete travel routes for each user and determine pick-up and drop-off locations accordingly. To ensure high user satisfaction, the morning and evening commutes of each user are planned together. We evaluate this algorithm on a set of benchmark instances derived from data provided by a ride sharing company operating in the metropolitan area of Vienna and compare it to their currently implemented dynamic first-come-first-served approach.