Orienteering Problem with Variable Profits, Fractional Objective Function and Demand on Arcs

Subject Areas : Statistics

S. M. khorramizadeh ¹ , D. Esfandyaran ²

1 - Assistant Professor, Department of Applied Mathematics (Operations Research), Faculty of Mathematics, Shiraz University of Technology, Shiraz, Iran
2 - Department of Mathematics, Shiraz University of Technology, Shiraz, Iran.

Received: 2018-02-26 Accepted : 2019-01-06 Published : 1970-01-01

Keywords: شاخه و برش, تابع هدف کسری, مساله جهت‌یابی, روش دوبخشی, مسیریابی کمان,

Abstract :

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.

References:

 

[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.