Search

CN-121998301-A - Network vehicle-appointment real-time dispatching method and system considering uncertainty of waiting and patience of passengers

CN121998301ACN 121998301 ACN121998301 ACN 121998301ACN-121998301-A

Abstract

The invention provides a real-time dispatching method and system for network taxi taking account of uncertainty of waiting patience of passengers. The method comprises the steps of carrying out space-time meshing classification on drivers and orders based on historical operation data to obtain supply and demand categories, calculating arrival rates, average journey gains, average service occupation time length, average waiting tolerance time length and carrying capacity supply quantity of various drivers of various orders, constructing a resource allocation model based on the parameters and solving the resource allocation model to generate reference matching probability, adding real-time orders into a dynamic candidate queue after tolerance verification, eliminating overtime invalid orders, searching peripheral idle drivers and generating random traversal sequences according to the categories aiming at effective orders, calculating an order allocation threshold value according to the reference matching probability and real-time supply and demand adjustment factors, carrying out random judgment, if the judgment is passed, allocating the orders and removing the orders, otherwise, reserving the orders in the queue to wait for the next cycle to be preferentially matched, and realizing cross-cycle resource reservation. The invention effectively reduces the order loss rate caused by overtime waiting.

Inventors

  • BAO YUE
  • LU BINGYANG
  • LU JIALIANG

Assignees

  • 北京交通大学

Dates

Publication Date
20260508
Application Date
20251226

Claims (10)

  1. 1. The real-time dispatching method for the network taxi taking account of the uncertainty of waiting for the passengers is characterized by comprising the following steps: the method comprises the steps of data feature extraction and parameter construction, namely carrying out space-time gridding classification on network about car drivers and passenger orders according to historical operation data of a target service area to obtain driver supply types and order demand types; The global optimal matching distribution planning is that a resource allocation model is built and solved based on average waiting endurance time, average service occupation time, average journey income and transport capacity supply quantity, and reference matching probability between various drivers and various orders is generated; adding the passenger orders received in real time into a dynamic candidate queue for endurance verification, removing the passenger orders exceeding the average waiting endurance time in the dynamic candidate queue as invalid orders, and reserving valid orders as pending orders; According to the random traversal sequence, combining the reference matching probability and the current supply and demand adjustment factor, calculating the real-time dispatch threshold value of the current order to be processed and the current traversal driver category and executing random judgment; And (3) dispatching the order and reserving resources, namely generating a dispatching order and removing the current order from a dynamic candidate queue if the current order passes through the decision of the cyclic probabilistic matching, and reserving the current order in the dynamic candidate queue to wait for the priority processing of the next dispatching cycle if all the available driver supply types are traversed and still not passed, so as to realize the global view-based resource reservation and cross-cycle matching.
  2. 2. The method of claim 1, wherein the performing space-time gridding classification on the network about car drivers and the passenger orders according to the historical operation data of the target service area to obtain a driver supply category and an order demand category, and calculating the arrival rate, the average trip gain, the average service occupation duration, the average waiting endurance duration and the capacity supply quantity of each type of drivers based on the historical statistics data, the driver supply category and the order demand category respectively comprises: Dividing an electronic map of a target service area into a plurality of standard physical grids; Based on a plurality of standard physical grids, dividing the passenger order into different order demand categories according to the starting grid, the ending grid, the estimated amount and the order service type of the passenger order ; Dividing drivers into different driver supply categories according to current position grids of drivers and vehicle service grades And counting the belonging categories in the target service area As the capacity supply quantity The historical operation data comprise a starting point grid, a terminal point grid, estimated amount and order service type of a passenger order, a current position grid of a driver and a vehicle service level; counting order demand categories within a set history period The arrival quantity per unit time as the order arrival rate ; Travel record and driver supply category based on historical orders And order demand category Calculating the average service occupation time length comprising the receiving driving time length and the passenger carrying travel time length from the space distance between the two ; Counting order demand categories Average value of time difference of historical orders from creation time to cancellation time as average waiting endurance time 。
  3. 3. The method of claim 1, wherein the resource allocation model is built with the objective of maximizing the overall expected revenue of the system per unit time, satisfying the following constraints: setting the expected matching quantity value of various orders not to exceed the corresponding arrival total quantity; setting the sum of the time for receiving orders and service of various drivers not to exceed the online total time, wherein the service time comprises the estimated idle receiving driving time and passenger carrying travel time, and the average service occupies the time Determining that the online total duration is the capacity supply quantity Determining; the objective function is set, namely the sum of estimated gains of all matched pairs is maximized, wherein the estimated gains are obtained by subtracting the execution cost from the amount of the order; Parameter generation, namely obtaining an optimal solution of the resource allocation model as a reference matching probability The reference matching probability For characterising driver supply category in ideal global optimum And order demand category Order matching ratio between.
  4. 4. The method of claim 1, wherein the calculation formula of the real-time dispatch threshold is: Wherein, the For the real-time dispatch threshold value, In order to accommodate the factors of the demand and supply, As a reference to the probability of matching, For the order arrival rate, Waiting for the patience duration on average.
  5. 5. The method of claim 4, wherein determining whether the currently pending order passes in a cycle probabilistic matching decision is performed by: generating a single Random number of interval ; If it is Judging passing; If it is And judging that the test is not passed.
  6. 6. The method of claim 4, wherein the supply and demand adjustment factor Executing a dynamic adjustment strategy based on the order queuing length, wherein the dynamic adjustment strategy specifically comprises: Real-time monitoring system current order queuing length ; When order queuing length When exceeding a preset backlog threshold value, the supply and demand regulating factor is regulated To improve the real-time order-sending threshold value and speed up the order processing; when order queuing length When the idle threshold is lower than the preset idle threshold, the supply and demand regulating factor is reduced To reduce the real-time order taking threshold, the reserved resources match the high value orders.
  7. 7. The method of claim 1, wherein the dynamic candidate queue employs a mechanism combining micro-batching with multiple priority ordering, specifically comprising: setting a tiny atomic processing time window; Collecting all the orders to be processed in the atomic processing time window and sequencing, wherein the method comprises the steps of taking an arrival time stamp as a first keyword to perform ascending sequencing, and preferentially processing the retained orders with early arrival time; And executing the cyclic probabilistic matching decision on the ordered orders in turn.
  8. 8. A real-time dispatch system for a network taxi taking account of uncertainty of waiting for passengers, comprising: The parameter calculation module is used for carrying out space-time meshing classification on the network about car drivers and the passenger orders according to the historical operation data of the target service area to obtain driver supply types and order demand types; The offline planning module is used for constructing a resource allocation model and solving based on the average waiting endurance time, the average service occupation time, the average journey income and the transportation capacity supply quantity, and generating reference matching probabilities between various drivers and various orders; the real-time scheduling engine is used for maintaining a dynamic candidate queue, executing a cyclic probabilistic matching decision and generating a dispatch instruction; and the dynamic monitoring module is used for monitoring the system load state and updating the supply and demand adjustment factors in real time according to the dynamic adjustment strategy.
  9. 9. An electronic device, comprising: A processor; a memory storing a program; Wherein the program comprises instructions which, when executed by the processor, cause the processor to perform the steps performed by the method according to any of claims 1-7.
  10. 10. A computer storage medium, characterized in that it has stored thereon a computer program which, when executed by a processor, implements the method according to any of claims 1-7.

Description

Network vehicle-appointment real-time dispatching method and system considering uncertainty of waiting and patience of passengers Technical Field The invention relates to the technical field of intelligent traffic systems and internet scheduling, in particular to a real-time dispatching method and system for network vehicles, which consider uncertainty of waiting and patience of passengers under the scene of limited waiting and patience of passengers and randomness. Background With the development of mobile internet technology, internet-based vehicles have become an important component of urban traffic. In an online booking system, the core task is to match passenger orders (demands) arriving in real time to free drivers (supplies) to maximize platform operating efficiency and revenue. The prior network vehicle-contract order-sending technology mainly has the following limitations: (1) Greedy matching strategies yield sub-optimal in that the strategy, once found free, immediately assigns it to the current nearest or most valuable order. However, this "short-looking" strategy ignores potential opportunities in the future, often resulting in high-value long-distance orders being unavailable at the time of arrival, thereby reducing the long-term global revenue for the system. (2) The batch matching strategy responds slowly, the strategy sets a fixed time window (such as 10-30 seconds), all orders and drivers in the window are collected, and a bipartite graph matching model is constructed for solving. While this improves the quality of the match to some extent, the forced waiting window increases the waiting anxiety of the passengers, and as the concurrency increases, the high frequency graph matching calculation creates a huge stress on the system computing power, which makes it difficult to meet the millisecond real-time response demands. (3) Policy data based on reinforcement learning or random optimization has strong dependence, and in recent years, methods using Markov decision process or deep reinforcement learning have been proposed. Such methods, while theoretically superior, generally assume that the probability distribution (e.g., poisson distribution, exponential distribution) of the arrival and service times of passengers is known accurately. However, in a real operating environment, the data distribution is extremely complex and fluctuates severely due to the influence of weather, emergencies, etc., resulting in poor robustness of algorithms depending on specific distribution models. In addition, the prior art mostly assumes that the passenger will wait until it is serviced, ignoring the uncertainty of the passenger's patience (i.e., the passenger may cancel the order at any time). In fact, the residence time of the passengers is highly random and the tolerance of different types of passengers (e.g. long distance versus short distance) varies greatly. Neglecting this factor can lead to deviations in the estimates of the effective demand by the dispatch system, which can lead to mismatching of the capacity resources. Therefore, there is a need for a real-time dispatching method for network vehicles that does not require precise probability distribution information, and that can take account of global long-term benefits, and that can accommodate passenger's endurance randomness. Disclosure of Invention The invention provides a real-time dispatching method and system for a network taxi taking account of uncertainty of waiting tolerance of passengers, and aims to solve the problems of short vision of dispatching strategies, high calculation delay and strong dependence on data distribution in the prior art. According to a first aspect of the embodiment of the invention, a real-time allocation method of an network about car is provided, which considers the uncertainty of waiting for a passenger, and comprises the following steps of data feature extraction and parameter construction, wherein the network about car drivers and passenger orders are subjected to space-time gridding classification according to historical operation data of a target service area to obtain driver supply categories and order demand categories, arrival rates, average journey gains, average service occupation time length, average waiting tolerance time length and the number of capacity supplies of various drivers of the various orders are calculated respectively based on historical statistics data, the driver supply categories and the order demand categories, global optimal matching distribution planning, resource allocation models are constructed and solved according to the average waiting tolerance time length, the average service occupation time length, the average journey gains and the number of capacity supplies, reference matching probabilities between various drivers and various orders are generated, real-time order response and queue maintenance, the real-time order response and queue are carried out, the passenger orders re