مساله‌ی جهت‌یابی با سودهای متغیر و تابع هدف کسری و تقاضا روی کمان
الموضوعات :
سید مصطفی خرمی زاده
1
(تحقیق در عملیات، دانشکده ریاضی، دانشگاه صنعتی شیراز، شیراز، ایران)
داریوش اسفندیاران
2
(گروه ریاضی، دانشگاه صنعتی شیراز، شیراز، ایران)
الکلمات المفتاحية: Bisection method, Fractional objective function, Branch and cut, Arc routing, Orienteering problem,
ملخص المقالة :
امروزه به دلیل توقع بالای مشتریان در برآورده کردن تقاضایشان و فضای رقابت در میان ارایه دهندگان خدمات، کارفرمایان در تلاشند تا با ارایه روش‌های جدید تقاضای مشتریان را در کوتاه‌ترین زمان و به بهترین شکل ممکن برآورده کنند تا رضایت مشتریان را جلب و بیشترین سود ممکن را نیز جمع‌آوری کنند. در این مقاله مساله‌ی جهت‌یابی با سودهای متغیر با تابع هدف کسری مورد مطالعه قرار می‌گیرد و سپس یک مدل برنامه‌ریزی صحیح برای حل آن مورد استفاده قرار می‌گیرد. در این مساله هدف تعیین یک مسیر برای وسیله‌ی نقلیه است به گونه‌ای که سود جمع‌آوری شده را بیشینه کند، شروع و پایان حرکتش در مبدا باشد، مشتریان دارای تقاضا را سرویس‌دهی کند و از مدت زمان در نظر گرفته شده برای سفر تجاوز نکند. در مساله‌ی جهت‌یابی با سودهای متغیر با تابع هدف کسری مشتریان در راس‌های گراف متناظر با مساله قرار دارند. در ادامه حالتی از مساله مورد بررسی قرار می‌گیرد که در آن سرویس‌دهی در کمان انجام می‌پذیرد. مساله حاصل را مساله‌ی جهت‌یابی کمان با سودهای متغیر با تابع هدف کسری می‌نامیم. در ادامه مساله را به روش دوبخشی حل می‌کنیم. در پایان مدل ارایه شده برای حل مساله را روی دسته‌ای از نمونه‌ها‌ی تصادفی پیاده‌سازی کرده و با ارایه نتایج عددی کارایی روش را مورد بحث و بررسی قرار خواهیم داد. خواهیم دید که الگوریتم‌های پیشنهادی قادرند مسایل را در مدت زمان معقولی حل کنند. همچنین خواهیم دید که مدت زمان حل مسایل وابسته به ساختار گراف آن‌ها می‌باشد و به بزرگی مسایل وابسته نیستند. همچنین خواهیم دید که جواب‌های بدست آمده برای مساله بهینه هستند.
[1] Golden, B. L., Levy, L., and Vohra, R. 1987 "The orienteering problem," Naval research logistics,vol. 34, pp. 307-318.
[2] Vansteenwegen, P., Souffriau, W., and Van Oudheusden, D. 2011 "The orienteering problem: A survey," European Journal of Operational Research,vol. 209, pp. 1-10.
[3] Chao, I., Golden, B. L., and Wasil, E. A. 1996 "The team orienteering problem," European Journal of Operational Research,vol. 3, pp. 464-474.
[4] Tang, H. and Miller-Hooks, E. 2005 "A tabu search heuristic for the team orienteering problem," Computers & Operations Research,vol. 32, pp. 1379-1407.
[5] Kantor, M. G. and Rosenwein, M. B. 1992 "The orienteering problem with time windows," Journal of the Operational Research Society,vol. 43, pp. 629-635.
[6] Fomin, F. V. and Lingas, A. 2002 "Approximation algorithms for time-dependent orienteering," Information Processing Letters,vol. 83, pp. 57-62.
[7] Ilhan, T., Iravani, S. M., and Daskin, M. S. 2008 "The orienteering problem with stochastic profits," Iie Transactions,vol. 40, pp. 406-421.
[8] Souffriau, W., Vansteenwegen, P., Berghe, G. V., and Van Oudheusden, D. 2011 "The planning of cycle trips in the province of East Flanders," Omega,vol. 39, pp. 209-213.
[9] Archetti, C. and Speranza, M. G. 2014 "Arc Routing Problems with Profits," Arc Routing: Problems, Methods, and Applications,vol. 20, p. 281.
[10] Archetti, C., Feillet, D., Hertz, A., and Speranza, M. G. 2009 "The capacitated team orienteering and profitable tour problems," Journal of the Operational Research Society,vol. 60, pp. 831-842.
[12] Angelelli, E., Archetti, C., and Vindigni, M. 2014 "The clustered orienteering problem," European Journal of Operational Research,vol. 238, pp. 404-414.
[13] Yu, J., Schwager, M., and Rus, D., "Correlated orienteering problem and its application to informative path planning for persistent monitoring tasks," in Intelligent Robots and Systems (IROS 2014), 2014 IEEE/RSJ International Conference on, 2014, pp. 342-349.
[14] Van Der Merwe, M., Minas, J., Ozlen, M., and Hearne, J. 2014 "The cooperative orienteering problem with time windows," Optimization Online
[15] Erdoǧan, G. and Laporte, G. 2013 "The orienteering problem with variable profits," Networks,vol. 61, pp. 104-116.
