گزینه های مسیریابی

این بخش برخی از گزینه های حل کننده مسیریابی را توضیح می دهد.

محدودیت های جستجو

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

جدول زیر رایج ترین محدودیت های جستجو را شرح می دهد.

نام	تایپ کنید	پیش فرض	توضیحات
solution_limit	int64	kint64max	محدود به تعداد راه حل های تولید شده در طول جستجو.
time_limit.seconds	int64	kint64max	محدود کردن در ثانیه به زمان صرف شده: در جستجو.
lns_time_limit.seconds	int64	100	محدود کردن در ثانیه به زمان صرف شده در: جستجوی تکمیل برای هر همسایه جستجوی محلی.

استراتژی راه حل اول

استراتژی راه حل اول روشی است که حل کننده برای یافتن راه حل اولیه استفاده می کند. جدول زیر گزینه های first_solution_strategy را فهرست می کند.

گزینه	توضیحات
AUTOMATIC	به حل کننده اجازه می دهد تا با توجه به مدل در حال حل، از کدام استراتژی استفاده کند.
PATH_CHEAPEST_ARC	با شروع از یک گره "شروع" مسیر، آن را به گره ای که ارزان ترین بخش مسیر را تولید می کند وصل کنید، سپس با تکرار روی آخرین گره اضافه شده به مسیر، مسیر را گسترش دهید.
PATH_MOST_CONSTRAINED_ARC	مشابه PATH_CHEAPEST_ARC ، اما کمان‌ها با انتخابگر مبتنی بر مقایسه ارزیابی می‌شوند که ابتدا محدودترین قوس را ترجیح می‌دهد. برای اختصاص دادن یک انتخابگر به مدل مسیریابی، از روش ArcIsMoreConstrainedThanArc() استفاده کنید.
EVALUATOR_STRATEGY	مشابه PATH_CHEAPEST_ARC ، با این تفاوت که هزینه‌های قوس با استفاده از تابع ارسال شده به SetFirstSolutionEvaluator() ارزیابی می‌شوند.
SAVINGS	الگوریتم پس انداز (کلارک و رایت). مرجع Clarke, G. & Wright, JW "Scheduling of Vehicles from a Central Depot to a Number of Delive Points" , Operations Research, Vol. 12، 1964، صص 568-581.
SWEEP	الگوریتم Sweep (Wren & Holliday). مرجع آنتونی رن و آلن هالیدی برنامه‌ریزی رایانه‌ای وسایل نقلیه از یک یا چند انبار تا تعدادی از نقاط تحویل فصلنامه تحقیقات عملیاتی (1970-1977)، جلد. 23، شماره 3 (شهریور 1351)، صص 333-344.
CHRISTOFIDES	الگوریتم کریستوفیدس (در واقع نوعی از الگوریتم کریستوفیدس با استفاده از تطبیق حداکثر به جای تطبیق حداکثر، که ضریب 3/2 تقریب را در یک فروشنده دوره گرد متریک تضمین نمی کند). با گسترش یک مسیر تا زمانی که هیچ گره‌ای روی آن وارد نشود، روی مدل‌های مسیریابی خودروی عمومی کار می‌کند. مرجع نیکوس کریستوفیدس، تحلیل بدترین حالت یک اکتشافی جدید برای مشکل فروشنده دوره گرد، گزارش 388، دانشکده تحصیلات تکمیلی مدیریت صنعتی، CMU، 1976.
ALL_UNPERFORMED	همه گره ها را غیر فعال کنید. تنها در صورتی راه حل را پیدا می کند که گره ها اختیاری باشند (عنصری از یک محدودیت تفکیک با هزینه جریمه محدود هستند).
BEST_INSERTION	به طور مکرر یک راه حل با قرار دادن ارزان ترین گره در ارزان ترین موقعیت آن بسازید. هزینه درج بر اساس تابع هزینه جهانی مدل مسیریابی است. از 2/2012، فقط روی مدل‌هایی با گره‌های اختیاری (با هزینه‌های جریمه محدود) کار می‌کند.
PARALLEL_CHEAPEST_INSERTION	به طور مکرر یک راه حل با قرار دادن ارزان ترین گره در ارزان ترین موقعیت آن بسازید. هزینه درج بر اساس تابع هزینه قوس است. سریعتر از BEST_INSERTION است.
LOCAL_CHEAPEST_INSERTION	به طور مکرر با قرار دادن هر گره در ارزان ترین موقعیت خود، یک راه حل بسازید. هزینه درج بر اساس تابع هزینه قوس است. با گره انتخاب شده برای درج با PARALLEL_CHEAPEST_INSERTION تفاوت دارد. در اینجا گره ها به ترتیب ایجاد در نظر گرفته می شوند. سریعتر از PARALLEL_CHEAPEST_INSERTION است.
GLOBAL_CHEAPEST_ARC	به طور مکرر دو گره را به هم متصل کنید که ارزان ترین بخش مسیر را تولید می کند.
LOCAL_CHEAPEST_ARC	اولین گره را با یک جانشین بدون محدودیت انتخاب کنید و آن را به گره ای که ارزان ترین بخش مسیر را تولید می کند وصل کنید.
FIRST_UNBOUND_MIN_VALUE	اولین گره را با یک جانشین غیر محدود انتخاب کنید و آن را به اولین گره موجود متصل کنید. این معادل استراتژی CHOOSE_FIRST_UNBOUND است که با ASSIGN_MIN_VALUE ترکیب شده است (ر.ک. constraint_solver.h).

وضعیت جستجو

می توانید وضعیت جستجو را با استفاده از روش status مدل مسیریابی برگردانید. در اینجا کد پایتون برای چاپ وضعیت جستجو آمده است:

print("Solver status: ", solver.status())

این یک عدد صحیح با معانی زیر چاپ می کند:

ارزش	توضیحات
0	ROUTING_NOT_SOLVED : مشکل هنوز حل نشده است.
1	ROUTING_SUCCESS : مشکل با موفقیت حل شد.
2	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED : مشکل پس از فراخوانی RoutingModel.Solve() با موفقیت حل شد، با این تفاوت که به یک بهینه محلی رسیده نشده است. گذاشتن زمان بیشتر باعث بهبود راه حل می شود.
3	ROUTING_FAIL : هیچ راه حلی برای مشکل پیدا نشد.
4	ROUTING_FAIL_TIMEOUT : محدودیت زمانی قبل از یافتن راه حل به پایان رسیده است.
5	ROUTING_INVALID : مدل، پارامترهای مدل یا پرچم‌ها معتبر نیستند.
6	ROUTING_INFEASIBLE : مشکل غیر ممکن بودن ثابت شده است.

گزینه های جستجوی محلی

جدول زیر گزینه‌های استراتژی‌های جستجوی محلی (همچنین فراابتکاری نامیده می‌شود) را فهرست می‌کند. برای نمونه هایی از تنظیم این گزینه ها به تغییر استراتژی جستجو مراجعه کنید.

گزینه	توضیحات
AUTOMATIC	به حل کننده اجازه می دهد فراابتکاری را انتخاب کند.
GREEDY_DESCENT	بهبود (کاهش هزینه) همسایگان جستجوی محلی را تا رسیدن به حداقل محلی می پذیرد.
GUIDED_LOCAL_SEARCH	از جستجوی محلی هدایت‌شده برای فرار از حداقل‌های محلی استفاده می‌کند. (ر.ک. جستجوی محلی هدایت شده ) این به طور کلی کارآمدترین فراابتکاری برای مسیریابی خودرو است.
SIMULATED_ANNEALING	از بازپخت شبیه سازی شده برای فرار از حداقل های محلی استفاده می کند (ر.ک. شبیه سازی آنیل ).
TABU_SEARCH	از جستجوی تابو برای فرار از حداقل‌های محلی استفاده می‌کند (به جستجوی Tabu مراجعه کنید).
GENERIC_TABU_SEARCH	از جستجوی تابو بر روی مقدار هدف راه حل برای فرار از حداقل های محلی استفاده می کند.

کنترل انتشار

نام	تایپ کنید	پیش فرض	توضیحات
use_full_propagation	بوول	درست است	از قیود با انتشار کامل در مدل مسیریابی (فقط به جای انتشار نور ) استفاده کنید. انتشار کامل تنها زمانی لازم است که از جستجوی اول عمق استفاده می شود یا برای مدل هایی که برای نهایی کردن مقدار متغیرهای ثانویه به انتشار قوی نیاز دارند. تغییر این تنظیم به true در اکثر موارد باعث کاهش سرعت جستجو و افزایش مصرف حافظه در همه موارد می شود.