中文摘要：

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

英文摘要：

Based on the study of travel cost computing method in reality and the particularity of the expressway toll method in China,the paper proposed the cumulative capacitated vehicle routing problem with time window（CCVRPTW）.We designed a new tabu search algorithm embedded with several effective local search strategies to achieve the goal of minimizing the actual cumulative travel cost.The algorithm also allowed to search on both feasible and infeasible spaces,and adopted Nagata＇s time window violation calculation method to assess the time window violation.From the computation results for the CCVRPTW instances first generated in this paper,the Nagata＇s time violation calculation method showed a significantly time efficiency than traditional one;besides.Computational experiments on the traditional problem benchmarks also showed that our algorithm is rather competitive with other approaches from the literature.