Comparison Between an Exact and a Heuristic-Based Traveling Salesman Problem with Time Window Constraints

This work aims to compare two distinct approaches for solving a Travelling Salesman Problem with time window constraints. Given an environment with a fixed number of cities (points of interest), a robot must determine a route such that each city is visited in an imposed time interval. Both of the examined techniques have the objective of identifying the path with the lowest cost in terms of the distance traveled.

The initial approach employs an exact method by defining the requirements as a mixed integer linear programming (MILP) optimization problem.

The second method involves a meta-heuristic approach, using an ant colony procedure to solve the optimization problem.

Besides qualitative information, the performed quantitative comparison relies on multiple numerical simulations performed in a MATLAB environment. We thus highlight the advantages and disadvantages of both methods, by taking into consideration criteria as the simulation time and the relative difference between the obtained costs versus the number of cities.