Novel Graph Model for Solving Collision‐Free Multiple‐Vehicle Traveling Salesman Problem  Using Ant Colony Optimization

Pamosoaji, Anugrah Kusumo and Setyohadi, Djoko Budiyanto (2020) Novel Graph Model for Solving Collision‐Free Multiple‐Vehicle Traveling Salesman Problem  Using Ant Colony Optimization. Journal Algorithms, 13 (6). pp. 1-19. ISSN 19994893

Preview

Text Pamosoaji & Setyohadi, Novel_graph.pdf Download (1MB) | Preview

Abstract

In  this  paper,  a  novel  graph  model  to  figure  Collision‐Free  Multiple  Traveling  Salesman Problem  (CFMTSP)  is  proposed.  In  this  problem,  a  group  of  vehicles  start  from  different  nodes  in an  undirected  graph  and  must  visit  each  node  in  the  graph,  following  the  well‐known  Traveling Salesman  Problem  (TSP)  fashion   without  any  collision.  This  paper’s  main  objective  is  to  obtain free‐collision  routes  for  each  vehicle  while  minimizing  the  traveling  time  of  the  slowest  vehicle.  This problem can be approached by applying speed to each vehicle, and a novel augmented graph model can perform it. This approach accommodates not only the position of nodes and inter‐node distances, but also the speed of all the vehicles is proposed. The proposed augmented graph should be  able  to  be  used  to  perform  optimal  trajectories,  i.e.,  routes  and  speeds,  for  all  vehicles.  An  ant  colony  optimization  (ACO)  algorithm  is  used  on  the  proposed  augmented   graph.  Simulations  show that the algorithm can satisfy the main objective. Considered factors, such as limitation of the mission successfulness, i.e., the inter‐vehicle arrival time on a node, the number of vehicles, and the numbers of vehicles and edges of the graph are also discussed.

Actions (login required)

View Item