For the Java equivalent see this link:
For the C++ equivalent see this link:
This post demonstrates how to apply the 2-opt algorithm to a number of standard test problems in C# while displaying the
results in a WPF style window, while using the MVVM design pattern.
See this link for an overview of the two opt algorithm.
http://en.wikipedia.org/wiki/2-opt
But essentially the 2-opt link swapping heuristic can be summarised by the following steps:
The actual 2-opt heuristic can be summarised by the following pseudocode steps, repeating for all feasible combinations of I and k:
1. take route[1] to route[i-1] and add them in order to new_route 2. take route[i] to route[k] and add them in reverse order to new_route 3. take route[k+1] to end and add them in order to new_route 4. return the new_route;
Architecture
This application is designed around the Model View ViewModel architecture (MVVM). I find that MVVM allows for a nice clean separation between the graphical
display, the business logic and data handling.
https://en.wikipedia.org/wiki/Model%E2%80%93view%E2%80%93viewmodel
As with the Java and C++ versions, the user interface is a simple window with buttons for opening the test problem (*.tsp file) and a run button to execute the algorithm(which causes the
display to get updated and re-draw the tour links each time a better tour is found)
Building the User Interface in XAML
I use standard WPF / XAML for the user interface components and the canvas in which to draw the city nodes, tour links etc:
MainWindow.xaml
<Window x:Class="TwoOpt.MainWindow"
xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
xmlns:twoOpt="clr-namespace:TwoOpt"
mc:Ignorable="d"
Title="{Binding Title}"
Height="620" Width="600">
<Window.DataContext>
<twoOpt:MainWindowViewModel />
</Window.DataContext>
<Grid>
<Grid.RowDefinitions>
<RowDefinition Height="70" />
<RowDefinition Height="5" />
<RowDefinition Height="*" />
<RowDefinition Height="5" />
</Grid.RowDefinitions>
<StackPanel
Orientation="Horizontal">
<Button
Command="{Binding OpenCommand}"
Width="110"
Content="Open"
Margin="10" />
<Button
Width="110"
Command="{Binding RunCommand}"
Content="Run"
Margin="10"/>
<Grid VerticalAlignment="Center" Width="200" Margin="10">
<Grid.RowDefinitions>
<RowDefinition Height="25" />
<RowDefinition Height="25" />
</Grid.RowDefinitions>
<Label
VerticalContentAlignment="Center"
Name="BestLabel"
VerticalAlignment="Center"/>
<Label
VerticalContentAlignment="Center"
Name="IterationLabel"
Grid.Row="1" />
</Grid>
</StackPanel>
<Grid
Grid.Row="2">
<Grid.ColumnDefinitions>
<ColumnDefinition Width="10" />
<ColumnDefinition Width="*" />
<ColumnDefinition Width="10" />
</Grid.ColumnDefinitions>
<Grid.RowDefinitions>
<RowDefinition Height="5" />
<RowDefinition Height="*" />
<RowDefinition Height="5" />
</Grid.RowDefinitions>
<Grid Name="DisplayGrid" Grid.Column="1" Grid.Row="1">
<Canvas Name="CanvasGrid">
</Canvas>
</Grid>
</Grid>
</Grid>
</Window>
The ViewModel class
This class I use for handling the business logic and the responding to the button press events from the main user interface.
MainWindowViewModel.cs
using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
using System.Windows.Forms;
using System.Windows.Input;
namespace TwoOpt
{
public class MainWindowViewModel : BaseViewModel
{
private readonly Model _model;
private ICommand _openCommand;
private ICommand _runCommand;
public MainWindowViewModel()
{
_model = new Model();
_model.TourUpdated += ModelOnTourUpdated;
}
public IMainWindow MainWindow { get; set; }
public string Title
{
get { return _model.Title; }
set
{
_model.Title = value;
OnPropertyChanged("Title");
}
}
public ICommand OpenCommand
{
get
{
return _openCommand ?? (_openCommand = new RelayCommand(
x =>
{
var openFileDialog1 = new OpenFileDialog
{
InitialDirectory = "c:\\",
Filter = @"txt files (*.tsp)|*.tsp|All files (*.*)|*.*",
FilterIndex = 2,
RestoreDirectory = true
};
if (openFileDialog1.ShowDialog() != DialogResult.OK) return;
try
{
Stream stream;
// ReSharper disable once ConditionIsAlwaysTrueOrFalse
if ((stream = openFileDialog1.OpenFile()) == null) return;
var height = MainWindow.GridHeight();
var width = MainWindow.GridWidth();
_model.CancelJobs();
_model.InitMatrix(stream, height, width);
Title = _model.Title;
DisplayNodes();
MainWindow.UpdateIteration(0, 0, null);
}
catch (Exception ex)
{
MessageBox.Show(@"Error: Could not read file from disk. Original error: " + ex.Message);
}
}));
}
}
public ICommand RunCommand
{
get
{
return _runCommand ?? (_runCommand = new RelayCommand(
x => { _model.Run(); }));
}
}
public List<Pair> Lines => _model.TourCoords;
private void ModelOnTourUpdated(object sender, EventArgs<Tuple<double, int>> eventArgs)
{
var iter = eventArgs.Value.Item2;
var best = eventArgs.Value.Item1;
Update(best, iter);
}
public IEnumerable<string> ReadLines(Func<Stream> streamProvider,
Encoding encoding)
{
using (var stream = streamProvider())
{
using (var reader = new StreamReader(stream, encoding))
{
string line;
while ((line = reader.ReadLine()) != null)
yield return line;
}
}
}
private void DisplayNodes()
{
MainWindow?.PlotNodes(_model.DisplayCoords);
}
private void Update(double best, int iter)
{
MainWindow.UpdateIteration(best, iter, _model.TourCoords);
}
}
}
Within this code I also make use of the Supervisor Controlling Pattern as means of accessing the View controls from within the ViewModel class.
It does this by allowing MainWindow.xaml.cs to inherits from the IMainWindow interface, which provide the functions to plot the nodes and draw the links:
IMainWindow.cs
using System.Collections.Generic;
namespace TwoOpt
{
public interface IMainWindow
{
void UpdateIteration(double best, int iter, List<Pair> tourCoords);
void PlotNodes(List<Pair> displayCoords);
double GridHeight();
double GridWidth();
}
}
MainWindow.xaml.cs
using System.Collections.Generic;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows.Shapes;
namespace TwoOpt
{
/// <summary>
/// Interaction logic for MainWindow.xaml
/// </summary>
public partial class MainWindow : IMainWindow
{
public MainWindow()
{
InitializeComponent();
var mainWindowViewModel = DataContext as MainWindowViewModel;
if (mainWindowViewModel != null)
mainWindowViewModel.MainWindow = this;
}
public void PlotNodes(List<Pair> displayCoords)
{
CanvasGrid.Children.Clear();
InvalidateVisual();
foreach (var coord in displayCoords)
{
var ellipse = new Ellipse
{
Width = 4,
Height = 4,
Fill = Brushes.Blue
};
Canvas.SetLeft(ellipse, coord.X());
Canvas.SetTop(ellipse, coord.Y());
CanvasGrid.Children.Add(ellipse);
}
}
public double GridHeight()
{
return DisplayGrid.ActualHeight;
}
public double GridWidth()
{
return DisplayGrid.ActualWidth;
}
public void UpdateIteration(double best, int iter, List<Pair> tourCoords)
{
Dispatcher.Invoke(() =>
{
IterationLabel.Content = "Iteration: " + iter;
BestLabel.Content = "Best distance: " + (int)best;
if (tourCoords == null) return;
var size = tourCoords.Count;
var startCoord = tourCoords[0];
CanvasGrid.Children.Clear();
for (var i = 1; i < size; ++i)
{
var endCoord = tourCoords[i];
var link = new Line
{
X1 = startCoord.X() + 2,
Y1 = startCoord.Y() + 2,
X2 = endCoord.X() + 2,
Y2 = endCoord.Y() + 2,
Stroke = Brushes.Blue
};
CanvasGrid.Children.Add(link);
startCoord = tourCoords[i];
}
var finalLink = new Line
{
X1 = tourCoords[0].X() + 2,
Y1 = tourCoords[0].Y() + 2,
X2 = tourCoords[size - 1].X() + 2,
Y2 = tourCoords[size - 1].Y() + 2,
Stroke = Brushes.Blue
};
CanvasGrid.Children.Add(finalLink);
});
}
}
}
C# implementation of the 2-opt algorithm
// Do all 2-opt combinations
private void TwoOpt()
{
// Get tour size
var size = _tour.TourSize();
//CHECK THIS!!
for (var i = 0; i < size; i++)
{
_newTour.SetCity(i, _tour.GetCity(i));
}
// repeat until no improvement is made
var improve = 0;
var iteration = 0;
while (improve < 500)
{
var bestDistance = _tour.TourDistance();
for (var i = 1; i < size - 1; i++)
{
for (var k = i + 1; k < size; k++)
{
TwoOptSwap(i, k);
iteration++;
var newDistance = _newTour.TourDistance();
if (!(newDistance < bestDistance)) continue;
// Improvement found so reset
improve = 0;
for (var j = 0; j < size; j++)
{
_tour.SetCity(j, _newTour.GetCity(j));
}
bestDistance = newDistance;
// Update the display
SetTourCoords();
TourUpdated.Raise(this, new Tuple<double, int>( bestDistance, iteration));
}
}
improve++;
}
}
And this is how the swap is done:
private void TwoOptSwap(int i, int k)
{
var size = _tour.TourSize();
// 1. take route[0] to route[i-1] and add them in order to new_route
for (var c = 0; c <= i - 1; ++c)
{
_newTour.SetCity(c, _tour.GetCity(c));
}
// 2. take route[i] to route[k] and add them in reverse order to new_route
var dec = 0;
for (var c = i; c <= k; ++c)
{
_newTour.SetCity(c, _tour.GetCity(k - dec));
dec++;
}
// 3. take route[k+1] to end and add them in order to new_route
for (var c = k + 1; c < size; ++c)
{
_newTour.SetCity(c, _tour.GetCity(c));
}
}
Trying out the program
Att48.tsp
I tend to always start out on a reasonably small test problem such as att48.tsp, available from here:
http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/att48.tsp
Click the Open button and navigate to the Att48.tsp test problem when prompted, which plots the city locations as a series of nodes:
Upon pressing Run, we obtain the solution of length 10959:
kroA200.tsp
I then try out the program on a larger problem with 200 nodes, “kroA200.tsp”, available from here:
http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/kroA200.tsp
Giving the following result:
lin318.tsp
Finally I try one more test problem, “lin318.tsp”, available from here:
http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/lin318.tsp
Results as shown:
Full code sample in the form of a Visual Studio 2015 project is available from here:
