فروشنده دوره‌گرد: مدل‌سازی TSP با add_circuit در CP-SAT

یک راننده پیک باید از انبار شروع کند، چند مشتری را ببیند و دوباره به انبار برگردد. ترتیب بازدید مهم است، چون هر ترتیب، مسافت کل متفاوتی دارد. این دقیقاً همان مسئله کلاسیک فروشنده دوره‌گرد یا TSP است. در این یادداشت، یکی از زیبا‌ترین ابزارهای CP-SAT برای حل آن را می‌بینیم: قید add_circuit.

مسئله فروشنده دوره‌گرد چیست؟

در TSP، مجموعه‌ای از نقاط داریم و فاصله بین هر دو نقطه مشخص است. هدف، پیدا‌کردن یک مسیر دایره‌ای است که از هر نقطه دقیقاً یک‌بار عبور کند. این مسیر باید از یک نقطه شروع شود و به همان نقطه برگردد. در میان همه مسیرهای ممکن، باید کوتاه‌ترین را پیدا کنیم.

سادگی صورت‌مسئله فریبنده است. برای ۵ نقطه، فقط چند ده مسیر ممکن وجود دارد و حل دستی آسان است. اما برای ۲۰ نقطه، تعداد مسیرهای ممکن از چندین میلیارد میلیارد بیشتر می‌شود. TSP یکی از معروف‌ترین مسائل NP-hard در علوم کامپیوتر و پژوهش عملیاتی است.

چرا add_circuit؟ مشکل روش‌های سنتی

سخت‌ترین بخش مدل‌سازی TSP، جلوگیری از زیرمسیر (Subtour) است. اگر فقط بگویید «هر نقطه دقیقاً یک یال ورودی و یک یال خروجی دارد»، کافی نیست. سالور ممکن است چند حلقه کوچک و جدا از هم تولید کند. این حلقه‌ها همگی قید درجه را رعایت می‌کنند، اما یک مسیر واحد نیستند.

در مدل‌های کلاسیک MILP، این مشکل معمولاً با قیدهای میلر-تاکر-زملین (MTZ) یا با حذف تدریجی زیرمسیرها حل می‌شود. هر دو روش جواب می‌دهند، اما هر کدام هزینه‌ای دارند. قیدهای MTZ کران‌های پایین ضعیفی تولید می‌کنند و سالور را کند می‌کنند. حذف تدریجی زیرمسیر هم نیاز به حلقه تکرار دارد. مدل را حل می‌کنید، زیرمسیرها را پیدا می‌کنید، قید جدید اضافه می‌کنید. سپس دوباره مدل را حل می‌کنید.

قید add_circuit در CP-SAT، این دردسر را از بین می‌برد. این قید مستقیماً تضمین می‌کند که یال‌های فعال، یک مدار واحد (Single Circuit) روی همه گره‌ها بسازند، نه چند حلقه جدا. منطق حذف زیرمسیر، داخل خود سالور و به‌صورت بسیار کارآمد پیاده شده است؛ شما دیگر نیازی به نوشتن آن ندارید.

اهمیت این موضوع

TSP فقط یک پازل ریاضی نیست؛ ستون فقرات بسیاری از مسائل مسیریابی صنعتی است. شرکتی مثل UPS سالانه میلیون‌ها مسیر تحویل بسته را برنامه‌ریزی می‌کند، و هسته هر مسیر تکی، دقیقاً یک نمونه از TSP است. حتی مسئله‌های بزرگ‌تر مثل مسیریابی وسایل نقلیه با چند خودرو، در عمل از ترکیب چند زیرمسئله TSP ساخته می‌شوند.

فراتر از حمل‌ونقل، TSP در طراحی مدار چاپی، توالی‌یابی DNA، و حتی برنامه‌ریزی حرکت بازوی رباتیک هم ظاهر می‌شود. هرجا که ترتیب بازدید از چند نقطه، روی هزینه کل اثر بگذارد، شکلی از TSP در پس‌زمینه پنهان است. همین گستردگی کاربرد، آن را به یکی از پرمطالعه‌ترین مسائل بهینه‌سازی ترکیبیاتی تبدیل کرده است.

فرمول‌بندی ریاضی TSP

برای $n$ گره، متغیر تصمیم دودویی $x_{ij}$ را تعریف می‌کنیم. اگر مسیر مستقیماً از گره $i$ به گره $j$ برود، این متغیر برابر یک است.

تابع هدف، کمینه‌کردن مجموع فاصله‌هاست:

$$\min \; \sum_{i=1}^{n} \sum_{j \ne i} d_{ij} \, x_{ij}$$

هر گره باید دقیقاً یک یال خروجی و یک یال ورودی داشته باشد:

$$\sum_{j \ne i} x_{ij} = 1 \quad \forall i, \qquad \sum_{i \ne j} x_{ij} = 1 \quad \forall j$$

این دو قید به‌تنهایی کافی نیستند، چون اجازه می‌دهند چند زیرمسیر جدا شکل بگیرد. فرمول‌بندی کلاسیک، یک قید سوم برای حذف زیرمسیر هم اضافه می‌کند که معمولاً پیچیده‌ترین بخش مدل است. دقیقاً همین قید سوم است که add_circuit آن را به‌صورت داخلی و بهینه مدیریت می‌کند.

مدل‌سازی با add_circuit در CP-SAT

ورودی این قید، یک لیست از یال‌هاست. هر یال، سه‌تایی (tail, head, literal) است: گره مبدأ، گره مقصد، و یک متغیر بولی. این متغیر نشان می‌دهد آیا یال در مسیر نهایی حضور دارد یا نه.

نکته جالب add_circuit، پشتیبانی از یال حلقه‌ای (Self-loop) است. یال (i, i, lit) به این معناست که اگر lit درست باشد، گره $i$ اصلاً در مدار حضور ندارد. این ویژگی، مدل‌سازی مسائل با بازدید اختیاری مثل TSP جایزه‌دار را بسیار ساده می‌کند. بدون این یال، همه گره‌ها باید حتماً بازدید شوند.

برای TSP کلاسیک که همه نقاط باید بازدید شوند، کار ساده است. فقط کافی است برای هر جفت گره $i \ne j$ یک یال با یک متغیر بولی بسازید. سپس همین لیست را به add_circuit بدهید. سالور خودش تضمین می‌کند خروجی، یک مدار واحد و بدون زیرمسیر باشد.

مثال عملی: مسیر یک پیک بین پنج مشتری

فرض کنید پیک باید از انبار (گره ۰) شروع کند و چهار مشتری دیگر را ببیند. ماتریس فاصله بین هر دو نقطه از قبل محاسبه شده است. هدف، یافتن ترتیبی است که مجموع فاصله طی‌شده را کمینه کند.

برای مدل‌سازی، به ازای هر جفت گره یک متغیر بولی و یک یال می‌سازیم. سپس همه این یال‌ها را به add_circuit می‌دهیم و تابع هدف را مجموع وزنی فاصله‌ها روی یال‌های فعال تعریف می‌کنیم. بعد از حل، فقط کافی است یال‌های فعال را دنبال کنیم تا ترتیب نهایی مسیر به دست بیاید.

نکات کاربردی و تعمیم‌ها

ماتریس فاصله لازم نیست متقارن باشد. add_circuit به‌خوبی با TSP نامتقارن (ATSP) هم کار می‌کند. در این حالت فاصله رفت و برگشت بین دو نقطه یکسان نیست، مثلاً به‌خاطر خیابان‌های یک‌طرفه. کافی است وزن یال $(i,j)$ و یال $(j,i)$ را جداگانه و متفاوت تعریف کنید.

اگر بخواهید پنجره زمانی هم به مسئله اضافه کنید، می‌توانید add_circuit را با متغیرهای بازه‌ای ترکیب کنید. دقیقاً همان الگویی که در راه‌اندازی وابسته به توالی در آموزش کامل CP-SAT دیده می‌شود. برای مقیاس‌های بزرگ‌تر که حل دقیق کند می‌شود، ترکیب add_circuit با روش جستجوی همسایگی بزرگ کمک می‌کند. این ترکیب می‌تواند جواب‌های خوب را در زمان معقول پیدا کند.

ظرفیت کار آکادمیک/پژوهشی

TSP با add_circuit، نقطه شروع خوبی برای پژوهش‌های گسترده‌تر است. یک مسیر پژوهشی، مقایسه عملکرد add_circuit در CP-SAT با فرمول‌بندی‌های کلاسیک MILP (مثل MTZ یا Dantzig-Fulkerson-Johnson) روی نمونه‌های استاندارد TSPLIB است.

مسیر دیگر، تعمیم به نسخه‌های صنعتی‌تر است: TSP با پنجره زمانی، TSP نامتقارن با ناوگان ناهمگن، یا TSP جایزه‌دار. در این نسخه آخر، بازدید از همه نقاط ضروری نیست. مقایسه سرعت همگرایی add_circuit در مقیاس‌های مختلف هم موضوع جالبی است. تأثیر ترتیب افزودن یال‌ها بر زمان حل نیز هنوز جای کار پژوهشی دارد.

پیاده‌سازی با پایتون

نکته مهم این است که TSP را می‌توان کاملاً با ابزارهای متن‌باز و رایگان پایتون حل کرد. نیازی به نرم‌افزار تجاری گران‌قیمت نیست. OR-Tools گوگل، با سالور CP-SAT، دقیقاً همین امکان را به‌صورت رایگان فراهم می‌کند.

اسکلت اولیه مدل این‌طور ساخته می‌شود:

from ortools.sat.python import cp_model

n = len(distance_matrix)
model = cp_model.CpModel()

# یک متغیر بولی و یک یال برای هر جفت گره
arcs = []
literals = {}
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        lit = model.new_bool_var(f'x_{i}_{j}')
        literals[(i, j)] = lit
        arcs.append((i, j, lit))

model.add_circuit(arcs)

ادامه تابع هدف (مجموع وزنی فاصله‌ها روی متغیرهای literals) و استخراج ترتیب نهایی مسیر از جواب سالور، به همین شیوه تعریف می‌شوند.

سوالات متداول

تفاوت add_circuit با ماژول Routing در OR-Tools چیست؟

ماژول Routing (پکیج `constraint_solver`) یک چارچوب آماده و سطح‌بالا برای VRP و TSP با قابلیت‌های فراوان است. `add_circuit` در CP-SAT، یک قید سطح‌پایین‌تر و انعطاف‌پذیرتر است که می‌توانید آن را با سایر قیدهای CP-SAT مثل متغیر بازه‌ای ترکیب کنید.

آیا add_circuit برای مسیریابی چند خودرو هم کاربرد دارد؟

بله، با یک تعمیم به نام `add_multiple_circuit` که چند مدار جدا را هم‌زمان مدل می‌کند. این موضوع در دوره مسیریابی وسایل نقلیه با پایتون با مثال‌های صنعتی کامل پوشش داده شده است.

برای پیاده‌سازی اختصاصی این مدل روی داده واقعی شرکتم چه کنم؟

اگر داده‌های واقعی مسیریابی دارید و می‌خواهید مدلی اختصاصی برایتان ساخته شود، از طریق مشاوره می‌توانید جزئیات پروژه را مطرح کنید.

جمع‌بندی

مسئله فروشنده دوره‌گرد، با وجود صورت ساده‌اش، یکی از سخت‌ترین و پرکاربردترین مسائل بهینه‌سازی ترکیبیاتی است. قید add_circuit در CP-SAT، سخت‌ترین بخش مدل‌سازی آن یعنی حذف زیرمسیر را به‌صورت داخلی و کارآمد حل می‌کند. این یعنی مدل تمیزتر، کد کوتاه‌تر، و زمان حل بهتر. دیگر مجبور نیستید منطق پیچیده MTZ یا حذف تدریجی زیرمسیر را خودتان پیاده‌سازی کنید.