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.
2013
14th International Conference on Computer Aided Systems Theory, EUROCAST 2013
Las Palmas de Gran Canaria, esp
February 2013
8111
332
339
Weyland, Dennis; Montemanni, Roberto; Gambardella Luca, Maria
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].
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1176134
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact