LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@rustcat

巡回セールスマン問題をOr-Opt法で解いてみた

Last updated at Posted at 2024-07-16

巡回セールスマン問題をOr-Opt法によりc++で解いてみました。
図1は赤丸の中の一つのポイントを切り取り、青の辺の中間に挿入したものです。
図2は赤丸の中の二つのポイントを切り取り、青の辺の中間に挿入したものです。
図3は赤丸の中の三つのポイントを切り取り、青の辺の中間に挿入したものです。
図4に示す初期経路をそれぞれ図1、図2、図3のように処理することにより、図5、図6、図7のように経路の距離を短縮できました。
図8は切り取るポイントの数を1、2、3、4、5～（町の数-4）と増やしてみたものです。
最大で（町の数-4）としたのは、これ以上増やすことができないからです。
Or-Opt法は通常繋ぎ変える枝の数は３本以下のものを指すようなので、これは正確にはOr-Optとは呼べないのかもしれませんが。

図1　Or-Opt(１ポイントを切り取る場合)
fig1a.png

図2　Or-Opt（2ポイントを切り取る場合）
or-opt2a 0001.png

図3　Or-Opt（3ポイントを切り取る場合）
or-opt3a 0001.png

図4　初期経路（n=100、L=5446.6）
_or-opt_240603_003.jpg

図5　最終経路（1ポイントの切り取り、n=100、L=941.6）
_or-opt_240603_004.jpg

図6　最終経路（2ポイントの切り取り、n=100、L=1003.8）
_or-opt2_240604_001.jpg

図7　最終経路（3ポイントの切り取り、n=100、L=1058.9）
_or-opt3_240604_001.jpg

図8　最終経路（1～[n-4]ポイントの切り取り、n=100、L=824.9）
_or-opt_240603_001.jpg

ConsoleOrOpt1.cpp
// Or-Opt (1pointの切り取り)

#include <iostream>
using namespace std;

#define NUM_TOWN 20    // 町の数
#define AREA_SCALE 100.0    // 町が存在するエリアの大きさ（正方形の一辺の長さ）

double town_map[NUM_TOWN][2];    // 町のx, y座標
int route[NUM_TOWN];    // 巡回経路

// ルートの中の二つの町の行く順番を交換
void swap(int* route1, int i, int j)
{
	int tmp = route1[i];
	route1[i] = route1[j];
	route1[j] = tmp;
}

// 町の座標をランダムに生成
void create_random_map()
{
	for (int i = 0; i < NUM_TOWN; i++)
		for (int j = 0; j < 2; j++)
			town_map[i][j] = AREA_SCALE * (double)rand() / ((double)RAND_MAX + 1);
}

// 都市間の距離を計算
double calc_dist(int i, int j)
{
	double dx = town_map[i][0] - town_map[j][0];
	double dy = town_map[i][1] - town_map[j][1];
	double dist = sqrt(dx * dx + dy * dy);
	return dist;
}

// 指定された巡回経路の長さを計算
double calc_length(int route1[])
{
	double sum_dist = 0.0;
	for (int i = 0; i < NUM_TOWN; i++)
		sum_dist += calc_dist(route1[i], route1[(i + 1) % NUM_TOWN]);
	return sum_dist;
}

// 巡回経路の初期化
void init_route()
{
	for (int i = 0; i < NUM_TOWN; i++)
		route[i] = i;
}

// 巡回経路と総距離の出力
void print_route()
{
	for (int i = 0; i < NUM_TOWN; i++)
		cout << route[i] + 1 << " ";
//		cout << route[i] << " ";
	cout << endl;

	double length = calc_length(route);
	cout << "Total Distance: " << length << endl;
}

// 町の座標を出力
void print_town_map()
{
	for (int i = 0; i < NUM_TOWN; i++) {
		cout << route[i] + 1 << " ";
		cout << town_map[route[i]][0] << " " << town_map[route[i]][1] << endl;
	}
}

// 2点間の距離を計算するマクロ
#define DIST(n,m)  calc_dist(route[(n) % NUM_TOWN], route[(m) % NUM_TOWN])

bool or_opt1(int i, int j)
{
	bool fImproved = false;
	double diff = DIST(i, i + 1) + DIST(j, j + 1) + DIST(j + 1, j + 2)
		- (DIST(i, j + 1) + DIST(i + 1, j + 1) + DIST(j, j + 2));
	if (diff > 0) {
		int temp = route[(j + 1) % NUM_TOWN];
		for (int k = j + 1; k > i + 1; k--)
			route[k % NUM_TOWN] = route[(k - 1) % NUM_TOWN];
		route[(i + 1) % NUM_TOWN] = temp;
		fImproved = true;   // 改善した
	}
	return fImproved;
}

void calc_or_opt1()
{
	bool fImproved = true;
	while (fImproved == true) { // 改善できるポイントが無くなるまで繰り返す
		fImproved = false;
		for (int i = 0; i < NUM_TOWN; i++) {
			for (int j = i + 2; j < i + NUM_TOWN - 2; j++) {
				if(or_opt1(i, j) == true) {
					fImproved = true;
				}
			}
		}
	}
}

int main()
{
	unsigned int seed = (unsigned)time(NULL);
	cout << "Seed = " << seed << endl;
	srand(seed);

	create_random_map();
	init_route();

	cout << "Number of town: " << NUM_TOWN << endl;

	cout << endl << "Town map" << endl;
	print_town_map();

	cout << endl << "First root" << endl;
	print_route();

	calc_or_opt1();

	cout << endl << "Last root" << endl;
	print_route();

	return 0;
}
ConsoleOrOpt2.cpp
// Or-Opt (2pointの切り取り)

#include <iostream>
using namespace std;

#define NUM_TOWN 20    // 町の数
#define AREA_SCALE 100.0    // 町が存在するエリアの大きさ（正方形の一辺の長さ）

double town_map[NUM_TOWN][2];    // 町のx, y座標
int route[NUM_TOWN];    // 巡回経路

// ルートの中の二つの町の行く順番を交換
void swap(int* route1, int i, int j)
{
	int tmp = route1[i];
	route1[i] = route1[j];
	route1[j] = tmp;
}

// 町の座標をランダムに生成
void create_random_map()
{
	for (int i = 0; i < NUM_TOWN; i++)
		for (int j = 0; j < 2; j++)
			town_map[i][j] = AREA_SCALE * (double)rand() / ((double)RAND_MAX + 1);
}

// 都市間の距離を計算
double calc_dist(int i, int j)
{
	double dx = town_map[i][0] - town_map[j][0];
	double dy = town_map[i][1] - town_map[j][1];
	double dist = sqrt(dx * dx + dy * dy);
	return dist;
}

// 指定された巡回経路の長さを計算
double calc_length(int route1[])
{
	double sum_dist = 0.0;
	for (int i = 0; i < NUM_TOWN; i++)
		sum_dist += calc_dist(route1[i], route1[(i + 1) % NUM_TOWN]);
	return sum_dist;
}

// 巡回経路の初期化
void init_route()
{
	for (int i = 0; i < NUM_TOWN; i++)
		route[i] = i;
}

// 巡回経路と総距離の出力
void print_route()
{
	for (int i = 0; i < NUM_TOWN; i++)
		cout << route[i] + 1 << " ";
//		cout << route[i] << " ";
	cout << endl;

	double length = calc_length(route);
	cout << "Total Distance: " << length << endl;
}

// 町の座標を出力
void print_town_map()
{
	for (int i = 0; i < NUM_TOWN; i++) {
		cout << route[i] + 1 << " ";
		cout << town_map[route[i]][0] << " " << town_map[route[i]][1] << endl;
	}
}

// 2点間の距離を計算するマクロ
#define DIST(n,m)  calc_dist(route[(n) % NUM_TOWN], route[(m) % NUM_TOWN])

bool or_opt2(int i, int j)
{
	bool fImproved = false;
	double diff = DIST(i, i + 1) + DIST(j, j + 1) + DIST(j + 2, j + 3)
		- (DIST(i, j + 2) + DIST(i + 1, j + 1) + DIST(j, j + 3));
	if (diff > 0) {
		int temp0 = route[(j + 2) % NUM_TOWN];
		int temp1 = route[(j + 1) % NUM_TOWN];
		for (int k = j + 2; k > i + 2; k--)
			route[k % NUM_TOWN] = route[(k - 2) % NUM_TOWN];
		route[(i + 2) % NUM_TOWN] = temp1;
		route[(i + 1) % NUM_TOWN] = temp0;
		fImproved = true;   // 改善した
	}
	return fImproved;
}

void calc_or_opt2()
{
	bool fImproved = true;
	while (fImproved == true) { // 改善できるポイントが無くなるまで繰り返す
		fImproved = false;
		for (int i = 0; i < NUM_TOWN; i++) {
			for (int j = i + 2; j < i + NUM_TOWN - 3; j++) {
				if (or_opt2(i, j) == true) {
					fImproved = true;
				}
			}
		}
	}
}

int main()
{
	unsigned int seed = (unsigned)time(NULL);
	cout << "Seed = " << seed << endl;
	srand(seed);

	create_random_map();
	init_route();

	cout << "Number of town: " << NUM_TOWN << endl;
	
	cout << endl << "Town map" << endl;
	print_town_map();

	cout << endl << "First root" << endl;
	print_route();

	calc_or_opt2();

	cout << endl << "Last root" << endl;
	print_route();

	return 0;
}
ConsoleOrOpt3.cpp
// Or-Opt (3pointの切り取り)

#include <iostream>
using namespace std;

#define NUM_TOWN 20    // 町の数
#define AREA_SCALE 100.0    // 町が存在するエリアの大きさ（正方形の一辺の長さ）

double town_map[NUM_TOWN][2];    // 町のx, y座標
int route[NUM_TOWN];    // 巡回経路

// ルートの中の二つの町の行く順番を交換
void swap(int* route1, int i, int j)
{
	int tmp = route1[i];
	route1[i] = route1[j];
	route1[j] = tmp;
}

// 町の座標をランダムに生成
void create_random_map()
{
	for (int i = 0; i < NUM_TOWN; i++)
		for (int j = 0; j < 2; j++)
			town_map[i][j] = AREA_SCALE * (double)rand() / ((double)RAND_MAX + 1);
}

// 都市間の距離を計算
double calc_dist(int i, int j)
{
	double dx = town_map[i][0] - town_map[j][0];
	double dy = town_map[i][1] - town_map[j][1];
	double dist = sqrt(dx * dx + dy * dy);
	return dist;
}

// 指定された巡回経路の長さを計算
double calc_length(int route1[])
{
	double sum_dist = 0.0;
	for (int i = 0; i < NUM_TOWN; i++)
		sum_dist += calc_dist(route1[i], route1[(i + 1) % NUM_TOWN]);
	return sum_dist;
}

// 巡回経路の初期化
void init_route()
{
	for (int i = 0; i < NUM_TOWN; i++)
		route[i] = i;
}

// 巡回経路と総距離の出力
void print_route()
{
	for (int i = 0; i < NUM_TOWN; i++)
		cout << route[i] + 1 << " ";
//		cout << route[i] << " ";
	cout << endl;

	double length = calc_length(route);
	cout << "Total Distance: " << length << endl;
}

// 町の座標を出力
void print_town_map()
{
	for (int i = 0; i < NUM_TOWN; i++) {
		cout << route[i] + 1 << " ";
		cout << town_map[route[i]][0] << " " << town_map[route[i]][1] << endl;
	}
}

// 2点間の距離を計算するマクロ
#define DIST(n,m)  calc_dist(route[(n) % NUM_TOWN], route[(m) % NUM_TOWN])

bool or_opt3(int i, int j)
{
	bool fImproved = false;
	double diff = DIST(i, i + 1) + DIST(j, j + 1) + DIST(j + 3, j + 4)
		- (DIST(i, j + 3) + DIST(i + 1, j + 1) + DIST(j, j + 4));
	if (diff > 0) {
		int temp0 = route[(j + 3) % NUM_TOWN];
		int temp1 = route[(j + 2) % NUM_TOWN];
		int temp2 = route[(j + 1) % NUM_TOWN];
		for (int k = j + 3; k > i + 3; k--)
			route[k % NUM_TOWN] = route[(k - 3) % NUM_TOWN];
		route[(i + 3) % NUM_TOWN] = temp2;
		route[(i + 2) % NUM_TOWN] = temp1;
		route[(i + 1) % NUM_TOWN] = temp0;
		fImproved = true;   // 改善した
	}
	return fImproved;
}

void calc_or_opt3()
{
	bool fImproved = true;
	while (fImproved == true) { // 改善できるポイントが無くなるまで繰り返す
		fImproved = false;
		for (int i = 0; i < NUM_TOWN; i++) {
			for (int j = i + 2; j < i + NUM_TOWN - 4; j++) {
				if(or_opt3(i, j) == true) {
					fImproved = true;
				}
			}
		}
	}
}

int main()
{
	unsigned int seed = (unsigned)time(NULL);
	cout << "Seed = " << seed << endl;
	srand(seed);

	create_random_map();
	init_route();

	cout << "Number of town: " << NUM_TOWN << endl;

	cout << endl << "Town map" << endl;
	print_town_map();

	cout << endl << "First root" << endl;
	print_route();

	calc_or_opt3();

	cout << endl << "Last root" << endl;
	print_route();

	return 0;
}
ConsoleOrOptAll.cpp
// Or-Opt (1～[n-4]pointの切り取り)

#include <iostream>
using namespace std;

#define NUM_TOWN 20    // 町の数
#define AREA_SCALE 100.0    // 町が存在するエリアの大きさ（正方形の一辺の長さ）

double town_map[NUM_TOWN][2];    // 町のx, y座標
int route[NUM_TOWN];    // 巡回経路

// ルートの中の二つの町の行く順番を交換
void swap(int* route1, int i, int j)
{
	int tmp = route1[i];
	route1[i] = route1[j];
	route1[j] = tmp;
}

// 町の座標をランダムに生成
void create_random_map()
{
	for (int i = 0; i < NUM_TOWN; i++)
		for (int j = 0; j < 2; j++)
			town_map[i][j] = AREA_SCALE * (double)rand() / ((double)RAND_MAX + 1);
}

// 都市間の距離を計算
double calc_dist(int i, int j)
{
	double dx = town_map[i][0] - town_map[j][0];
	double dy = town_map[i][1] - town_map[j][1];
	double dist = sqrt(dx * dx + dy * dy);
	return dist;
}

// 指定された巡回経路の長さを計算
double calc_length(int route1[])
{
	double sum_dist = 0.0;
	for (int i = 0; i < NUM_TOWN; i++)
		sum_dist += calc_dist(route1[i], route1[(i + 1) % NUM_TOWN]);
	return sum_dist;
}

// 巡回経路の初期化
void init_route()
{
	for (int i = 0; i < NUM_TOWN; i++)
		route[i] = i;
}

// 巡回経路と総距離の出力
void print_route()
{
	for (int i = 0; i < NUM_TOWN; i++)
		cout << route[i] + 1 << " ";
//		cout << route[i] << " ";
	cout << endl;

	double length = calc_length(route);
	cout << "Total Distance: " << length << endl;
}

// 町の座標を出力
void print_town_map()
{
	for (int i = 0; i < NUM_TOWN; i++) {
		cout << route[i] + 1 << " ";
		cout << town_map[route[i]][0] << " " << town_map[route[i]][1] << endl;
	}
}

// 2点間の距離を計算するマクロ
#define DIST(n,m)  calc_dist(route[(n) % NUM_TOWN], route[(m) % NUM_TOWN])

bool or_opt_all(int cut_branch, int i, int j)
{
	bool fImproved = false;
	double diff = DIST(i, i + 1) + DIST(j, j + 1)
		+ DIST(j + cut_branch, j + cut_branch + 1)
		- (DIST(i, j + cut_branch) + DIST(i + 1, j + 1) + DIST(j, j + cut_branch + 1));
	if (diff > 0) {
		int* temp = new int[NUM_TOWN];
		for (int k = 0; k < cut_branch; k++)
			temp[k] = route[(j + cut_branch - k) % NUM_TOWN];
		for (int k = j + cut_branch; k > i + cut_branch; k--)
			route[k % NUM_TOWN] = route[(k - cut_branch) % NUM_TOWN];
		for (int k = 0; k < cut_branch; k++)
			route[(i + cut_branch - k) % NUM_TOWN] = temp[cut_branch - k - 1];
		delete []temp;
		fImproved = true;   // 改善した
	}
	return fImproved;
}

void calc_or_opt()
{
	bool fImproved = true;
	while (fImproved == true) { // 改善できるポイントが無くなるまで繰り返す
		fImproved = false;
		for (int cut_branch = 1; cut_branch <= NUM_TOWN - 4; cut_branch++) {
			for (int i = 0; i < NUM_TOWN; i++) {
				for (int j = i + 2; j < i + NUM_TOWN - 1 - cut_branch; j++) {
					if (or_opt_all(cut_branch, i, j) == true) {
						fImproved = true;
					}
				}
			}
		}
	}
}

int main()
{
	unsigned int seed = (unsigned)time(NULL);
	cout << "Seed = " << seed << endl;
	srand(seed);

	create_random_map();
	init_route();

	cout << "Number of town: " << NUM_TOWN << endl;

	cout << endl << "Town map" << endl;
	print_town_map();

	cout << endl << "First root" << endl;
	print_route();

	calc_or_opt();

	cout << endl << "Last root" << endl;
	print_route();

	return 0;
}
実行結果 (All Point）
Seed = 1721135208
Number of town: 20

Town map
1 15.2039 29.2816
2 41.925 51.4374
3 94.4031 59.5398
4 6.38733 15.9821
5 56.0608 21.3776
6 42.3553 57.8888
7 38.1439 80.0476
8 66.629 39.1022
9 67.7521 65.4358
10 5.99976 79.892
11 32.1655 21.402
12 61.7493 27.8107
13 84.4879 51.3916
14 85.321 93.2465
15 49.4598 63.4644
16 55.6976 79.715
17 45.0928 67.8711
18 99.2096 86.9965
19 85.7819 30.2856
20 42.3187 15.2435

First root
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Total Distance: 878.283

Last root
5 12 8 19 13 3 18 14 16 9 15 6 2 17 7 10 1 4 11 20
Total Distance: 387.769
1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?