关键词: 网约车调度, 实时订单选择, 在线问题, 竞争比

Abstract: With the rapid development of Internet technology, the online car-hailing industry is also growing, gradually becoming the primary choice for urban residents to travel. However, with the gradual expansion of the scale of online car-hailing, online car-hailing platforms need to effectively match a large number of random orders, and it is difficult for the current scheme to meet the requirements for effective order scheduling. In reality, in order to pursue higher order profits, the phenomenon of “rejecting orders” emerges constantly, which reduces the satisfaction of passengers and the efficiency of vehicle scheduling. In order to improve the response rate of online car-hailing orders and optimize the vehicle scheduling scheme of online car-hailing platforms, this paper uses online algorithms and competition analysis methods to design online strategies to optimize the order decision-making of online car-hailing drivers and improve the income of drivers.
Most online car-hailing platforms in the market now have two basic order matching systems: Assigning Mode and Grabbing Mode, and the corresponding order services are Real-time Order Service and Reservation Order Service.
According to the billing rules of the car-hailing companies, when the travel distance of the order exceeds a certain distance, an additional unit price will be charged according to the original billing rules according to the excess distance. This distance is named as the Empty Drive Distance, and the charge is called the Empty Drive Fee.
This paper discusses the situation where drivers receive real-time orders under assigning mode, and the driving distance of the order is less than the empty drive distance, that is, no empty drive fee will be charged. For drivers, whether they use assigning mode or grabbing mode for order service, only when the online car-hailing platform transmits the passenger order information to the driver and will they know the corresponding service information: the service time of the order, the starting place and destination, the driving distance of order, the driving time of order and the estimated revenue available for serving the order.And they need to immediately decide whether to serve the order based on the above service information. This type of decision maker needs to make decisions about the current state when the future information is partially known or unknown, which is suitable for solving by using online algorithms and competitive analysis methods.
Online algorithms and competitive analysis methods are mainly used in the field of optimization. The essence of optimization theory is the optimization theory, which is an effective algorithm for solving decision problems under incomplete information. The theory of online algorithms and competitive strategy was first used to solve problems related to machine scheduling, and then ones in the field of computer and finance. As uncertain decision-making problems, online ones are widely used in various fields in real life, such as leasing, procurement, scheduling and so on.Many researches on vehicle scheduling problems are carried out on the basis of in-depth researches on traveling salesman problems.
According to the method of online algorithm and strategy analysis, after describing the problem of online real-time order selection for online car-hailing drivers and making environmental assumptions, the lower bound of the competitive ratio of this problem is analyzed by analyzing the ratio of the minimum order revenue of online drivers and the maximum revenue of offline drivers. Then, the Profit Threshold strategy (PT strategy) is designed, and by analyzing the competitive ratio lower bound of the strategy, it is proved that online drivers could avoid getting the worst returns by using the PT strategy. Finally, a simple arithmetic case analysis is conducted through Python to demonstrate the practical effect of the designed PT strategy by comparing the total value of the driver’s work gain and the competitive ratio with the lower bound of the competitive ratio.
The research results of this paper have certain management implications for improving the benefits and work efficiency of car-hailing drivers, platforms and governments. It not only provides suggestions and guidance for improving the benefits of real-time order decision-making for drivers, but also reduces the safety risks of distracted order selection by drivers while driving. Moreover, by reducing the driver’s rejection rate, the scheduling efficiency of the car-hailing platform is improved. Residents’ satisfaction with online car travel has increased, which has also increased the probability of choosing online car travel, and alleviated the environmental governance problems caused by a large number of private cars. Further research from more types of orders may be considered in the future.

Key words: car-hailing dispatch, real-time order selection, online problems, competitive ratio