Meta Heuristic Algorithms for Vehicle Routing Problem with Stochastic Demands | Science Publications

Journal of Computer Science

Dr. P.T. Vanathi¹  Poonthalir Ganesan¹  Geetha Shanmugam¹ 

关键词: Genetic algorithm;    Particle Swarm Optimization (PSO);    Dynamic Programming (DP);    Vehicle Routing Problem (VRP);    stochastic demands;    hybrid PSO;    distribution logistics;    random variables;    priori route;    exact algorithm;   

DOI  :  10.3844/jcssp.2011.533.542

学科分类：计算机科学（综合）

来源: Science Publications

【 摘 要 】

Problem statement: The shipment of goods from manufacturer to the consumer is a focalpoint of distribution logistics. In reality, the demand of consumers is not known a priori. This kind ofdistribution is dealt by Stochastic Vehicle Routing Problem (SVRP) which is a NP-hard problem. Inthis proposed work, VRP with stochastic demand is considered. A probability distribution is consideredas a random variable for stochastic demand of a customer. Approach: In this study, VRPSD isresolved using Meta heuristic algorithms such as Genetic Algorithm (GA), Particle SwarmOptimization (PSO) and Hybrid PSO (HPSO). Dynamic Programming (DP) is used to find theexpected cost of each route generated by GA, PSO and HPSO. Results: The objective is to minimizethe total expected cost of a priori route. The fitness value of a priori route is calculated using DP. Inproposed HPSO, the initial particles are generated based Nearest Neighbor Heuristic (NNH). Elitism isused in HPSO for updating the particles. The algorithm is implemented using MATLAB7.0 and testedwith problems having different number of customers. The results obtained are competitive in terms ofexecution time and memory usage. Conclusion: The computational time is reduced as polynomial timeas O(nKQ) time and the memory required is O(nQ). The ANOVA test is performed to compare theproposed HPSO with other heuristic algorithms.

【 授权许可】

Unknown