چکيده— مسائل جهت یابی (OPs) نوع دیگری از مساله معروف «فروشنده دوره گرد» می باشند که هدف آن عبارت است از محاسبه مسیری با بیشترین میزان پاداش (سود) که شامل زیر مجموعه ای از گره ها می باشد و مجموع زمان پیمایش آن مسیر، کمتر از زمان تعیین شده است. مسائل جهت یابی تصادفی (SOPs)، شکل گسترش یافته مسائل جهت یابی (OPs) هستند که در مورد زمان های سفر نامعین کاربرد دارند و حل آنها نسبت به مسائل جهت یابی قطعی، دشوار تر است. در این مقاله، برای حل مسائل جهت یابی تصادفی (SOPs) از نوع «آگاه از ریسک» ، از فرمول بندی مقیاس پذیر «برنامه ریزی خطی عدد صحیح مختلط (MILP)» استفاده می کنیم که یک روش تقریب باقاعده در مورد مساله بهینه سازی تصادفی (موضوع این مقاله) می باشد. روش ما، به صورت تجربی، نسبت به بهترین روش قبلی، راهکار بهتری را در خصوص معیار های ساختگی و نیز در مورد مساله واقعی برنامه ریزی سفر در پارک های موضوعی (theme park) ارائه می دهد.

Abstract:  Orienteering problems (OPs) are typically used to model routing and trip planning problems. OP is a variant of the well known traveling salesman problem where the goal is to compute the highest reward path that includes a subset of nodes and has an overall travel time less than the specified deadline. Stochastic orienteering problems (SOPs) extend OPs to account for uncertain travel times and are significantly harder to solve than deterministic OPs. In this paper, we contribute a scalable mixed integer LP formulation for solving risk aware SOPs, which is a principled approximation of the underlying stochastic optimization problem. Empirically, our approach provides significantly better solution quality than the previous best approach over a range of synthetic benchmarks and on a real-world theme park trip planning problem.