Title :
An importance sampling method based on the variance minimization with applications to Vehicle Routing Problem
Author_Institution :
Inf. Coll., Capital Univ. of Economic & Bus., Beijing, China
Abstract :
Vehicle routing problem belongs to classical Combination Optimization hard problem and has been extensively studied by many researchers. Vehicle Routing Problem with Weight Coefficients and Stochastic Demands (WVRPSD) is established and a new implementation for importance sampling method to solve this model is proposed in this paper, in which the classical exponential change of measure is adopted to construct the family of importance sampling distributions, and the optimal importance sampling distribution is obtained by minimizing the variance of importance sampling estimator. Numerical experiments have been conducted and the results indicate that the method can effectively solve this problem.
Keywords :
combinatorial mathematics; computational complexity; minimisation; sampling methods; stochastic processes; combination optimization hard problem; importance sampling distributions; importance sampling method; stochastic demands; variance minimization; vehicle routing problem; weight coefficients; Costs; Educational institutions; Minimization methods; Monte Carlo methods; NP-hard problem; Routing; Sampling methods; Stochastic processes; Transportation; Vehicles; Important Sampling; Stochastic Demands; Variance Minimization; Vehicle Routing Problem;
Conference_Titel :
Future Computer and Communication (ICFCC), 2010 2nd International Conference on
Conference_Location :
Wuhan
Print_ISBN :
978-1-4244-5821-9
DOI :
10.1109/ICFCC.2010.5497664