Optimizing Traveling Salesman Problem in Multi-Agent Systems with Practical Constraints
The Traveling Salesman Problem (TSP) is a fundamental challenge in multi-agent systems, particularly in task allocation scenarios. Traditional models considering the unconstrained multi-agent TSP, which require multiple salesmen to visit all customers collectively, often fail to produce feasible sol...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155420 |
| _version_ | 1826215447025942528 |
|---|---|
| author | Yang, Ruixiao |
| author2 | Fan, Chuchu |
| author_facet | Fan, Chuchu Yang, Ruixiao |
| author_sort | Yang, Ruixiao |
| collection | MIT |
| description | The Traveling Salesman Problem (TSP) is a fundamental challenge in multi-agent systems, particularly in task allocation scenarios. Traditional models considering the unconstrained multi-agent TSP, which require multiple salesmen to visit all customers collectively, often fail to produce feasible solutions for real-world applications due to practical constraints. To address this gap, we explore two prevalent constraints: energy limitations and aerial robot collaboration. We introduce two novel formulations: the Multi-Agent EnergyConstrained TSP (MA-ECTSP) and the Multi-Agent Flying Sidekick TSP (MA-FSTSP). The MA-ECTSP considers constraints such as limited battery levels and inter-agent conf licts at replenishment sites, while the MA-FSTSP models scenarios where multiple trucks, each equipped with several drones, collaborate to visit all customers, with trucks restricted to roads and drones having greater freedom in their flight paths. We propose a three-phase framework that first deconstructs these complex problems into more manageable single-agent versions, then optimizes them separately without constraints as heuristics, and finally integrates the heuristics and optimizes under the practice constraints. For the MA-ECTSP, we decompose the instance into smaller sub-problems by splitting the minimum spanning tree (MST), solve each using a combination of TSP solvers and heuristic searches, and then aggregate the tours into a feasible solution using a Mixed-Integer Linear Program (MILP) with significantly few variables and constraints. For the MA-FSTSP, we initially decompose the problem into subproblems of one truck with multiple drones, compute routes for trucks without drones, and use these in the final phase as heuristics to optimize both drone and truck routes concurrently. Our approach demonstrates significant effectiveness and scalability compared to existing baselines, as validated on real-world road networks. |
| first_indexed | 2024-09-23T16:29:23Z |
| format | Thesis |
| id | mit-1721.1/155420 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:29:23Z |
| publishDate | 2024 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1554202024-06-28T03:03:12Z Optimizing Traveling Salesman Problem in Multi-Agent Systems with Practical Constraints Yang, Ruixiao Fan, Chuchu Massachusetts Institute of Technology. Department of Aeronautics and Astronautics The Traveling Salesman Problem (TSP) is a fundamental challenge in multi-agent systems, particularly in task allocation scenarios. Traditional models considering the unconstrained multi-agent TSP, which require multiple salesmen to visit all customers collectively, often fail to produce feasible solutions for real-world applications due to practical constraints. To address this gap, we explore two prevalent constraints: energy limitations and aerial robot collaboration. We introduce two novel formulations: the Multi-Agent EnergyConstrained TSP (MA-ECTSP) and the Multi-Agent Flying Sidekick TSP (MA-FSTSP). The MA-ECTSP considers constraints such as limited battery levels and inter-agent conf licts at replenishment sites, while the MA-FSTSP models scenarios where multiple trucks, each equipped with several drones, collaborate to visit all customers, with trucks restricted to roads and drones having greater freedom in their flight paths. We propose a three-phase framework that first deconstructs these complex problems into more manageable single-agent versions, then optimizes them separately without constraints as heuristics, and finally integrates the heuristics and optimizes under the practice constraints. For the MA-ECTSP, we decompose the instance into smaller sub-problems by splitting the minimum spanning tree (MST), solve each using a combination of TSP solvers and heuristic searches, and then aggregate the tours into a feasible solution using a Mixed-Integer Linear Program (MILP) with significantly few variables and constraints. For the MA-FSTSP, we initially decompose the problem into subproblems of one truck with multiple drones, compute routes for trucks without drones, and use these in the final phase as heuristics to optimize both drone and truck routes concurrently. Our approach demonstrates significant effectiveness and scalability compared to existing baselines, as validated on real-world road networks. S.M. 2024-06-27T19:52:12Z 2024-06-27T19:52:12Z 2024-05 2024-05-28T19:36:15.511Z Thesis https://hdl.handle.net/1721.1/155420 In Copyright - Educational Use Permitted Copyright retained by author(s) https://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Yang, Ruixiao Optimizing Traveling Salesman Problem in Multi-Agent Systems with Practical Constraints |
| title | Optimizing Traveling Salesman Problem in Multi-Agent Systems with Practical Constraints |
| title_full | Optimizing Traveling Salesman Problem in Multi-Agent Systems with Practical Constraints |
| title_fullStr | Optimizing Traveling Salesman Problem in Multi-Agent Systems with Practical Constraints |
| title_full_unstemmed | Optimizing Traveling Salesman Problem in Multi-Agent Systems with Practical Constraints |
| title_short | Optimizing Traveling Salesman Problem in Multi-Agent Systems with Practical Constraints |
| title_sort | optimizing traveling salesman problem in multi agent systems with practical constraints |
| url | https://hdl.handle.net/1721.1/155420 |
| work_keys_str_mv | AT yangruixiao optimizingtravelingsalesmanprobleminmultiagentsystemswithpracticalconstraints |