关键词: 叫车接送问题, 众包模式, 网约车平台, 路径优化, 变邻域搜索算法

Abstract: In recent years, the continuous growth of urban population and economic development have brought great pressure to transportation. Due to the inability of current urban road development to accommodate the increasing number of vehicles, various regions have implemented measures such as license plate and license plate restrictions to control the number of vehicles on the roads. Under these measures, new modes of transportation have emerged as a result, and in order to meet the convenient travel needs of consumers, ride dialing services have emerged. Relying on information technology such as Internet big data, online car hailing service can arrange vehicles for passengers nearby. Compared with fixed public transport, it can flexibly meet the needs of passengers and achieve “point-to-point” transportation. This problem can be described as a ride dialing service company dispatching a group of vehicles to provide shuttle services for passengers with a time window. The vehicles need to pick up passengers at the designated departure point within a specified time window and deliver them to the designated destination, while minimizing operating costs under various constraints. Studying this scheduling problem is of certain theoretical and practical significance to develop the ride dialing industry. It enriches the research content of vehicle routing problems in theory and can provide reference for solving similar problems. In practice, it is expected to provide decision support for ride dialing platforms.
   Therefore, this article first reviews the current research status of scholars at home and abroad on this problem, summarizes the shortcomings of current research, and proposes the optimization problem of ride dialing routes considering crowdsourcing model. This article studies a ride dialing problem composed of self-owned vehicles and crowdsourced vehicles. Taking into account constraints such as time windows, vehicle capacity and the service scope of part-time drivers, the service scope of crowdsourced vehicles is used as a decision variable to minimize the additional cost of empty driving of crowdsourced vehicles to the starting point of passengers while meeting their order requirements. In addition, the total waiting time of all passengers and the compensation cost of part-time drivers are included in the optimization objectives, in order to maximize the satisfaction of passengers and part-time drivers while controlling the total cost. To effectively solve this problem, this paper first uses a greedy insertion heuristic algorithm to construct an initial solution and then designs a variable neighborhood search algorithm based on the characteristics of the problem, and three neighborhood operators are designed in the algorithm. The accuracy of the model and effectiveness of the algorithm are verified through numerical experiments at different case scales.
   The performance comparison analysis between the variable neighborhood search algorithm and CPLEX shows that CPLEX can only solve small-scale cases. As the problem size increases, the variable neighborhood search algorithm designed in this paper exhibits significant advantages, proving the effectiveness of the algorithm proposed in this paper. In the sensitivity analysis section, factors such as crowdsourcing model, crowdsourcing vehicle service radius, number of crowdsourcing vehicles and fixed compensation for crowdsourcing vehicles are analyzed. It is found that using more crowdsourcing vehicles within a certain range and expanding the service radius of crowdsourcing vehicles as much as possible can reduce the total transportation cost to a certain extent.
   The problem model studied in this article is a static deterministic model. From the characteristics of the model, future research can further consider the dynamic needs of passengers, such as an increase in passenger demand, an increase in crowdsourced vehicles, passengers canceling orders, passengers changing destinations, etc. From the perspective of solving algorithms, this article only uses the variable neighborhood search algorithm to solve this problem. Currently, with the development of big data and artificial intelligence, machine learning and other technologies can be used for data prediction and problem solving, making it more realistic.

Key words: ride dialing problem, crowdsourcing model, online ride hailing platform, route optimization, variable neighborhood search