Optimizing Mobility for Elderly and Disabled Dutch Citizens Using Taxis

In the Netherlands, 200,000 elderly and disabled citizens annually use subsidized taxi rides executed by Transvision. The day-to-day planning of up to 15,000 long-distance rides was previously a complex and daunting task split over dozens of subcontractors. Transvision, CQM, and Geodan developed an optimization solution that combines the rides into efficient taxi routes. Starting in January 2020, this solution significantly improved the mobility challenge for elderly and disabled citizens, including (1) increased punctuality and a 50% improvement in passenger satisfaction, (2) savings of 15 million driving kilometers per year, and (3) combined financial savings for all stakeholders of 60 million euros over the years 2019 to 2023 and another total of 30 million euros projected for 2024 and 2025, according to conservative estimates. Daily planning in a single batch can range from 1,000 to 15,000 rides. To construct high-quality ride plans in reasonable time for this massive-scale operations research problem, we applied classical operations research techniques viewed through a modern lens. In this paper, we explain how practical large-scale dial-a-ride problems can be solved using high-quality heuristics that exploit the power of parallel processing. Furthermore, we present new and efficient techniques to perform the required millions to billions of calculations to determine distances and driving times on the Dutch road network. We overcome several practical challenges such as (1) aligning the interests of a vulnerable passenger group and over 60 different taxi operators, (2) aligning the software that interfaces with the various companies, and (3) adapting to changing regulations and ad hoc COVID-19 measures.