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

• US 8,370,053 B2
• Filed: 11/27/2007
• Issued: 02/05/2013
• Est. Priority Date: 04/23/2007
• Status: Active Grant

• Current Assignee: Iteris Incorporated
• Original Assignee: Trafficcast International Incorporated
• Inventors: Li, Jing
• Primary Examiner(s): Nguyen, John Q
• Assistant Examiner(s): NGUYEN, CHUONG P
• Application Number:
  US11/945,650
• Publication Number:
  US 20080262716A1
• Time in Patent Office: 1,897 Days
• Field of Search: 701/1, 701117-120, 701201-213, 701/400, 701/411, 701/414, 701/422, 701/423, 701/425, 3409951-99513, 340/995.19, 340/995.22, 340/995.23, 342/454, 342/456, 705/1, 705/5, 705/6, 705/13, 705/400
• US Class Current: 701/117
• CPC Class Codes: G08G 1/01 Detecting movement of traffic to be counted or controlled G08G1/07 - G08G1/14 take precedence
• CPC Class Codes: G08G 1/096811 where the route is computed offboard
• CPC Class Codes: G08G 1/096838 where the user preferences are taken into account or the user selects one route out of a plurality
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data

Abstract

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.

Claims

1. A device for assigning routes for a plurality of users allocated to different classes, the system comprising:

a computer-readable medium having computer-readable instructions stored therein, the instructions comprising

identifying a first group of users based on a user classification, wherein each user of the first group of users has a first user classification;

identifying a second group of users based on the user classification, wherein each user of the second group of users has a second user classification, wherein the first user classification is different from the second user classification;

calculating a disutility value 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;

executing a bi-level problem solver to optimize the disutility value based on the user classification; and

recommending a route to each user of the first group of users and to each user of the second group of users based on the bi-level problem execution;

a communication interface, the communication interface sending the recommended route to each user of the first group of users and to each user of the second group of users; and

a processor, the processor coupled to the communication interface and to the computer-readable medium and configured to execute the instructions.

2. The device of claim 1, wherein the travel disutility function is defined for each user of the first group of users and for each user of the second group of users.

3. The device of claim 1, wherein the user classification is based on one or more factor selected from the group consisting of a subscription fee, a transaction fee, a length of membership, a sponsorship, an advertisement income, a seniority ranking, and a service provider of the user.

4. The device of claim 1, wherein the bi-level problem solver comprises:

minimizing π

_j^rs(t) subject to π

_j^rs(t)≧

π

_j-1^rs(t) ∀

r, s, j and π

_ij^rs(t)≧

π

_j^rs(t) ∀

r, s, i, j where π

_j^rs(t) is a minimum travel disutility for users in a user classification j departing an origin r at a time t toward a destination s and π

_ij^rs(t) is a travel disutility for a traveler i in the user classification j departing the origin r at the time t toward the destination s; and

minimizing π

_ij^rs(t) subject to π

_ijp^rs(t)≧

π

_ij^rs(t) ∀

r, s, i, j, p where π

_ijp^rs(t) is the travel disutility for traveler i in class j departing origin r at time t toward destination s via route p and π

_ij^rs(t) is the minimum travel disutility for users i in class j departing origin r at time t toward destination s.

5. The device of claim 1, wherein executing the bi-level problem solver comprises:

determining first routes for each user of the first group of users and second routes for each user of the second group of users based on a minimum travel disutility assuming free-flow traffic conditions;

assigning routes to each user of the second group of users based on the determined second routes;

loading a traffic network with traffic flow based on the assigned routes;

determining third routes for each user of the second group of users based on a minimum travel disutility considering the loaded traffic network;

assigning fourth routes to each user of the second group of users based on the determined third routes;

loading the traffic network with traffic flow based on the assigned fourth routes;

determining fifth routes for each user of the first group of users based on the minimum travel disutility considering the traffic network loaded based on the assigned fourth routes; and

assigning sixth routes to each user of the first group of users based on the determined fifth routes.

6. The device of claim 1, wherein the calculated travel disutility for each user of the first group of users is less than or equal to the calculated travel disutility for each user of the second group of users.

7. A non-transitory computer-readable medium having computer-readable instructions therein that, upon execution by a processor, cause the processor to assign routes for a plurality of users allocated to different classes, the instructions comprising:

identifying a first group of users based on a user classification, wherein each user of the first group of users has a first user classification;

identifying a second group of users based on the user classification, wherein each user of the second group of users has a second user classification, wherein the first user classification is different from the second user classification;

calculating a disutility value 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;

executing a bi-level problem solver to optimize the disutility value based on the user classification; and

recommending a route to each user of the first group of users and to each user of the second group of users based on the bi-level problem execution.

8. The non-transitory computer-readable medium of claim 7, wherein the travel disutility function is defined for each user of the first group of users and for each user of the second group of users.

9. The non-transitory computer-readable medium of claim 7, wherein the user classification is based on one or more factor selected from the group consisting of a subscription fee, a transaction fee, a length of membership, a sponsorship, an advertisement income, a seniority ranking, and a service provider of the user.

10. The non-transitory computer-readable medium of claim 7, wherein the bi-level problem solver comprises:

minimizing π

_j^rs(t) subject to π

_j^rs(t)≧

π

_j-1^rs(t) ∀

r, s, j and π

_ij^rs(t)≧

π

_j^rs(t) ∀

r, s, i, j where π

_j^rs(t) is a minimum travel disutility for users in a user classification j departing an origin r at a time t toward a destination s and π

_ij^rs(t) is a travel disutility for a traveler i in the user classification j departing the origin r at the time t toward the destination s; and

minimizing π

_ij^rs(t) subject to π

_ijp^rs(t)≧

π

_ij^rs(t) ∀

r, s, i, j, p where π

_ijp^rs(t) is the travel disutility for traveler i in class j departing origin r at time t toward destination s via route p and π

_ij^rs(t) is the minimum travel disutility for users i in class j departing origin r at time t toward destination s.

11. The non-transitory computer-readable medium of claim 7, wherein executing the bi-level problem solver comprises:

determining first routes for each user of the first group of users and second routes for each user of the second group of users based on a minimum travel disutility assuming free-flow traffic conditions;

assigning routes to each user of the second group of users based on the determined second routes;

loading a traffic network with traffic flow based on the assigned routes;

determining third routes for each user of the second group of users based on a minimum travel disutility considering the loaded traffic network;

assigning fourth routes to each user of the second group of users based on the determined third routes;

loading the traffic network with traffic flow based on the assigned fourth routes;

determining fifth routes for each user of the first group of users based on the minimum travel disutility considering the traffic network loaded based on the assigned fourth routes; and

assigning sixth routes to each user of the first group of users based on the determined fifth routes.

12. The non-transitory computer-readable medium of claim 7, wherein the calculated travel disutility for each user of the first group of users is less than or equal to the calculated travel disutility for each user of the second group of users.

13. A method of assigning routes for a plurality of users allocated to different classes, the method comprising:

identifying a first group of users based on a user classification, wherein each user of the first group of users has a first user classification;

identifying a second group of users based on the user classification, wherein each user of the second group of users has a second user classification, wherein the first user classification is different from the second user classification;

calculating a disutility value 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;

executing a bi-level problem solver to optimize the disutility value based on the user classification; and

recommending a route to each user of the first group of users and to each user of the second group of users based on the bi-level problem execution.

14. The method of claim 13, wherein the travel disutility function is defined for each user of the first group of users and for each user of the second group of users.

15. The method of claim 13, wherein the user classification is based on one or more factor selected from the group consisting of a subscription fee, a transaction fee, a length of membership, a sponsorship, an advertisement income, a seniority ranking, and a service provider of the user.

16. The method of claim 13, wherein the bi-level problem solver comprises:

minimizing π

_j^rs(t) subject to π

_j^rs(t)≧

π

_j-1^rs(t) ∀

r, s, j and π

_ij^rs(t)≧

π

_j^rs(t) ∀

r, s, i, j where π

_j^rs(t) is a minimum travel disutility for users in a user classification j departing an origin r at a time t toward a destination s and π

_ij^rs(t) is a travel disutility for a traveler i in the user classification j departing the origin r at the time t toward the destination s; and

minimizing π

_ij^rs(t) subject to π

_ijp^rs(t)≧

π

_ij^rs(t) ∀

r, s, j, p where π

_ijp^rs(t) is the travel disutility for traveler i in class j departing origin r at time t toward destination s via route p and π

_ij^rs(t) is the minimum travel disutility for users i in class j departing origin r at time t toward destination s.

17. The method of claim 13, wherein executing the bi-level problem solver comprises:

determining first routes for each user of the first group of users and second routes for each user of the second group of users based on a minimum travel disutility assuming free-flow traffic conditions;

assigning routes to each user of the second group of users based on the determined second routes;

loading a traffic network with traffic flow based on the assigned routes;

determining third routes for each user of the second group of users based on a minimum travel disutility considering the loaded traffic network;

assigning fourth routes to each user of the second group of users based on the determined third routes;

loading the traffic network with traffic flow based on the assigned fourth routes;

determining fifth routes for each user of the first group of users based on the minimum travel disutility considering the traffic network loaded based on the assigned fourth routes; and

assigning sixth routes to each user of the first group of users based on the determined fifth routes.

18. The method of claim 13, wherein the calculated travel disutility for each user of the first group of users is less than or equal to the calculated travel disutility for each user of the second group of users.