In this paper, we consider that a private company has developed a platform to provide intercity ride-sharing (IRS) services for riders between two cities. The riders between the two cities need to provide their travel information to the platform hours in advance. The company adopts commercial vehicles to pick up riders from one city and deliver them to the other city. The vehicle routing problem of IRS (VRP-IRS) is one of the core problems in the platform’s decision making process. Due to the private nature of IRS platform, it is assumed that the platform aims to maximize the total profit of the IRS system by optimizing vehicle routing. As the IRS is long-distance travel, in order to ensure driving safety, each driver has to take a break after completing a long-distance trip. In this paper, the VRP-IRS is defined on a directed graph and formulated as a mixed integer linear programming problem. As the VRP-IRS is NP-hard, we propose a variable neighborhood search algorithm to solve the VRP-IRS. According to the characteristics of the feasible solutions to the VRP-IRS, a greedy sequential route construction method is developed to generate the initial solution. Four trip-based neighborhood operators and four rider-based local search operators are proposed to shake the current solutio
