﻿ ﻿Application of 2-opt to the Traveling Salesman Problem - 10 Lessons About C++ (2015)

### Chapter 8: Application of 2-opt to the Traveling Salesman Problem

A 2-opt is a simple local search algorithm for solving 'traveling salesman' type problems. Its operation is simple: it modifies a route that crosses over itself, reordering it so there are no longer any crossovers and therefore a shorter overall route:

This can be a useful technique for finding reasonable solutions to traveling salesman problems with hundreds or even thousands of node locations.

The Mechanism by which the 2-opt swaps a given route between nodes i and k to create a new route:

1. add route[0] to route[i-1] in order to the new route

2. add route[i] to route[k] in reverse order to the new route

3. add route[k+1] to end in order to the new route;

And as applied to the example route above, following steps 1-3:

route[ 0 to 3 ] : Glasgow > Edinburgh > Manchester > Leeds where i = 1; k = 2. New route:

1. Glasgow

2. Glasgow > ( Manchester > Edinburgh )

3. Glasgow > Manchester > Edinburgh > ( Leeds )

The complete 2-opt swap heuristic making use of the above mechanism to search every possible valid combination:

While ( no further improvement made )

{

start_again:

best_distance = calculateTotalDistance(existing_route)

for (i = 0; i < number of nodes eligible to be swapped - 1; i++) {

for (k = i + 1; k < number of nodes eligible to be swapped; k++) {

new_route = 2optSwap(existing_route, i, k)

new_distance = calculateTotalDistance(new_route)

if (new_distance < best_distance) {

existing_route = new_route

goto start_again

}

}

}

}

The creation of a Visual Studio 2010 dialog-based project to implement the optimization algorithm and present the output graphically is described, together with some results from applying the program to a standard traveling salesman test problem.

Step 1: Create a standard dialog-based application:

In Visual Studio select File > New > Project. Select MFC Application:

Uncheck all boxes and select a dialog-based application, then click Next:

Again uncheck all boxes:

Do the same for the advanced features page:

Click Next and then click Finish.

Step 2: Create the dialog controls

In the Resource View see how the basic dialog has been created:

Remove the “TODO: Place dialog controls here.” static control in the middle. Right-click the OK button and select Properties and rename its Caption property to Run. Change the ID property from IDOK to IDC_RUN Create one more button: from the Toolbox, select the Button control and drag it on to the dialog. Set its Caption property to Open and set its ID to IDC_OPEN. Reposition your three buttons so they are located in the top right part of the dialog:

From the Toolbox drag and resize two static controls on to the dialog:

Let the top static text control be captioned as “Total distance:” and set its ID property to IDC_DISTANCE. Then set the bottom static text Caption property as “Tour:” and set its ID to IDC_TOUR:

This is everything needed for creating the user interface.

In the solution explorer, right click the project folder and select Add > New Item. Do this to create the following C++ header and source files:

1. CoordMatrix.h, CoordMatrix.cpp

2. Tour.h, Tour.cpp

3. TSPalgorithm.h, TSPalgorithm.cpp

4. MakeString.h

Your solution explorer will be updated as follows:

Insert the code for each of the source files.

Full Code Listings

CoordMatrix.h

#pragma once

#include <vector>

#include <map>

#include <fstream>

#include <tuple>

#include <string>

class CoordMatrix

{

public:

enum EDGE_WEIGHT_TYPE

{

ATT = 0

};

CoordMatrix();

~CoordMatrix();

void Initialize( std::string filepath );

int CalcPseudoEuclidDistance(

const int& x1,

const int& x2,

const int& y1,

const int& y2 );

double Distance( const int& c1, const int& c2 );

int size() const;

int GetX( const int& index ) const;

int GetY( const int& index ) const;

int GetMinX() const;

int GetMinY() const;

int GetMaxX() const;

int GetMaxY() const;

std::string GetFileTitle() const;

private:

void tokenize( std::vector<std::string>& tokens,

const std::string& text,

const std::string& delimiter );

void SetDistanceMatrix();

void Reset();

private:

std::vector< std::pair<int, int> > coords;

std::map< std::pair<int,int>, double > distMatrix;

std::string title;

int minx, miny;

int maxx, maxy;

int edge_weight_type;

};

CoordMatrix.cpp

#include "StdAfx.h"

#include "CoordMatrix.h"

#include <iostream>

#include <fstream>

#include <sstream>

#include <cmath>

const int infinity = 99999999;

#define round(n) ((int)((n)+0.5))

CoordMatrix::CoordMatrix()

{

minx = infinity; miny = infinity;

maxx = -infinity; maxy = -infinity;

edge_weight_type = ATT;

title = "";

}

CoordMatrix::~CoordMatrix() {}

// Initialise cost / distance matrix from input file

void CoordMatrix::Initialize( std::string filepath )

{

Reset();

minx = infinity;

miny = infinity;

maxx = infinity * -1;

maxy = infinity * -1;

std::vector< std::pair<int, int> >().swap( coords );

std::ifstream file;

file.open( filepath.c_str() );

if ( !file )

{

std::cout << "Error in opening text/tsp file\n";

return;

}

int line = 0;

while( !file.eof() )

{

line++;

char buf[ 255 ];

file.getline( buf, 128 );

std::vector<std::string> tokens;

std::string text( buf );

tokenize( tokens, text, " " );

if ( tokens.at( 0 ) == "NAME" )

{

title = tokens.at( 2 );

}

if ( tokens.at( 0 ) == "EDGE_WEIGHT_TYPE" )

{

if ( tokens.at( 2 ) == "ATT" )

{

edge_weight_type = ATT;

}

}

if (line < 7 || ( tokens.size() == 1 && text != "EOF"))

continue;

if ( text == "EOF" )

break;

int node = atoi( tokens.at( 0 ).c_str() );

int x = atoi( tokens.at( 1 ).c_str() );

int y = atoi( tokens.at( 2 ).c_str() );

std::pair<int,int> n( x, y );

coords.push_back( n );

if ( x > maxx ) maxx = x;

if ( y > maxy ) maxy = y;

if ( x < minx ) minx = x;

if ( y < miny ) miny = y;

}

file.close();

SetDistanceMatrix();

}

// Get Euclidean distance between two cities

double CoordMatrix::Distance( const int& c1, const int& c2 )

{

if ( c1 < c2 )

{

std::pair<int,int> p( c1, c2 );

return distMatrix[ p ];

}

else

{

std::pair<int,int> p( c2, c1 );

return distMatrix[ p ];

}

}

// Reset the distance matrix

void CoordMatrix::Reset()

{

std::vector< std::pair<int, int> >().swap( coords );

std::map< std::pair<int,int>, double >().swap( distMatrix );

}

// Tokenize the input string

void CoordMatrix::tokenize( std::vector<std::string>& tokens,

const std::string& text,

const std::string& delimiter )

{

size_t next_pos = 0;

size_t init_pos = text.find_first_not_of( delimiter, next_pos );

while ( next_pos != std::string::npos &&

init_pos != std::string::npos ) {

next_pos = text.find( delimiter, init_pos );

std::string token = text.substr( init_pos, next_pos - init_pos );

tokens.push_back( token );

init_pos = text.find_first_not_of( delimiter, next_pos );

}

}

// Get number of items contained in matrix

int CoordMatrix::size() const

{ return (int) coords.size(); }

// Get selected x coordinate

int CoordMatrix::GetX( const int& index ) const

{

std::pair<int,int> n = coords.at( index );

return n.first;

}

// Get selected y coordinate

int CoordMatrix::GetY( const int& index ) const

{

std::pair<int,int> n = coords.at( index );

return n.second;

}

// Get minimum x coordinate

int CoordMatrix::GetMinX() const

{ return minx; }

// Get minimum y coordinate

int CoordMatrix::GetMinY() const

{ return miny; }

// Get maximum x coordinate

int CoordMatrix::GetMaxX() const

{ return maxx; }

// Get maximum y coordinate

int CoordMatrix::GetMaxY() const

{ return maxy; }

// Get the file name

std::string CoordMatrix::GetFileTitle() const

{ return title; }

// Set up distance matrix between node pairs

void CoordMatrix::SetDistanceMatrix()

{

for ( int i = 0; i < (int) coords.size() - 1; i++ )

{

std::pair<int,int> p1 = coords.at( i );

int x1 = p1.first; int y1 = p1.second;

for ( int j = i + 1; j < (int) coords.size(); j++ )

{

std::pair<int,int> p2 = coords.at( j );

int x2 = p2.first; int y2 = p2.second;

double dist = 0.0;

if ( edge_weight_type == ATT )

{

dist = CalcPseudoEuclidDistance( x1, x2, y1, y2 );

}

else

{

dist = (double) sqrt( (double) ( x1 - x2 ) * ( x1 - x2 ) +

(double) ( y1 - y2 ) * ( y1 - y2 ) );

}

std::pair< int, int > p( i, j );

distMatrix[ p ] = dist;

}

}

}

// For edge weight type 'ATT'

// Pseudo Euclidean distance

int CoordMatrix::CalcPseudoEuclidDistance( const int& x1,

const int& x2,

const int& y1,

const int& y2 )

{

int dij = 0;

int xd = x1 - x2; int yd = y1 - y2;

double rij = sqrt( (xd*xd + yd*yd) / 10.0 );

int tij = round( rij );

if ( tij < rij )

dij = tij + 1;

else

dij = tij;

return dij;

}

Tour.h

#pragma once

#include "CoordMatrix.h"

#include <vector>

#include <set>

class Tour

{

public:

Tour();

Tour( const Tour& t );

Tour& operator=( const Tour& t );

~Tour();

void DoTwoOpt( const int& c1, const int& c2,

const int& c3, const int& c4 );

double TourDistance() const;

int TourSize() const;

int GetCity( const int& index );

void SetCity( const int& index, const int& value );

void SetMatrix( CoordMatrix* mat );

void CreateRandomTour();

void CreateTour();

void CreateNearestNeighbourTour();

void Reset();

void SetCities( const std::vector<int>& v );

private:

double Distance( const int& c1, const int& c2 ) const;

int GetNearestNeighbour( const int& c, std::set<int>& cset );

private:

std::vector< int > cities;

CoordMatrix* matrix;

};

Tour.cpp

#include "StdAfx.h"

#include "Tour.h"

#include <algorithm>

#include <functional>

Tour::Tour(){}

Tour::~Tour(){}

Tour::Tour( const Tour& t )

{ cities = t.cities; }

Tour& Tour::operator=( const Tour& t )

{

if ( this != &t )

cities = t.cities;

return *this;

}

void Tour::DoTwoOpt( const int& c1, const int& c2,

const int& c3, const int& c4 )

{

if ( c3 == c1 || c3 == c2 || c4 == c1 || c4 == c2 )

return;

int c1old = cities.at( c1 );

int c2old = cities.at( c2 );

int c3old = cities.at( c3 );

int c4old = cities.at( c4 );

double old_distance = TourDistance();

int tmp = cities.at( c2 );

cities[ c2 ] = cities.at( c3 );

cities[ c3 ] = tmp;

double new_distance = TourDistance();

if ( new_distance > old_distance )

{

cities[ c1 ] = c1old;

cities[ c2 ] = c2old;

cities[ c3 ] = c3old;

cities[ c4 ] = c4old;

}

}

// Get total distance of tour

double Tour::TourDistance() const

{

double dist = 0.0;

int size = (int) cities.size();

int c1, c2;

for ( int i = 0; i < size - 1; i++ ) {

c1 = cities.at( i );

c2 = cities.at( i + 1 );

dist += Distance( c1, c2 );

}

c1 = cities.at( size - 1 );

c2 = cities.at( 0 );

dist += Distance( c1, c2 );

return dist;

}

// Generate arbitrary tour

void Tour::CreateRandomTour()

{

Reset();

for ( int i = 0; i < matrix->size(); i++ )

cities.push_back( i );

random_shuffle( cities.begin() + 1, cities.end() );

}

// Generate arbitrary tour

void Tour::CreateTour()

{

Reset();

for ( int i = 0; i < matrix->size(); i++ )

cities.push_back( i );

}

// Get distance bewteen selected cities

double Tour::Distance( const int& c1,

const int& c2 ) const

{ return matrix->Distance( c1, c2 ); }

// Set pointer to cost / distance matrix object

void Tour::SetMatrix( CoordMatrix* mat )

{ matrix = mat; }

// Reset existing tour data

void Tour::Reset()

{ std::vector< int >().swap( cities ); }

// Return the number of cities in the tour

int Tour::TourSize() const

{ return (int) cities.size(); }

// Get the tour city, given the index passed to it

int Tour::GetCity( const int& index )

{

int node = cities.at( index );

return node;

}

// Get tour from the set of nearest neighbours

void Tour::CreateNearestNeighbourTour()

{

Reset();

std::set<int> city_set;

std::set<int>::iterator it;

for ( int i = 0; i < matrix->size(); i++ )

city_set.insert( i );

int city = 0;

for ( int i = 1; i <= matrix->size(); i++ )

{

cities.push_back( city );

it = city_set.find( city );

city_set.erase( it );

city = GetNearestNeighbour( city, city_set );

}

}

int Tour::GetNearestNeighbour( const int& c, std::set<int>& cset )

{

int city = 0;

double min_dist = 99999999;

std::set<int>::iterator cit;

for ( cit = cset.begin(); cit != cset.end(); cit++ ) {

int n = *cit;

if ( n == c ) continue;

double dist = Distance( c, n );

if ( dist < min_dist ) {

city = n;

min_dist = dist;

}

}

return city;

}

void Tour::SetCities( const std::vector<int>& v )

{ cities = v; }

void Tour::SetCity( const int& index, const int& value )

{ cities[ index ] = value; }

TSPalgorithm.h

#pragma once

#include "Tour.h"

#include <string>

class Observer;

class TSPalgorithm

{

public:

TSPalgorithm(void);

~TSPalgorithm(void);

void Initialize( const int& iterations, CoordMatrix* mat );

void TwoOptSwap( const int& i, const int& k );

void Run();

int GetTourCity( const int& index );

void Notify( const int& dist );

private:

void TwoOpt();

private:

Tour tour, new_tour;

int iterations;

std::vector<Observer*> ob_set;

};

class Observer

{

public:

virtual void UpdateDisplay( const float& dist ) = 0;

};

TSPalgorithm.cpp

#include "StdAfx.h"

#include "TSPalgorithm.h"

TSPalgorithm::TSPalgorithm()

{}

TSPalgorithm::~TSPalgorithm()

{}

// Set up TSP problem to run

void TSPalgorithm::Initialize(

const int& iter,

CoordMatrix* mat )

{

tour.SetMatrix( mat );

new_tour.SetMatrix( mat );

iterations = iter;

}

// Run the optimization algorithm

void TSPalgorithm::Run()

{

tour.Reset();

tour.CreateNearestNeighbourTour();

TwoOpt();

}

// Get the tour node, given the index

int TSPalgorithm::GetTourCity( const int& index )

{

}

// Notify observers of changes

void TSPalgorithm::Notify( const int& dist )

{

for ( std::vector<Observer*>::iterator it = ob_set.begin();

it != ob_set.end();

it++ )

{

(*it)->UpdateDisplay( dist );

}

}

{

ob_set.push_back( ob );

}

// Do all 2-opt combinations

void TSPalgorithm::TwoOpt()

{

int size = tour.TourSize();

new_tour = tour;

bool improve = true;

double best_distance, new_distance;

while ( improve )

{

best_distance = tour.TourDistance();

improve = false;

for ( int i = 0; i < size - 1; i++ )

{

for ( int k = i + 1; k < size; k++)

{

TwoOptSwap( i, k );

new_distance = new_tour.TourDistance();

if ( new_distance < best_distance )

{

improve = true;

tour = new_tour;

best_distance = new_distance;

Notify( tour.TourDistance() );

i = size;

break;

}

}

}

}

}

void TSPalgorithm::TwoOptSwap( const int& i, const int& k )

{

for ( int c = 0; c <= i - 1; ++c )

{

new_tour.SetCity( c, tour.GetCity( c ) );

}

int dec = 0;

for ( int c = i; c <= k; ++c )

{

new_tour.SetCity( c, tour.GetCity( k - dec ) );

dec++;

}

for ( int c = k + 1; c < tour.TourSize(); ++c )

{

new_tour.SetCity( c, tour.GetCity( c ) );

}

}

MakeString.h

#include <fstream>

#include <sstream>

#include <string>

class make_string

{

public:

template <typename T>

make_string& operator<<( T const & datum )

{

buffer_ << datum;

return *this;

}

operator std::string () const

{ return buffer_.str(); }

private:

std::ostringstream buffer_;

};

Step 4: add the static control variables

In the Resource View, right-click the “Total Distance” static control you added and select Add Variable. Give it the variable name m_Distance:

Repeat this step for the “Tour” static control, giving it the variable name m_Tour. Notice that following this step will insert the CStatic controls in the dialog header class CTwoOptDlg.h and insert the DDX controls in CTwoOptDlg.cpp:

void CTwoOptDlg::DoDataExchange(CDataExchange* pDX)

{

CDialogEx::DoDataExchange(pDX);

DDX_Control(pDX, IDC_DISTANCE, m_Distance);

DDX_Control(pDX, IDC_TOUR, m_Tour);

}

Step 5: Implement the button event handling logic

In the Resource View, double-click the Run button to generate the event handler code in CTwoOptDlg.cpp for when this button is clicked.

Once this is generated, insert the following code inside OnBnClickedRun to invoke the algorithm and display updates:

void CTwoOptDlg::OnBnClickedRun()

{

alg.Run();

hasRun = true;

RedrawWindow( 0, 0, RDW_INVALIDATE | RDW_UPDATENOW | RDW_ERASE );

}

Do the same for the Open button: Double click the Open button to generate its event handler code, and insert the following code that will enable the user to open the desired *.tsp file:

RedrawWindow( 0, 0, RDW_INVALIDATE | RDW_UPDATENOW | RDW_ERASE );

}void CTwoOptDlg::OnBnClickedOpen()

{

CPaintDC dc(this);

CRect rect;

GetClientRect(&rect);

// Open the file opening dialog

CFileDialog fileDlg(

TRUE,

NULL,

NULL,

(LPCTSTR) ".tsp Files(*.tsp)|*.tsp||",

this );

INT_PTR result = fileDlg.DoModal();

CString path = fileDlg.GetPathName();

if ( result == IDOK )

{

// Reset matrix data contents

CT2CA pszConvertedAnsiString( path );

std::string path_str( pszConvertedAnsiString );

mat.Initialize( path_str );

hasRun = false;

(AfxGetMainWnd( ))->SetWindowText(mat.GetFileTitle().c_str());

}

Step 6: Update the OnPaint method

Update OnPaint method to draw the current best solution found by the algorithm:

void CTwoOptDlg::OnPaint()

{

// device context for painting

CPaintDC dc(this);

if (IsIconic())

{

SendMessage(

WM_ICONERASEBKGND,

reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);

// Center icon in client rectangle

int cxIcon = GetSystemMetrics(SM_CXICON);

int cyIcon = GetSystemMetrics(SM_CYICON);

CRect rect;

GetClientRect(&rect);

int x = (rect.Width() - cxIcon + 1) / 2;

int y = (rect.Height() - cyIcon + 1) / 2;

// Draw the icon

dc.DrawIcon(x, y, m_hIcon);

}

else

{

if ( mat.size() < 1 ) return;

CRect rect;

GetClientRect(&rect);

int rectx1 = rect.left + 20;

int rectx2 = rect.right - 150;

int recty1 = rect.top + 20;

int recty2 = rect.bottom - 140;

CPen pen( PS_SOLID, 1, RGB( 0, 0, 0 ) );

dc.SelectStockObject(BLACK_BRUSH);

int tour_size = mat.size();

for ( count = 0; count < tour_size; count++ )

{

xc1 = mat.GetX( count );

yc1 = mat.GetY( count );

xn1 = (float) ( xc1 - mat.GetMinX() ) /

(float) ( mat.GetMaxX() - mat.GetMinX() );

yn1 = (float) ( yc1 - mat.GetMinY() ) /

(float) ( mat.GetMaxY() - mat.GetMinY() );

xcoord1 = rectx1 + (int) (float) ( xn1 * abs( rectx1 - rectx2 ) );

ycoord1 = recty2 - (int) (float) ( yn1 * abs( recty1 - recty2 ) );

dc.Ellipse( xcoord1 - 2, ycoord1 - 2, xcoord1 + 2, ycoord1 + 2 );

if ( hasRun && count < tour_size - 1 )

{

cc1 = alg.GetTourCity( count );

cc2 = alg.GetTourCity( count + 1 );

xc1 = mat.GetX( cc1 );

yc1 = mat.GetY( cc1 );

xc2 = mat.GetX( cc2 );

yc2 = mat.GetY( cc2 );

xn1 = (float) ( xc1 - mat.GetMinX() ) /

(float) ( mat.GetMaxX() - mat.GetMinX() );

yn1 = (float) ( yc1 - mat.GetMinY() ) /

(float) ( mat.GetMaxY() - mat.GetMinY() );

xn2 = (float) ( xc2 - mat.GetMinX() ) /

(float) ( mat.GetMaxX() - mat.GetMinX() );

yn2 = (float) ( yc2 - mat.GetMinY() ) /

(float) ( mat.GetMaxY() - mat.GetMinY() );

xcoord1 = rectx1 + (int)(float)(xn1 * abs( rectx1 - rectx2));

ycoord1 = recty2 - (int)(float)(yn1 * abs( recty1 - recty2));

xcoord2 = rectx1 + (int)(float)(xn2 * abs( rectx1 - rectx2));

ycoord2 = recty2 - (int)(float)(yn2 * abs( recty1 - recty2));

dc.MoveTo( xcoord1, ycoord1 );

dc.LineTo( xcoord2, ycoord2 );

}

}

if ( hasRun )

{

cc1 = alg.GetTourCity( tour_size - 1 );

cc2 = alg.GetTourCity( 0 );

xc1 = mat.GetX( cc1 );

yc1 = mat.GetY( cc1 );

xc2 = mat.GetX( cc2 );

yc2 = mat.GetY( cc2 );

xn1 = (float) ( xc1 - mat.GetMinX() ) /

(float) ( mat.GetMaxX() - mat.GetMinX() );

yn1 = (float) ( yc1 - mat.GetMinY() ) /

(float) ( mat.GetMaxY() - mat.GetMinY() );

xn2 = (float) ( xc2 - mat.GetMinX() ) /

(float) ( mat.GetMaxX() - mat.GetMinX() );

yn2 = (float) ( yc2 - mat.GetMinY() ) /

(float) ( mat.GetMaxY() - mat.GetMinY() );

xcoord1 = rectx1 + (int) (float) ( xn1 * abs( rectx1 - rectx2 ) );

ycoord1 = recty2 - (int) (float) ( yn1 * abs( recty1 - recty2 ) );

xcoord2 = rectx1 + (int) (float) ( xn2 * abs( rectx1 - rectx2 ) );

ycoord2 = recty2 - (int) (float) ( yn2 * abs( recty1 - recty2 ) );

dc.MoveTo( xcoord1, ycoord1 );

dc.LineTo( xcoord2, ycoord2 );

}

CDialogEx::OnPaint();

}

}

Step 7: Add methods to initialize observer and refresh display

Insert this code to CTwoOptDlg.cpp to initialize the observer pattern and output the details of the best tour found:

void CTwoOptDlg::Init( TSPalgorithm* tsp )

{

}

void CTwoOptDlg::UpdateDisplay( const float& dist )

{

hasRun = true;

std::string s = make_string() << "Total distance: "

<< dist;

m_Distance.SetWindowText( s.c_str() );

int tour_size = mat.size();

std::string tour = make_string() << "Tour:\n";

std::string t;

for ( int i = 0; i < tour_size; i++ )

{

t = make_string() << alg.GetTourCity( i ) + 1

<< "-";

tour.append( t );

if ( i > 0 && i % 35 == 0 )

{

tour.append( "\n" );

}

}

t = make_string() << alg.GetTourCity( 0 ) + 1;

tour.append( t );

m_Tour.SetWindowText( tour.c_str() );

RedrawWindow(

0,

0,

RDW_INVALIDATE | RDW_UPDATENOW | RDW_ERASE );

}

Step 8: Ensure necessary headers are present in CTwoOptDlg.cpp and update OnInitDialog

Make sure the following headers are included in CTwoOptDlg.cpp:

#include "stdafx.h"

#include "Two-Opt.h"

#include "Two-OptDlg.h"

#include "MakeString.h"

#include <fstream>

#include <sstream>

#include <string>

#include "afxdialogex.h"

BOOL CTwoOptDlg::OnInitDialog()

{

CDialogEx::OnInitDialog();

SetIcon(m_hIcon, TRUE); // Set big icon

SetIcon(m_hIcon, FALSE); // Set small icon

Init( &alg );

alg.Initialize( 10000, &mat );

hasRun = false;

font.CreatePointFont(100, _T("Arial"));

m_Distance.SetFont(&font);

m_Tour.SetFont(&font);

GetDlgItem(IDC_DISTANCE)->SetFont(&font);

GetDlgItem(IDC_TOUR)->SetFont(&font);

return TRUE; // return TRUE unless you set the focus to a control

}

This includes the TSPalgorithm and CoordMatrix objects and methods to initialize the observer and update the display. You can just copy and insert the complete CTwoOptDlg.h code listing shown here:

#pragma once

#include "TSPalgorithm.h"

#include "CoordMatrix.h"

#include "afxwin.h"

// CTwoOptDlg dialog

class CTwoOptDlg : public CDialogEx, Observer

{

// Construction

public:

CTwoOptDlg(CWnd* pParent = NULL);

// Dialog Data

enum { IDD = IDD_TWOOPT_DIALOG };

protected:

virtual void DoDataExchange(CDataExchange* pDX);

// Implementation

protected:

HICON m_hIcon;

// Generated message map functions

virtual BOOL OnInitDialog();

afx_msg void OnPaint();

afx_msg HCURSOR OnQueryDragIcon();

DECLARE_MESSAGE_MAP()

public:

afx_msg void OnBnClickedOk();

afx_msg void OnBnClickedOpen();

afx_msg void OnBnClickedRun();

void Init( TSPalgorithm* tsp );

void UpdateDisplay( const float& dist );

private:

TSPalgorithm alg;

CoordMatrix mat;

bool hasRun;

int cc1, cc2, xc1, xc2, yc1, yc2;

float xn1, xn2, yn1, yn2;

int xcoord1, xcoord2, ycoord1, ycoord2;

int x1, y1, count;

CStatic m_Distance, m_Tour;

LOGFONT lf;

CFont font;

};

Once the project is completed, using it is simple: download a test problem as a *.tsp file such as Att48.tsp, representing 48 capital cities of the USA:

Click Open to load this test problem and then click Run.

To try out the algorithm, first click Open to load the test problem. This will represent the geographical locations of cities as a series of nodes:

Upon pressing Run, the 2-opt algorithm is applied to run through all two-edge combinations and find the best solution obtained from this process. The program will periodically update the graphical layout as the algorithm finds progressively better solutions.

Chapter Summary

To summarize this master lesson, you have learned how to:

·Apply the 2-opt algorithm in C++ to generate near-optimal solutions to traveling salesman test problems.

·Create a MFC dialog application and use standard drawing objects to present the results graphically.

﻿