Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Taxi scheduling method and system based on deep reinforcement learning

A technology of reinforcement learning and scheduling methods, applied in the field of artificial intelligence, can solve problems that are not interpretable, cannot reflect the impact of historical decisions, and do not consider the road network structure.

Active Publication Date: 2020-10-30
SHENZHEN UNIV
View PDF14 Cites 7 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

These methods have the following problems: 1) The road network structure is not considered, and the area is simply divided by a grid with a certain side length. Decision-making often does not conform to the road network structure, which may cause taxis to detour or even fail to reach, thereby reducing dispatch efficiency
2) The existing methods using reinforcement learning directly input multi-dimensional complex data into the vehicle scheduling model to obtain decision results, without separating the two independent tasks of potential order demand prediction and vehicle scheduling strategy, which greatly increases the state The complexity of the space makes it difficult for the model to converge, and it is not interpretable, and cannot intuitively reflect the relationship between taxi demand and supply in different regions
3) The existing work lacks the design of the interdependence of dispatching decisions, or the unified actions of taxis in a region, or independent decision-making, which cannot reflect the impact of historical decisions on current decisions

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Taxi scheduling method and system based on deep reinforcement learning
  • Taxi scheduling method and system based on deep reinforcement learning
  • Taxi scheduling method and system based on deep reinforcement learning

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0096] This embodiment provides a taxi scheduling method based on deep reinforcement learning, such as figure 1 As shown, the method includes the following steps:

[0097] Step 1: Formulate the road network of the selected area into a directed graph G(V,E), where each vertex v∈V represents a geographic location, that is, a road intersection, each edge e∈E represents a road segment, and each Side e obtains the travel cost by calculating cost(e) as the weight of side e.

[0098] Step 2: Apply a region clustering algorithm to pass the graph G through the classified vertices v, thereby forming a specified number of distinct regions Z i .

[0099] Such as figure 2 As shown, the clustering method of the construction region specifically includes:

[0100] First, the road network of the selected city is modeled as a directed graph G(V,E), where each vertex v∈V represents a geographic location, that is, a road intersection, each edge e∈E represents a road segment, and each Side e...

Embodiment 2

[0135] This embodiment provides a taxi dispatching system based on deep reinforcement learning, such as Figure 4 As shown, the system includes: an area building module, a demand forecasting module, a vehicle scheduling module, and a simulator;

[0136] Regional building blocks are used to build regional networks;

[0137] The demand forecasting module predicts the number of orders that will appear in any region at any time according to the regional network;

[0138] The vehicle dispatching module is responsible for the dispatching of vehicles and the training and updating of the taxi dispatching model;

[0139] The simulator simulates the external environment and trains the reinforcement deep learning algorithm based on the actual situation, as well as models the entire process of how the ride-hailing platform manages taxis and handles ride requests.

[0140] The vehicle scheduling module specifically implements the following functions:

[0141] (1) Context state:

[0142...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention relates to a taxi scheduling method and system based on deep reinforcement learning. The system comprises an area construction module, a demand prediction module, a vehicle scheduling module and a simulator. The method comprises the steps of S1 forming a regional network; S2 predicting the number of orders that will appear in any area at any time; S3 calculating the total vehicle supply of one area; obtaining a demand / supply state of each area; and S4 inputting the states of the area where any idle vehicle is located and the neighbor area into a trained taxi scheduling model to obtain a scheduling strategy of the vehicle, and determining whether the vehicle is continuously left in the local area or scheduled to the neighbor area specified by the system. According to the invention, idle taxis are dispatched, the success rate of order matching is increased, the waiting time of passengers is reduced, and the utilization rate of taxis is improved.

Description

technical field [0001] The present invention relates to the technical field of artificial intelligence, and more specifically, to a taxi dispatching method and system based on deep reinforcement learning. Background technique [0002] The emergence of large-scale modern ride-hailing platforms will greatly benefit our daily travel, allowing passengers to book travel plans in advance and match available taxis with ride requests in real time. Although such a system can serve millions of ride requests and tens of thousands of taxis in the city every day, there will still be a large number of requests that cannot be served every day due to the lack of available taxis nearby for some passengers. On the other hand, in other places, there may be a large number of idle taxis looking for passengers, causing a waste of taxi resources. The imbalance between supply and demand of taxis among different geographic locations in cities is common, which will seriously reduce the efficiency of...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
IPC IPC(8): G08G1/00G08G1/01
CPCG08G1/202G08G1/0104G08G1/0137
Inventor 刘志丹李江舟伍楷舜
Owner SHENZHEN UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com