Vehicle routing in one-way carsharing service with ridesharing options: A variable neighborhood search algorithm

Abstract

The widespread adoption of one-way carsharing systems faces a significant hurdle in the form of vehicle imbalance. To address this challenge, this study proposes a novel hybrid operator-user-based relocation scheme that integrates one-way carsharing systems with ridesharing options, enabling users to complete their trips by sharing carsharing vehicles with others. This integration necessitates the concurrent optimization of vehicle relocation routing and ridesharing matching strategies by carsharing operators. The underlying problem, termed the vehicle relocation and ridesharing matching problem, is formulated as a mixed-integer linear program with the objective of maximizing total system profit. Given the NP-hard nature of the vehicle relocation and ridesharing matching problem, a variable neighborhood search algorithm is developed for its solution. The algorithm incorporates an efficient route evaluation scheme to improve the efficiency of the algorithm. Numerical experiments demonstrate that the proposed solution method is capable of producing high-quality solutions within short computing time. We also show that the mutual benefits of the proposed integrated scheme for both carsharing operators and users, including increased profitability, reduced travel costs, and improved service quality.