Measuring Backtracking on Delivery Routes through Community Detection
In logistics, backtracking is the act of a route returning to an area that it has already visited. Despite backtracking’s clear potential to be a source of inefficiency and driver frustration, there is little existing research on backtracking in transportation. We set out to devise a method to measu...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/144575 https://orcid.org/0000-0002-6214-5585 |
| _version_ | 1826212112831086592 |
|---|---|
| author | Noszek, Joseph Robert |
| author2 | Winkenbach, Matthias |
| author_facet | Winkenbach, Matthias Noszek, Joseph Robert |
| author_sort | Noszek, Joseph Robert |
| collection | MIT |
| description | In logistics, backtracking is the act of a route returning to an area that it has already visited. Despite backtracking’s clear potential to be a source of inefficiency and driver frustration, there is little existing research on backtracking in transportation. We set out to devise a method to measure backtracking that is consistently scalable and transferable to different route settings. Our measurement method utilizes community detection, a group of machine learning algorithms for clustering nodes within graphs, based on edge structure and weight. We then investigate the ability of backtracking, as measured by our community detection-based method, to predict suboptimality of Asymmetric Traveling Salesman Problem (ATSP) solutions. We find that backtracking does demonstrate viability as a predictor of suboptimality, particularly when it utilizes the Louvain algorithm or the Leiden algorithm for community detection. We also investigate the relationship between backtracking and suboptimality when adjusting our measurement process and when considering the additional variables of the number of customers and the number of backtracking instances. After these adjustments, we observe continued and increased viability as a predictor of suboptimality. |
| first_indexed | 2024-09-23T15:16:35Z |
| format | Thesis |
| id | mit-1721.1/144575 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:16:35Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1445752022-08-30T03:10:51Z Measuring Backtracking on Delivery Routes through Community Detection Noszek, Joseph Robert Winkenbach, Matthias Sheffi, Yossi Massachusetts Institute of Technology. Department of Civil and Environmental Engineering In logistics, backtracking is the act of a route returning to an area that it has already visited. Despite backtracking’s clear potential to be a source of inefficiency and driver frustration, there is little existing research on backtracking in transportation. We set out to devise a method to measure backtracking that is consistently scalable and transferable to different route settings. Our measurement method utilizes community detection, a group of machine learning algorithms for clustering nodes within graphs, based on edge structure and weight. We then investigate the ability of backtracking, as measured by our community detection-based method, to predict suboptimality of Asymmetric Traveling Salesman Problem (ATSP) solutions. We find that backtracking does demonstrate viability as a predictor of suboptimality, particularly when it utilizes the Louvain algorithm or the Leiden algorithm for community detection. We also investigate the relationship between backtracking and suboptimality when adjusting our measurement process and when considering the additional variables of the number of customers and the number of backtracking instances. After these adjustments, we observe continued and increased viability as a predictor of suboptimality. S.M. 2022-08-29T15:56:50Z 2022-08-29T15:56:50Z 2022-05 2022-06-15T20:49:16.505Z Thesis https://hdl.handle.net/1721.1/144575 https://orcid.org/0000-0002-6214-5585 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Noszek, Joseph Robert Measuring Backtracking on Delivery Routes through Community Detection |
| title | Measuring Backtracking on Delivery Routes through Community Detection |
| title_full | Measuring Backtracking on Delivery Routes through Community Detection |
| title_fullStr | Measuring Backtracking on Delivery Routes through Community Detection |
| title_full_unstemmed | Measuring Backtracking on Delivery Routes through Community Detection |
| title_short | Measuring Backtracking on Delivery Routes through Community Detection |
| title_sort | measuring backtracking on delivery routes through community detection |
| url | https://hdl.handle.net/1721.1/144575 https://orcid.org/0000-0002-6214-5585 |
| work_keys_str_mv | AT noszekjosephrobert measuringbacktrackingondeliveryroutesthroughcommunitydetection |