Routing Sales Territory by Solving a Multi-objective TSP Variant with Evolutionary Algorithms

The Traveling Salesman Problem is a classic NP-hard combinatorial problem. However, many real-world scenarios do not match the classic TSP modeling. Thus, this paper proposes generating vendors' routes in a sales territory by extending and combining different TSP variants. The proposal deals with many constraints such as prioritizing the most valuable customers, resource limits to visit all customers, time and day windows, multiple days horizon, lunch stop, visit frequency and destination importance. We also introduce a permutational representation with a series of directed arcs, and with a slot to indicate customers that could not be visited. We evaluate SPEA2, NSGA-II, and IVF/NSGA-II Multi-Objective Evolutionary Algorithms against three real-world scenarios. The results demonstrate that the proposed model can produce good results in a realistic scenario, maintaining a balance between prioritizing important customers and economic routes. Besides, IVF/NSGA-II outperformed the other algorithms in most cases, and also the manually-created routes, e.g., reducing 35% the route's distance and increasing 60% the route's importance.