Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel Monte Carlo sampling

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-pa...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2013-07, Vol.40 (7), p.1661-1670
Main Authors: Weyland, Dennis, Montemanni, Roberto, Gambardella, Luca Maria
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Approximation
Computation
Computer simulation
Exact sciences and technology
Flows in networks. Combinatorial problems
Heuristic
Inventory control, production control. Distribution
Local search
Logistics
Mathematical analysis
Mathematics
Monte Carlo methods
Monte Carlo sampling
Monte Carlo simulation
Operational research and scientific management
Operational research. Management science
Probability and statistics
Probability theory
Random restart local search
Route optimization
Sampling
Sampling theory, sample surveys
Sciences and techniques of general use
Statistics
Stochastic vehicle routing
Studies
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2012.12.015