Vehicle Routing Under Correlated Rewards With an Application to Fish Trawling

Abstract

Routing problems where a vehicle travels through a network to collect rewards are known as orienteering problems. In these types of problems, typically the objective is to maximize the total collected reward. Certain real life problems in this class exhibit uncertainty and spatial and possibly temporal correlation. We develop a methodology that handles correlated rewards in stochastic orienteering problems. We model the problem as a Markov Decision Process and use the Approximate Dynamic Programming framework to generate routing solutions using a variable neighborhood search technique. To model uncertainty, we use various predictive methods ranging from neural networks to Kriging (geospatial Gaussian interpolation). We test our methodology on a fishing dataset for the Baltic Sea. We find that as the predictive performance of a method increases, so does the average reward collected from a fishing trip. However, this relationship is not linear, but it is nonlinear. We suggest that under stochastic rewards, spending time building highly accurate prediction methods is valuable to increase the profit generated from a vehicle routing trip.

Kar toplama amacıyla belirlenen güzergahlar, güzergah belirleme problemleri sınıfında önemli bir yer teşkil ediyor. Gerçek hayatta ise bilinmezliklerden kaynaklanan değişkenler mekansal ve zaman olarak korelasyon göstermekte. Bu tür şartlarda kullanılabilecek bir metodoloji sunuyoruz bu araştırmamızda. Problemimizi Markov Karar Süreci olarak modelleyip, Approximate Dinamik Programlama teknikleri ile çözüyoruz. Parametre değişkenliğini ise çeşitli öngörü modelleri kullanarak test ediyoruz. Bulgularımıza göre öngörü modelinin kesinliği ile optimizasyon sonucu bulunan güzergah değeri arasında pozitif ama lineer olmayan bir ilişki mevcut.