A Survey on the Vehicle Routing Problem and Its Variants  

作　　者：Suresh Nanda Kumar Ramasamy Panneerselvam 

机构地区：[1]Department of Management Studies, Pondicherry University, Pondicherry, India [2]Education Department, CII Institute of Logistics, Chennai, India

出　　处：《Intelligent Information Management》2012年第3期66-74,共9页智能信息管理（英文）

摘　　要：In this paper, we have conducted a literature review on the recent developments and publications involving the vehicle routing problem and its variants, namely vehicle routing problem with time windows (VRPTW) and the capacitated vehicle routing problem (CVRP) and also their variants. The VRP is classified as an NP-hard problem. Hence, the use of exact optimization methods may be difficult to solve these problems in acceptable CPU times, when the problem involves real-world data sets that are very large. The vehicle routing problem comes under combinatorial problem. Hence, to get solutions in determining routes which are realistic and very close to the optimal solution, we use heuristics and meta-heuristics. In this paper we discuss the various exact methods and the heuristics and meta-heuristics used to solve the VRP and its variants.In this paper, we have conducted a literature review on the recent developments and publications involving the vehicle routing problem and its variants, namely vehicle routing problem with time windows (VRPTW) and the capacitated vehicle routing problem (CVRP) and also their variants. The VRP is classified as an NP-hard problem. Hence, the use of exact optimization methods may be difficult to solve these problems in acceptable CPU times, when the problem involves real-world data sets that are very large. The vehicle routing problem comes under combinatorial problem. Hence, to get solutions in determining routes which are realistic and very close to the optimal solution, we use heuristics and meta-heuristics. In this paper we discuss the various exact methods and the heuristics and meta-heuristics used to solve the VRP and its variants.

关 键 词：Vehicle Routing Problem Exact Methods HEURISTICS META-HEURISTICS VRPTW OPTIMIZATION Ant COLONY OPTIMIZATION Genetic Algorithms 

分 类 号：TP1[自动化与计算机技术—控制理论与控制工程]