Intelligent travel routing system and method

A method of assigning routes to a plurality of users includes determining a cost for each of a plurality of roadway segments. The cost of a roadway segment is commensurate with the roadway segment's inclusion in one or more existing routes from a start location to a destination location. The method further includes generating a plurality of new routes. Each generated route includes one or more roadway segments. The generated routes are assigned to each of the plurality of users.

CROSS REFERENCE TO RELATED APPLICATIONS

This application is related to co-pending U.S. patent application Ser. No. 12/200,096, filed Aug. 28, 2008, entitled Networked Navigation System.

DETAILED DESCRIPTION

Unified Modeling Language (“UML”) can be used to model and/or describe methods and systems and provide the basis for better understanding their functionality and internal operation as well as describing interfaces with external components, systems and people using standardized notation. When used herein, UML diagrams including, but not limited to, use case diagrams, class diagrams and activity diagrams, are meant to serve as an aid in describing the embodiments of the present disclosure, but do not constrain implementation thereof to any particular hardware or software embodiments. Unless otherwise noted, the notation used with respect to the UML diagrams contained herein is consistent with the UML 2.0 specification or variants thereof and is understood by those skilled in the art.

This disclosure is drawn, inter alia, to methods, apparatus, computer programs and systems related to travel route selection technology, and, more particularly, to the dynamic generation of routes for a collection of users with networked navigation and positioning devices. A travel route refers to one or more courses, roads, or road segments that link a start location and a destination location. Given a user seeking a travel route to a destination, the system described herein selects from a plurality of possible routes by considering the current and predicted roadway usage by other users. The system may also consider environmental conditions such as traffic flow, roadway characteristics, weather conditions, and event scheduling. By collecting and aggregating this information, users may be optimally distributed over the plurality of available routes. Optimal distribution in this context is not determined by a single user's travel time; rather, the system will consider the travel time of all users when selecting a route from a plurality of roadway segments. Thus, while the travel time of an individual user may be longer than optimal, this system will ensure that any increase in travel time caused by environmental conditions (e.g., traffic congestion) may be efficiently shared across all other users.

For clarity, some embodiments of the subject matter disclosed herein are described with respect to an automobile and a wireless system. However, in light of the present disclosure those skilled in the art will recognize that the suggested travel routing techniques described herein may be used with any mode of travel and any communication system generally known in the art, including air travel, fixed and mobile computing devices such as a PDA or personal computer, and wireless communication channels such as cellular telephone networks, WiFi and WiMax networks, wired telephone networks, and cable networks.

Referring toFIG. 1, one embodiment of a travel routing system100is shown. The travel routing system100includes user equipment101, an intelligent routing system102, and external data sources, including an event data source104, a traffic data source105, a roadway characteristics database106, a weather data source107, and a geographic mapping data source108. In addition, the intelligent routing system102maintains a database of previous routing assignments103. By combining information from the external data sources104,105,106,107,108and the previous routing assignments database103, the travel routing system102provides an optimal distribution of traffic. In one embodiment, this distribution minimizes the collective travel time of the users of the system.

As shown inFIG. 1, the travel route system100includes user equipment (UE)101. The UE101is generally a mobile or fixed communication device. Examples of UE101include, without limitation, Personal Digital Assistants (PDA), cell phones (including smart phones), personal computers, and in-vehicle navigation devices (both OEM and after-market). Such communication devices are generally known in the art, and a detailed discussion thereof is omitted here for convenience only and should not be considered limiting. A user109, such as an operator or vehicle driver, interacts with the UE101via a user interface201(seeFIG. 2) associated with the UE101, in any manner generally understood in the art (e.g., GUI, keypad, touch-screen).

The UE101gathers real-time information about the user109. This information may include, for example, the user's geographic location, direction, speed, and time. In one embodiment, the UE101also collects data which indicates user preferences based on user input or past travel habits. A UE101that includes an internal position sensing device may automatically determine the start location based on the current position or location of the user. Such a device may employ any position sensing technique generally known in the art, including, without limitation, Global Positioning System (GPS), cell triangulation, inertial sensing, or some combination thereof. The user109may also manually input a start location to the UE.

Referring toFIG. 2, one embodiment of a route request generation component202in the UE101generates route request messages that are sent to the intelligent routing system (IRS)102. A route request message may be generated by user input via interaction with the UE101. The UE101may also automatically generate route request messages based on some event (e.g., a user's deviation from an assigned route). A route request message includes information for the IRS102to provide directions from the user's current location to a desired destination location. Examples of information incorporated in a route request message include, without limitation, a user identifier, a start location, a destination location, vehicle classification (number of axels, weight, etc.), and toll preferences. In one embodiment the information included in the route request message is gathered from one or more components in the UE101. For example, inFIG. 2, a positional data component203provides data that indicates the user's current location. This component may include, for example, a GPS receiver (not shown). The UE may also contain a user preferences component216that supplies one or more user preferences related to past, current, and future route requests by the user109and/or the user equipment101. For example, user preferences may include types of routes preferred by the user, types of roads traveled, preferred vehicle type, preferred time of day for travel, etc. In one embodiment, the route request generation component202generates a single message to provide directions between a location and a destination. In another embodiment, the route request generation component periodically sends route requests to the intelligent routing system102. By regularly requesting a data from the intelligent routing system, a user's route may be modified based on real-time data and the user's updated position. The update interval for such a message may be set by the user via the UE101or, alternatively, the UE manufacturer or developer may provide a preset periodic value.

Referring toFIG. 5, one embodiment of the intelligent routing system (IRS)102processes route request messages to determine at least one route that links a specified start position and a destination. The IRS compiles environmental data from a plurality of external sources and uses geographic mapping data to generate a list of possible routes that link the specified start position and a destination. Using the environmental data, the IRS102provides a cost value to each potential route. The IRS102also considers the projected usage level of a route based on previous route assignments. Based on all of these considerations, one or more routes are selected from the list and delivered to the user109.FIG. 7shows a use case diagram that reflects a user's109interaction with the UE101and the interaction of the UE101with the IRS102, according to one embodiment.

In one embodiment, the IRS102is co-located within the UE101. In this embodiment, one user's UE101may communicate with the UE101of other users to gather data via the network interface204and the network205. In another embodiment, the IRS102resides in a location remote from the UE101, and route request messages are transmitted from the UE102to the IRS102via the network205.

The network205is used to facilitate communication between the various devices, modules and components of the travel routing system100. The network205may be any network or system generally known in the art, including the Internet, an intranet, a local area network (LAN), a wide area network (WAN), a metropolitan area network (MAN), a direct connection or series of connections, a cable television infrastructure, a cellular telephone network or any other network capable of facilitating communication between the devices, modules and other components of the travel routing system100. The network maybe wired, wireless or a combination thereof. Wired connections may be implemented using Ethernet, Universal Serial Bus (USB), RJ-11 or any other wired connection generally known in the art. Wireless connections may be implemented using wifi, wimax, bluetooth, infrared, cellular networks, satellite or any other wireless connection methodology generally known in the art. The network maybe implemented in a client-server, token-ring, peer-to-peer manner or any other network topology known in the art. Additionally, several networks may work alone or in communication with each other to facilitate communication in the network205.

The IRS102compiles environmental data from any device or network location capable of providing access to data that may be relevant to providing routing information to a user109. Examples of data sources employed by the IRS102include, without limitation, the event data source104, the traffic data source105, the roadway characteristics data source106, the weather data source107, and the geographic mapping data source108. The IRS102may request data from an external data source or the source may automatically send data to the IRS102at predefined or periodic intervals. Also, the IRS102can be updated with data stored on a storage medium. For example, the IRS102my obtain stored data from a floppy or hard magnetic disk, a magnetic tape, an optical disk such as a CD, CD-ROM, DVD, a flash memory device, or any other type of media generally known in the art that is capable of retaining digital data used for some interval of time. Data gathered from external sources may also be stored locally inside the IRS102. In particular, environmental data gathered from the external sources105,106,104,107,108is stored by the IRS102in one or more databases209,210,211,212,213. Referring to the use case diagram ofFIG. 6, in this example use cases associated with updating each of these external sources are shown in601,602,603,604and605as interacting with their respective data sources,104,105,106,107,108.

The event data source104provides information related to events that are currently impacting traffic conditions or events that may impact traffic conditions in the future. Examples of an event or event type include, but are not limited to, sports events, concerts, political rallies, emergency events, such as a building fires or floods, terrorist acts, and community events such as street festivals or parades, and religious services. Information about an event may include the venue for the event, a start time for the event, an end time (either projected or actual), expected or actual attendance, and roadway closures and restrictions associated with the event. Data received from the event data source104may be stored in an event database211local to the IRS102.

The traffic data source105provides information related to the real-time or near real-time traffic conditions on roadways, road segments, parking areas or any other area where traffic flow or volume is impacted and/or observed. This information may include congestion levels on roadways or portions thereof, traffic flow or rate of vehicle movement, a description of current road closings, bridge and railroad gate openings, accident reports, and an indication of police activity of the roadway. In addition to current traffic information, the traffic data source may provide historical traffic data and predictions of future traffic conditions. Potential sources of traffic data include, without limitation, government agency data, roadway observations from cameras or sensors, or Internet-based traffic data aggregators. Alternatively, the IRS102may record traffic data as it receives it, so that it maintains a record of historical traffic conditions. The IRS102may then forecast traffic conditions based on locally executed algorithms. A traffic database209in the IRS102may store information received from the traffic data source105as well as traffic data which is generated by the IRS102.

The roadway characteristics106data source provides information related to the physical characteristics of roadways, road segments, parking areas or other areas that are traversed by vehicles. This information may include, without limitation, the speed limit of each roadway, the number of lanes on the highway, exit destinations and merging roadways, weight limitations, toll locations, and capacity. The roadway characteristics database may also store information that indicates whether traffic on a roadway is controlled or uncontrolled (e.g., whether lane markings and traffic control signals are employed). Roadway characteristics may be stored in a roadway characteristics database210in the IRS102.

The weather data source107provides real-time or near real-time data related to current and historical weather conditions, as well as a prediction of future weather conditions, including radar and satellite data, temperature, wind and other generally observed weather conditions. Weather events tracked by the weather data source107include, without limitation, rain, tornados, hail, snow, ice, thunderstorms and hurricanes. The weather data source may also provide an indication of natural disasters such as avalanches, earthquakes, floods, tsunamis, volcanic eruptions, landslides, and mudslides. If a weather event is currently occurring, the weather data source107may provide an indication of the location of the event, as well as an indication of locations that will be impacted in the future. The IRS102may compile and store the weather data in a weather database212.

Geographic mapping data may be gathered from one or more mapping data sources108that provide mapping data that describes a plurality of roadways as well as the location of major landmarks. Roadways that are specified in the data may include, without limitation, interstate highways, intrastate highways, local roads, and residential streets. Each roadway may be described as single item or a roadway may be partitioned into one or more road segments (i.e., any section of a roadway that is utilized by travelers). Road segments may be further described by suggested usage. For example, a road segment that is a portion of a major highway may be described as usable by vehicles, but not pedestrians. Landmarks included in the mapping data may aid in the prediction of increased traffic conditions. Such landmarks may include, without limitation, police and fire stations, amusement parks, arenas, stadiums, parks, restaurants, shopping malls, and churches. The geographic mapping may be stored in mapping database213in the IRS102.

Route request messages received from the UE101are parsed by the IRS102to retrieve a user's specified start location and desired destination location. The mapping database213is queried by a route generation component207to determine one or more potential routes that link the start and destination locations. The relationship between a route request in the UE101and the initiation of route selection in the IRS102is illustrated by send route request use case701and determine routes use case706, respectively (seeFIG. 7). A route includes one or more road segments and may be distinguished from other routes through the inclusion or exclusion of one or more road segments.

In one embodiment, every potential route linking the start location and the destination location is retrieved from the mapping database213. In other embodiments, a subset of the complete set of available routes is selected based on factors such as distance, average speed limit, or toll charges. A user's preference for a particular type of road may also be considered. For example, a user may specify that only highways should be included in a proposed route.

The IRS102includes a cost determination component that determines a cost associated with each road segment included in the route list. This cost is a measure of the impact to optimal system performance associated with assigning a road segment to a new route. Note that cost is not user-specific; rather, the assignment's effect on all users is considered. The cost of a roadway segment is represented by one or more numerical values that are assigned on a set scale for the system. In one embodiment, cost is a function of two factors: the number of user routes affected by an assignment and the increase in travel time for each user affected. The IRS102may use current cost and other relevant information to forecast future cost values on road segments that could be included in a route. By considering projected cost, the IRS102can efficiently create routes even if a roadway segment will not be traversed in the near future.

A road segment's cost is related to its capacity, or the number of vehicles that can simultaneously travel the length of the road segment at the segment's posted speed limit. Cost increases as the number of vehicles simultaneously using the road segment increases. When the number of vehicles approaches capacity, cost may asymptotically rise. At this point, one or more users may need to be rerouted and any new routes would not include that road segment. The IRS102will attempt to distribute traffic in a manner that prevents roadways from reaching their capacity levels. This may entail routing a certain number of users along the road segment, while other users are routed via alternate segments.

Aside from capacity, environmental conditions such as vehicle accidents, weather conditions, and event occurrences may also impact the cost of a road segment. Thus, the IRS102uses information from each available source of environmental data to further refine the cost of each road segment included in the route list. The cost of a particular road segment may be increased to reflect an increased level of actual or projected traffic congestion. For example, if a major vehicle accident occurs on a particular road segment, the cost for that road segment and nearby segments will increase. As a result, when selecting a new route, the IRS102may route users around the accident area. For users that are in-transit on a previously generated route, the IRS102may reroute those users before they encounter the accident area or even residue local traffic congestion due to the accident. Information that may be considered in formulating new routes may include the final destination of the user, current and forecast traffic flows along the possible alternate routes, capacity of the road segments in alternate routes, and the expected duration of increased congestion level. It should be noted that, based on an analysis of the increased congestion levels, the IRS102may direct a certain number of users directly through the accident area, assuming that it is not completely blocked and it has some capacity for additional traffic.

In addition, the IRS102may review the routes of other users when calculating cost for a list of proposed routes, as the planned routes of other users provides an indication of the future cost of a road segment. For example, if the IRS102determines that many users will be routed along a particular road segment during a particular time interval, the IRS102may distribute other users along other available roadways during that time interval. Moreover, cost can be efficiently distributed over a plurality of roadways by allocating road segments appropriately.

Once the cost of each road segment has been determined by the IRS, the IRS102determines a route cost for each route included in the route list. In one embodiment, each route includes one or more roadway segments and route cost is calculated by summing the cost associated with each roadway segment. In another embodiment, one or more user preferences are considered in addition to the roadway segment costs. For example, the IRS102may consider routes followed by the user in the past to appropriately weight the cost of each new route. Once a cost for each route is determined, the route list may be ordered by route cost.

The IRS102may also consider the destination location of the user in calculating route cost. More specifically, the IRS102may determine the detriment associated with not providing a user with a particular route. For example, for a user traveling a relatively short distance between two points, it may be more efficient to provide the user with the shortest route between two points. This may be a single roadway segment. If another user is on much longer trip, the IRS could reroute that user because the diversion would be less noticeable over the longer travel time. For example, inFIG. 3a first user307is traveling from point A301to point F106, while a second user308is traveling from point B302to point E305. Both users307,308could traverse the C-E roadway segment; however, the IRS102may determine that the first user's route is long when compared with the second user308. Moreover, the IRS may note that there is a storm309on roadway segment C-E that may limit the flow of traffic along that portion. Thus, the first user307could be diverted to point D304and then to E305, thus avoiding the C-E roadway segment altogether.

Without further processing of the route list, each user may be directed to use the route with the lowest overall route cost. As many users proceed along this route, it may become congested, thus increasing the true travel time for the user. Meanwhile, there may be one or more road segments that remain under utilized or not utilized at all because routes containing those segments are ranked lower in route or segment cost on the list. These lower ranked routes may entail a slight increase in the travel time based solely on the external conditions as they existed at the time the list was created. Yet, as users begin using the higher ranked route(s), the lower ranked routes and segments will start to have lower true travel times.

To alleviate the problem of underutilization or non-utilization of routes and roadway segments, an optimal route selection component220of the IRS102efficiently distributes available routes and road segments over the users of the travel routing system100. The optimal route selection component220may distribute roadway segments randomly or by utilizing an algorithm such as round-robin; First In, First Out (FIFO); Last In, First Out (LIFO); or priority-based selection. Those skilled in the art in light of the present disclosure will appreciate that other distribution algorithms may be employed as well.

FIG. 8is a block diagram of a computer architecture or system1000through which the embodiments of the travel routing system100, including the intelligent routing system102, may be realized and/or implemented. A system bus1002transports data amongst the Central Processing Unit (CPU)1004, RAM1006, the Basic Input Output System (BIOS)1008and other components. The CPU1004may include a cache memory component1024. The computer system1000may include one or more external storage ports1017for accessing a hard disk drive, optical storage drive (e.g., CD-ROM, DVD-ROM, DVD-RW), flash memory, tape device, or other storage device (not shown). The relevant storage device(s) are connected through the external storage port1017which is connected to the system bus1002via a disk controller1022. A keyboard and pointing device (e.g. mouse. touch pad) (not shown) can be connected to the keyboard/mouse port(s)1012, and other I/O devices could be connected to additional I/O port(s)1013, which are connected to the system bus1002through the I/O controller1010. Additional ports or devices, such as serial ports, parallel ports, firewire adapters, or biometric devices (not shown), may be utilized through the I/O controller1010. A display device (not shown) can be connected to a display device port1014which is connected to the system bus1002through the video controller1015. A network device (not shown), including but not limited to an Ethernet device or other device having networking capability, can be connected to a network port1020which is connected through the network controller1016to the system bus1002. The computer system1000may be wirelessly connected to a network device that is configured for wireless operation (not shown), including but not limited to wireless routers, using an antenna1028connected to a wireless controller1026connected to the system bus1002, where the antenna transmits/receives signals to/from the network device. The computer system1000may include one or more USB ports1023. A USB device (not shown), including but not limited to a printer, scanner, keyboard, mouse, digital camera, storage device, PDA, cellular phone, biometric device, webcam, and I/O adapters can be connected to the USB port1023which is connected to the system bus1002through the USB controller1011. Other devices, such as cellular phones, PDAs, and other portable devices may also be connected wirelessly via a wireless I/O antenna1032that is connected to a wireless I/O controller1030. Examples of wireless I/O technologies include, but are not limited to, Bluetooth, Infrared (IR), and Radio-Frequency (RF). Audio devices, such as microphones, speakers, or headphones may be connected to a sound port1038that is connected to a sound controller1034that is connected to the system bus1002. Expansion slots1018can be comprised of Industry Standard Architecture (ISA) slots, Peripheral Component Interconnect (PCI) expansion slots, PCI Express expansion slots, Accelerated Graphics Port (AGP) slots or any other slot generally known in the art to allow additional cards to be placed into the computer system1000. These slots can be used to connect network cards, video cards, sound cards, modems and any other peripheral devices generally used with a computer. The computer system1000also includes a source of power (not shown), including but not limited to a power supply connected to an external source of power, and an internal or external battery. Detailed descriptions of these devices have been omitted for convenience only and should not be construed as limiting.

The IRS102may also adjust a route based on the intended route of one or more nearby users. For example, an accident on a roadway may impact many vehicles located on that roadway. Vehicles traveling on the roadway may become stopped or slowed as congestion rises on the roadway. Moreover, well-known alternate routes will also quickly become congested as drivers seek to avoid the affected roadway. To provide for more efficient re-routing of drivers, vehicles can communicate with one another to optimally route the traffic. Following this technique, the intended destination of each driver may be considered along with other relevant environmental conditions.

Once the IRS102determines a route for a user, a route message is sent from the IRS102to the UE101. This message may contain only the top-ranked route or it may contain the top-ranked route, along with one or more secondary route choices. These secondary route choices allow the user to select an alternative to the top-ranked route presented by the user. In the display potential routes use case703(seeFIG. 7), the user equipment101interacts with the determine routes use case706of the IRS102to display the routes to the user109. Routes may be displayed to user via the UE101using any technique understood in the art. For example, routes may be listed in text format or they may appear graphically highlighted on a map.

The user109may reject all routes presented by the IRS102by providing an indication to the user's equipment101. After receiving a rejection indication, the UE101sends a new route request message to the IRS102. The IRS may then regenerate an optimal route for the user, considering the routes previously rejected by the user. Thus, the send route rejection use case702interacts with the re-determine routes use case707of the IRS102to produce a new route list. Alternatively, the IRS102may simply consult the ranked route list previously generated for the user and select a new optimal route. The IRS can continue to generate routes for the user until the user's equipment indicates that the route suggested by the IRS is being followed by the user.

The user may select a route either by providing an indication to the UE101, or the UE101may monitor the user's position to determine that the route is being followed. After the UE101determines that the user has selected the route, it sends a message to the IRS102so that the IRS102may consider the user's selected route when making future routing decisions. Accordingly, the select route use case704provides the user's selection to the record route selection use case708. The user's selection is thus recorded by the IRS. Additionally, the UE101may continue to monitor the user's position in monitor user position use case705and periodically provide updates to the IRS102in record user position use case709.

The flow chart ofFIG. 4, showing steps401,402,403,404,405,406, reflects one embodiment of the process of generating a route for a user as described herein.

The efficiency of the IRS102is determined, in part, by the amount of data that it uses to make routing decisions. As explained above, one of the sources of data for the IRS102is previous routing assignments to other users. By considering which road segments will be used in the near future, the IRS can efficiently distribute roadway segments when developing new routes.

It may be problematic, however, if there are multiple routing service providers, with each service provider maintaining an independent IRS-type system. Under this scenario, a service provider's IRS may consider route assignments for that provider's users, while ignoring the planned routes of users of other routing service providers. To alleviate this problem and enhance the routing selection capabilities of each IRS, data may be shared between providers and individual IRSs. Providers may exchange data using any method of data transfer generally known in the art. For example, each IRS may automatically send a routing report at regular intervals to other IRS units.

Data may also be shared among a plurality of user equipment (UE) components. In one embodiment, the IRS102is co-located with the UE101. In this embodiment, there may be no centralized routing service provider; rather, each user independently makes routing decisions. The UE101may communicate with the equipment of other users via a peer-to-peer connection. Information may be gathered from external sources as well as other users in the area. By considering the destination of nearby users, utilization of local roadways can be maximized.

UE devices may communicate with each another via a wireless connection. Examples of potentially suitable wireless network types include, without limitation, Cellular Digital Packet Data (CDPD), High Speed Circuit Switched Data (HSCSD), Packet Data Cellular (PDC-P), General Packet Radio Service (GPRS), 1× Radio Transmission Technology, (1×RTT), Bluetooth, Infrared Light Transmission (IrDA), Multichannel Multipoint Distribution Service (MMDS), Local Multipoint Distribution Service (LMDS), Worldwide Interoperability for Microwave Access WiMAX, and IEEE 802.11 Wi-Fi.

User equipment may provide updated positional coordinates to the intelligent routing system. The system can use these coordinates to monitor if the user is following the suggested route. If the route is not being followed, the IRS may update the routing information provided to the user equipment.

In one embodiment, the IRS does not return a complete route to the user. Instead, dynamic turn by turn directions are delivered to the user in near-real time based on all data available the intelligent routing engine. This might be particularly useful in an urban setting where quickly changing traffic patterns could be detected using GPS or other position data (e.g., inertial sensing or cell triangulation). In the context of vehicle-based systems, incorporating traffic signal timing data could provide most efficient paths between origin and destination locations that are relatively close to each other for a large number of vehicles traversing the same roadways.

In a peer to peer network of GPS-enabled navigation systems, dynamic turn by turn directions can be delivered by monitoring the routes being provided to other users within the immediate vicinity and anticipating the expected utilization of those routes. For example, if many vehicles indicate that they will make a left turn at the same intersection, a vehicle may be directed to turn in advance of that intersection or even directed to a turn past the intersection to avoid a lengthy wait.

The embodiments of the present disclosure may be implemented with any combination of hardware and software. If implemented as a computer-implemented apparatus, the embodiment is implemented using means for performing all of the steps and functions described above.

The embodiments of the present disclosure can be included in an article of manufacture (e.g., one or more computer program products) having, for instance, computer useable media. The media has embodied therein, for instance, computer readable program code means for providing and facilitating the mechanisms of the embodiments of the present disclsoure. The article of manufacture can be included as part of a computer system or sold separately.