A multiagent-based approach for vehicle routing by considering both arriving on time and total travel time
Arriving on time and total travel time are two important properties for vehicle routing. Existing route guidance approaches always consider them independently, because they may conflict with each other. In this article, we develop a semi-decentralized multiagent-based vehicle routing approach where...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2019
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/84440 http://hdl.handle.net/10220/49185 |
| _version_ | 1811697303786881024 |
|---|---|
| author | Cao, Zhiguang Guo, Hongliang Zhang, Jie |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Cao, Zhiguang Guo, Hongliang Zhang, Jie |
| author_sort | Cao, Zhiguang |
| collection | NTU |
| description | Arriving on time and total travel time are two important properties for vehicle routing. Existing route guidance approaches always consider them independently, because they may conflict with each other. In this article, we develop a semi-decentralized multiagent-based vehicle routing approach where vehicle agents follow the local route guidance by infrastructure agents at each intersection, and infrastructure agents perform the route guidance by solving a route assignment problem. It integrates the two properties by expressing them as two objective terms of the route assignment problem. Regarding arriving on time, it is formulated based on the probability tail model, which aims to maximize the probability of reaching destination before deadline. Regarding total travel time, it is formulated as a weighted quadratic term, which aims to minimize the expected travel time from the current location to the destination based on the potential route assignment. The weight for total travel time is designed to be comparatively large if the deadline is loose. Additionally, we improve the proposed approach in two aspects, including travel time prediction and computational efficiency. Experimental results on real road networks justify its ability to increase the average probability of arriving on time, reduce total travel time, and enhance the overall routing performance. |
| first_indexed | 2024-10-01T07:53:07Z |
| format | Journal Article |
| id | ntu-10356/84440 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:53:07Z |
| publishDate | 2019 |
| record_format | dspace |
| spelling | ntu-10356/844402020-03-07T11:48:56Z A multiagent-based approach for vehicle routing by considering both arriving on time and total travel time Cao, Zhiguang Guo, Hongliang Zhang, Jie School of Computer Science and Engineering Intelligent Transportation Systems Multiagent-based Route Guidance Engineering::Computer science and engineering Arriving on time and total travel time are two important properties for vehicle routing. Existing route guidance approaches always consider them independently, because they may conflict with each other. In this article, we develop a semi-decentralized multiagent-based vehicle routing approach where vehicle agents follow the local route guidance by infrastructure agents at each intersection, and infrastructure agents perform the route guidance by solving a route assignment problem. It integrates the two properties by expressing them as two objective terms of the route assignment problem. Regarding arriving on time, it is formulated based on the probability tail model, which aims to maximize the probability of reaching destination before deadline. Regarding total travel time, it is formulated as a weighted quadratic term, which aims to minimize the expected travel time from the current location to the destination based on the potential route assignment. The weight for total travel time is designed to be comparatively large if the deadline is loose. Additionally, we improve the proposed approach in two aspects, including travel time prediction and computational efficiency. Experimental results on real road networks justify its ability to increase the average probability of arriving on time, reduce total travel time, and enhance the overall routing performance. MOE (Min. of Education, S’pore) Accepted version 2019-07-09T01:46:33Z 2019-12-06T15:45:16Z 2019-07-09T01:46:33Z 2019-12-06T15:45:16Z 2018 Journal Article Cao, Z., Guo, H., & Zhang, J. (2018). A multiagent-based approach for vehicle routing by considering both arriving on time and total travel time. ACM Transactions on Intelligent Systems and Technology, 9(3), 25-. doi:10.1145/3078847 2157-6904 https://hdl.handle.net/10356/84440 http://hdl.handle.net/10220/49185 10.1145/3078847 en ACM Transactions on Intelligent Systems and Technology © 2017 ACM. All rights reserved. This paper was published by ACM in ACM Transactions on Intelligent Systems and Technology and is made available with permission of ACM. 22 p. application/pdf |
| spellingShingle | Intelligent Transportation Systems Multiagent-based Route Guidance Engineering::Computer science and engineering Cao, Zhiguang Guo, Hongliang Zhang, Jie A multiagent-based approach for vehicle routing by considering both arriving on time and total travel time |
| title | A multiagent-based approach for vehicle routing by considering both arriving on time and total travel time |
| title_full | A multiagent-based approach for vehicle routing by considering both arriving on time and total travel time |
| title_fullStr | A multiagent-based approach for vehicle routing by considering both arriving on time and total travel time |
| title_full_unstemmed | A multiagent-based approach for vehicle routing by considering both arriving on time and total travel time |
| title_short | A multiagent-based approach for vehicle routing by considering both arriving on time and total travel time |
| title_sort | multiagent based approach for vehicle routing by considering both arriving on time and total travel time |
| topic | Intelligent Transportation Systems Multiagent-based Route Guidance Engineering::Computer science and engineering |
| url | https://hdl.handle.net/10356/84440 http://hdl.handle.net/10220/49185 |
| work_keys_str_mv | AT caozhiguang amultiagentbasedapproachforvehicleroutingbyconsideringbotharrivingontimeandtotaltraveltime AT guohongliang amultiagentbasedapproachforvehicleroutingbyconsideringbotharrivingontimeandtotaltraveltime AT zhangjie amultiagentbasedapproachforvehicleroutingbyconsideringbotharrivingontimeandtotaltraveltime AT caozhiguang multiagentbasedapproachforvehicleroutingbyconsideringbotharrivingontimeandtotaltraveltime AT guohongliang multiagentbasedapproachforvehicleroutingbyconsideringbotharrivingontimeandtotaltraveltime AT zhangjie multiagentbasedapproachforvehicleroutingbyconsideringbotharrivingontimeandtotaltraveltime |