Determining network maps of transport networks

• US 10,359,291 B2
• Filed: 09/04/2014
• Issued: 07/23/2019
• Est. Priority Date: 09/19/2013
• Status: Active Grant

• Current Assignee: National ICT Australia Limited
• Original Assignee: National ICT Australia Limited
• Inventors: Kilby, Phillip, Robards, Matthew
• Primary Examiner(s): Bhattacharya, Sam
• Application Number:
  US15/508,399
• Publication Number:
  US 20170248432A1
• Time in Patent Office: 1,783 Days
• Field of Search: 455 6711, 455446, 340429, 3405721, 705 5, 705 735
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations

Abstract

This disclosure relates a processor determining a network map of a transport network by. The processor optimises for each of multiple sets of nodes a travel cost of trips with a start node and an end node in that set. This way, the processor selects from each of the multiple sets one node as a hub. The travel cost is based on whether the start node or end node is the hub. The processor then optimises for each node a direct travel time between that node and a hub to select an optimised hub for that node. Finally, the processor determines a network map comprising the selected hubs connected by a first transport mode and the remaining nodes connected to the selected hub by a second transport mode. Passengers need to change less often at the hub because the hub is placed at the most popular destination or origin.

Claims

1. A computer implemented method for determining a network map of a transport network, the method comprising:

optimising for each of multiple sets of nodes a travel cost of trips with a start node and an end node in that set to select from each of the multiple sets one node as a hub, wherein the travel cost is based on whether the start node or end node is the hub;

optimising for each node a direct travel time between that node and a hub to select an optimised hub for that node;

determining a network map comprising the selected hubs connected to one another by a first transport mode and the remaining nodes connected to the respectively selected optimised hub by a second transport mode; and

repeating the optimisation steps to iteratively improve the network map wherein optimising the direct travel time further determines the multiple sets of transport nodes as nodes for which the same hub is selected.

2. The computer implemented method of claim 1, wherein the trips are historically collected trips.

3. The computer implemented method of claim 1, further comprising repeating the method after an operating time period, wherein the trips comprise trips travelled during the operating time period.

4. The computer implemented method of claim 1, wherein the first transport mode is a bus transport mode.

5. The computer implemented method of claim 4, wherein the bus transport mode is scheduled.

6. The computer implemented method of claim 1, wherein the second transport mode is a taxi or minibus transport mode.

7. The computer implemented method of claim 6, wherein the taxi or minibus transport mode is on-demand.

8. The computer implemented method of claim 1, further comprising storing the network map on a data store.

9. The computer implemented method of claim 1, further comprising operating the transport network according to the network map.

10. The computer implemented method of claim 1, wherein the travel cost of trips is further based on a travel time.

11. The computer implemented method of claim 1, wherein the travel cost of trips is further based on passenger convenience.

12. The computer implemented method of claim 1, further comprising determining routes to connect the selected hubs.

13. The computer implemented method of claim 12, wherein determining the routes is based on the number of direct trips between hubs along the routes.

14. The computer implemented method of claim 12, wherein determining the routes is based on the number of transport vehicles required to service the routes and on a predefined headway.

15. The computer implemented method of claim 12, wherein determining the routes is based on a distance of trips between the hubs.

16. A non-transitory computer readable medium with an executable program stored thereon that when executed causes a computer to perform the method of claim 1.

17. A computer system for determining a network map of a transport network, the computer system comprising:

a data store to store trip data comprising multiple trips;

a processor

to optimise for each of multiple sets of nodes a travel cost of the trips with a start node and an end node in that set to select from each of the multiple sets one node as a hub, wherein the travel cost is based on whether the start node or end node is the hub,

to optimise for each node a direct travel time between that node and a hub to select an optimised hub for that node,

to determine a network map comprising the selected hubs connected to one another by a first transport mode and the remaining nodes connected to the respectively selected optimised hub by a second transport mode, and

to repeat the optimisation steps to iteratively improve the network map wherein optimising the direct travel time further determines the multiple sets of transport nodes as nodes for which the same hub is selected; and

a data store to store the determined network map.