The static ridesharing routing problem with flexible locations: A Norwegian case study

Abstract

The municipalities in the Bergen region in Norway have recently announced a pilot project for ridesharing in the region as a means to reduce traffic congestion. As part of this project, we study the Static Ridesharing Routing Problem with Flexible Locations (SRRPFL), which aims at determining efficient routes and schedules for a set of drivers to pick up and deliver passengers at different, flexible pickup and delivery locations. We present a bi-objective mixed integer programming (MIP) model for the SRRPFL where we (lexicographically) first maximize the number of passengers serviced and then minimize the total travel times. To solve real-life instances of the SRRPFL, we propose a new Adaptive Large Neighborhood Search (ALNS) heuristic. To further improve its performance, we extend the ALNS heuristic with a local search, as well as with a set partitioning problem (denoted the Route Combination Problem) that optimally recombines the routes previously encountered in the search. The ALNS heuristic is tested on a number of test instances based on real trip data and the results demonstrate its effectiveness. The results also provide a number of insights regarding the potential benefits of ridesharing in our case study.