文章基本信息

标题：Constructive and Clustering Methods to Solve Capacitated Vehicle Routing Problem
本地全文：下载
作者：M. A. H. Akhand ; Tanzima Sultana ; M. I. R. Shuvo 等
期刊名称：Oriental Journal of Computer Science and Technology
印刷版ISSN：0974-6471
出版年度：2017
卷号：10
期号：3
页码：549-562
语种：English
出版社：Oriental Scientific Publishing Company
摘要：Vehicle Routing Problem (VRP) is a real life constraint satisfaction problem to find minimal travel distances of vehicles to serve customers. Capacitated VRP (CVRP) is the simplest form of VRP considering vehicle capacity constraint. Constructive and clustering are the two popular approaches to solve CVRP. A constructive approach creates routes and attempts to minimize the cost at the same time. Clarke and Wright’s Savings algorithm is a popular constructive method based on savings heuristic. On the other hand, a clustering based method first assigns nodes into vehicle wise cluster and then generates route for each vehicle. Sweep algorithm and its variants and Fisher and Jaikumar algorithm are popular among clustering methods. Route generation is a traveling salesman problem (TSP) and any TSP optimization method is useful for this purpose. In this study, popular constructive and clustering methods are studied, implemented and compared outcomes in solving a suite of benchmark CVRPs. For route optimization, Genetic Algorithm (GA), Ant Colony Optimization (ACO) and Velocity Tentative Particle Swarm Optimization (VTPSO) are employed in this study which are popular nature inspired optimization techniques for solving TSP. Experimental results revealed that parallel Savings is better than series Savings in constructive method. On the other hand, Sweep Reference Point using every stop (SRE) is the best among clustering based techniques.
关键词：Capacitated Vehicle Routing Problem ; Constructive method ; Clustering method ; Clarke and Wright’s Savings Algorithm ; Sweep Algorithm ; Fisher and Jaikumar Algorithm ; Genetic Algorithm ; Ant Colony Optimization and Velocity Tentative Particle Swarm Optimization