Traveling of multiple salesmen to dynamically changing locations for satisfying multiple goals
Polymer grade scheduling, maritime surveillance, e-food delivery, e-commerce, and military tactics necessitate multiple agents (e.g., extruders, speed boats, salesmen) capable of visiting (or completing) dynamically changing locations (or tasks) in minimum time and distance. This study proposes a no...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-06-01
|
| Series: | Digital Chemical Engineering |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2772508124000115 |
| _version_ | 1797214796966264832 |
|---|---|
| author | Anubha Agrawal Manojkumar Ramteke |
| author_facet | Anubha Agrawal Manojkumar Ramteke |
| author_sort | Anubha Agrawal |
| collection | DOAJ |
| description | Polymer grade scheduling, maritime surveillance, e-food delivery, e-commerce, and military tactics necessitate multiple agents (e.g., extruders, speed boats, salesmen) capable of visiting (or completing) dynamically changing locations (or tasks) in minimum time and distance. This study proposes a novel methodology based on clustering and local heuristic-based evolutionary algorithms to address the dynamic traveling salesman problem (TSP) and the dynamic multi-salesman problem with multiple objectives. The proposed algorithm is evaluated on 11 benchmark TSP problems and large-scale problems with up to 10,000 instances. The results show the superior performance of the proposed methodology called the dynamic two-stage evolutionary algorithm as compared to the dynamic hybrid local search evolutionary algorithm. Furthermore, the algorithm's applicability is illustrated through various scenarios involving up to four salesmen and three objectives with dynamically changing locations. To demonstrate real-world relevance, a maritime surveillance problem employing a helideck monitoring system is solved, wherein the objective is to minimize the patrolling route while visiting faulty vessels that threaten marine vessels. This study provides a general framework of TSP which finds application in several sectors, including planning and scheduling in chemical and manufacturing industries, the defense sector, and the e-commerce sector. Finally, the results showcase the effectiveness of the proposed methodology in solving the dynamic multiobjective, and multiple salesmen problem, which represents a more generalized version of the TSP. |
| first_indexed | 2024-04-24T11:19:52Z |
| format | Article |
| id | doaj.art-0918f0071fac4d97932c55028bcb7fa2 |
| institution | Directory Open Access Journal |
| issn | 2772-5081 |
| language | English |
| last_indexed | 2024-04-24T11:19:52Z |
| publishDate | 2024-06-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Digital Chemical Engineering |
| spelling | doaj.art-0918f0071fac4d97932c55028bcb7fa22024-04-11T04:42:13ZengElsevierDigital Chemical Engineering2772-50812024-06-0111100149Traveling of multiple salesmen to dynamically changing locations for satisfying multiple goalsAnubha Agrawal0Manojkumar Ramteke1Department of Chemical Engineering, Indian Institute of Technology Delhi, Hauz Khas, New Delhi 110016, IndiaCorresponding author.; Department of Chemical Engineering, Indian Institute of Technology Delhi, Hauz Khas, New Delhi 110016, IndiaPolymer grade scheduling, maritime surveillance, e-food delivery, e-commerce, and military tactics necessitate multiple agents (e.g., extruders, speed boats, salesmen) capable of visiting (or completing) dynamically changing locations (or tasks) in minimum time and distance. This study proposes a novel methodology based on clustering and local heuristic-based evolutionary algorithms to address the dynamic traveling salesman problem (TSP) and the dynamic multi-salesman problem with multiple objectives. The proposed algorithm is evaluated on 11 benchmark TSP problems and large-scale problems with up to 10,000 instances. The results show the superior performance of the proposed methodology called the dynamic two-stage evolutionary algorithm as compared to the dynamic hybrid local search evolutionary algorithm. Furthermore, the algorithm's applicability is illustrated through various scenarios involving up to four salesmen and three objectives with dynamically changing locations. To demonstrate real-world relevance, a maritime surveillance problem employing a helideck monitoring system is solved, wherein the objective is to minimize the patrolling route while visiting faulty vessels that threaten marine vessels. This study provides a general framework of TSP which finds application in several sectors, including planning and scheduling in chemical and manufacturing industries, the defense sector, and the e-commerce sector. Finally, the results showcase the effectiveness of the proposed methodology in solving the dynamic multiobjective, and multiple salesmen problem, which represents a more generalized version of the TSP.http://www.sciencedirect.com/science/article/pii/S2772508124000115Dynamic traveling salesman problemMultiple salesmenMultiobjective optimizationEvolutionary algorithmMaritime surveillance |
| spellingShingle | Anubha Agrawal Manojkumar Ramteke Traveling of multiple salesmen to dynamically changing locations for satisfying multiple goals Digital Chemical Engineering Dynamic traveling salesman problem Multiple salesmen Multiobjective optimization Evolutionary algorithm Maritime surveillance |
| title | Traveling of multiple salesmen to dynamically changing locations for satisfying multiple goals |
| title_full | Traveling of multiple salesmen to dynamically changing locations for satisfying multiple goals |
| title_fullStr | Traveling of multiple salesmen to dynamically changing locations for satisfying multiple goals |
| title_full_unstemmed | Traveling of multiple salesmen to dynamically changing locations for satisfying multiple goals |
| title_short | Traveling of multiple salesmen to dynamically changing locations for satisfying multiple goals |
| title_sort | traveling of multiple salesmen to dynamically changing locations for satisfying multiple goals |
| topic | Dynamic traveling salesman problem Multiple salesmen Multiobjective optimization Evolutionary algorithm Maritime surveillance |
| url | http://www.sciencedirect.com/science/article/pii/S2772508124000115 |
| work_keys_str_mv | AT anubhaagrawal travelingofmultiplesalesmentodynamicallychanginglocationsforsatisfyingmultiplegoals AT manojkumarramteke travelingofmultiplesalesmentodynamicallychanginglocationsforsatisfyingmultiplegoals |