مسیریابی جهت دار

مسیریابی جهت‌دار دارای قدمت زیادی است و برای اولین بار در 1984 مطالعه شده است.

مسیریابی جهت‌دار دارای قدمت زیادی است و برای اولین بار در (Tsiligirides, 1984) مطالعه شده است و سپس توسط (Golden et al., 1987) و (Chao et al., 1996) بررسی شده است.
در مسئله مسیریابی جهت‌دار تعدادی نقطه بالقوه با امتیازهای مشخص وجود دارد. این امتیازها می‌تواند در هر مسئله متناسب با کاربرد آن، متفاوت باشد. هدف مشخص کردن یک مسیر با انتخاب تعدادی از این نقاط است، که هر نقطه حداکثر یکبار بازدید شود، به طوری که با توجه به محدودیت مدت زمان طول مسیر، مجموع سود حاصل از بازدید نقاط انتخابی و جمع‌آوری امتیاز آن بیشینه شود. مسئله در ادبیات با نام Orienteering Problem یا به اختصار OP شناخته می‌شود.
اهمیت این مسئله در کاربرد مشخص می‌شود. با توجه به اینکه در همه شرایط، محدودیت منابع وجود دارد، هنگام مسیریابی، مسئله انتخاب مناسب‌ترین گزینه‌ها جهت بازدید از اهمیت بسیاری برخوردار می‌شود. مناسب‌ترین گزینه‌ی بازدید در هر حالت با توجه به شرایط و نوع صنعت، می‌تواند با معیارهای متفاوتی تعریف شود که در نهایت می‌توان با تعیین معیار امتیاز برای هر نقطه (روش محاسبه و تعیین مقدار امتیاز متناسب با شرایط در نظر گرفته می‌شود)، مسئله مورد نظر را به مسئله مسیریابی جهت‌دار تبدیل نمود.