Building a minimum path between the specified points (traveling salesman problem)

Previous Top Next

ici_9036 The traveling salesman problem is to find the best route, passing through the specified nodes. Search of optimum tour is carried out by full search of the variants, therefore the processed number of nodes is limited by 13.

After pressing of the button ici_9036 of starting the problem, you must indicate on the map the nodes to be visited. The choice of nodes finishes by Ctrl+left mouse button or by double clicking the left mouse button. By double pressing, the node nearest to a point of pressing is added into the list of nodes.

After a choice of points the dialog of options customizations is called.

Dialog of options customizations of the traveling salesman problem is similar to dialog of building a route, only there is added the switch Finish route that defines where tour is finished - in the first or in the last entered node.

After clicking the Build button, search of optimal tour is carried out. Search of tour consists of search of routes between all pairs of points and then search of an optimal combination of these routes. The name of a step and processing percent are shown in group the Processing status. To interrupt processing it is possible by pressing the Cancel button. After the processing completion in dialog the Statistic bookmark is opened.

The table shows the routes between points that make up the tour. At a route choice in the table, it is shown on a map by a dotted red line.

Below the table the total length of tour and time of its passage are shown.

Saving a tour into object is executed when the button is clicked Save route to object. It is not recommended to save tour onto a map of the graph, because at performance of the following task of search the binary file WMN of an image of the graph will be repeatedly created.

After analysis of the tour, you can rebuild it by changing the settings on the Options bookmark, or close the dialog by pressing the Exit button.

When the dialog is closed the found round is shown by a red dotted line.

 

ici_9037 Traveling salesman problem in a mode of loading points from a file

The solution of the traveling salesman problem in the mode of loading points from a file differs only in the way of specifying the nodes which should be visited in the tour. In this mode they are loaded from the chosen text file.

In a text file line by line the names of nodes should be written down how they are defined in semantics «Name» of object of the graph's map node. Therefore for search of nodes in this mode at building a map of the graph the semantics «Name» should be marked as semantics that are copied to the nodes.