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

A Tabu Search Algorithm for the Cumulative Capacitated Vehicle Routing Problem with Time Window

作　　者：董蕊[1] 刘冉[1] 江志斌[1] 任盼[1] 

机构地区：[1]上海交通大学工业工程与管理系,上海200240

出　　处：《工业工程与管理》2015年第1期49-55,共7页Industrial Engineering and Management

基　　金：国家自然科学基金资助项目(71302013);高等学校博士学科点专项科研基金资助项目(20130073120047);上海市浦江人才计划项目(13PJC075);上海市自然科学基金资助项目(13ZR1456400)

摘　　要：基于对中国实际物流运输中成本计算方法的研究,考虑到我国高速公路系统计价方式的特殊性,提出了具有时间窗约束的累积性车辆路径问题。以降低实际车辆运输成本为目标,设计了新型的禁忌搜索算法对问题进行有效求解;算法中嵌入多种邻域搜索方法,允许同时在可行和不可行解空间内进行邻域搜索,同时采用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.

关 键 词：累积性成本 车辆路径 时间窗 禁忌搜索 

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