Paper Info
Title
Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel Monte Carlo sampling
Abstract
The Probabilistic Traveling Salesman Problem with Deadlines (PTSPD) is a Stochastic Vehicle Routing Problem with a computationally demanding objective function. In this work we propose an approximation for that objective function based on Monte Carlo Sampling and using the novel approach of quasi-parallel evaluation of samples. We perform comprehensive computational studies that reveal the efficiency of this approximation. Additionally, we examine different Local Search Algorithms and present a Random Restart Local Search Algorithm for solving the PTSPD together with an extensive computational study on a large set of benchmark instances.
Year
DOI
Venue
2013
10.1016/j.cor.2012.12.015
Computers & OR
Keywords
DocType
Volume
benchmark instance,large set,Random Restart Local Search,salesman problem,quasi-parallel Monte Carlo sampling,Stochastic Vehicle Routing Problem,objective function,Monte Carlo Sampling,different Local Search Algorithms,Salesman Problem,extensive computational study,comprehensive computational study
Journal
40
Issue
ISSN
Citations 
7
0305-0548
6
PageRank 
References 
Authors
0.47
26
3
Name
Order
Citations
PageRank
Dennis Weyland11088.43
Roberto Montemanni264344.25
Luca Maria Gambardella360.47