Heuristic for Min-Max Heterogeneous Multi-Vehicle Multi-Depot Traveling Salesman Problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913181059776512 |
|---|---|
| author | Kumar, Deepak Prakash Rathinam, Sivakumar Darbha, Swaroop Bihl, Trevor |
| author_facet | Kumar, Deepak Prakash Rathinam, Sivakumar Darbha, Swaroop Bihl, Trevor |
| contents | In this article, a heuristic is proposed for a min-max heterogeneous multi-vehicle multi-depot traveling salesman problem (TSP), wherein heterogeneous vehicles start from given depot positions and need to cover a given set of targets. The vehicles should cover given targets such that the maximum tour time is minimized. In the considered problem, vehicles considered can be functionally heterogeneous, wherein specific targets must be covered by a particular vehicle, structurally heterogeneous, wherein the vehicles can travel at different speeds, or both. The proposed heuristic generalizes the MD heuristic for the min-max homogeneous multi-vehicle multi-depot TSP and has three stages: an initialization stage to generate a feasible solution, a local search stage in which the vehicle with the maximum tour time is improved, and a perturbation stage to break from a local minimum. The proposed heuristic is benchmarked with the optimal solution obtained by solving a mixed integer linear program using branch and cut for instances considering three vehicles covering thirty targets. Variations in the percentage of vehicle-target assignments and the number of vehicles starting at the same depot are studied to show the heuristic's effectiveness in producing high-quality solutions. It was observed that the heuristic generated feasible solutions within 4% of the optimum on average for the considered instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_17403 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Heuristic for Min-Max Heterogeneous Multi-Vehicle Multi-Depot Traveling Salesman Problem Kumar, Deepak Prakash Rathinam, Sivakumar Darbha, Swaroop Bihl, Trevor Optimization and Control In this article, a heuristic is proposed for a min-max heterogeneous multi-vehicle multi-depot traveling salesman problem (TSP), wherein heterogeneous vehicles start from given depot positions and need to cover a given set of targets. The vehicles should cover given targets such that the maximum tour time is minimized. In the considered problem, vehicles considered can be functionally heterogeneous, wherein specific targets must be covered by a particular vehicle, structurally heterogeneous, wherein the vehicles can travel at different speeds, or both. The proposed heuristic generalizes the MD heuristic for the min-max homogeneous multi-vehicle multi-depot TSP and has three stages: an initialization stage to generate a feasible solution, a local search stage in which the vehicle with the maximum tour time is improved, and a perturbation stage to break from a local minimum. The proposed heuristic is benchmarked with the optimal solution obtained by solving a mixed integer linear program using branch and cut for instances considering three vehicles covering thirty targets. Variations in the percentage of vehicle-target assignments and the number of vehicles starting at the same depot are studied to show the heuristic's effectiveness in producing high-quality solutions. It was observed that the heuristic generated feasible solutions within 4% of the optimum on average for the considered instances. |
| title | Heuristic for Min-Max Heterogeneous Multi-Vehicle Multi-Depot Traveling Salesman Problem |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2312.17403 |