A method for solving vehicle routing problems with pickup and delivery with time windows for ride-sharing services

With the increase of population and personal tourism, traffic congestion becomes a major problem in transportation systems with limited resource. Recently, on-demand ride-sharing service have emerged as an important type of transportation service, which can help reduce the adverse effects of traffic congestion caused by driving-alone trips, and contribute to the environmental protection and sustainable development. One key issue in the optimization of on-demand ride-sharing services is how to solve a class of complex vehicle routing problems with pickup and delivery with time windows (VRPPDTW). This paper proposes a method to solve the complex VRPPDTW with large demands. The method introduces the ruin and recreate algorithm into the VRPPDTW. Considering heterogeneous vehicles with different properties including maximum loads, multi-time windows, different starting and ending nodes, and tasks with a fixed direction of pickup and delivery, a mathematical model for solving the VRPPDTW is developed. In this paper, three strategies, including radial ruin, random ruin, and sequential ruin, are designed when removing nodes, and a best insertion principle is used as the reinsertion strategy. A prototype system is developed to demonstrate the validity of the method using real data.