शुरू करेंमुफ़्त में शुरू करें

Traveling Salesman Problem (TSP)

Traveling Salesman Problem (TSP) एक लोकप्रिय समस्या है और लॉजिस्टिक्स में इसके उपयोग हैं। TSP में एक सेल्समैन को शहरों की सूची और हर जोड़ी के बीच की दूरी दी जाती है। उसे मूल स्थान से शुरू करके सभी बिंदुओं से होकर गुजरते हुए सबसे छोटा मार्ग खोजना होता है और अंत में फिर से मूल शहर पर लौटना होता है। यह संगणकीय रूप से कठिन समस्या है, लेकिन Miller-Tucker-Zemlin (MTZ) ने दिखाया कि इसे Integer Linear Programming से हल किया जा सकता है। इस अभ्यास में आप 15 शहरों वाले एक छोटे डेटासेट (नीचे दी गई इमेज देखें) के लिए TSP का objective और कुछ constraints परिभाषित करेंगे। आपका लक्ष्य LpVariable.dicts को list comprehension के साथ आज़माना है।

Photo of Cities

तीन Python वैरिएबल n, cities, और dist आपके लिए बनाए गए हैं $^{1}$। n शहरों की संख्या है, cities नंबर किए गए शहरों की सूची है, और dist एक pandas DataFrame है जिसमें प्रत्येक शहर-जोड़ी के बीच की pairwise दूरी है। आप इन्हें कंसोल में देख सकते हैं। इसके अलावा, मॉडल भी आपके लिए initialize कर दिया गया है।

\(^{1}\) डेटासेट स्रोत: Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,

यह अभ्यास पाठ्यक्रम का हिस्सा है

Python में सप्लाई चेन एनालिटिक्स

पाठ्यक्रम देखें

इंटरैक्टिव व्यावहारिक अभ्यास

इस अभ्यास को इस नमूना कोड को पूरा करके आज़माएँ।

# Define Decision Variables
x = LpVariable.dicts('X', [(____, ____) for c1 in ____ for c2 in ____], 
                     cat='____')
u = LpVariable.dicts('U', [____ for c1 in ____], 
                     lowBound=0, upBound=(n-1), cat=____)
कोड संपादित करें और चलाएँ