English

Problem: Route solver with FindBestSequence does not return the optimal tour solution

Description

The Route solver with the FindBestSequence option computes a tour solution that is not optimal. For example, computing the best order to visit a set of 20 stops with two different settings for Preserve First Stop and Preserve Last Stop gives the following results:
- when Preserve First Stop and Preserve Last Stop are checked, the total cost of the route is equal to 100 units
- when Preserve First Stop and Preserve Last Stop are unchecked, the total cost of the route is equal to 110 units

The second problem gives a longer tour solution than the first problem. In the second problem, neither the first stop nor the last stop is fixed, the route with the FindBestSequence algorithm should find a solution that is equal to or better than the first problem.

Solution or Workaround

The ArcGIS Network Analyst's Route solver with the FindBestSequence option solves the well-known Traveling Salesman Problem (TSP). To solve TSP, a heuristic approach has been implemented. This heuristic approach provides a good trade-off between tour quality and computation time. However, since the TSP algorithm uses a heuristic approach, the route returned by the Route solver is not guaranteed to be optimal.