2-ऑप्ट

2-ऑप्ट

अनुकूलन में, ट्रैवलिंग सेल्समैन की समस्या को हल करने के लिए 2-ऑप्ट एक सरल स्थानीय खोज (लोकल सर्च) एल्गोरिदम है। 2-ऑप्ट एल्गोरिदम पहली बार 1958 में क्रोज़ द्वारा प्रस्तावित किया गया था, हालांकि मूल चाल का सुझाव फ्लड द्वारा पहले ही दिया जा चुका था। इसके पीछे मुख्य विचार यह है कि एक ऐसा रूट अपनाया जाए जो स्वयं को पार करे और उसे पुन: व्यवस्थित किया जाए ताकि वह स्वयं पार न हो। संपूर्ण 2-ऑप्ट स्थानीय खोज स्वैपिंग तंत्र के हर संभव वैध संयोजन की तुलना करेगी। यह तकनीक ट्रैवलिंग सेल्समैन की समस्या के साथ-साथ कई संबंधित समस्याओं पर भी लागू की जा सकती है। इनमें वाहन रूटिंग समस्या (वीआरपी) के साथ-साथ कैपेसिटेटेड वीआरपी भी सम्मिलित है, जिसमें एल्गोरिदम में साधारण संशोधन की आवश्यकता होती है।

स्यूडोकोड

दृष्टिगत रूप से, एक स्वैप इस तरह दिखता है:

 - A   B -             - A - B -
     ×         ==>
 - C   D -             - C - D -

स्यूडोकोड में, वह तंत्र जिसके द्वारा 2-ऑप्ट स्वैप किसी दिए गए रूट में हेरफेर करता है, इस प्रकार है। यहां v1 और v2 किनारों के पहले शीर्ष हैं जिन्हें आप रूट से गुजरते समय स्वैप करना चाहते हैं:

procedure 2optSwap(route, v1, v2) {
    1. take route[0] to route[v1] and add them in order to new_route
    2. take route[v1+1] to route[v2] and add them in reverse order to new_route
    3. take route[v2+1] to route[start] and add them in order to new_route
    return new_route;
}

यहां यादृच्छिक माध्यम से इनपुट के साथ उपरोक्त का एक उदाहरण दिया गया है:

• उदाहरण रूट: A → B → E → D → C → F → G → H → A
• उदाहरण पैरामीटर: v1=1, v2=4 (प्रारंभिक सूचकांक 0 मानते हुए)
• नया_रूट की विषय वस्तु:

1. (A → B)
2. A → B → (C → D → E)
3. A → B → C → D → E → (F → G → H → A)

यह उपरोक्त तंत्र का उपयोग करते हुए पूर्ण 2-ऑप्ट स्वैप है:

repeat until no improvement is made {
    best_distance = calculateTotalDistance(existing_route)
    start_again:
    for (i = 0; i <= number of nodes eligible to be swapped - 1; i++) {
        for (j = i + 1; j <= number of nodes eligible to be swapped; j++) {
            new_route = 2optSwap(existing_route, i, j)
            new_distance = calculateTotalDistance(new_route)
            if (new_distance < best_distance) {
                existing_route = new_route
                best_distance = new_distance
                goto start_again
            }
        }
    }
}

नोट: यदि आप किसी विशेष नोड या डिपो पर प्रारम्भ / समाप्त करते हैं, तो आपको इसे स्वैपिंग के लिए योग्य आवेदक के रूप में परिवर्तन से निकालना होगा, क्रम को व्युत्क्रम से अमान्य पथ हो जाएगा।

उदाहरण के लिए, A स्थित डिपो के साथ:

   A → B → C → D → A

नोड[0] और नोड[2] का उपयोग करके स्वैप करने से परिणाम मिलेगा

   C → B → A → D → A

जो वैध नहीं है (A डिपो नहीं छोड़ता है)।

कुशल कार्यान्वयन

नए रूट का निर्माण करना और नए रूट की दूरी की गणना करना एक बहुत अधिक संचालन हो सकता है, सामान्यतः $O(n)$ जहां n रूट में शीर्षों की संख्या है। इसे $O(1)$ संचालन निष्पादित करके सममित स्तिथि में (जहां दो नोड्स के बीच की दूरी प्रत्येक विपरीत दिशा में समान है) छोड़ा जा सकता है। चूंकि 2-ऑप्ट संचालन में 2 किनारों को हटाना और 2 अलग-अलग किनारों को जोड़ना सम्मिलित है, इसलिए हम केवल उन किनारों की दूरियां घटा और जोड़ सकते हैं।

lengthDelta = - dist(route[v1], route[v1+1]) - dist(route[v2], route[v2+1]) + dist(route[v1+1], route[v2+1]) + dist(route[v1], route[v2])

यदि lengthDeltaऋणात्मक है तो इसका मतलब यह होगा कि स्वैप के बाद नई दूरी छोटी होगी। एक बार जब यह पता चल जाता है कि lengthDelta ऋणात्मक है, तो हम 2-ऑप्ट स्वैप करते हैं। इससे हमें बहुत सारी संगणना करने से बचाया जा सकता है।

साथ ही वहां वर्ग दूरी का उपयोग करने से वर्गमूल फ़ंक्शन कॉल को छोड़कर गणना को कम करने में सहायता मिलती है। चूँकि हम केवल दो दूरियों की तुलना करने की परवाह करते हैं, सटीक दूरी की नहीं, इससे चीज़ों की गति बढ़ाने में मदद मिलेगी। यह बहुत ज़्यादा नहीं है, लेकिन यह लाखों शीर्षों वाले बड़े डेटासेट के साथ सहायता करता है।

C++ कोड

#include <algorithm>
#include <random>
#include <stdio.h>
#include <vector>

using namespace std;

class Point {
  public:
	int x, y;

	Point(int x, int y) {
		this->x = x;
		this->y = y;
	}
	Point() {
		this->x = 0;
		this->y = 0;
	}

	// Distance between two points squared
	inline int dist2(const Point &other) const {
		return (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y);
	}
};

// Calculate the distance of the whole path (Squared Distances between points)
int pathLengthSq(vector<Point> &path) {
	int length = 0;
	for (int i = 0; i < path.size(); i++) {
		length += path[i].dist2(path[(i + 1) % path.size()]);
	}
	return length;
}

// Perform a 2-opt swap
void do2Opt(vector<Point> &path, int i, int j) {
	reverse(begin(path) + i + 1, begin(path) + j + 1);
}

// Print the path. 
void printPath(string pathName, vector<Point> &path) {
	printf("%s = [", pathName.c_str());
	for (int i = 0; i < path.size(); i++) {
		if (i % 10 == 0) {
			printf("\n    ");
		}

		if (i < path.size() - 1) {
			printf("[ %3d, %3d], ", path[i].x, path[i].y);
		}
		else {
			printf("[ %3d, %3d]", path[i].x, path[i].y);
		}
	}
	printf("\n];\n");
}

// Create a path of length n with random points between 0 and 1000
vector<Point> createRandomPath(int n) {
	vector<Point> path;
	for (int i = 0; i < n; i++) {
		path.push_back(Point(rand() % 1000, rand() % 1000));
	}
	return path;
}

int main() {
	vector<Point> path = createRandomPath(100);
	printPath("path1", path);

	int curLength = pathLengthSq(path);
	int n = path.size();
	bool foundImprovement = true;
	while (foundImprovement) {
		foundImprovement = false;
		for (int i = 0; i <= n - 2; i++) {
			for (int j = i + 1; j <= n - 1; j++) {
				int lengthDelta = -path[i].dist2(path[(i + 1) % n]) - path[j].dist2(path[(j + 1) % n]) + path[i].dist2(path[j]) + path[(i + 1) % n].dist2(path[(j + 1) % n]);

				// If the length of the path is reduced, do a 2-opt swap
				if (lengthDelta < 0) {
					do2Opt(path, i, j);
					curLength += lengthDelta;
					foundImprovement = true;
				}
			}
		}
	}

	printPath("path2", path);
	return 0;
}

आउटपुट

path1 = [
    [ 743, 933], [ 529, 262], [ 508, 700], [ 256, 752], [ 119, 256], [ 351, 711], [ 705, 843], [ 393, 108], [ 366, 330], [ 932, 169],
    [ 847, 917], [ 868, 972], [ 223, 980], [ 592, 549], [ 169, 164], [ 427, 551], [ 624, 190], [ 920, 635], [ 310, 944], [ 484, 862],
    [ 301, 363], [ 236, 710], [ 431, 876], [ 397, 929], [ 491, 675], [ 344, 190], [ 425, 134], [  30, 629], [ 126, 727], [ 334, 743],
    [ 760, 104], [ 620, 749], [ 932, 256], [ 613, 572], [ 509, 490], [ 405, 119], [  49, 695], [ 719, 327], [ 824, 497], [ 649, 596],
    [ 184, 356], [ 245,  93], [ 306,   7], [ 754, 509], [ 665, 352], [ 738, 783], [ 690, 801], [ 337, 330], [ 656, 195], [  11, 963],
    [  42, 427], [ 968, 106], [   1, 212], [ 480, 510], [ 571, 658], [ 814, 331], [ 564, 847], [ 625, 197], [ 931, 438], [ 487,  18],
    [ 187, 151], [ 179, 913], [ 750, 995], [ 913, 750], [ 134, 562], [ 547, 273], [ 830, 521], [ 557, 140], [ 726, 678], [ 597, 503],
    [ 893, 408], [ 238, 988], [  93,  85], [ 720, 188], [ 746, 211], [ 710, 387], [ 887, 209], [ 103, 668], [ 900, 473], [ 105, 674],
    [ 952, 183], [ 787, 370], [ 410, 302], [ 110, 905], [ 996, 400], [ 585, 142], [  47, 860], [ 731, 924], [ 386, 158], [ 400, 219],
    [  55, 415], [ 874, 682], [   6,  61], [ 268, 602], [ 470, 365], [ 723, 518], [ 106,  89], [ 130, 319], [ 732, 655], [ 974, 993]
];
path2 = [
    [ 743, 933], [ 750, 995], [ 847, 917], [ 868, 972], [ 974, 993], [ 913, 750], [ 920, 635], [ 874, 682], [ 726, 678], [ 732, 655],
    [ 830, 521], [ 900, 473], [ 893, 408], [ 931, 438], [ 996, 400], [ 932, 256], [ 952, 183], [ 968, 106], [ 932, 169], [ 887, 209],
    [ 760, 104], [ 746, 211], [ 720, 188], [ 656, 195], [ 625, 197], [ 624, 190], [ 585, 142], [ 557, 140], [ 487,  18], [ 306,   7],
    [ 245,  93], [ 187, 151], [ 169, 164], [ 106,  89], [  93,  85], [   6,  61], [   1, 212], [ 119, 256], [ 130, 319], [ 184, 356],
    [ 301, 363], [ 337, 330], [ 366, 330], [ 410, 302], [ 344, 190], [ 393, 108], [ 405, 119], [ 425, 134], [ 386, 158], [ 400, 219],
    [ 529, 262], [ 547, 273], [ 470, 365], [ 509, 490], [ 597, 503], [ 710, 387], [ 665, 352], [ 719, 327], [ 814, 331], [ 787, 370],
    [ 824, 497], [ 754, 509], [ 723, 518], [ 649, 596], [ 571, 658], [ 613, 572], [ 592, 549], [ 480, 510], [ 427, 551], [ 268, 602],
    [ 134, 562], [  55, 415], [  42, 427], [  30, 629], [  49, 695], [ 103, 668], [ 105, 674], [ 126, 727], [  47, 860], [  11, 963],
    [ 110, 905], [ 179, 913], [ 223, 980], [ 238, 988], [ 310, 944], [ 256, 752], [ 236, 710], [ 334, 743], [ 351, 711], [ 491, 675],
    [ 508, 700], [ 431, 876], [ 397, 929], [ 484, 862], [ 564, 847], [ 620, 749], [ 690, 801], [ 738, 783], [ 705, 843], [ 731, 924]
];

दृश्य-चित्रण

यह भी देखें

• 3-ऑप्ट
• लोकल सर्च (अनुकूलन)
• लिन-कर्निघन अनुमानी

संदर्भ

• G. A. CROES (1958). A method for solving traveling salesman problems. Operations Res. 6 (1958), pp., 791-812.
• M. M. FLOOD (1956). The traveling-salesman problem. Operations Res. 4 (1956), pp., 61-75.

बाहरी संबंध

• The Traveling Salesman Problem: A Case Study in Local Optimization
• Improving Solutions: 2-opt Exchanges