Order dispatching and vacant vehicles rebalancing for the first-mile ride-sharing problem

Given a set of transport requests to a transit station and a set of homogeneous vehicle, both geographically dispersed in a business area, the First-Mile Ride-Sharing Problem (FMRSP) consists of finding least cost vehicle routes to transport passengers to the station by shared rides as well as preventive movements of idle vehicles (i.e., rebalancing) in order to anticipate future demand. This paper formulates the problem as a mathematical optimization problem and provides methods for identifying promising rebalanacing locations. Extensive tests are performed by simulating online usage of the mathematical model to assess the impact of preventive rebalancing. The results show that rebalancing is consistently preferable both in terms of profits and service rate. Particularly, in operating contexts where the station is not centrally located, rebalancing movements increase both profits and service rates by around 30% on average.