Stochastic combinatorial optimization problems have received increasing attention in recent years. These problems can be used to obtain more realistic models for real world applications. The drawback is that stochastic combinatorial optimization problems are usually much harder to solve than their non-stochastic counterparts and therefore efficient heuristics for these problems are of great importance. In this paper we focus on the Probabilistic Traveling Salesman Problem with Deadlines, a well-known stochastic vehicle routing problem. This problem can be efficiently solved using a heuristic based on general-purpose computing on graphics processing units. We show how such a heuristic can be further improved to allow a more efficient utilization of the graphics processing unit. We extensively discuss our results and point out how our techniques can be generalized for solving other stochastic combinatorial optimization problems.
An improved heuristic for the probabilistic traveling salesman problem with deadlines based on GPGPU / Weyland, Dennis; Montemanni, Roberto; Gambardella Luca, Maria. - 8111:1(2013), pp. 332-339. (Intervento presentato al convegno 14th International Conference on Computer Aided Systems Theory, EUROCAST 2013 tenutosi a Las Palmas de Gran Canaria, esp nel February 2013) [10.1007/978-3-642-53856-8_42].
An improved heuristic for the probabilistic traveling salesman problem with deadlines based on GPGPU
Montemanni Roberto;
2013
Abstract
Stochastic combinatorial optimization problems have received increasing attention in recent years. These problems can be used to obtain more realistic models for real world applications. The drawback is that stochastic combinatorial optimization problems are usually much harder to solve than their non-stochastic counterparts and therefore efficient heuristics for these problems are of great importance. In this paper we focus on the Probabilistic Traveling Salesman Problem with Deadlines, a well-known stochastic vehicle routing problem. This problem can be efficiently solved using a heuristic based on general-purpose computing on graphics processing units. We show how such a heuristic can be further improved to allow a more efficient utilization of the graphics processing unit. We extensively discuss our results and point out how our techniques can be generalized for solving other stochastic combinatorial optimization problems.Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris