Program "Travelling Salesman Problem in the city."

And not only in the city, and not only the Travelling Salesman.

Let's imagine for an example such situation. You are engaged in delivery of small goods in the city. You need to optimize a route of the courier (traveling salesman or vehicle) to go round some customers in different places of city and to return to a point of departure.

There can be such situation. You need to go round, we shall admit, 16 customers. One vehicle can to not have time to make it. It is necessary to make the plan of use of several vehicles, having optimized, both the general route, and a route of each vehicle.

To resolve this problem a program "Travelling Salesman problem in the city" described below is proposed. It is absolutely free. Requires for its work to the computer was installed DotNet version is not lower than 4.0.

(If you are interested in a program that simply solves the traveling salesman problem - you here ATspCalc.)

In Version added mode to import data from a file with GPS coordinates of the points. Main Menu => Additional commands => Import data (GPS). File format - text , tab delimited,with utf-8 encoding, The following format:

[Point name] tab [Additional information] tab [Latitude] tab [Longitude]

Sample file SOME_PLACES.txt included in the archive with the program.

When importing, the program reads the all the points with the coordinates from the file, builds all the possible connections between them, then leave only those that fall within the minimum spanning tree (MST), and those with length is < 0.588 of average length of compounds belonging to the MST. After this you can adjust data manually. (If we don't do such a way you'll got a lot of spare distances. May be it will be convenient,in case of airplanes ?)

This can greatly facilitate the construction of your map.

In version - added two other modes of file importing : Import data (XYZ) - in this mode utf-8 encoded file must have format :

[Point name] tab [Additional information] tab [X-coord] tab [Y-coord] tab [Z-coord].

- Processing is the same as in previous case.

In mode Import text data - program reads utf-8 encoded text file.File format :

[Point name 1] tab [Point name 2] tab [distance from Point 1 to Point 2] tab [distance from Point 2 to Point 1].

If , at example Point 1 have no connection to Point 2 , distance from Point 1 to Point 2 - must be empty.

You can download program below, on this page.

Let's consider on an example as it works.

1.Input of distances between sites (points).

Before use of the program it is necessary to make plan(map) of your city (area, country - what is relevant to you). It is done once.In the future it is possible to bring corrections, if it is required, in this plan. To do this, divide the city into small areas.Choose a point in the center of such area. Then you need to know the distance between these points. Generally it will not be equal there and back, Since in any city there are unilateral streets, detours, etc. Distances, depending on your problems, can be both in terms of distance and in terms of time and in monetary units. Archive of the program includes test data (file spsl.mdb). This file should be located in the same directory, that the application itself (spsl.exe). Test data - distances and points - are stored in it. If you remove this file, the program will create a new, blank. The test data file allows you to try,how the program is running, without any effort. This file - in Microsoft Access format.So you can fill it through the program interface, and with the help of any suitable external programs - database structure is trivial.

So, when you run you will see the first window for reference / correction your plan or "map":

Points window

In this window, you can add, delete, or change information on points. After any change of points you must save the changes to the database (the button "Save"). Point number must be unique. If you do not want to save changes - simply exit the program and enter again. (Note: If you delete a point - all the associated distances are removed. ) Then you can set the distance from one point to all the other points - the button "Dist.from;" for a specific point. (Or ";" - for settind distances to thi point from others points.) If you click it, you will see a window :

Distances window

Automatically appear every possible point, to which you can set a distance. Editable is only one field - "Distance." If there is no a direct connection to this point the field should be empty.Distance must be greater than or equal to 0. When you click on Ok - the changes are saved, Cancel or close the window - the changes are lost.

If you are satisfied with the information on the points and distances between them,you click "Next". The window in which you can choose the points you want to visit and the number of vehicles appears.

2.The window to choose points for the route and number of vehicles.

Choice Window

In the left list you can choose necessary points. When you click on the button "->" ,they moved to the right list of points to visit. Attention - the first point in the right list is considered the beginning of the route. It is from the vehicles go on a journey and it is expected to return. If you want to remove a point from the already chosen - select it in the right list and click "<-". In the "Number vehicles" - sets the number of vehicles to be used for visiting the points.

There are of three modes of optimization - (makes sense only if Number of vehicles is greater than one): "Min.tour for all vehicles" - In this mode, we seek route with minimal length passing through all the selected points for all vehicles. In this mode path length of each vehicle can be quite different. When you choose mode "Min.tour for each vehicle." - a criterion for optimizing is some different - we seek for a minimum sum of squares of route length, for each vehicle.In this case,common path length of all vehicles may be somewhat higher than in the previous mode, but the path length for each of the vehicles may vary much less. "Equalize num. of points" - In this mode , program optimazes not only path of each vehicle, but also tries to equalize number of points for each vehicle.

Generally, in the case of one vehicle - the task is equivalent to "Travelling Salesman Problem" (TSP). In the case of multiple vehicles - it is the Vehicle Routing Problem (VRP).

So, if you want to go back to the first screen - click "Back". To continue working click "Next". And get to the next window.

3.Window of processing and Results.

The program starts processing.It tries to find a shortest route between the selected points for a specified number of your vehicles.You see a log. After the program finds a suitable solution it shows the results :

Results Window

I.e. the list of items of a route, distances between them and intermediate sites of a route will be visible, for each vehicle.

To the clipboard will be copied next text - It gives you the ability to copy it in any external program, adjust and print.

If under specified conditions result can not be found (not enough distances between points too many vehicles) - the result will be zero.If you specify too few or too many points - there will be an appropriating message.

You can go back to the previous window by pressing the "Back" button to change the terms and repeat the calculation. This will help you quickly find the appropriate solution. The program works as follows :At the beginning we seek the shortest path between your chosen locations, including, and through intermediate points on your "map." Then we search the shortest routes to visit all the selected points on these pathways (using technique "simulation annealing" and local search) with given specified search criteria.But before finding the shortest route, the program looks for any route, passing through all the points for further optimization.It does this by exhaustive search. And if the program "hangs" - you probably have insufficient distances between points, to build a route.

You can download an archive with the program and test data: (v on your computer (If you agree that the author is not responsible for operating of the program and obtained by means of its results.And you use it for non-commercial purpose. ) (By copying the archive to any directory on your computer, unpack it. You will see two files: spsl.exe - the program itself, spsl.mdb - test data.) In this version the maximum number of points you can choose to visit - 56, and the maximum number of vehicles - 8. (more - for money:))

If somebody is intresting - here solutions to ft53, ftv55 and ftv170 Asymmetric TSP instance from TSPLIB,solved with this program.


You can also take a look at Vrp programs VrpCalc and VrpPd.

© 2010-2015 If you have any suggestions, requests, comments, orders - contact me by email

Travelling Salesman problem in the city antivirus report at    

Travelling Salesman problem in the city received 100% CLEAN award on