Method and system for a traffic management system based on multiple classes

A method of method of assigning routes for a plurality of users allocated to different classes is provided. A first group of users is identified based on a user classification, wherein each user of the first group of users has a first user classification. A second group of users is identified based on the user classification, wherein each user of the second group of users has a second user classification. The first user classification is different from the second user classification. A disutility value is calculated for each user of the first group of users and for each user of the second group of users using a travel disutility function based on an origin and a destination of each user of the first group of users and each user of the second group of users. A bi-level problem solver is executed to optimize the disutility value based on the user classification. A route is recommended for each user of the first group of users and for each user of the second group of users based on the bi-level problem execution.

FIELD

The field of the disclosure relates generally to traffic management systems. More specifically, the disclosure relates to a traffic management system that allocates traffic routes based on multiple tiers of user classification.

BACKGROUND

Currently, various types of information service providers (ISPs) provide traffic information to users. The various types of ISPs include traffic and map systems such as Westwood One, Traffic.com/Navteq, Clear Channel Traffic; portal systems such as Yahoo!, Google, MapQuest/AOL, MicroSoft MSN; wireless carriers such as Verizon Wireless, Cingular Wireless, Sprint Nextel, T-Mobile; telematics and navigation systems—GM OnStar, Ford, Toyota, XM Satellite Radio, Sirius Satellite Radio, Garmin, TomTom, Magellen, Motorola, AAA; and media companies such as NBC, ABC, CBS, etc. With the improvement in the quality and the granularity of traffic and travel time information, ISPs attempt to provide route-specific travel time information and dynamic route guidance information to individual users to influence the individual's travel choices including departure time, arrival time, route, destination, etc. An individual traveler relies on the ISP's information and personal experiences and preferences to make individual decisions for their travel choices.

As ISPs provide route-specific travel time information and dynamic route guidance information to more and more individual users, market penetration of actionable traffic information services may increase rapidly. As this type of actionable traffic information provision market penetration reaches a critical threshold, users with similar traffic and travel time information may compete for the shortest travel time routes creating new congestion for these routes. For example, users in the San Francisco Bay Area typically choose US 101 to travel from San Francisco to San Jose. When severe congestion occurs on US 101, for example, due to a major traffic accident, many ISPs advise motorists to use alternate routes I-280 or El Camino Real to avoid major congestion on US 101. However, with the diversion of a large number of users from US 101 to I-280 or El Camino Real these routes quickly become congested.

As the market penetration of personalized traffic and travel time information becomes higher and higher, customers of different ISPs may compete for limited roadways to find the quickest routes to their destinations. Such unregulated competition among ISPs and individual users results in the unnecessary waste of societal resources such as fuel and time, and increases the uncertainty of travel times for individual users' trips. Current traffic information dissemination is fragmented and not coordinated or connected because the many parties involved compete and do not communicate. Furthermore, no feedback process is provided between a motorist and an ISP. Thus, what is needed is a method and a system for the coordinated allocation of traffic routes. What is additionally needed is a method and a system for allocating traffic routes with consideration of route congestion.

SUMMARY

A method and a system for the coordinated allocation of traffic routes is provided in an exemplary embodiment. For an ISP, a traffic and travel time information system provides tiered traffic and travel time information to different classes of users so that higher classes of users obtain higher quality and higher valued traffic and travel time information to enable faster travel or to reduce congestion. Additionally, for an urban area, a system coordinator coordinates the provision of traffic and travel time information to individual users across multiple ISPs.

In another exemplary embodiment, a method of assigning routes for a plurality of users allocated to different classes is provided. A first group of users is identified based on a user classification, wherein each user of the first group of users has a first user classification. A second group of users is identified based on the user classification, wherein each user of the second group of users has a second user classification. The first user classification is different from the second user classification. A disutility value is calculated for each user of the first group of users and for each user of the second group of users using a travel disutility function based on an origin and a destination of each user of the first group of users and each user of the second group of users. A bi-level problem solver is executed to optimize the disutility value based on the user classification. A route is recommended for each user of the first group of users and for each user of the second group of users based on the bi-level problem execution.

In an exemplary embodiment, a device for assigning routes for a plurality of users allocated to different classes is provided. The device includes, but is not limited to, a computer-readable medium having computer-readable instructions stored thereon, a communication interface, and a processor. The computer-readable instructions implement the operations of the method of assigning routes for a plurality of users allocated to different classes. The communication interface sends the recommended route to each user of the first group of users and to each user of the second group of users. The processor is coupled to the communication interface and to the computer-readable medium and is configured to execute the instructions.

In yet another exemplary embodiment, a computer-readable medium is provided. The computer-readable medium has computer-readable instructions therein that, upon execution by a processor, cause the processor to implement the operations of the method of assigning routes for a plurality of users allocated to different classes.

DETAILED DESCRIPTION

With reference toFIG. 1, a traffic management system100is provided in accordance with an exemplary embodiment. Traffic management system100provides a travel time and traffic information provision system for a traffic information service provider (ISP). In the exemplary embodiment ofFIG. 1, traffic management system100comprises a class management system102and a user network103. Class management system102allocates traffic route information for users of user network103. Class management system102may include a plurality of class managers and a master class manager104. For example, with reference to the exemplary embodiment ofFIG. 1, the plurality of class managers include a class A manager106a, a class B manager106b, a class C manager106c, a class D manager106d. A class manager106(shown in more detail with reference toFIG. 2) manages and coordinates the provision of travel time and traffic information to a plurality of user classes of user network103who access the same types of traffic and travel time information services.

Class management system102may comprise one or more computing devices which perform the functionality described. If class management system102is comprised of a plurality of computing devices, the computing devices may communicate using one or more network. Class management system102optimizes the travel time and traffic information provision for a plurality of user classes, while coordinating the interaction and feedback of different user classes.

Master class manager104manages and coordinates the processing of the plurality of class managers in providing traffic information for each class of users. Master class manager104optimizes the provision of traffic and travel time information services based on business objectives, user needs, raw traffic data provided by third party traffic data providers and coordinates the interaction of the plurality of user classes to optimize the travel time and traffic information provision for each class of users based on the provision of traffic information and user compliance and feedback. Master class manager104optimizes the provision of traffic and travel time information services to serve each class of users according to their classification and priority ranking under traffic congestion caused by: (1) users without a subscription to the ISP's information services, (2) users served by the ISP, and (3) users served by other ISPs. A bi-level dynamic travel decision making problem finds the optimal travel time and dynamic routing solutions for traffic management system100. Specifically, for each class j users at any time interval, the objective of master class manager104is to minimize a travel disutility between each origin-destination, i.e. to minimize
πjrs(t)  (1)
subject to πjrs(t)≧πj-1rs(t)∀r,s,j(2)
and πijrs(t)≧πjrs(t)∀r,s,i,j(3)
if the ISP chooses or recommends routes for a traveler i at time t,
πijrs(t)=πjrs(t)∀r,s,i,j(4)
and network flow constraints where πijrs(t) is the travel disutility for traveler i in class j departing origin r at time t toward destination s and πjrs(t) is the minimum travel disutility for users in class j departing origin r at time t toward destination s.

As noted in equation (2), the travel disutility for class j is greater than or equal to the travel disutility for class j−1 (j=2, 3, 4, . . . , N) such that class1users have the lowest travel disutility among all classes. As noted in equations (3)-(4), when the ISP finds and suggests a route for traveler i in class j, the travel disutility for traveler i is equal to the travel disutility for all users in class j receiving a best route recommendation from the ISP. For example, if travel disutility is simply represented by travel time, equation (2) ensures that class1users have the lowest travel time routes, and class2users have lower travel time routes than class3users, etc. Equations (3)-(4) ensure that all users in class1receive dynamic routing suggestions which have equal and minimum travel times.

Additionally, for users in class j at any time interval, master class manager104minimizes the travel disutility between each origin-destination, i.e., to minimize
πijrs(t)  (5)
subject to πijprs(t)≧πijrs(t)∀r,s,i,j,p(6)
if the ISP chooses or recommends routes p for a traveler i at time t,
πijprs(t)=πijrs(t)∀r,s,i,j,p(7)
and network flow constraints where πijprs(t) is the travel disutility for traveler i in class j departing origin r at time t toward destination s via route p and πijrs(t) is the minimum travel disutility for users i in class j departing origin r at time t toward destination s. As noted in equations (6)-(7), when the ISP finds and suggests a route p for user i in class j, the travel disutility on route p for user i is equal to the minimum travel disutility from origin r to destination s at time interval t.

A variety of methods may be used to determine a set of solutions for equations (1)-(7) for a plurality of users allocated among a plurality of classes. For example, the methods described in LeBlanc, L and Boyce, D. E., A BILEVEL PROGRAMMING ALGORITHM FOR EXACT SOLUTION OF THE NETWORK DESIGN PROBLEM WITH USER-OPTIMAL FLOWS, Transpn. Res.-B, Vol. 20B, No. 3, pp. 259-265, 1986 could be used to solve equations (1)-(7). Simulation models can be used to solve equations (1)-(7) also. Moreover, a hybrid approach using both analytic and simulation models could be used to solve (1)-(7).

With reference toFIG. 9, exemplary operations associated with determining a set of solutions for equations (1)-(7) for a plurality of users allocated among a plurality of classes are described. Additional, fewer, or different operations may be performed, depending on the embodiment. Additionally, the order of presentation of the operations ofFIG. 9is not intended to be limiting. In an operation900, first minimum travel disutility routes between each origin-destination pair are determined based on free-flow traffic conditions producing the initial minimum travel disutilityπijrs(t) for each class j (j=1, 2, . . . , J) and each traveler i and the initial minimum travel disutilityπjrs(t) for each class j. To consider incremental traffic flow loading, in an operation902, a class counter j is initialized to J the lowest ranking class index. In an operation904, minimum travel disutility routes are assigned to class j (j=J, J−1, . . . , 1) users. In an operation906, the traffic network is loaded with traffic flows generated by the assignment of routes to class j users as known to those skilled in the art. In an operation908, second minimum travel disutility routes are determined between each origin-destination pair based on the latest traffic conditions after loading the traffic flows generated by class j (j=J, J−1, . . . , 2) users. In an operation910, a determination is made concerning whether or not all classes have been processed. If all classes have not been processed, in an operation912, the class counter j is decremented, and processing continues at operation904. If all classes have been processed, processing continues at an operation914. Operations904-912produce an updated minimum travel disutilityπijrs(t) for class j−1 (j=J, J−1, . . . , 2) and each traveler i and an updated minimum travel disutilityπjrs(t) for each class j−1 (j=J, J−1, . . . , 2). In operation914, the resulting minimum travel disutilityπijrs(t) for class j (j=J, J−1, . . . , 1) and each traveler i and the updated minimum travel disutilityπjrs(t) for each class j (j=J, J−1, . . . , 1) are used to recommend routes to the travelers.

Several approaches may be used to improve the accuracy of the solution procedure discussed with reference toFIG. 9. One example approach is to design multiple sub-classes for each class of users and to implement the operations of900-914for a larger number of sub-classes of users. The more sub-classes used, the higher the accuracy the solution procedure tends to produce. For example, an ISP may have only two classes of users. For computational purposes, each class of users may be further classified into five sub-classes resulting in ten sub-classes of users used in the above incremental traffic flow loading. After completion of operation914, the results for sub-classed1-5may be averaged to represent the results for class1, and the results for sub-classed6-10may be averaged to represent the results for class2.

As shown inFIG. 1, master class manager104may include a plurality of sub-modules132, a communication interface134, a memory136, and a processor138. Different and additional components may be incorporated into master class manager104. For example, master class manager104may include a display and/or an input interface to facilitate user interaction with the plurality of sub-modules132. Communication interface134provides an interface for receiving and transmitting data between devices using various protocols, transmission technologies, and media as known to those skilled in the art. The communication interface may support communication using various transmission media that may be wired or wireless. Master class manager104may include a plurality of communication interfaces that use the same or a different transmission technology and/or transmission media. For example, if master class manager104and the plurality of class managers are implemented in different computing devices, communication interface may support the exchange of data between master class manager104and the plurality of class managers.

Memory136is an electronic holding place or storage for information so that the information can be accessed by processor138as known to those skilled in the art. Master class manager104may include one or more memories that use the same or a different memory technology. Memory technologies include, but are not limited to, any type of RAM, any type of ROM, any type of flash memory, etc. Master class manager104also may includes one or more drives that support the loading of a memory media such as a compact disk or digital video disk.

Processor138executes instructions as known to those skilled in the art. The instructions may be carried out by a special purpose computer, logic circuits, or hardware circuits. Thus, processor138may be implemented in hardware, firmware, software, or any combination of these methods. The instructions may be written using one or more programming language, scripting language, assembly language, etc. Processor138executes an instruction, meaning that it performs the operations called for by that instruction. Processor138operably couples with communication interface134and with memory136to receive, to send, and to process information. Processor138may retrieve a set of instructions from a permanent memory device and copy the instructions in an executable form to a temporary memory device that is generally some form of RAM. Master class manager104may include a plurality of processors that use the same or a different processing technology.

The plurality of sub-modules132may be implemented using one or more computing device. If the plurality of sub-modules132are implemented in different computing devices, each computing device may include a communication interface, memory, and/or processor. Thus, the plurality of sub-modules132may be implemented in a single computing device, in a single location, in a single facility, and/or may be remote from one another. The plurality of sub-modules132may include a map and geographic information system (GIS) application112, an information processor114, a point of interest (POI) and location based service (LBS) information receiver116, a coordinator118, a route assignor120, a traffic data feed receiver122, a traffic data fusion engine124, a feedback provider126, a traffic assignment calculator128, and a disutility optimizer130. The plurality of sub-modules132perform operations associated with optimizing the provision of traffic and travel time information services based on the class of each user. The operations may be implemented using hardware, firmware, software, or any combination of these methods.

Map and GIS application112provides a digital map database and the GIS tools for the data manipulation of traffic data, POI data, and LBS information. information processor114handles the information processing specific for the ISP, including information coverage, update frequency, and background information. POI and LBS information receiver116receives time-sensitive and location-sensitive POI and LBS information from third parties. Coordinator118manages the interaction of Master class manager104with the plurality of class managers. Route assignor120generates personalized, route-specific traffic information and time-dependent best routes for individual users. For example, if there are 100 class A users who desire to travel from Point A to Point B at 8 a.m. on a Tuesday, after traffic assignment calculator128completes its calculation and generates two best time-dependent routes between Point A and Point B for class1users at 8 a.m., route assignor120assigns the two best time-dependent routes to 100 class1users and generates personalized dynamic routing and travel time information for each of the 100 users. Route1may receive 40 users and Route2may receive 60 users. Such an assignment applies the embedded dynamic user-optimal routing criteria so as to avoid creating additional congestion on the two best time-dependent routes.

Traffic data feed receiver122receives one or more raw traffic data feeds. Fusion engine124fuses the traffic data received from the one or more raw traffic data feeds and creates a customized traffic database appropriate for its own applications such as applications in trip planning, en-route dynamic routing, and dynamic navigation in areas such as web, mobile, telematics, media, fleet, and government. Feedback provider126generates feedback information related to data quality and user responses to the route assignments. Traffic assignment calculator128solves equations (1)-(7) of the bi-level problem and computes the best time-dependent routes for each class of users at each time interval. The time interval may be defined as increments of one second and can range from one second to five minutes or longer. Disutility optimizer130generates an optimal travel disutility based on user input and the ISP's default parameters and is used in conjunction with traffic assignment calculator128.

For class i, master class manager104further uses a set of route-based dynamic route choice decision tools and models to assign and disperse users onto equal travel disutility routes at each decision time instant. The assignment and dispersion spreads traffic congestion over feasible routes between each origin-destination. When a traveler navigates through traffic congestion, they can receive updated best route information based on travel disutility updates at each time interval.

The plurality of class managers minimize the travel disutility or travel times for each traveler in that class under the constraint of congestion caused by other vehicles. The travel disutility for traveler i may be defined as a function of one or more of the following factors: travel time, travel cost, travel distance, personal preference, comfort, convenience, safety, security, ISP information accuracy, ISP information reliability, ISP information update frequency, etc. Personal preference represents a traveler's preference, for example, for driving on a highway versus arterial roads. Convenience represents the impact of a route-specific POI and LBS. Safety may relate to a possibility of a wreck; whereas security may relate to a possibility of a crime. To represent social responsibility and equity, the consideration of high-occupancy vehicles may be considered. For an ISP that considers social responsibility, a high-occupancy vehicle may be classified into a higher level class when compared to other vehicles having similar conditions.

An example function of travel disutility is a linear weighted average of the above factors defined as disutility(i)=a1*travel_time(i)+a2*travel_cost(i)+a3*travel_Distance(i)+a4*personal_preference(i)+a5*comfort(i)+a6*convenience(i)+a7*safety(i)+a8*security(i)+a9*ISP_information_accuracy(i)+a10*ISP_information_reliability(i)+a11*ISP_information_update_frequency(i)+a12*other_factors(i) where ajis the weighting factor for traveler i, j=1, 2, . . . , 12. The travel disutility for traveler i can be determined by traveler i based on the formulae provided by an ISP. The travel disutility information can be stored on a computing device, such as an in-vehicle navigation system, a mobile device such as a wireless phone, a computer of any form factor including a desktop, laptop, and pocket computer, an Apple™ iPod, etc. Additionally, the travel disutility information can be stored on a server managed by the ISP or a password protected public site. A user may update the travel disutility function and conduct calibration of the travel disutility function based on personal driving and travel experiences.

Class A manager106a, class B manager106b, class C manager106c, and class D manager106dare classified based on the user classifications defined for the ISP. For example, class A manager106amay be associated with users assigned to a class A membership. The user classification may be determined, for example, based on a subscription fee paid by a user, a transaction fee paid by a user, a length of membership, a sponsorship, an advertisement income, a sponsorship of the user, a seniority ranking, and a service provider as well as other valuable consideration related to the user's membership with an ISP. A higher class of users receives a class of travel time and traffic information service having a lower travel disutility or a higher value than a lower class of users. Class A manager106a, class B manager106b, class C manager106c, and class D manager106dmay be integrated in the same or different computing devices.

User network103may include a plurality of user devices and a network110. In the exemplary embodiment ofFIG. 1, the plurality of user devices include a pocket computer108a, a laptop108b, a first wireless phone108c, and a second wireless phone108dwhich communicate with class management system102. A user of traffic management system100accesses the functionality provided by traffic management system100using the user device that may be integrated into a vehicle. Thus, each user device of the plurality of user devices may include an in-vehicle navigation system, a wireless phone, a computer of any form factor including a laptop, a pocket computer, and a personal digital assistant, a personal navigation device, an Apple™ iPod, etc. Network110may be wired or wireless.

With reference toFIG. 2, a class manager106may include a plurality of sub-modules200, a communication interface202, a memory204, and a processor206. Class A manager106a, class B manager106b, class C manager106c, and class D manager106dare each examples of class manager106. Different and additional components may be incorporated into class manager106. If class manager106is integrated with master class manager104, one or more of communication interface202, memory204, and processor206of class manager106may be the same as communication interface134, memory136, and processor138. In the exemplary embodiment ofFIG. 1, class A manager106a, class B manager106b, class C manager106c, and class D manager106dmay be integrated into the same computing device or implemented at different computing devices. As a result, class manager106may or may not include communication interface202, memory204, and processor206.

The plurality of sub-modules200may include a coordinator208, a classification manager210, a POI and LBS information provider212, a disutility calculator214, an information provider216, and a feedback receiver218. Coordinator208interacts with master class manager104. Classification manager210handles user registration information and classifies users based on the ISP's rules. POI and LBS information provider212overlays personalized, route-specific POI and LBS information for user-selected routes in combination with disutility calculator214and information provider216.

Disutility calculator214is used to personalize travel disutility based on the traveler's personal experiences and personal preferences. For example, aggressive young drivers may prefer freeways over arterials. As a result, their personalized travel disutility for freeway routes is lower than for senior drivers who tend to drive more slowly. A traveler uses their self-defined travel disutility to make travel choice decisions. Information provider216provides personalized, route-specific travel time and traffic information for individual users. Feedback receiver218receives feedback information from individual users. For a traveler, the feedback information may include the actual route taken by the traveler and compliance information of the traveler with the dynamic routing information provided by the ISP. Thus, a traveler may choose not to follow the routes that the ISP recommends.

With reference toFIG. 3, a user device108used to interact with class management system102may include a display300, an input interface302, a communication interface304, a memory306, a processor308, and a map and GIS application310. Pocket computer108a, laptop108b, first wireless phone108c, and second wireless phone108dare each examples of user device108. Exemplary user devices include an in-vehicle navigation system, a wireless phone, a computer of any form factor including a laptop, a pocket computer, and a personal digital assistant, a personal navigation device, an Apple™ iPod, etc. Different and additional components may be incorporated into user device108. User device108may further include a disutility calculator that can be utilized by the user instead of disutility calculator214(shown with reference toFIG. 2). In other words, the traveler may store their self-defined travel disutility on user device108. User device108may be integrated into a vehicle or may be mobile. Display300presents information to a user of user device108as known to those skilled in the art. For example, display300may be a thin film transistor display, a light emitting diode display, a liquid crystal display, or any of a variety of different displays known to those skilled in the art.

Input interface302provides an interface for receiving information from the user for entry into user device108as known to those skilled in the art. Input interface302may use various input technologies including, but not limited to, a keyboard, a pen and touch screen, a mouse, a track ball, a touch screen, a keypad, one or more buttons, voice, etc. to allow the user to enter information into user device108or to make selections presented in a user interface displayed on display300. Input interface302may provide both an input and an output interface. For example, a touch screen both allows user input and presents output to the user.

Communication interface304provides an interface for receiving and transmitting data between user device108and class management system102using various protocols, transmission technologies, and media as known to those skilled in the art. The communication interface may support communication using various transmission media that may be wired or wireless. User device108may include a plurality of communication interfaces that use the same or a different transmission technology and/or transmission media. Memory306is an electronic holding place or storage for information so that the information can be accessed by processor308as known to those skilled in the art. User device108may include one or more memories that use the same or a different memory technology. Processor308executes instructions as known to those skilled in the art. The instructions may be carried out by a special purpose computer, logic circuits, or hardware circuits. Thus, processor308may be implemented in hardware, firmware, software, or any combination of these methods. The term “execution” is the process of running an application or the carrying out of the operation called for by an instruction. The instructions may be written using one or more programming language, scripting language, assembly language, etc. Processor308executes an instruction, meaning that it performs the operations called for by that instruction. Processor308operably couples with display300, input interface302, communication interface304, and memory306to receive, to send, and to process information. Processor308may retrieve a set of instructions from a permanent memory device and copy the instructions in an executable form to a temporary memory device that is generally some form of RAM. User device108may include a plurality of processors that use the same or a different processing technology.

Map and GIS application310performs operations associated with presentation of a map and routes using a digital map database and GIS tools for the data manipulation of traffic data, POI data, and LBS information. The operations may be implemented using hardware, firmware, software, or any combination of these methods. With reference to the exemplary embodiment ofFIG. 3, map and GIS application310is implemented in software stored in memory306and accessible by processor308for execution of the instructions that embody the operations of map and GIS application310. Map and GIS application310may be written using one or more programming languages, assembly languages, scripting languages, etc. In an exemplary embodiment, user device108may interact with information provider216(shown with reference toFIG. 2) to receive the personalized, route-specific traffic and travel time information which may be displayed to the user using map and GIS application310on display300. Alternatively, the user may use map and GIS application310to make their dynamic travel decisions.

The operations of traffic management system100can be explained using an example. A traveler subscribes to a travel time and traffic information service of the ISP. Class manager106uses classification manager210to collect basic demographic information and personal preference information associated with the traveler. Disutility calculator214customizes parameters based on the input of the traveler to calculate a personalized travel disutility. Coordinator208of class manager106sends user information to master class manager104for further processing. Coordinator118of master class manager104receives the user information from Coordinator208of class manager106. Traffic assignment calculator128of master class manager104uses the user information and information from other users to estimate and predict the best travel time and routing decisions for all classes of users. Route assignor120produces dynamic routing information for each class of users. Information provider216of class manager106presents the user with personalized, route-specific travel time and traffic information as well as dynamic routing information. POI and LBS information provider212of class manager106adds related POI and LBS information for the best routes assigned to the user. The user uses their user device108to receive the personalized, route-specific travel time and traffic information from information provider216of class manager106. Any feedback from the traveler is received by feedback receiver218of class manager106. Because the user may or may not rely on the travel time and traffic information as well as dynamic routing information from information provider216of class manager106to make their own travel decisions, feedback is useful for traffic assignment calculator128of master class manager104to make a better estimation and prediction for travel time and coordinated routing.

For an urban area in particular, it is beneficial and more efficient for a single super ISP (SISP) to coordinate the traffic and travel time information provision among a plurality of ISPs and for a majority of the users. Consequently, all classes of users from all ISPs associated with the SISP have similar coordination of travel time, traffic, and dynamic routing information provision, although at its own discretion, each ISP may provide different travel time, traffic, and dynamic routing information services bundled with other location sensitive information. For the SISP, all users are considered in one pool in classification and travel time, traffic, and dynamic routing information provision.

With reference toFIG. 4, a hierarchical traffic management system400for a SISP is shown in accordance with an exemplary embodiment. For a region or a country, multiple ISPs exist and compete for users who typically drive on the same roadways in the same region or city. Competing ISPs may provide the same best travel disutility routes to their users so that many users may end up choosing the same routes at the same time interval, thus generating new congestion on routes which recently were determined to have the lowest travel disutility. This type of competition among ISPs and information provision methods does not serve users well, reduces the credibility of ISPs, causes an unnecessary waste of resources, and increases the societal costs. A coordinated approach among competing ISPs provides a balanced traffic and travel time information provision approach that disperses traffic among various types of congested routes.

Hierarchical traffic management system400includes multiple class management tiers that interact to provide a balanced traffic and travel time information provision approach that disperses traffic among various types of congested routes. Hierarchical traffic management system400may include a plurality of network class managers, a plurality of network master class managers, a second tier coordinator404, a plurality of second tier class managers, and a master system manager408. Master system manager408manages and coordinates the acts of the plurality of second tier class managers, which generate and manage traffic and travel time information for each class of users. Master system manager408optimizes the overall offering of traffic, travel time, and dynamic routing information services for all ISPs and all users based on collective business objectives of all associated ISPs, user needs, raw traffic data provided by third party traffic data providers. Master system manager408coordinates the interaction of the plurality of second tier class managers to optimize the travel time and dynamic routing information provision for the class of users based on traffic information provision and user compliance and feedback. The plurality of second tier class managers manage and coordinate the provision of travel time and dynamic routing information to a plurality of classes of users generating the same type of travel time and dynamic routing information for the same class of users. Second tier coordinator404manages and coordinates the provision of traffic, travel time, and dynamic routing information to a plurality of ISPs, regardless of the ISP to which a user belongs. Second tier coordinator404coordinates the interaction of all associated ISPs and all users in order to optimize the travel time, traffic, and dynamic routing information provision for the class of users based on compliance and feedback from all users of all associated ISPs.

The objective of master system manager408is to optimize the information provision of traffic, travel time, and dynamic routing information to serve each class of users according to their classification and priority ranking within the SISP. In such a context, the traffic congestion under consideration is caused by: (1) background traffic served by ISPs associated with the SISP, (2) background traffic served by ISPs not associated with the SISP, and (3) background traffic not served by any ISP. For example, Google™, GM OnStar®, Verizon Wireless, MicroSoft®, and Garmin™ may be the ISPs associated with the SISP for a city. Each ISP has its own classification of users and each ISP submits its classification and pricing scheme to the SISP. The SISP pools the classes of users from all of the ISPs and defines its own classification scheme.

In the exemplary embodiment ofFIG. 4, the plurality of network class managers include a network A class A manager401a, a network A class B manager401b, a network B class A manager401c, a network B class B manager401d, a network C class A manager401e, and a network C class B manager401f. Network A class A manager401aand network A class B manager401bmay be associated with a first ISP or network A of users and may be integrated in the same or different computing devices. Network B class A manager401cand network B class B manager401dmay be associated with a second ISP or network B of users and may be integrated in the same or different computing devices. Network C class A manager401eand network C class B manager401fmay be associated with a third ISP or network C of users and may be integrated in the same or different computing devices.

In the exemplary embodiment ofFIG. 4, the plurality of network master class managers include a network A master class manager402a, a network B master class manager402b, and a network C master class manager402c. Network A class A manager401aand network A class B manager401binteract with network A master class manager402a. Network B class A manager401cand network B class B manager401dinteract with network B master class manager402b. Network C class A manager401eand network C class B manager401finteract with network C master class manager402c. Thus, the exemplary embodiment ofFIG. 4include three ISPs.

Second tier coordinator404may include a plurality of sub-modules410, a communication interface412, a memory414, and a processor416. Different and additional components may be incorporated into second tier coordinator404. For example, second tier coordinator404may include a display and/or an input interface to facilitate user interaction with the plurality of sub-modules410. Communication interface412provides an interface for receiving and transmitting data between devices using various protocols, transmission technologies, and media that may be wired or wireless as known to those skilled in the art. Second tier coordinator404may include a plurality of communication interfaces that use the same or a different transmission technology and/or transmission media. Memory414is an electronic holding place or storage for information so that the information can be accessed by processor416as known to those skilled in the art. Second tier coordinator404may include one or more memories that use the same or a different memory technology. Processor416executes instructions as known to those skilled in the art and discussed previously with reference to processor138shown with reference toFIG. 1. Second tier coordinator404may include a plurality of processors that use the same or a different processing technology.

The plurality of sub-modules410may be implemented using one or more computing device. If the plurality of sub-modules410are implemented in different computing devices, each computing device may include a communication interface, memory, and/or processor. Thus, the plurality of sub-modules410may be implemented in a single computing device, in a single location, in a single facility, and/or may be remote from one another. The plurality of sub-modules410may include a classification manager418, a classification index manager420, a feedback receiver422, and a route assignor424. The plurality of sub-modules410perform operations associated with optimizing the provision of traffic and travel time information services based on the class of each user. The operations may be implemented using hardware, firmware, software, or any combination of these methods.

With reference toFIG. 4, the plurality of sub-modules410of second tier coordinator404may include classification manager418, classification index manager420, feedback receiver422, and route assignor424. Classification manager418re-defines the classification of the traveler in conjunction with the information from other users from all of the ISPs, for example networks A, B, and C. Classification index manager420builds a conversion index to translate a user classification of master system manager408into the user classification for all ISPs. Any feedback from ISPs is received by feedback receiver422. Specifically, user compliance information for each ISP is useful for master system manager408to estimate and to predict the best travel time and dynamic routing information for all classes of users and all of the ISPs.

Second tier coordinator404manages travel time and traffic information delivery for network A master class manager402a, network B master class manager402b, and network C master class manager402c. Second tier coordinator404assigns different sets of best routes to the various ISPs. For example, second tier coordinator404may assign two best routes to Google and another two best routes to Verizon Wireless for the same origin-destination at the same time interval. Network A master class manager402a, network B master class manager402b, and network C master class manager402cfunction as the information receivers and feedback providers in such a scenario. Based on its own business operating mechanism, network A master class manager402a, network B master class manager402b, and network C master class manager402cmanage travel time, traffic, and dynamic routing information delivery for its end users who subscribe to the ISP service.

With reference toFIG. 5, a network master class manager402may include a plurality of sub-modules500, a communication interface502, a memory504, and a processor506. Network A master class manager402a, network B master class manager402b, and network C master class manager402care each examples of network master class manager402. Different and additional components may be incorporated into network master class manager402. The plurality of sub-modules500may be implemented using one or more computing device. If the plurality of sub-modules500are implemented in different computing devices, each computing device may include a communication interface, memory, and/or processor. Thus, the plurality of sub-modules500may be implemented in a single computing device, in a single location, in a single facility, and/or may be remote from one another. The plurality of sub-modules500may include a map and GIS application508, an information processor510, a POI and LBS receiver512, a coordinator514, a route assignor516, a traffic data feed receiver518, a fusion engine520, a feedback provider522, and a disutility optimizer524. The plurality of sub-modules600perform operations associated with managing travel time, traffic, and dynamic routing information delivery for its end users who subscribe to the ISP service. The operations may be implemented using hardware, firmware, software, or any combination of these methods. For each ISP network, network master class manager402receives dynamic route and travel plan information from second tier coordinator404. Network master class manager402refines the dynamic route and travel plan information with its own user classification and traffic information generation.

With reference to the exemplary embodiment ofFIG. 4, the plurality of second tier class managers includes a second tier class A manager406a, a second tier class B manager406b, a second tier class C manager406c, and a second tier class D manager406d. With reference toFIG. 6, a second tier class manager406may include a plurality of sub-modules600, a communication interface602, a memory604, and a processor606. Communication interface602provides an interface for receiving and transmitting data between devices using various protocols, transmission technologies, and media that may be wired or wireless as known to those skilled in the art. Second tier class manager406may include a plurality of communication interfaces that use the same or a different transmission technology and/or transmission media. Memory604is an electronic holding place or storage for information so that the information can be accessed by processor606as known to those skilled in the art. Second tier class manager406may include one or more memories that use the same or a different memory technology. Processor606executes instructions as known to those skilled in the art and discussed previously with reference to processor138shown with reference toFIG. 1. Second tier class manager406may include a plurality of processors that use the same or a different processing technology. Second tier class A manager406a, second tier class B manager406b, second tier class C manager406c, and second tier class D manager406dare each examples of second tier class manager406. Different and additional components may be incorporated into second tier class manager406.

The plurality of sub-modules600may be implemented using one or more computing device. If the plurality of sub-modules600are implemented in different computing devices, each computing device may include a communication interface, memory, and/or processor. Thus, the plurality of sub-modules600may be implemented in a single computing device, in a single location, in a single facility, and/or may be remote from one another. The plurality of sub-modules600may include a coordinator608, a classification manager610, a disutility calculator612, and information provider614. Coordinator608interacts with master system manager408. Classification manager610handles user registration information and classifies users based on the rules of master system manager408. The plurality of sub-modules600perform operations associated with generating and managing traffic and travel time information for each class of users. The operations may be implemented using hardware, firmware, software, or any combination of these methods.

As shown with reference toFIG. 7, master system manager408may include a plurality of sub-modules700, a communication interface702, a memory704, and a processor706. Different and additional components may be incorporated into master system manager408. For example, master system manager408may include a display and/or an input interface to facilitate user interaction with the plurality of sub-modules700. Communication interface702provides an interface for receiving and transmitting data between devices using various protocols, transmission technologies, and media that may be wired or wireless as known to those skilled in the art. Master system manager408may include a plurality of communication interfaces that use the same or a different transmission technology and/or transmission media. If master system manager408and the plurality of second tier class managers are implemented in different computing devices, communication interface702may support the exchange of data between master system manager408and the plurality of second tier class managers.

Master system manager408, second tier class A manager406a, second tier class B manager406b, second tier class C manager406c, second tier class D manager406d, and/or second tier coordinator404may be integrated in one or more computing devices. As a result, master system manager408, second tier class A manager406a, second tier class B manager406b, second tier class C manager406c, second tier class D manager406d, and/or second tier coordinator404may or may not include separate communication interfaces, separate memories, and separate processors.

Memory704is an electronic holding place or storage for information so that the information can be accessed by processor706as known to those skilled in the art. Master system manager408may include one or more memories that use the same or a different memory technology. Processor706executes instructions as known to those skilled in the art and discussed previously with reference to processor138shown with reference toFIG. 1. Master system manager408may include a plurality of processors that use the same or a different processing technology.

The plurality of sub-modules700may be implemented using one or more computing device. If the plurality of sub-modules700are implemented in different computing devices, each computing device may include a communication interface, memory, and/or processor. Thus, the plurality of sub-modules700may be implemented in a single computing device, in a single location, in a single facility, and/or may be remote from one another. The plurality of sub-modules700may include a map and GIS application708, an information manager710, a feedback generator712, an information processor714, a traffic data feed receiver716, a feedback provider718, a traffic data fusion engine720, a travel plan generator722, a traffic assignment calculator724, and a disutility optimizer726. The plurality of sub-modules700perform operations associated with optimizing the provision of traffic and travel time information services based on the class of each user. The operations may be implemented using hardware, firmware, software, or any combination of these methods.

Information processor714handles the information processing specific for the master system manager408, including information coverage, update frequency, and background information. Information manager710re-groups all users from all associated ISP networks into new classes based on similar classification schemes used by the ISP networks. Subsequently, a classification index is created to convert the classification of master system manager408to the classification of all associated ISP networks, i.e., networks A, B, C. When each ISP network deals with its end users, the ISP network may use a different classification system. To coordinate with master system manager408for travel time, traffic, and dynamic routing information generation purposes, the ISP network uses pre-defined user classifications and a classification index. Furthermore, information manager710stores and manages all demographic and user behavior information for all end users. The demographic and user behavior information is used by traffic assignment calculator724, disutility optimizer726, and travel plan generator722.

Feedback generator712produces feedback information for all of the ISP networks, including consistency of user classification. Map and GIS application708provides the basis for operating traffic assignment calculator724, disutility optimizer726, and travel plan generator722. In other words, digital maps enable dynamic route calculation. Traffic data feed receiver716receives historical, real-time, and predictive traffic data from vendors. Traffic data fusion engine720fuses and integrates the traffic data from multiple sources into one dataset. Feedback provider718sends feedback information including traffic volume and accuracy to traffic data vendors to help vendors refine their traffic data and modeling.

As the core module, traffic assignment calculator724implements a bi-level problem to find the optimal travel time and dynamic routing solutions for the traffic and travel time information system for master system manager408. Disutility optimizer726optimizes end user travel disutilities for each class of users classified by master system manager408. Travel plan generator722produces a set of dynamic routes and dynamic travel plans for each class of users at each time interval. The bi-level problem is defined below with reference to equations (8)-(14). Specifically, for each class j at any time interval, the objective of master system manager408is to minimize the travel disutility between each origin-destination regardless of user classification and ISP association, i.e. to minimize
πjrs(t)  (8)
subject to πjrs(t)≧πj-1rs(t)∀r,s,j(9)
and πijrs(t)≧πjrs(t)∀r,s,i,j(10)
if master system manager408chooses or recommends routes for a traveler i at time t,
πijrs(t)=πjrs(t)∀r,s,i,j(11)
and network flow constraints where πijrs(t) is the travel disutility for traveler i in new class j (defined by master system manager408) departing origin r at time t toward destination s and πjrs(t) is the minimum travel disutility for users in new class j departing origin r at time t toward destination s.

As noted in equation (9), the travel disutility for new class j is greater than or equal to the travel disutility for new class j−1 (j=2, 3, 4, . . . , N). New class1users have the lowest travel disutility among all classes within the jurisdiction of master system manager408. As noted in equations (10)-(11), when master system manager408finds and suggests a route for traveler i in new class j, the travel disutility for traveler i is equal to the travel disutility for all users in new class j receiving best route recommendations from master system manager408. For example, if travel disutility is simply represented by travel time, equation (9) ensures that new class1users have the lowest travel time routes, and new class2users have lower travel time routes than class3users, etc. Equations (10)-(11) ensure that all users in new class1receive dynamic routing suggestions which have equal and minimum travel times.

The operating system of master system manager408is to ensure the above information provision criterion or principle is satisfied. Accordingly, traffic assignment calculator724is designed to follow the above principle. On the other hand, for all users in new class j at any time interval, the objective of master system manager408is to minimize the travel disutility between each origin-destination, i.e., to minimize
πijrs(t)  (12)
subject to πijprs(t)≧πijrs(t)∀r,s,i,j,p(13)
if master system manager408chooses or recommends routes p for a traveler i at time t,
πijprs(t)=πijrs(t)∀r,s,i,j,p(14)
and network flow constraints where πijprs(t) is the travel disutility for traveler i in new class j (defined by master system manager408) departing origin r at time t toward destination s via route p and πijrs(t) is the travel disutility for traveler i in new class j departing origin r at time t toward destination s.

As noted in equations (13)-(14), when master system manager408finds and suggests route p for traveler i in new class j, the travel disutility on route p for traveler i is equal to the minimum travel disutility from origin r to destination s at time interval t regardless of to which ISP the user belongs. With the coordination of master system manager408, each ISP's functions are refined. Equations (8)-(14) may be solved in a similar manner as outlined with reference to equations (1)-(7).

With reference toFIG. 8, a network class manager401may include a plurality of sub-modules800, a communication interface802, a memory804, and a processor806. Network A class A manager401a, a network A class B manager401b, a network B class A manager401c, a network B class B manager401d, a network C class A manager401e, and a network C class B manager401fare each examples of network class manager401. Different and additional components may be incorporated into network class manager401. The plurality of sub-modules800may be implemented using one or more computing device. If the plurality of sub-modules800are implemented in different computing devices, each computing device may include a communication interface, memory, and/or processor. Thus, the plurality of sub-modules800may be implemented in a single computing device, in a single location, in a single facility, and/or may be remote from one another.

The plurality of sub-modules800may include a coordinator808, a classification manager810, a POI and LBS provider812, a disutility calculator814, an information provider816, and a feedback receiver818. The plurality of sub-modules800perform operations associated with completing the user information gathering and information delivery for its own individual users. The operations may be implemented using hardware, firmware, software, or any combination of these methods. An end user can make dynamic travel decisions based on their own calculation of travel disutility. The travel disutility for traveler i can be determined by traveler i based on the formulae provided by an ISP. The travel disutility information can be stored on a computing device, such as an in-vehicle navigation system, a mobile device such as a wireless phone, a computer of any form factor including a desktop, laptop, and pocket computer, an Apple™ iPod, etc. Additionally, the travel disutility information can be stored on a server managed by the ISP or a password protected public site. A user may update the travel disutility function and conduct calibration of the travel disutility function based on personal driving and travel experiences. Therefore, disutility calculator612performs such a function to help the traveler make their dynamic travel choice decisions.

By interacting with travel plan generator722, information provider614provides dynamic route and travel plan information as well as personalized, route-specific travel time and traffic information for all ISPs so that each ISP can customize such information and provide to its users. Subsequently, route assignor424of second tier coordinator404takes over such information and generates appropriate dynamic route assignments for each ISP. A traveler subscribes to the travel time and traffic information service of an ISP (network). The network class manager401to which the user subscribes uses classification manager810to collect the basic demographic information and travel preference information. Moreover, disutility calculator814is used by the traveler to customize the parameters based on the input of the traveler to calculate a personalized travel disutility. Subsequently, coordinator808sends such user information to the network master class manager402to which the user subscribes for further processing.

Moreover, coordinator514of network master class manager402receives all the user information from coordinator808of network class manager401. At this stage, two processes may occur. The first process is to send all of the user information to second tier coordinator404. The second process is to use route assignor516of network master class manager402to produce personalized, route-specific travel time and traffic information. Preferably, the second process waits until the first process is complete and sends back the dynamic routing information produced by route assignor424of second tier coordinator404.

At master system manager408, travel plan generator722receives the predicted best travel time and dynamic routing information from traffic assignment calculator724and produces a set of best dynamic route and travel plans for the ISP to which the user subscribes. Subsequently, route assignor516of network master class manager402produces dynamic routing and traffic information for each class of users, including the user. Then, information provider816of network class manager401presents the user with personalized, route-specific travel time and traffic information as well as dynamic routing information. POI and LBS provider812of network class manager401adds related POI and LBS information for routes assigned to the user. The user uses their own mobile device or navigation device to receive the personalized, route-specific travel time and traffic information from information provider816of network class manager401. Any feedback from the traveler will be received by feedback receiver818of network class manager401. Because the user may or may not rely on the travel time and traffic information as well as routing information from information provider816of network class manager401to make their own travel decisions. Such feedback is useful for traffic assignment calculator724of master system manager408to make a better estimation and prediction for travel time and coordinated routing.

The word “exemplary” is used herein to mean serving as an example, instance, or illustration. Any aspect or design described herein as “exemplary” is not necessarily to be construed as preferred or advantageous over other aspects or designs. Further, for the purposes of this disclosure and unless otherwise specified, “a” or “an” means “one or more”.

The exemplary embodiments may be implemented as a method, apparatus, or article of manufacture using standard programming and/or engineering techniques to produce software, firmware, hardware, or any combination thereof to control a computer to implement the disclosed embodiments. The term “computer readable medium” can include, but is not limited to, magnetic storage devices (e.g., hard disk, floppy disk, magnetic strips, . . . ), optical disks (e.g., compact disk (CD), digital versatile disk (DVD), . . . ), smart cards, flash memory devices, etc. Additionally, it should be appreciated that a carrier wave can be employed to carry computer-readable media such as those used in transmitting and receiving electronic mail or in accessing a network such as the Internet or a local area network (LAN).

The foregoing description of exemplary embodiments of the invention have been presented for purposes of illustration and of description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed, and modifications and variations are possible in light of the above teachings or may be acquired from practice of the invention. The functionality described may be implemented in a single executable or application or may be distributed among modules that differ in number and distribution of functionality from those described herein. Additionally, the order of execution of the functions may be changed depending on the embodiment. The embodiments were chosen and described in order to explain the principles of the invention and as practical applications of the invention to enable one skilled in the art to utilize the invention in various embodiments and with various modifications as suited to the particular use contemplated. It is intended that the scope of the invention be defined by the claims appended hereto and their equivalents.