مساله‌ی جهت‌یابی با سودهای متغیر و تابع هدف کسری و تقاضا روی کمان
محورهای موضوعی : آمارسید مصطفی خرمی زاده 1 , داریوش اسفندیاران 2
1 - تحقیق در عملیات، دانشکده ریاضی، دانشگاه صنعتی شیراز، شیراز، ایران
2 - گروه ریاضی، دانشگاه صنعتی شیراز، شیراز، ایران
کلید واژه: Bisection method, Fractional objective function, Branch and cut, Arc routing, Orienteering problem,
چکیده مقاله :
امروزه به دلیل توقع بالای مشتریان در برآورده کردن تقاضایشان و فضای رقابت در میان ارایه دهندگان خدمات، کارفرمایان در تلاشند تا با ارایه روش‌های جدید تقاضای مشتریان را در کوتاه‌ترین زمان و به بهترین شکل ممکن برآورده کنند تا رضایت مشتریان را جلب و بیشترین سود ممکن را نیز جمع‌آوری کنند. در این مقاله مساله‌ی جهت‌یابی با سودهای متغیر با تابع هدف کسری مورد مطالعه قرار می‌گیرد و سپس یک مدل برنامه‌ریزی صحیح برای حل آن مورد استفاده قرار می‌گیرد. در این مساله هدف تعیین یک مسیر برای وسیله‌ی نقلیه است به گونه‌ای که سود جمع‌آوری شده را بیشینه کند، شروع و پایان حرکتش در مبدا باشد، مشتریان دارای تقاضا را سرویس‌دهی کند و از مدت زمان در نظر گرفته شده برای سفر تجاوز نکند. در مساله‌ی جهت‌یابی با سودهای متغیر با تابع هدف کسری مشتریان در راس‌های گراف متناظر با مساله قرار دارند. در ادامه حالتی از مساله مورد بررسی قرار می‌گیرد که در آن سرویس‌دهی در کمان انجام می‌پذیرد. مساله حاصل را مساله‌ی جهت‌یابی کمان با سودهای متغیر با تابع هدف کسری می‌نامیم. در ادامه مساله را به روش دوبخشی حل می‌کنیم. در پایان مدل ارایه شده برای حل مساله را روی دسته‌ای از نمونه‌ها‌ی تصادفی پیاده‌سازی کرده و با ارایه نتایج عددی کارایی روش را مورد بحث و بررسی قرار خواهیم داد. خواهیم دید که الگوریتم‌های پیشنهادی قادرند مسایل را در مدت زمان معقولی حل کنند. همچنین خواهیم دید که مدت زمان حل مسایل وابسته به ساختار گراف آن‌ها می‌باشد و به بزرگی مسایل وابسته نیستند. همچنین خواهیم دید که جواب‌های بدست آمده برای مساله بهینه هستند.
Nowadays, due to the high expectations of customers in meeting their demand and the competition environment among service providers, employers are working to provide customers with new methods in the shortest possible time and in the best possible way to attract customer’s satisfaction and maximize profits. In this paper, the orienteering problem with variable profits, fractional objective function and demand on arcs is studied. An appropriate integer programming model is proposed to solve it. In this case, the purpose is to determine a route for a vehicle so that it maximizes the profit, the start and end of its route is at the origin, serving demands of customers, and does not exceed a maximum allowed travel time. In the orinteering problem with variable profits and fractional objective function the customers are located on vertices of the graph corresponding to the problem. Next, a problem is considered in which the service is performed on arcs. The resulting problem is called the orinteering arc routing problem with variable profits and fractional objective function. We solve the problem by bisection method. In the end, the numerical efficiency of the proposed model is examined. The proposed algorithms can solve problems in a reasonable amount of time. We will also see that the time of solving problems depends on their graph structure and not on their size.
[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.