文档介绍：1 ·论文· 车辆路径调度问题的启发式算法综述 1 杨燕旋 1 ,宋士吉 1 (,北京 100084) 摘要:车辆路径调度问题是一类具有重大研究意义及广泛应用价值的NP 难优化问题。本文给出了该问题的定义和基本描述,并将目前为止被应用于求解 VRP 问题的启发式算法分为构造型启发式算法、改进型启发式算法和人工智能算法这三大类,接着介绍了各类中比较典型的算法,并对算法的应用和研究情况进行了分析和总结,最后对进一步的研究做出了展望。关键词:物流;车辆路径问题;调度;启发式算法中图分类号: F252 A Survey on the Heuristic Algorithms for the Vehicle Routing Problem YANG Yan-Xuan,1 SONG Shi-Ji,1 (1. Department of Automation, Tsinghua University, Beijing 100084, China) Abstract :Vehicle Routing Problem is an NP-hard probl em with great research and application significance. In this research, we first present the definition of the problem and give a classification to the existed heuristic algorithms for the problem. Then typical algorithms are introduced and research on the algorithms are in vestigated and summarized. Finally, further research directions are given. Key words :Logistics; Vehicle Routing Problem; Scheduling; Heuristic Algorithm 1959 年, Dantzig 等人首先从旅行商问题(Traveling Salesman Problem , 简称 TSP 问题, ) 得到启发,提出了车辆分配问题 TDP (Truck Dispatching Problem )。这是一类具有重要研究价值的问题。一方面,它代表了一类典型的组合优化问题,具有深远的理论意义;另一方面, 它是一类重要的物流运输问题,直接影响着相关企业的运转效率,具有广泛的实践意义。半个世纪以来,许多的专家学者对该问题进行了广泛而深入的研究,并将这类问题统称为车辆路径调度问题( Vehicle Routing Problem ,简称为 VRP 问题) 。他们从基本问题出发,根据 1 基金项目:自然科学基金(编号: 60574077 ) 、国家“八六三”高技术项目(编号: 2007AA04Z102 ) 作者简介: 杨燕旋( 1983- ) , 女, 汉族, 广东, 清华大学硕士研究生, 从事车辆路径调度方向的研究, E-mail: ******@.. 宋士吉( 1965- ) ,男,汉族,黑龙江,清华大学教授,博导,从事供应链管理等方向的研究, E-mail: ******@ma . 2 不同的约束和目标,构建了不同的模型,并有针对性地开发出了有效的算法。从大的框架上讲,用于求解 VRP 问题的算法可以分为两类,一类是精确算法;一类是启发式算法。精确算法主要是基于对具体的问题建立具体的数学模型,并利用数学方法进行求解;启发式算法主要是基于直观或者凭借经验,开发出能够朝着最优解的方向搜索或靠近的一类算法。精确算法以时间和空间的复杂度为代价,换取了解的质量,但往往只能应用于小规模的问题中,这是由 VRP 是 NP 难问题的属性所决定的;启发式算法通常能够在时间和空间复杂度以及解的质量中获得一个平衡,因此,该类算法被越来越多的学者所采用和研究,在实际应用中,它们也显示出了它们的优势。本文对目前被应用得比较多且相对较为成熟的启发式算法进行一个综述。启发式算法可以分为三大类: (一)构造型启发式算法; (二)改进型启发式算法; (三)人工智能算法。本文在总结时,将对各类算法中比较经典和基本的算法(见表 1)进行描述,并对相关的研究进行总结。表 1 启发式算法分支图三大类经典算法插入算法节约算法先聚类后路线算法构造型启发式算法先路线后分割算法 Petal 算法 Swee p 算法改进型启发式算法 O r -o p t 算法禁忌搜索算