Simple experiments with Traveling Salesman Problem

I recently implemented some simple algorithms solving TSP. To check how the algorithms performed I used some of the instances in the National Traveling Salesman Problems. It is a lot of fun and I learned a lot when started to visualize the algorithm steps.

On algorithm side, I have used some combination of 2-Opt, Swap and a custom meta-heuristic. The results are promising despite the simplicity of the steps used. Code is written entirely in Java 7.

Since this is a work-in-progress, will update the post with some new results and improvements.

Initial construction heuristics used is a simple implementation of Nearest Neighbor (NN). On each step the nearest to the current node is found and added as a next node. You can see in the image below that the main drawback is that it creates huge jumps from one end to another. This happens when in one area of the map neighbors are exhausted and the algorithm jumps to another area.

Below is a artificial instance slow-motion. NN is used as initial path and some of the first implementations of 2-Opt heuristic is used to optimize it to the final solution.

National Traveling Salesman Problems are instances that represent set of countries from World TSP instance. I have used some of them with increasing number of cities: lu890.tsp, gr9882.tsp and ch71009.tsp.

Below is a lu980.tsp instance animation. It goes fast to 5.3% gap with 2-Opt heuristics and then more slowly to 2.3% when the meta-heuristics is used.

Below is animation of the algorithm applied to gr9882.tsp instance. Initial path construction is just a random node selection to check some features of the custom meta-heuristics. Final solution gap is 9.23% above the optimal.

Visualization technique

Improving the technique over the time I have come to the following process to visualize such algorithm steps. It is important to have an idea of what the final movie size and quality have to be in order to use this information consistently on each processing step.

  1. The simulation program generates nothing more then frames in SVG format. The SVG is useful because it allows me to use simple expression in Java code to generate lines points and text. It is also useful for debugging purposes as a plain text format. Below is SVG file of some small test instance.

    solution00305.svg

    Each frame have to have a number with fixed size format: solution00503.svg. During the optimization the distance to optimum decrease with variable speed, so the frame generation is adjusted accordingly to have more constant rate. For example, for total path distances below some values, each frame is generated when distance changes with 100 and for some distances when it changes with 10. More convenient will be probably to change it with some step as a percentage of the current value.

  2. On the next processing step, PNG files are generated from SVG. This can be achieved in multiple ways. One is to use a Inkscape and another to use ImageMagick Convert command. I experimented with both but Convert command seems to work faster with comparable quality. This is due to how both programs are loaded in memory on each frame processing. Below is some bash script used to process all frames.

    #!/bin/bash
    
    FILES=solution*.svg
    for svgname in $FILES
    do
            num=`echo $svgname|cut -c9-13`
            pngname=frame${num}.png
            echo ${pngname} 
    	convert -density 90 -resize 1280x720 ${svgname} PNG32:${pngname} 
    done
    

    Note that this expect that all svg files are named solutionXXXXX.svg, where the XXXXX is fixed format secuential numbers from 0 or 1. The result is files: frameXXXXX.png in PNG32 format. The size of the frames is tuned for YouTube 720p format.

  3. Each PNG frame is converted to mkv (or mp4) movie format with lossless compression. The parameters are tuned to preserve sharpens of the images. Initially I used ffmpeg but since Ubuntu switched to avconv, this is what I use currently. The parameters can probably be used with ffmpeg with some small changes

    avconv -r 25 -i frame%05d.png -c:v libx264 -preset veryslow -qp 0 -pix_fmt yuv420p -an output.mkv

    The frame rate is set by -r 25. It can be adjusted accordingly to make the final movie less boring/short. Libx264 must be installed if missed. It is used to encode in H.264 video stream format.