Balancing fairness and efficiency in traffic routing via interpolated traffic assignment
Abstract System optimum (SO) routing, wherein the total travel time of all users is minimized, is a holy grail for transportation authorities. However, SO routing may discriminate against users who incur much larger travel times than others to achieve high system efficiency, i.e., low...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2023
|
| Online Access: | https://hdl.handle.net/1721.1/152184 |
| _version_ | 1811082921787785216 |
|---|---|
| author | Jalota, Devansh Solovey, Kiril Tsao, Matthew Zoepf, Stephen Pavone, Marco |
| author_facet | Jalota, Devansh Solovey, Kiril Tsao, Matthew Zoepf, Stephen Pavone, Marco |
| author_sort | Jalota, Devansh |
| collection | MIT |
| description | Abstract
System optimum (SO) routing, wherein the total travel time of all users is minimized, is a holy grail for transportation authorities. However, SO routing may discriminate against users who incur much larger travel times than others to achieve high system efficiency, i.e., low total travel times. To address the inherent unfairness of SO routing, we study the
$${\beta }$$
β
-fair SO problem whose goal is to minimize the total travel time while guaranteeing a
$${\beta \ge 1}$$
β
≥
1
level of unfairness, which specifies the maximum possible ratio between the travel times of different users with shared origins and destinations. To obtain feasible solutions to the
$${\beta }$$
β
-fair SO problem while achieving high system efficiency, we develop a new convex program, the interpolated traffic assignment problem (I-TAP), which interpolates between a fairness-promoting and an efficiency-promoting traffic-assignment objective. We evaluate the efficacy of I-TAP through theoretical bounds on the total system travel time and level of unfairness in terms of its interpolation parameter, as well as present a numerical comparison between I-TAP and a state-of-the-art algorithm on a range of transportation networks. The numerical results indicate that our approach is faster by several orders of magnitude as compared to the benchmark algorithm, while achieving higher system efficiency for all desirable levels of unfairness. We further leverage the structure of I-TAP to develop two pricing mechanisms to collectively enforce the I-TAP solution in the presence of selfish homogeneous and heterogeneous users, respectively, that independently choose routes to minimize their own travel costs. We mention that this is the first study of pricing in the context of fair routing for general road networks (as opposed to, e.g., parallel road networks). |
| first_indexed | 2024-09-23T12:13:25Z |
| format | Article |
| id | mit-1721.1/152184 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:13:25Z |
| publishDate | 2023 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1521842024-09-19T05:18:28Z Balancing fairness and efficiency in traffic routing via interpolated traffic assignment Jalota, Devansh Solovey, Kiril Tsao, Matthew Zoepf, Stephen Pavone, Marco Abstract System optimum (SO) routing, wherein the total travel time of all users is minimized, is a holy grail for transportation authorities. However, SO routing may discriminate against users who incur much larger travel times than others to achieve high system efficiency, i.e., low total travel times. To address the inherent unfairness of SO routing, we study the $${\beta }$$ β -fair SO problem whose goal is to minimize the total travel time while guaranteeing a $${\beta \ge 1}$$ β ≥ 1 level of unfairness, which specifies the maximum possible ratio between the travel times of different users with shared origins and destinations. To obtain feasible solutions to the $${\beta }$$ β -fair SO problem while achieving high system efficiency, we develop a new convex program, the interpolated traffic assignment problem (I-TAP), which interpolates between a fairness-promoting and an efficiency-promoting traffic-assignment objective. We evaluate the efficacy of I-TAP through theoretical bounds on the total system travel time and level of unfairness in terms of its interpolation parameter, as well as present a numerical comparison between I-TAP and a state-of-the-art algorithm on a range of transportation networks. The numerical results indicate that our approach is faster by several orders of magnitude as compared to the benchmark algorithm, while achieving higher system efficiency for all desirable levels of unfairness. We further leverage the structure of I-TAP to develop two pricing mechanisms to collectively enforce the I-TAP solution in the presence of selfish homogeneous and heterogeneous users, respectively, that independently choose routes to minimize their own travel costs. We mention that this is the first study of pricing in the context of fair routing for general road networks (as opposed to, e.g., parallel road networks). 2023-09-20T18:49:43Z 2023-09-20T18:49:43Z 2023-08-02 2023-08-03T03:17:49Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/152184 Autonomous Agents and Multi-Agent Systems. 2023 Aug 02;37(2):32 en https://doi.org/10.1007/s10458-023-09616-7 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer Science+Business Media, LLC, part of Springer Nature application/pdf Springer US Springer US |
| spellingShingle | Jalota, Devansh Solovey, Kiril Tsao, Matthew Zoepf, Stephen Pavone, Marco Balancing fairness and efficiency in traffic routing via interpolated traffic assignment |
| title | Balancing fairness and efficiency in traffic routing via interpolated traffic assignment |
| title_full | Balancing fairness and efficiency in traffic routing via interpolated traffic assignment |
| title_fullStr | Balancing fairness and efficiency in traffic routing via interpolated traffic assignment |
| title_full_unstemmed | Balancing fairness and efficiency in traffic routing via interpolated traffic assignment |
| title_short | Balancing fairness and efficiency in traffic routing via interpolated traffic assignment |
| title_sort | balancing fairness and efficiency in traffic routing via interpolated traffic assignment |
| url | https://hdl.handle.net/1721.1/152184 |
| work_keys_str_mv | AT jalotadevansh balancingfairnessandefficiencyintrafficroutingviainterpolatedtrafficassignment AT soloveykiril balancingfairnessandefficiencyintrafficroutingviainterpolatedtrafficassignment AT tsaomatthew balancingfairnessandefficiencyintrafficroutingviainterpolatedtrafficassignment AT zoepfstephen balancingfairnessandefficiencyintrafficroutingviainterpolatedtrafficassignment AT pavonemarco balancingfairnessandefficiencyintrafficroutingviainterpolatedtrafficassignment |