CN112129306B

CN112129306B - Route generation method, route generation device, computer equipment and storage medium

Info

Publication number: CN112129306B
Application number: CN202011015613.4A
Authority: CN
Inventors: 李大韦; 宋玉晨; 杨敏; 刘向龙
Original assignee: Tencent Technology Shenzhen Co Ltd; Southeast University
Current assignee: Tencent Technology Shenzhen Co Ltd; Southeast University
Priority date: 2020-09-24
Filing date: 2020-09-24
Publication date: 2024-05-28
Anticipated expiration: 2040-09-24
Also published as: CN112129306A

Abstract

The application relates to a route generation method, a route generation device, a computer device and a storage medium. The method relates to a path planning technology integrating a plurality of travel modes, and comprises the following steps: acquiring travel information and travel preference information; determining a multi-layer traffic network corresponding to a geographic position related to the travel information, wherein the multi-layer traffic network comprises a road sub-network, a walking sub-network and a public traffic sub-network; inquiring the passing time length among all network nodes in different sub-networks of the multi-layer traffic network; and generating a travel route matched with the travel information according to the travel preference information and the travel time based on the multilayer traffic network, wherein a sequence formed by travel mode identifiers corresponding to a plurality of travel modes adopted by the travel route is a feasible sequence in a travel mode state transition model. By adopting the method, the travel route considering various travel modes can be generated.

Description

Route generation method, route generation device, computer equipment and storage medium

Technical Field

The present application relates to the field of computer technologies, and in particular, to a route generating method, apparatus, computer device, and storage medium.

Background

With the rapid development of intelligent transportation technology, some map software on the market can generate travel paths based on user demands. Specifically, the user can set a starting point and an ending point according to the needs of the user, and the route planning algorithm adopted by the map software can generate a corresponding travel route for the user according to the shortest transit time, the shortest distance or the least transfer times.

However, the route generated by the method generally only relates to a single travel mode, and the combination of multiple travel modes which can be adopted by people in real life is omitted. The mode does not consider that the user can combine a plurality of travel modes, so that an optimal path with better passing efficiency cannot be provided for the user.

Disclosure of Invention

In view of the foregoing, it is desirable to provide a route generation method, apparatus, computer device, and storage medium that can take into account a plurality of travel modes.

A route generation method, the method comprising:

Acquiring travel information and travel preference information;

determining a multi-layer traffic network corresponding to a geographic position related to the travel information, wherein the multi-layer traffic network comprises a road sub-network, a walking sub-network and a public traffic sub-network;

inquiring the passing time length among all network nodes in different sub-networks of the multi-layer traffic network;

And generating a travel route matched with the travel information according to the travel preference information and the travel time based on the multilayer traffic network, wherein a sequence formed by travel mode identifiers corresponding to a plurality of travel modes adopted by the travel route is a feasible sequence in a travel mode state transition model.

A route generation device, the device comprising:

The acquisition module is used for acquiring travel information and travel preference information;

The determining module is used for determining a multi-layer traffic network corresponding to the geographic position related to the travel information, wherein the multi-layer traffic network comprises a road sub-network, a walking sub-network and a public traffic sub-network;

the inquiry module is used for inquiring the passing time length among all network nodes in different sub-networks of the multi-layer traffic network;

the generation module is used for generating a travel route matched with the travel information according to the travel preference information and the travel duration based on the multilayer traffic network, wherein a sequence formed by travel mode identifiers corresponding to a plurality of travel modes adopted by the travel route is a feasible sequence in a travel mode state transition model.

A computer device comprising a memory storing a computer program and a processor which when executing the computer program performs the steps of:

Acquiring travel information and travel preference information;

A computer readable storage medium having stored thereon a computer program which when executed by a processor performs the steps of:

Acquiring travel information and travel preference information;

The route generation method, the device, the computer equipment and the storage medium are characterized in that the multi-layer traffic network comprises a road sub-network, a walking sub-network and a public traffic sub-network, and can provide support for generating travel routes comprising a plurality of different travel modes; the travel mode state transition model defines a reasonable and feasible combination sequence corresponding to various travel modes, and ensures that the generated travel route comprising the various travel modes accords with the travel habit of people. After the travel information and the travel preference information of the user are acquired, the passing duration between each network node in different sub-networks of the multi-layer traffic network is queried, so that path planning can be performed according to the passing duration between each network node based on the multi-layer traffic network, the travel preference information of the user can be considered during path planning, various travel modes and the feasibility of transformation among the various travel modes can be considered, and the generated route matched with the travel information accords with the user preference and is efficient and feasible.

Drawings

FIG. 1 is an application environment diagram of a route generation method in one embodiment;

FIG. 2 is a flow diagram of a route generation method in one embodiment;

FIG. 3 is a schematic diagram of a traffic network in one embodiment;

FIG. 4 is a schematic diagram of a multi-layer traffic network generated in one embodiment;

FIG. 5 is a schematic illustration of a road segment defined in one embodiment;

FIG. 6 is a schematic diagram of a travel mode state transition model in one embodiment;

FIG. 7 is a schematic diagram of path planning using label correction in one embodiment;

FIG. 8 is a schematic diagram of a way segment list update process in one embodiment;

FIG. 9 is a schematic frame diagram of a method for generating travel routes in one embodiment

FIG. 10 is a schematic diagram of a multi-layer traffic network generated in one particular embodiment;

FIG. 11 is a block diagram showing the construction of a route generating device;

fig. 12 is an internal structural diagram of a computer device in one embodiment.

Detailed Description

The present application will be described in further detail with reference to the drawings and examples, in order to make the objects, technical solutions and advantages of the present application more apparent. It should be understood that the specific embodiments described herein are for purposes of illustration only and are not intended to limit the scope of the application.

The route generation method provided by the application can be applied to an application environment shown in figure 1. Wherein the terminal 102 communicates with the server 104 via a network. The terminal 102 can acquire travel information and travel preference information input by a user and then send the travel information and the travel preference information to the server 104, and the server 104 receives the travel information and the travel preference information sent by the terminal 102 and determines a multi-layer traffic network corresponding to the geographic position related to the travel information, wherein the multi-layer traffic network comprises a road sub-network, a walking sub-network and a public traffic sub-network; inquiring the passing time length among all network nodes in different sub-networks of the multi-layer traffic network; and generating a travel route matched with the travel information according to the travel preference information and the travel time based on the multilayer traffic network, wherein a sequence formed by travel mode identifiers corresponding to various travel modes adopted by the travel route is a feasible sequence in the travel mode state transition model. The terminal 102 may be, but not limited to, various personal computers, notebook computers, smartphones, tablet computers, and portable wearable devices, and the server 104 may be implemented by a stand-alone server or a server cluster composed of a plurality of servers. The server 104 may be a server of MaaS (Mobility AS A SERVICE, travel as a service) platform.

In a specific application scenario, a user can input travel information and travel preference information of the user through a map client, and after the map client sends the travel information and the travel preference information input by the user to a server, the server returns a corresponding travel route.

It can be understood that before the server performs route planning, a traffic network needs to be generated, and a traffic distance, a traffic duration, travel fees corresponding to different travel modes and the like corresponding to road sections between network nodes in the traffic network are acquired, so that a reasonable travel route can be planned for a user based on the information.

In one embodiment, as shown in fig. 2, a route generating method is provided, which is described by taking as an example that the method is applied to the computer device (the terminal 102 or the server 104) in fig. 1, and includes the following steps:

step 202, obtaining travel information and travel preference information.

The travel information is information comprising at least one group of travel data, and the travel data comprises a start point and an end point of travel. The travel information may include only one set of travel data including a start point and an end point of the user's travel plan. The trip information may also be trip information of the user on the whole day, where the trip information of the whole day includes a plurality of sets of trip data, and the plurality of sets of trip data are connected in series to form a trip process of the user on the whole day, and an end point of the preceding trip data is a start point of the following trip data, for example, the first set of trip data is: from location a to location B, the second set of travel data is from location B to location C, and the third set of travel data is from location C to location a. In order to be able to plan a travel route for the user more accurately, the travel information may also comprise a time window corresponding to the travel data, i.e. a start-stop time, i.e. a start time from a start point in the travel data and an arrival time at an end point of the travel data. The starting point and the end point of the travel data can be expressed by longitude and latitude.

The travel preference information is information related to user travel preferences. The travel preference information can comprise whether the user uses the private car, whether the user rides the private bicycle, whether the user needs to go to a parking lot to get the car and whether the user needs to go to a parking spot to park in the process of returning when the user starts the car, and the like, and the travel preference information relates to the travel process of the user, so that a more detailed travel route meeting the user requirement can be generated for the user. The travel preference information may further include at least one of a transfer number upper limit value, a travel fee upper limit value, a walking distance upper limit value, and a riding distance upper limit value acceptable to the user, and such travel preference information may be used to generate a travel route conforming to the travel demand of the user. It should be noted that, the travel preference information may be set for the whole travel information, for example, the user may require that the travel cost of the whole day cannot exceed the set travel cost upper limit value; the travel preference information may be set for each travel data in the travel information, for example, the user may request that the travel cost of a certain set of travel data in the travel information cannot exceed the set travel cost upper limit value.

Specifically, the computer device may acquire travel information and travel preference information input by the user, and may also acquire travel information and travel preference information sent by other computer devices. The computer equipment can also obtain the current position of the user through the positioning device, take the current position of the user as a starting point in travel information, and then obtain an end point input by the user. And the computer equipment performs subsequent path planning according to the obtained travel information and the travel preference information of the user.

Step 204, determining a multi-layer traffic network corresponding to the geographic position related to the travel information, wherein the multi-layer traffic network comprises a road sub-network, a walking sub-network and a public traffic sub-network.

When the embodiment of the application is applied to path planning in cities, the geographic position related to the travel information can be a target city, and the corresponding multilayer traffic network is a road network corresponding to the target city. When the embodiment of the application is applied to the path planning across cities, the geographic position related to the travel information can be a target province, the corresponding multilayer traffic network is a road network corresponding to the target province, and the multilayer traffic network corresponding to the target province can be obtained by connecting the multilayer traffic networks corresponding to a plurality of cities in the province. The embodiment of the application is mainly described by taking path planning in cities as an example.

The traffic network used in the traditional path planning technology is single, only the route which the user needs to pass through for self-driving and public transportation service taking by the user is considered, and the multi-layer traffic network in the application is different from the single traffic network used in the traditional path planning technology, and the multi-layer traffic network considers the road network which needs to be used in various travel modes, so that all travel modes can be considered when the path planning is carried out. The multi-layer traffic network includes a road sub-network, a walking sub-network, and a public traffic sub-network. The public transportation subnetwork may include a bus subnetwork and a subway subnetwork. The network nodes in the road sub-network are road nodes, the road nodes comprise road stop points and parking points, and the road nodes are connected with each other by road sections. The network nodes in the walking sub-network are walking nodes, the walking nodes comprise road stop points, parking points and public transportation stations, and the walking nodes are connected with each other by road sections. The network nodes in the public transportation sub-network are public transportation nodes, the public transportation nodes comprise public transportation stations, such as bus stations and subway stations, and the public transportation nodes are connected with the public transportation nodes by road sections.

Before a travel route is generated according to travel information of a user, a multi-layer traffic network corresponding to a geographic position related to the travel information needs to be built in advance, and the generated multi-layer traffic network can provide support for generating the travel route comprising a plurality of different travel modes. In one embodiment, the route generation method further comprises a step of constructing a multi-layer traffic network, the step comprising:

Acquiring map data of a geographic position; generating a road sub-network according to the map data, wherein the road sub-network comprises road nodes and road sections between the road nodes, and the road nodes comprise road stop points and parking points; generating a walking sub-network according to the map data, wherein the walking sub-network comprises walking nodes and road sections between the walking nodes, and the walking nodes comprise road stop points, parking points and public transportation stations; generating a public transportation sub-network according to the map data and the public transportation line data, wherein the public transportation sub-network comprises public transportation nodes and road sections between the public transportation nodes, and the public transportation nodes comprise public transportation sites; connecting the road sub-network with the walking sub-network according to the road stop points and the parking points, and connecting the walking sub-network with the public transportation sub-network according to the public transportation stations to obtain the multi-layer transportation network.

The computer device may obtain map data of the target geographic location, and obtain, according to the map data, connection relationships presented by locations of the respective sites and the roads on the map, thereby generating a multi-layer traffic network. Specifically, the road subnetwork may be generated according to a connection relationship between the road stop point and the parking point in the map data, the walking subnetwork may be generated according to a connection relationship between the road stop point, the parking point and the public transportation station in the map data, and the public transportation subnetwork may be generated according to a connection relationship between the map data and the public transportation station presented in the public transportation route data. The walking sub-network is generated on the basis of the road sub-network, a user can walk in any closed loop formed by the road stop points, the parking points and the public transportation stations, and the public transportation sub-network needs to be matched with the road sub-network. In one embodiment, the computer device may obtain map data for the target geographic location according to the Open source map service of Open STREET MAP.

In one embodiment, generating a public transportation sub-network from map data and public transportation line data includes: acquiring the order of public transportation stations of a public transportation line according to the public transportation line data; obtaining geographic coordinates of public transportation sites of a public transportation line according to the map data; and matching the public transportation sites with the road sub-network according to the sequence and the geographic coordinates, and generating the public transportation sub-network comprising the public transportation sites and road sections between the public transportation sites.

The geographical coordinates of the public transportation sites can be represented by longitude and latitude coordinates, the computer equipment can acquire public transportation line data from the network, the public transportation line data comprise the longitude and latitude of the public transportation sites and the sequence of the public transportation sites on the public transportation lines, the computer equipment needs to match the public transportation sites with corresponding places in the road sub-network, namely, after mapping the public transportation sites to corresponding road nodes in the road sub-network, an actual public transportation line is generated, and the public transportation sub-network is generated according to the actual public transportation line and the public transportation sites. It should be noted that, for a bus route, the transit time period between public transportation stations may not be fixed, whereas for a subway route, the transit time period between subway stations is usually a fixed value.

Referring to fig. 3, a schematic diagram of a traffic network in one embodiment is shown in fig. 3, and the traffic network includes six road stop points 1 to 6, one parking point 7, and six public transportation stations a1, a2, b1, b2, c1, c2, where the six public transportation stations correspond to two public transportation lines a-b and a-c.

As shown in fig. 4, a schematic diagram of a multi-layer traffic network generated according to an embodiment is shown, wherein the multi-layer traffic network is generated according to the traffic network shown in fig. 3, first, a road sub-network is generated according to road stops 1 to 6, parking points 7 and road segments between them, a walking sub-network is generated according to road stops 1 to 6, parking points 7, six public transportation stations and road segments between them, a public transportation sub-network is generated according to six public transportation stations and road segments between them, then the road sub-network is connected with the walking sub-network through the road stops 1 to 6 and the parking points 7, and the multi-layer traffic network is obtained after the walking sub-network is connected with the public transportation sub-network through the public transportation stations a1, a2, b1, b2, c1 and c 2.

In this embodiment, the multi-layer traffic network considers road networks required to be used by various travel modes, including a road sub-network, a walking sub-network and a public traffic sub-network, so that various travel modes can be considered when path planning is performed.

In the above-described embodiment, the multi-layered traffic network includes sub-networks corresponding to travel modes using public traffic, private traffic, walking, and the like, that is, a public traffic sub-network, a road sub-network, and a walking sub-network. In other embodiments, the multi-layer traffic network may also include sub-networks corresponding to private travel services (private transport service) provided by other companies, referred to as private traffic sub-networks, which are connected to walking sub-networks. The private traffic nodes of the private sub-network also belong to walking nodes in the walking sub-network, and the private sub-network can be similar to the road sub-network, connected with the walking sub-network through the private traffic nodes, and can also be similar to the public traffic sub-network, and connected with the walking sub-network through public traffic stations.

In one embodiment, the walking nodes in the walking subnetwork further comprise private traffic nodes, and the method further comprises: acquiring private traffic road data corresponding to private traffic services; generating a private traffic sub-network according to the private traffic road data, wherein the private traffic sub-network comprises a private traffic node and a road section between the private traffic nodes; connecting the road sub-network with the walking sub-network according to the road stop points and the parking points, and connecting the walking sub-network with the public transportation sub-network according to the public transportation stations to obtain the multi-layer transportation network, wherein the multi-layer transportation network comprises the following steps: connecting the road sub-network with the walking sub-network according to the road stop points and the parking points, connecting the walking sub-network with the public transportation sub-network according to the public transportation stations, and connecting the private transportation sub-network with the walking sub-network according to the private transportation nodes to obtain the multi-layer transportation network.

The private traffic service data is data related to a private travel service process and is used for generating a private traffic sub-network. For example, when the private transportation service is a private car rental service, the private transportation service data includes the geographical location of the car rental points and the car rental fees, and in particular, the private car rental service may provide the car rental service to the user, and when the user needs to go through the car rental, the user needs to go to the rental points of the private car rental service to rent the car, so the computer device may take these rental points as the private transportation nodes, generate the private transportation subnetworks corresponding to the private car rental service according to the geographical location of the private transportation nodes, and connect the generated private transportation subnetworks with the walking subnetworks through the rental points, wherein the car rental fees are used to calculate the travel fees corresponding to the travel mode.

For another example, when the private transportation service is a private taxi service, the private transportation service data includes a road stop and a parking spot within a service range of the private taxi service, and further includes a pricing rule, specifically, the private taxi service may provide a taxi service to a user, and when the user needs to go out in such a manner, the user needs to walk to the road stop or the parking spot to taxi, and thus, the private transportation sub-network is similar to the road sub-network, the computer device may take the road stop and the parking spot within the service range as the private transportation node, generate the private transportation sub-network corresponding to the private taxi service according to a geographical position of the private transportation node, and connect the private transportation sub-network with the walking sub-network through the road stop and the parking spot, wherein the pricing rule is used for calculating a travel fee corresponding to the manner.

For another example, when the private transportation service is a customized class car service provided to a user, the private transportation service data includes a route and a fee corresponding to the customized class car, and stop points and road segments in the route are used to generate a corresponding private transportation sub-network linked to the public transportation sub-network type through the stop points in the route.

In this embodiment, by acquiring the private traffic service data provided by different private traffic services to generate corresponding private traffic sub-networks and connecting the generated private traffic sub-networks with the road sub-network or the walking sub-network, a multi-layer traffic network including rich travel modes can be obtained, and thus, during path planning, the rich travel modes can be considered to provide users with as many travel choices as possible.

The multi-layer traffic network comprises network nodes and road segments between the network nodes, wherein the road segments can be understood as edges between the network nodes, and when two network nodes are connected through the edges, the two network nodes are adjacent. The embodiment of the application mainly aims at the shortest passing time to carry out path planning although a plurality of limiting conditions are considered when the path planning is carried out, so the weights of the edges between the network nodes are expressed by the passing time in different modes. For example, in the road subnetwork, the weight of the edge between the road stop points may be the corresponding traffic duration when the road stop points pass through in a driving manner, the corresponding traffic duration when the road stop points pass through in a walking manner, or the corresponding traffic duration when the road stop points pass through in a riding manner.

In one embodiment, a data structure such as an adjacency matrix, adjacency table, or linked list may be used to store the connection relationships between network nodes and the weights of road segments between network nodes in a multi-layer traffic network. For example, a two-dimensional matrix may be used to represent the topology of the multi-layer traffic network, where the rows and columns of the two-dimensional matrix each represent a network node in the multi-layer traffic network, and if a value exists at the intersection of row pm of the matrix with column pn of the matrix, this indicates that network node pm is a neighboring network node to network node pn, and this value represents the weight of the edge from network node v to network node w; if there is no value at the intersection of row pm of the matrix with column pn of the matrix, it is indicated that network node pm is a non-adjacent network node to network node pn. For another example, the topology relationship of the multi-layer traffic network may be implemented by using an adjacency list, and if there is an adjacent network node b in the network node a corresponding to the header, the adjacent network node b is sequentially stored in a unidirectional linked list pointed by the header, and the weight of the edge between the network node a and the network node b is recorded in the unidirectional linked list.

Step 206, inquiring the passing time length between each network node in different sub-networks of the multi-layer traffic network.

As mentioned above, in the embodiment of the present application, although many constraint conditions are considered when the path planning is performed, the path planning is performed mainly by taking the shortest traffic duration as the target, so when the path planning is performed by using the planning algorithm, the traffic duration between each network node in the multi-layer traffic network needs to be acquired, so as to find the travel route with the shortest traffic duration on the premise of meeting the travel preference of the user.

It should be noted that the traffic duration may be a generalized traffic duration obtained according to data statistics, for example, for a driving mode, the traffic duration of a road section may be a value determined according to an average traffic time of the road section, for a walking mode, the traffic duration may be a value determined based on an average pace of a large number of users, and for a riding mode, the traffic duration may be a value determined based on an average riding speed of a large number of users. In other embodiments, for driving mode, the traffic duration may be a real-time traffic duration queried according to real-time road traffic conditions, for walking mode, the traffic duration may be a value determined according to the length of the road segment after determining the pace of the current user according to the historical walking data of the current user, and for riding mode, the traffic duration may be a value determined according to the length of the road segment after determining the pace of the current user according to the historical riding data of the current user.

In one embodiment, querying a time of flight between each network node in different sub-networks of a multi-layer traffic network includes: inquiring the passing time length among road nodes in a road sub-network of the multi-layer traffic network; inquiring the passing time length among all walking nodes in a walking sub-network of the multi-layer traffic network; inquiring the running time length and the vehicle frequency of each public transportation line among public transportation nodes in a public transportation sub-network of the multi-layer transportation network, and calculating the passing time length among the public transportation nodes according to the running time length and the vehicle frequency of each public transportation line.

Specifically, the computer device may obtain the traffic duration between the road nodes in the sub-network through some map real-time services, for example, the traffic duration corresponding to the current moment or the travel time in the travel information of the user may be obtained by using the Web API service provided by the open platform of the german, and the traffic duration of the road may be stored or calculated by using the database of the open platform. The traffic duration between the walking nodes in the walking sub-network can be calculated according to the walking distance and the generalized walking speed, and then the traffic duration is used as the weight of the edges between the walking nodes to be recorded in the walking sub-network.

When the public transportation sub-network is a subway rail sub-network, the public transportation nodes are subway stations, the traffic duration between the public transportation nodes, namely the subway stations, is usually a fixed value, and the computer equipment can record the traffic duration between the stations of the subway line as the weight of the edges between the public transportation nodes into the subway rail sub-network after inquiring the traffic duration between the stations from the network.

When the public transportation sub-network is a public transportation sub-network, as various public transportation lines may be available between the public transportation stations and the public transportation stations, the user usually takes the public transportation line which arrives preferentially when waiting at the public transportation stations, but the specific public transportation line which arrives preferentially at the public transportation stations is uncertain, so that the passing duration between the public transportation stations and the public transportation stations is uncertain, and therefore, the passing duration between the public transportation stations in the public transportation sub-network needs to be redefined.

For the case that a plurality of reachable public transportation lines exist between two public transportation stations, the computer device defines the type of the road section between the two public transportation stations as a super road section, namely, when a road section ei from a public transportation station i to another public transportation station j exists a plurality of reachable public transportation lines, the passing duration of the road section ei is uncertain, and the road section ei is defined as a super road section. As shown in fig. 5, which is a schematic diagram of the road segment defined in one embodiment, there are three bus routes j1, j2 and j3 at the bus stop i, which can travel to the destination j of the user.

In one embodiment, calculating the transit time between the public transportation nodes according to the travel time and the vehicle frequency of each public transportation line comprises: when a plurality of public transportation lines exist between a first station in the public transportation sub-network and a second station in the public transportation sub-network, marking a road section from the first station to the second station in the public transportation sub-network as a super road section; acquiring the vehicle frequency of each public transportation line in a plurality of public transportation lines; acquiring the driving time length of each public transport line from a first station to a second station; obtaining the joint vehicle frequency of the super road section according to the vehicle frequency of each public transport line; determining average waiting time corresponding to the first station according to the combined vehicle frequency; determining the probability of each public transportation line as a first line reaching a first station according to the vehicle frequency of each public transportation line and the combined vehicle frequency; and calculating the traffic duration of the road section between the first station and the second station according to the average waiting time, the probability and the running duration.

Specifically, when there are a plurality of public transportation lines between the first station and the second station, the computer device may determine a transit time of the road section between the two stations according to a frequency of vehicles combining each public transportation line and a travel time from the first station and the travel to the second station through each public transportation line. Defining a road section from a first station i to a second station j as ei, ei= (i, j), wherein a plurality of public transportation lines exist between the first station i and the second station j, and in the process of taking a bus by a user, the public transportation lines arrive at the public transportation stations on the assumption that the user arrives at each public transportation station randomly and the user takes the public transportation line arriving at the public transportation station on the first arrival, and the public transportation lines are mutually independent, so that the public transportation lines arrive at the public transportation stations and obey exponential distribution.

Let ei denote the road segment between the first station i and the second station j, θ _k denote the vehicle frequency of the public transportation line k, and c (i, j _k) denote the travel time of the vehicle of the public transportation line k from the first station i to the second station j

f(ei)＝∑θ_k；

w(ei)＝1/f(ei)；

p(ei,k)＝θ_k/f(ei)；

Where f (ei) represents the joint vehicle frequency of multiple reachable public transportation lines between the first station i and the second station i, and w (ei) represents the average waiting time of the vehicles waiting for reaching the second station j at the first station i by the user; p (ei, k) represents the probability that the public transportation line k is the first line to reach the first station i; Representing a desired passage duration of the bypass segment ei between the first station i and the second station j; vj represents the shortest transit time from the second station j to the destination, vi represents the shortest transit time from the first station i to the destination. When the computer equipment performs path planning, after the shortest passing time length Vj from the second station j to the terminal point is obtained, the shortest passing time length Vi from the first station i to the terminal point can be obtained by inquiring the passing time length of the super road section between the first station i and the second station j.

In one embodiment, calculating the transit time between the public transportation nodes according to the travel time and the vehicle frequency of each public transportation line comprises: when only one public transportation line exists between a first station in the public transportation sub-network and a second station in the public transportation sub-network, marking a road section from the first station to the second station in the public transportation sub-network as a common road section; acquiring a driving time length from a first station to a second station; the driving duration is taken as the traffic duration of a common road section between the first station and the second station.

Specifically, for the case where there is only one reachable public transportation route between two public transportation stations, the computer device defines the type of the road section between the two public transportation stations as a common road section, in which case the traffic duration of the road section between the first station and the second station can be directly represented by the travel duration C (i, j) of the vehicle of the public transportation route, and then the shortest traffic duration Vi from the first station i to the destination can be represented by the following formula:

Vi＝Vj+C(i，j)。

In the embodiment, the vehicle frequency and the driving time length of a plurality of bus routes corresponding to the super road section between the first station and the second station are combined to determine the passing time length between the two stations, so that the weight of the edges between public transportation nodes in the public transportation sub-network can be more accurately represented, and support is provided for generating more reasonable travel routes.

Step 208, generating a travel route matched with the travel information according to the travel preference information and the travel time based on the multilayer traffic network, wherein a sequence formed by travel mode identifiers corresponding to a plurality of travel modes adopted by the travel route is a feasible sequence in the travel mode state transition model.

The travel mode state transition model is used for restraining the transition between different travel modes, and is essentially a possible sequence formed by the marks corresponding to the plurality of feasible travel modes. In order to support the generation of travel routes in a plurality of travel modes, the computer device may construct the travel mode state transition model in advance so as to be present. After the travel mode state transition model is constructed, path planning can be performed by taking the shortest passing time as a target based on the pre-generated multilayer traffic network, the travel mode state transition model, travel information of a user and travel preference information, and a travel route matched with the travel information is generated.

In one embodiment, the method further includes the step of generating a travel mode state transition model: acquiring travel mode identifiers corresponding to preset various travel modes; acquiring transfer limiting conditions for restricting a change of a travel mode in a travel process; the travel mode identification sequence meeting the transfer limiting condition is used as a feasible sequence; and generating a travel mode state transition model according to the feasible sequence.

The preset travel modes are travel modes commonly used when people go out, and can comprise travel modes such as walking, private single cars, shared single cars, subway rail transit, road surface public transit, private cars, shared cars and transfer, wherein transfer refers to transfer between stations of the subway rail transit, transfer between stations of the road surface public transit or transfer between stations of the subway rail transit and stations of the road surface public transit. In theory, there may be a very large number of combinations of modes, but in order to generate a reasonable travel route according to the travel habits of the user, there are transfer constraints between preset modes, and these transfer constraints are used to exclude some combinations of unreasonable modes. The transfer limiting conditions may include at least one of: private bicycles, private vehicles can only start to use or park at a starting point, a destination point or a parking point, and one trip data can only use the private bicycle or the private vehicle once; the shared automobile and the shared bicycle can only start to be used or parked at a designated place; private bicycles and shared bicycles cannot be used continuously.

The travel mode identifiers are used for representing corresponding travel modes, and travel mode identifiers corresponding to different travel modes are different. And the sequence obtained by arranging the travel mode identifiers corresponding to the travel modes in sequence represents that the user uses the travel modes to travel in sequence. The computer equipment takes the travel mode identification sequence meeting the transfer limiting conditions as a feasible sequence, and generates a travel mode state transfer model according to the feasible sequence, wherein the combination of travel modes adopted by the travel of the user needs to meet any one of the feasible sequences in the travel mode state transfer model. Referring to fig. 6, the numbers in the drawing indicate the travel modes, the letters indicate the travel states, and the travel states mark the types and the order of the travel modes currently used by the user, and the travel states are a subset of the feasible sequences. For example, the travel state corresponding to letter f indicates that the user walks (1) before riding the sharing bicycle (3); the travel state corresponding to the letter g indicates that the user walks (1) before taking the subway rail transit (4), can also indicate that the user walks (1) before taking the road surface bus (5), can also indicate that the user walks (1) before riding the sharing bicycle (3) before taking the subway rail transit (4), and can also indicate that the user walks (1) before riding the sharing bicycle (3) before taking the road surface bus (5). It can be understood that the travel state corresponding to the letter a is the initial state of the path planning.

In one embodiment, based on a multilayer traffic network, generating a travel route matched with travel information according to travel preference information and a travel duration comprises: acquiring the start-stop places and start-stop time of each group of travel data in the travel information; for each set of travel data, carrying out path planning based on a multi-layer traffic network and taking the shortest passing duration as a target to obtain a travel route of which the passing path accords with a start-stop place, the passing duration accords with start-stop time, the passing process accords with travel preference information, and the travel mode accords with a travel mode state transition model; the travel preference information comprises a transfer frequency upper limit value, a riding fee upper limit value, a walking distance upper limit value and a riding distance upper limit value; and after the travel routes corresponding to each group of travel data are connected, the travel route of the whole day is obtained.

Specifically, the computer device may determine, according to the start-stop points in the travel data, that is, the start point and the end point, network nodes corresponding to the start point and the end point from the multi-layer traffic network, so as to determine a travel route from the start point to the end point from the multi-layer traffic network. The computer equipment also needs to determine the upper limit value of the passing duration of the travel data according to the start-stop time in the travel data, wherein the upper limit value is used for restraining the passing duration of the travel route in path planning, namely the passing duration of the generated travel route needs to be smaller than the passing duration determined according to the start-stop time. The computer device also needs to consider travel preference information of the user in the path planning process, if the user does not want to ride, the travel route generated for the user does not use the travel mode of riding, if the user returns to park, the travel route comprising the parking path needs to be generated for the user, if the user does not want to transfer, the travel route which does not comprise transfer needs to be generated for the user. The computer equipment also needs to consider a travel mode state transition model in path planning, and ensures that a sequence formed by travel mode identifiers corresponding to the travel modes adopted by the travel routes is a feasible sequence in the travel mode transition model. That is, the travel data, the travel preference information and the travel mode state transition model will affect the generated travel route together, so as to ensure that the travel route meets the requirements of users, is reasonable and feasible, and has better passing efficiency.

In one embodiment, the travel information includes a plurality of sets of travel data related to the user traveling all day, and then the computer device may obtain a travel route corresponding to each set of travel data according to the above method, and connect the corresponding travel routes according to the start and stop places of the travel data, so as to obtain an all day travel route corresponding to the all day travel information.

When a travel route is required to be generated, the computer equipment acquires a multi-layer traffic network which is built in advance, network nodes in the multi-layer traffic network represent all places, two adjacent network nodes represent road sections which can pass through between the two corresponding places, and the weight of the edge between the network nodes represents the passing time length between the two corresponding places. The computer equipment also acquires a travel mode state transition matrix which is constructed in advance. The computer device also obtains predetermined data representing a route type (super road segment or common road segment) of a road segment in the multi-layer traffic network. The computer equipment also acquires travel information and travel preference information of the user. The computer equipment takes the acquired multilayer traffic network, travel mode state transition matrix, road section types of all road sections in the multilayer traffic network, travel information and travel preference information as input, and then adopts a path planning algorithm to carry out path planning based on the input information so as to output corresponding travel routes.

The computer device may employ a label correction method (Label Correcting Algorithm) to route the route with the shortest pass length as a goal, taking into account the input information. Referring to fig. 7, a schematic diagram of path planning with a shortest transit time by using a label correction method in one embodiment is shown, referring to fig. 7, the multi-layer traffic network includes 6 nodes, namely ABCDEF, where the weight of the edge between the nodes represents the transit time, i.e. the number on the edge in the figure. Assuming that the end point is node a and the start point is node F, the computer device needs to plan the path of the shortest transit time from the end point a to the start point F. Defining the shortest passing time length from a storage node to a starting point in a road section list, firstly, determining a road section taking A as a head node, namely AB, AC and AD, recording the path in a node-passing time length pair mode, namely adding the node-passing time length pair into the road section list, and then adding the node-passing time length pair into the road section list; then selecting the node-passing time length pair with the shortest passing time length from the road section list, namely node B, wherein the path with the shortest passing time length reaching the end point A from the multi-layer traffic network is from A to B, so that the computer equipment marks A as the processed node; the computer device then continues to iterate, determining from the multi-layer traffic network a road segment with a starting point B as a head node, namely BC, BF, wherein the shortest transit time of the node F to a is ab+bc=27 since the tail node F of the road segment BF is connected with a node B, adding F-27 to the road segment list, and the transit time corresponding to AC after comparing the tail node ab+bc with ac=9 recorded in the road segment list is required to be shorter since the tail node C of the road segment BC is directly connected with the starting point a, thus not updating C-9, and at this time, the shortest transit time of all nodes in the multi-layer traffic network with the node B as a middle node to the ending point a has been determined, so the computer device marks B as processed nodes. The computer device then continues the iteration, the node that is not currently marked and has the shortest passage length to A is C, a road segment with the starting point C as the head node, namely CE, is determined from the multi-layer traffic network, E-15 is added to the road segment list, at this time, the shortest passage length of all nodes in the multi-layer traffic network with the C node as the middle node to the end point A is determined, so the computer device marks C as the processed node. And by analogy, the computer equipment continuously updates the road section list, updates E-15 into E-14, updates F-27 into F-15, and all nodes are marked at the moment, so that the shortest passing duration of F distance A recorded in the road section list is 15 directly according to the fact that the corresponding path is ADEF, and the path from the starting point F to the end point A is determined to be FEDA.

In one embodiment, the road segments in the multi-layer traffic network are represented by head nodes and tail nodes, and for each set of travel data, path planning is performed based on the multi-layer traffic network and targeting the shortest traffic duration, including: acquiring a starting point and an ending point in travel data; determining all road sections taking the end point as a head node from a multi-layer traffic network; traversing each determined road section, acquiring a travel state Si of a tail node i of the currently traversed road section according to a travel mode state transition model, determining a travel mode of the currently traversed road section according to the travel state Si, and adding a node state pair [ i, si ] formed by the tail node i of the currently traversed road section and the travel state Si of the tail node i into a road section list when travel parameters corresponding to the travel mode accord with travel preference information; after the traversal is finished, the iterative execution steps are as follows until the road section list is empty: selecting a node state pair [ k, sk ] corresponding to a tail node k with the shortest passing time length reaching a destination d from a road section list, removing the selected node state pair [ k, sk ] from the road section list, and storing the passing time from the node k to the destination d by adopting a passing mode corresponding to a travel state Sk; determining all road sections taking a node k as a head node from a multi-layer traffic network; traversing each determined road section, and acquiring a travel state Si of a tail node i of the currently traversed road section according to a travel mode state transition model; determining a travel mode of a currently traversed road section according to the travel state Si, and adding a node state pair [ i, si ] formed by a tail node i of the currently traversed road section and the travel state Si of the tail node i into a road section list when travel parameters corresponding to the travel mode accord with travel preference information; after the iteration is finished, a travel state corresponding to the starting point is obtained, and a travel route matched with travel data is obtained by backtracking from the starting point to the end point according to the travel state corresponding to the starting point.

In this embodiment, a road segment in the multilayer traffic network may be defined as e= (i, j), i representing a tail node of the road segment e, and j representing a head node of the road segment e. After the starting point a and the ending point d in the travel data are acquired, path planning is performed from the ending point d in the travel data, the shortest passing time length from each node in the multilayer traffic network to the ending point d is sequentially determined, and when the shortest passing time length from the starting point a to the ending point d is determined, the corresponding travel route is also determined. Of course, the route planning may be performed from the starting point a in the trip data, and the embodiment of the present application mainly takes the route planning performed from the ending point in the trip data as an example for illustration. Before the path planning starts, the computer device also needs to initialize each item of data, for example, the travel time from all network nodes to the destination in all travel states in the multilayer traffic network can be initialized to infinity, the travel expense is initialized to infinity, the transfer number is initialized to 0, and the travel state is initialized to a.

The shortest passing time from the node j to the terminal d can be expressed by Vj, and in the planning process, the node j is any node which is continuously changed in the multi-layer traffic network; the road section list stores node state pairs [ i, si ], wherein the node i in the node state pairs is a node which has not determined the shortest passing time length with the terminal d in the multi-layer traffic network, and the state Si in the node state pairs is the travel state of the node i.

The computer device determines all road segments with the end point d as the head node from the multi-layer traffic network, so as to find the determined tail nodes i of each road segment, for example, the number of the determined tail nodes is m, and then the m road segments are sequentially traversed and determined. Since the travel state of the destination d is the initial state a (as shown in fig. 6, a represents the initial travel state), the travel state Si of the tail node i of the currently traversed road section is obtained according to the travel mode state transition model, as shown in fig. 6, in the travel mode state transition model, the travel state adjacent to the travel state may include b, c, d, e, the travel mode of the currently traversed road section is determined according to the travel state Si, and is sequentially walking, a private bicycle and a shared automobile, when the travel parameters corresponding to the travel mode conform to the travel preference information, for example, if the walking mode is adopted, and the walking distance is smaller than the walking distance maximum value set by the user, for example, and if the private bicycle mode is adopted, and the riding distance is smaller than the riding distance upper limit set by the user, for example, and if the user allows the travel mode to be adopted, the node state pair [ i, si ] of the tail node i of the currently traversed road section and the travel state Si of the tail node i may be added to the road section, that is the feasible path and the travel mode are kept. Of course, the travel modes that different tail nodes can adopt are different, for example, if it is determined that the tail node i is a bus stop, the user needs to walk to the bus stop, the corresponding travel mode is walking, if it is determined that the tail node i of the road section is a parking lot, the user needs to walk to the parking lot, the corresponding travel mode is walking, and if it is determined that the tail node of the road section is a certain road stop, the corresponding travel mode can be private bicycle, private car or shared car.

According to the above steps, the computer device determines all possible paths and travel modes from the destination, then, the computer device selects the node state pair [ k, sk ] corresponding to the tail node k with the shortest travel time to the destination d from the road section list, and eliminates the selected node state pair [ k, sk ] from the road section list, and stores the travel time from the node k to the destination d in the travel mode corresponding to the travel state Sk. Next, the computer device needs to determine the node with the shortest passing time length and conforming to the travel preference information of the user in all the network nodes adjacent to the tail node k of the multi-layer traffic network, so as to update the road section list after determining the next node.

Specifically, the computer device iteratively performs the steps of: determining all road sections taking the node k as a head node from a multi-layer traffic network, traversing each road section determined, acquiring the travel state Si of the tail node i of the currently traversed road section according to a travel mode state transition model, for example, if the travel state of the tail node k is determined as b in the previous step, referring to fig. 6, theoretically, the state of the tail node i of the currently traversed road section can be at least one of f, g, l, m, but the computer equipment not only needs to exclude some travel states which do not accord with the type of the tail node i from the travel states, but also needs to exclude the travel states according to travel preference information of a user, namely, determining the travel mode of the currently traversed road section according to the travel state Si, and when the travel mode corresponds to the travel preference information, namely, when the travel mode relates to a riding distance, a walking distance, a transfer number and a travel cost, the computer equipment needs to judge the travel mode of the tail node to update the travel parameters, judges whether the updated travel parameter meets the upper limit value set in travel preference information of the user, if the updated travel mode meets the travel mode, and if the travel mode of the tail node i does not accord with the travel preference information of the user, the travel mode is not added to the travel state of the road section to the road section Si. The iteration stop condition may be that nodes in the multilayer traffic network are traversed or the road section list is empty, after the iteration is finished, the computer device obtains a travel state corresponding to the starting point, and backtracks from the starting point to the end point according to the travel state corresponding to the starting point, so as to obtain a travel route matched with travel data.

In addition, in the iterative process, the computer equipment also judges the type of the road section, and if the road section is the super road section or the common road section determined according to the type, the computer equipment needs to update the transfer times.

Referring to fig. 7, the computer device selects a node-state pair [ k, sk ] with the shortest traffic duration from the road segment list, and then eliminates the node-state pair [ k, sk ] from the road segment list after recording the shortest traffic duration from the node k to the destination; selecting m road sections [ i, k ] taking k as head nodes from the multilayer traffic network, traversing tail nodes of the m road sections, obtaining travel states Si of the tail nodes i according to travel mode state transition models, updating travel parameters according to travel modes corresponding to the travel states Si, judging whether the updated travel parameters meet user travel preference information, if so, adding the tail nodes i and the corresponding travel states Si into a road section queue, if not, traversing the tail nodes i of the next road section in the m road sections until the m road sections are traversed, returning to the road section list to pick up a node-state pair [ k, sk ] with the shortest pass duration, and continuing to execute until the road section list is empty.

Fig. 9 is a schematic diagram of a frame of a method for generating a travel route in one embodiment. Referring to fig. 9, the data related to the method includes a road sub-network, a walking sub-network, a public transportation sub-network generated according to map data, and a private transportation sub-network generated according to private traffic road data and service information related to private transportation services and travel, and then the sub-networks are connected by using a common network node in each network to obtain a multi-layer transportation network considering various travel modes. The model related to the method comprises a feasible sequence formed by the combination of a defined hyper path and a travel mode state transition model. After the data and the model are provided, a travel route is generated by using a path planning algorithm, the passing duration is obtained from the road real-time service, an improved label correction method is adopted, and the travel state and the connection of the travel modes of each travel data are considered in the planning process, so that a reasonable travel route set is obtained.

The route generation method comprises the steps that the multi-layer traffic network comprises a road sub-network, a walking sub-network and a public traffic sub-network, and can provide support for generating travel routes comprising a plurality of different travel modes; the travel mode state transition model defines a reasonable and feasible combination sequence corresponding to various travel modes, and ensures that the generated travel route comprising the various travel modes accords with the travel habit of people. After the travel information and the travel preference information of the user are acquired, the passing time length between each network node in different sub-networks of the multi-layer traffic network is queried, so that path planning can be performed according to the passing time length between each network node based on the multi-layer traffic network, the travel preference information of the user can be considered during path planning, various travel modes and the feasibility of transformation among the various travel modes can be considered, and the generated route matched with the travel information accords with the user preference and is efficient and feasible.

Taking Nanjing as an example, the route generation method provided by the embodiment of the application is verified: first, a multi-layer traffic network is generated, and due to data limitation, only services provided by public transportation companies, namely buses and subways, are considered, and some private traffic services are not considered. As shown in fig. 10, in the generated visual multi-layer traffic network, the road sub-network has 40710 roads, 16427 nodes, the bus sub-network has 1321 lines, 3043 stations, and 10 subway lines. The travel preference information of the user is set as follows: the maximum walking distance is 3km, the maximum riding distance is 10km, the maximum multiplier is 3, and the travel information is: starting from four-level building school east residential area (longitude and latitude: 118.797385,32.053281), 8:00 in the morning and reaching nine-Dragon lake school area of the university of east and south in the morning (longitude and latitude: 118.8269,31.892234) 10:00-10:20 in the morning; the method is characterized in that the method starts from a nine-dragon lake district of southeast university to a Zhou Donglu valley (longitude and latitude: 118.828123,31.867818) at the afternoon 19:00, and returns to a four-story east-school residential district before 22:00 a night, so that a private car can be started, and the car is required to be taken in the return journey. The generated travel route has two schemes:

Scheme one: the first section, walk to the north road of Taiping, drive to the north door of Jiulong lake district of southeast university, walk to the destination again, 46min when sharing, it takes 65 yuan. The second stage, walking to the North gate of Jiulong lake school district at the university of southward, starts to drive to the end point, takes 11 yuan, and takes 12 minutes. And the third section, the driving return journey to the north road, and stopping. The time period is 65min, and 80 yuan is spent.

Scheme II: the first section, walk to the floating bridge subway station, the 3B port gets on the bus and takes the line No. three to the nine-Dragon lake school station of southeast university, the 2 port gets off, and then walks to the end point, and the total time is 102min, and the cost is 5 yuan. The second section, walking to a nine-Dragon lake school district station of the university of southwest, getting on a vehicle at port 2, taking a line 3 to a vehicle at port 3 of a furnace Zhou Donglu station, walking to a terminal point, spending 2 yuan, and taking 32 minutes; or the second section, walking to the east gate of Jiulong lake district of the university of southward, taking 838 routes to the tomb site, the next step to the end point, spending 2 yuan, and taking 38 minutes. And thirdly, walking to a furnace Zhou Donglu station, taking a third line to a floating bridge station for getting off, walking to a terminal point, and taking 93 minutes to take 5 yuan.

It should be understood that, although the steps in the flowchart of fig. 2 are shown in sequence as indicated by the arrows, the steps are not necessarily performed in sequence as indicated by the arrows. The steps are not strictly limited to the order of execution unless explicitly recited herein, and the steps may be executed in other orders. Moreover, at least a portion of the steps in fig. 2 may include a plurality of steps or stages, which are not necessarily performed at the same time, but may be performed at different times, and the order of the steps or stages is not necessarily sequential, but may be performed in rotation or alternatively with at least a portion of the steps or stages in other steps or other steps.

In one embodiment, as shown in fig. 11, a route generation device 1100 is provided, which may employ a software module or a hardware module, or a combination of both, as part of a computer apparatus, and specifically includes: an acquisition module 1102, a determination module 1104, a query module 1106, and a generation module 1108, wherein:

An acquisition module 1102, configured to acquire travel information and travel preference information;

a determining module 1104, configured to determine a multi-layer traffic network corresponding to a geographic location related to the travel information, where the multi-layer traffic network includes a road sub-network, a walking sub-network, and a public transportation sub-network;

The query module 1106 is configured to query a traffic duration between network nodes in different sub-networks of the multi-layer traffic network;

The generating module 1108 is configured to generate, based on the multilayer traffic network, a travel route matching the travel information according to the travel preference information and the travel duration, where a sequence formed by travel mode identifiers corresponding to a plurality of travel modes adopted by the travel route is a feasible sequence in the travel mode state transition model.

In one embodiment, the apparatus further comprises a road network construction module for acquiring map data of a geographic location; generating a road sub-network according to the map data, wherein the road sub-network comprises road nodes and road sections between the road nodes, and the road nodes comprise road stop points and parking points; generating a walking sub-network according to the map data, wherein the walking sub-network comprises walking nodes and road sections between the walking nodes, and the walking nodes comprise road stop points, parking points and public transportation stations; generating a public transportation sub-network according to the map data and the public transportation line data, wherein the public transportation sub-network comprises public transportation nodes and road sections between the public transportation nodes, and the public transportation nodes comprise public transportation sites; connecting the road sub-network with the walking sub-network according to the road stop points and the parking points, and connecting the walking sub-network with the public transportation sub-network according to the public transportation stations to obtain the multi-layer transportation network.

In one embodiment, the road network construction module is further configured to obtain an order of public transportation sites of the public transportation line according to the public transportation line data; obtaining geographic coordinates of public transportation sites of a public transportation line according to the map data; and matching the public transportation sites with the road sub-network according to the sequence and the geographic coordinates, and generating the public transportation sub-network comprising the public transportation sites and road sections between the public transportation sites.

In one embodiment, the walking nodes in the walking sub-network further comprise private traffic nodes, and the road network construction module is further used for acquiring private traffic road data corresponding to the private traffic service; generating a private traffic sub-network according to the private traffic road data, wherein the private traffic sub-network comprises a private traffic node and a road section between the private traffic nodes; connecting the road sub-network with the walking sub-network according to the road stop points and the parking points, connecting the walking sub-network with the public transportation sub-network according to the public transportation stations, and connecting the private transportation sub-network with the walking sub-network according to the private transportation nodes to obtain the multi-layer transportation network.

In one embodiment, the device further comprises a travel mode state transition model generation module, which is used for acquiring travel mode identifiers corresponding to preset various travel modes; acquiring transfer limiting conditions for restricting a change of a travel mode in a travel process; the travel mode identification sequence meeting the transfer limiting condition is used as a feasible sequence; and generating a travel mode state transition model according to the feasible sequence.

In one embodiment, the query module 1106 is further configured to query a traffic duration between road nodes in a road sub-network of the multi-layer traffic network; inquiring the passing time length among all walking nodes in a walking sub-network of the multi-layer traffic network; inquiring the running time length and the vehicle frequency of each public transportation line among public transportation nodes in a public transportation sub-network of the multi-layer transportation network, and calculating the passing time length among the public transportation nodes according to the running time length and the vehicle frequency of each public transportation line.

In one embodiment, the query module 1106 is further configured to mark a road segment from a first site to a second site in the public transportation sub-network as a super road segment when there are a plurality of public transportation lines between the first site and the second site in the public transportation sub-network; acquiring the vehicle frequency of each public transportation line in a plurality of public transportation lines; acquiring the driving time length of each public transport line from a first station to a second station; obtaining the joint vehicle frequency of the super road section according to the vehicle frequency of each public transport line; determining average waiting time corresponding to the first station according to the combined vehicle frequency; determining the probability of each public transportation line as a first line reaching a first station according to the vehicle frequency of each public transportation line and the combined vehicle frequency; and calculating the traffic duration of the road section between the first station and the second station according to the average waiting time, the probability and the running duration.

In one embodiment, the query module 1106 is further configured to mark a road segment from a first site to a second site in the public transportation sub-network as a common road segment when there is only one public transportation line from the first site to the second site in the public transportation sub-network; acquiring a driving time length from a first station to a second station; the driving duration is taken as the traffic duration of a common road section between the first station and the second station.

In one embodiment, the generating module 1108 is further configured to obtain a start-stop location and a start-stop time of each set of trip data in the trip information; for each set of travel data, carrying out path planning based on a multi-layer traffic network and taking the shortest passing duration as a target to obtain a travel route of which the passing path accords with a start-stop place, the passing duration accords with start-stop time, the passing process accords with travel preference information, and the travel mode accords with a travel mode state transition model; the travel preference information comprises a transfer frequency upper limit value, a riding fee upper limit value, a walking distance upper limit value and a riding distance upper limit value; and after the travel routes corresponding to each group of travel data are connected, the travel route of the whole day is obtained.

In one embodiment, the generating module 1108 is further configured to obtain a start point and an end point in the travel data; determining all road sections taking the end point as a head node from a multi-layer traffic network; traversing each determined road section, acquiring a travel state Si of a tail node i of the currently traversed road section according to a travel mode state transition model, determining a travel mode of the currently traversed road section according to the travel state Si, and adding a node state pair [ i, si ] formed by the tail node i of the currently traversed road section and the travel state Si of the tail node i into a road section list when travel parameters corresponding to the travel mode accord with travel preference information; after the traversal is finished, the iterative execution steps are as follows until the road section list is empty: selecting a node state pair [ k, sk ] corresponding to a tail node k with the shortest passing time length reaching a destination d from a road section list, removing the selected node state pair [ k, sk ] from the road section list, and storing the passing time from the node k to the destination d by adopting a passing mode corresponding to a travel state Sk; determining all road sections taking a node k as a head node from a multi-layer traffic network; traversing each determined road section, and acquiring a travel state Si of a tail node i of the currently traversed road section according to a travel mode state transition model; determining a travel mode of a currently traversed road section according to the travel state Si, and adding a node state pair [ i, si ] formed by a tail node i of the currently traversed road section and the travel state Si of the tail node i into a road section list when travel parameters corresponding to the travel mode accord with travel preference information; after the iteration is finished, a travel state corresponding to the starting point is obtained, and a travel route matched with travel data is obtained by backtracking from the starting point to the end point according to the travel state corresponding to the starting point.

The route generation device 1100, the multi-layer traffic network includes a road sub-network, a walking sub-network and a public traffic sub-network, and can provide support for generating travel routes including a plurality of different travel modes; the travel mode state transition model defines a reasonable and feasible combination sequence corresponding to various travel modes, and ensures that the generated travel route comprising the various travel modes accords with the travel habit of people. After the travel information and the travel preference information of the user are acquired, the passing time length between each network node in different sub-networks of the multi-layer traffic network is queried, so that path planning can be performed according to the passing time length between each network node based on the multi-layer traffic network, the travel preference information of the user can be considered during path planning, various travel modes and the feasibility of transformation among the various travel modes can be considered, and the generated route matched with the travel information accords with the user preference and is efficient and feasible.

The specific definition of the route generating device may be referred to the definition of the route generating method hereinabove, and will not be described herein. The respective modules in the above-described route generating device may be implemented in whole or in part by software, hardware, and combinations thereof. The above modules may be embedded in hardware or may be independent of a processor in the computer device, or may be stored in software in a memory in the computer device, so that the processor may call and execute operations corresponding to the above modules.

In one embodiment, a computer device is provided, which may be a server, and the internal structure of which may be as shown in fig. 12. The computer device includes a processor, a memory, and a network interface connected by a system bus. Wherein the processor of the computer device is configured to provide computing and control capabilities. The memory of the computer device includes a non-volatile storage medium and an internal memory. The non-volatile storage medium stores an operating system, computer programs, and a database. The internal memory provides an environment for the operation of the operating system and computer programs in the non-volatile storage media. The database of the computer device is used for storing data of the multi-layer traffic network and data of the traffic duration. The network interface of the computer device is used for communicating with an external terminal through a network connection. The computer program is executed by a processor to implement a route generation method.

It will be appreciated by those skilled in the art that the structure shown in FIG. 11 is merely a block diagram of some of the structures associated with the present inventive arrangements and is not limiting of the computer device to which the present inventive arrangements may be applied, and that a particular computer device may include more or fewer components than shown, or may combine some of the components, or have a different arrangement of components.

In an embodiment, there is also provided a computer device comprising a memory and a processor, the memory having stored therein a computer program, the processor implementing the steps of the method embodiments described above when the computer program is executed.

In one embodiment, a computer-readable storage medium is provided, storing a computer program which, when executed by a processor, implements the steps of the method embodiments described above.

In one embodiment, a computer program product or computer program is provided that includes computer instructions stored in a computer readable storage medium. The processor of the computer device reads the computer instructions from the computer-readable storage medium, and the processor executes the computer instructions, so that the computer device performs the steps in the above-described method embodiments.

Those skilled in the art will appreciate that implementing all or part of the above described methods may be accomplished by way of a computer program stored on a non-transitory computer readable storage medium, which when executed, may comprise the steps of the embodiments of the methods described above. Any reference to memory, storage, database, or other medium used in embodiments provided herein may include at least one of non-volatile and volatile memory. The nonvolatile Memory may include Read-Only Memory (ROM), magnetic tape, floppy disk, flash Memory, optical Memory, or the like. Volatile memory can include random access memory (Random Access Memory, RAM) or external cache memory. By way of illustration, and not limitation, RAM can be in various forms such as static random access memory (Static Random Access Memory, SRAM) or dynamic random access memory (Dynamic Random Access Memory, DRAM), etc.

The technical features of the above embodiments may be arbitrarily combined, and all possible combinations of the technical features in the above embodiments are not described for brevity of description, however, as long as there is no contradiction between the combinations of the technical features, they should be considered as the scope of the description.

The above examples illustrate only a few embodiments of the application, which are described in detail and are not to be construed as limiting the scope of the application. It should be noted that it will be apparent to those skilled in the art that several variations and modifications can be made without departing from the spirit of the application, which are all within the scope of the application. Accordingly, the scope of protection of the present application is to be determined by the appended claims.

Claims

1. A method of route generation, the method comprising:

Acquiring travel information and travel preference information;

Inquiring the passing time length among road nodes in the road sub-network;

inquiring the passing time length among all walking nodes in the walking sub-network;

Inquiring the running time length between public transportation nodes in the public transportation sub-network and the vehicle frequency of each public transportation line, when a plurality of public transportation lines exist between a first station in the public transportation sub-network and a second station in the public transportation sub-network, marking a road section from the first station to the second station in the public transportation sub-network as a super road section, acquiring the vehicle frequency of each public transportation line in the plurality of public transportation lines, acquiring the running time length of each public transportation line from the first station to the second station, acquiring the joint vehicle frequency of the super road section according to the vehicle frequency of each public transportation line, determining the average waiting time corresponding to the first station according to the joint vehicle frequency, determining the probability of each public transportation line as a first station to reach the first station according to the vehicle frequency of each public transportation line and the joint vehicle frequency, and calculating the super road section from the first station to the second station according to the average waiting time, the probability and the running time length;

And generating a travel route matched with the travel information according to the travel preference information and the travel time based on the multilayer traffic network, wherein the travel route is generated by adopting a plurality of travel modes, and a sequence formed by travel mode identifiers corresponding to the travel modes is a feasible sequence in a travel mode state transition model.

2. The method according to claim 1, wherein the method further comprises:

Acquiring map data of the geographic position;

generating a road sub-network according to the map data, wherein the road sub-network comprises road nodes and road sections between the road nodes, and the road nodes comprise road stop points and parking points;

Generating a walking sub-network according to the map data, wherein the walking sub-network comprises walking nodes and road sections between the walking nodes, and the walking nodes comprise road stop points, parking points and public transportation stations;

generating a public transportation sub-network according to the map data and the public transportation line data, wherein the public transportation sub-network comprises public transportation nodes and road sections between the public transportation nodes, and the public transportation nodes comprise public transportation stations;

And connecting the road sub-network with the walking sub-network according to the road stop point and the parking point, and connecting the walking sub-network with the public transportation sub-network according to the public transportation station to obtain the multi-layer transportation network.

3. The method of claim 2, wherein the generating a public transportation sub-network from the map data and public transportation line data comprises:

acquiring the sequence of public transportation sites of a public transportation line according to the public transportation line data;

obtaining geographic coordinates of public transportation sites of a public transportation line according to the map data;

And matching the public transportation sites with the road sub-network according to the sequence and the geographic coordinates, and generating a public transportation sub-network comprising the public transportation sites and road sections between the public transportation sites.

4. The method of claim 2, wherein the walking nodes in the walking subnetwork further comprise private traffic nodes, the method further comprising:

acquiring private traffic road data corresponding to private traffic services;

Generating a private traffic sub-network according to the private traffic road data, wherein the private traffic sub-network comprises a private traffic node and a road section between the private traffic nodes;

The step of connecting the road sub-network with the walking sub-network according to the road stop point and the parking point, and connecting the walking sub-network with the public transportation sub-network according to the public transportation station to obtain a multi-layer transportation network comprises the following steps:

The road sub-network is connected with the walking sub-network according to the road stop point and the parking point, the walking sub-network is connected with the public transportation sub-network according to the public transportation station, and the private transportation sub-network is connected with the walking sub-network according to the private transportation point, so that the multi-layer transportation network is obtained.

5. The method according to claim 1, wherein the method further comprises:

Acquiring travel mode identifiers corresponding to preset various travel modes;

Acquiring transfer limiting conditions for restricting a change of a travel mode in a travel process;

a travel mode identification sequence meeting the transfer limiting condition is used as the feasible sequence;

and generating the travel mode state transition model according to the feasible sequence.

6. The method according to claim 1, wherein the method further comprises:

When only one public transportation line exists between a first station in the public transportation sub-network and a second station in the public transportation sub-network, marking a road section from the first station to the second station in the public transportation sub-network as a common road section;

acquiring a driving time length from the first station to the second station;

and taking the driving duration as the traffic duration of a common road section from the first station to the second station.

7. The method according to any one of claims 1 to 6, wherein the generating, based on the multi-layer traffic network, a travel route matching the travel information according to the travel preference information and the passage duration, includes:

acquiring the start-stop places and the start-stop time of each group of travel data in the travel information;

For each set of travel data, carrying out path planning based on the multilayer traffic network and taking the shortest passing duration as a target to obtain a travel route of which the passing path accords with the starting and stopping place, the passing duration accords with the starting and stopping time, the passing process accords with the travel preference information and the travel mode accords with the travel mode state transition model; the travel preference information comprises a transfer frequency upper limit value, a riding fee upper limit value, a walking distance upper limit value and a riding distance upper limit value;

And after the travel routes corresponding to each group of travel data are connected, the travel route of the whole day is obtained.

8. The method of claim 7, wherein the road segments in the multi-layer traffic network are represented by head nodes and tail nodes, wherein for each set of trip data, path planning is performed based on the multi-layer traffic network and targeting a shortest pass time, comprising:

acquiring a starting point and an ending point in travel data;

Determining all road sections taking the end point as a head node from the multi-layer traffic network;

Traversing each determined road section, acquiring a travel state Si of a tail node i of the currently traversed road section according to a travel mode state transition model, determining a travel mode of the currently traversed road section according to the travel state Si, and adding a node state pair [ i, si ] formed by the tail node i of the currently traversed road section and the travel state Si of the tail node i into a road section list when travel parameters corresponding to the travel mode accord with the travel preference information;

After the traversing is finished, iteratively executing a road section list updating step until the road section list is empty; the step of updating the road section list comprises the following steps: selecting a node state pair [ k, sk ] corresponding to a tail node k with the shortest passing time reaching a destination d from the road section list, removing the selected node state pair [ k, sk ] from the road section list, storing the passing time from the node k to the destination d by adopting a passing mode corresponding to a traveling state Sk, determining all road sections taking the node k as a head node from the multi-layer traffic network, traversing each determined road section, acquiring the traveling state Si of a tail node i of the road section currently traversed according to a traveling mode state transition model, determining the traveling mode of the road section currently traversed according to the traveling state Si, and adding the node state pair [ i, si ] formed by the tail node i of the road section currently traversed and the traveling state Si of the tail node i into the road section list when the traveling parameters corresponding to the traveling mode accord with the traveling preference information;

and after the iteration is finished, acquiring a travel state corresponding to the starting point, and backtracking from the starting point to the end point according to the travel state corresponding to the starting point to acquire a travel route matched with the travel data.

9. A route generation device, the device comprising:

The inquiring module is used for inquiring the passing time length among the road nodes in the road sub-network; inquiring the passing time length among all walking nodes in the walking sub-network; inquiring the running time length between public transportation nodes in the public transportation sub-network and the vehicle frequency of each public transportation line, when a plurality of public transportation lines exist between a first station in the public transportation sub-network and a second station in the public transportation sub-network, marking a road section from the first station to the second station in the public transportation sub-network as a super road section, acquiring the vehicle frequency of each public transportation line in the plurality of public transportation lines, acquiring the running time length of each public transportation line from the first station to the second station, acquiring the joint vehicle frequency of the super road section according to the vehicle frequency of each public transportation line, determining the average waiting time corresponding to the first station according to the joint vehicle frequency, determining the probability of each public transportation line as a first station to reach the first station according to the vehicle frequency of each public transportation line and the joint vehicle frequency, and calculating the super road section from the first station to the second station according to the average waiting time, the probability and the running time length;

The generation module is used for generating a travel route matched with the travel information according to the travel preference information and the travel duration based on the multilayer traffic network, wherein the travel route is generated by adopting a plurality of travel modes, and a sequence formed by travel mode identifiers corresponding to the travel modes is a feasible sequence in a travel mode state transition model.

10. The apparatus of claim 9, further comprising a road network construction module for obtaining map data of the geographic location; generating a road sub-network according to the map data, wherein the road sub-network comprises road nodes and road sections between the road nodes, and the road nodes comprise road stop points and parking points; generating a walking sub-network according to the map data, wherein the walking sub-network comprises walking nodes and road sections between the walking nodes, and the walking nodes comprise road stop points, parking points and public transportation stations; generating a public transportation sub-network according to the map data and the public transportation line data, wherein the public transportation sub-network comprises public transportation nodes and road sections between the public transportation nodes, and the public transportation nodes comprise public transportation stations; and connecting the road sub-network with the walking sub-network according to the road stop point and the parking point, and connecting the walking sub-network with the public transportation sub-network according to the public transportation station to obtain the multi-layer transportation network.

11. The apparatus of claim 10, wherein the road network construction module is further configured to obtain an order of public transportation sites of a public transportation line based on the public transportation line data; obtaining geographic coordinates of public transportation sites of a public transportation line according to the map data; and matching the public transportation sites with the road sub-network according to the sequence and the geographic coordinates, and generating a public transportation sub-network comprising the public transportation sites and road sections between the public transportation sites.

12. The apparatus of claim 10, wherein the walking nodes in the walking subnetwork further comprise private traffic nodes, and the road network construction module is further configured to obtain private traffic road data corresponding to a private traffic service; generating a private traffic sub-network according to the private traffic road data, wherein the private traffic sub-network comprises a private traffic node and a road section between the private traffic nodes; the road sub-network is connected with the walking sub-network according to the road stop point and the parking point, the walking sub-network is connected with the public transportation sub-network according to the public transportation station, and the private transportation sub-network is connected with the walking sub-network according to the private transportation point, so that the multi-layer transportation network is obtained.

13. The device according to claim 9, further comprising a travel mode state transition model generation module, configured to obtain travel mode identifiers corresponding to preset various travel modes; acquiring transfer limiting conditions for restricting a change of a travel mode in a travel process; a travel mode identification sequence meeting the transfer limiting condition is used as the feasible sequence; and generating the travel mode state transition model according to the feasible sequence.

14. The apparatus of claim 9, wherein the query module is further configured to mark a road segment from a first site to a second site in the public transportation subnetwork as a common road segment when there is only one public transportation line from the first site to the second site in the public transportation subnetwork; acquiring a driving time length from the first station to the second station; and taking the driving duration as the traffic duration of a common road section from the first station to the second station.

15. The apparatus according to any one of claims 9 to 14, wherein the generating module is further configured to obtain a start-stop location and a start-stop time of each set of trip data in the trip information; for each set of travel data, carrying out path planning based on the multilayer traffic network and taking the shortest passing duration as a target to obtain a travel route of which the passing path accords with the starting and stopping place, the passing duration accords with the starting and stopping time, the passing process accords with the travel preference information and the travel mode accords with the travel mode state transition model; the travel preference information comprises a transfer frequency upper limit value, a riding fee upper limit value, a walking distance upper limit value and a riding distance upper limit value; and after the travel routes corresponding to each group of travel data are connected, the travel route of the whole day is obtained.

16. The apparatus of claim 15, wherein the road segments in the multi-layer traffic network are represented by head nodes and tail nodes, the generating module further configured to obtain a start point and an end point in travel data; determining all road sections taking the end point as a head node from the multi-layer traffic network; traversing each determined road section, acquiring a travel state Si of a tail node i of the currently traversed road section according to a travel mode state transition model, determining a travel mode of the currently traversed road section according to the travel state Si, and adding a node state pair [ i, si ] formed by the tail node i of the currently traversed road section and the travel state Si of the tail node i into a road section list when travel parameters corresponding to the travel mode accord with the travel preference information; after the traversing is finished, iteratively executing a road section list updating step until the road section list is empty; the step of updating the road section list comprises the following steps: selecting a node state pair [ k, sk ] corresponding to a tail node k with the shortest passing time reaching a destination d from the road section list, removing the selected node state pair [ k, sk ] from the road section list, storing the passing time from the node k to the destination d by adopting a passing mode corresponding to a traveling state Sk, determining all road sections taking the node k as a head node from the multi-layer traffic network, traversing each determined road section, acquiring the traveling state Si of a tail node i of the road section currently traversed according to a traveling mode state transition model, determining the traveling mode of the road section currently traversed according to the traveling state Si, and adding the node state pair [ i, si ] formed by the tail node i of the road section currently traversed and the traveling state Si of the tail node i into the road section list when the traveling parameters corresponding to the traveling mode accord with the traveling preference information; and after the iteration is finished, acquiring a travel state corresponding to the starting point, and backtracking from the starting point to the end point according to the travel state corresponding to the starting point to acquire a travel route matched with the travel data.

17. A computer device comprising a memory and a processor, the memory storing a computer program, characterized in that the processor implements the steps of the method of any one of claims 1 to 8 when the computer program is executed.

18. A computer readable storage medium storing a computer program, characterized in that the computer program when executed by a processor implements the steps of the method of any one of claims 1 to 8.