具有时间窗约束累积性车辆路径问题的禁忌搜索优化算法

作者：董蕊,刘冉,江志斌,任盼

摘要：基于对中国实际物流运输中成本计算方法的研究,考虑到我国高速公路系统计价方式的特殊性,提出了具有时间窗约束的累积性车辆路径问题。以降低实际车辆运输成本为目标,设计了新型的禁忌搜索算法对问题进行有效求解;算法中嵌入多种邻域搜索方法,允许同时在可行和不可行解空间内进行邻域搜索,同时采用Nagata提出的时间窗违反量计算方法[1-2]对解的时间窗约束违反进行评估。针对提出的新型问题的数值试验证明了所采用的时间窗违反量计算方法的时间节约性和有效性;同时由于该问题可以覆盖传统的累积性车辆路径问题,对后者的数值实验以及与其他优化算法的对比验证了所提出算法的优良求解效果。

发文机构：上海交通大学工业工程与管理系

关键词：累积性成本车辆路径时间窗禁忌搜索cumulative costvehicle routing problemtime windowTabu search

分类号： TP301[自动化与计算机技术—计算机系统结构][自动化与计算机技术—计算机科学与技术]