集装箱车辆调度问题的变邻域禁忌搜索算法  

A Variable Neighborhood Tabu Search for Container Vehicle Routing Problem

作　　者：汪翼[1] 孙林岩[1,2] 李刚[1] 

机构地区：[1]西安交通大学管理学院,陕西西安710049 [2]机械制造系统工程国家重点实验室,陕西西安710049

出　　处：《工业工程与管理》2008年第5期6-10,28,共6页Industrial Engineering and Management

基　　金：国家自然科学基金重点资助项目(70433003);国家自然科学家基金资助项目(70701029)

摘　　要：研究一类带工作时间约束的集装箱专用车辆调度问题的混合禁忌搜索算法。此问题可分解为车辆路线设定和车辆分配两个组合优化问题,但是两个问题的分开求解最优解的组合却并不一定是总问题的最优解。首先对问题给出数学描述,之后通过引入一个变邻域搜索策略,提出一个解决该问题的混合禁忌搜索算法。该算法使用两行向量进行编码,采用随机扩大禁忌步长,并设计三种邻域变换定义,采用变邻域策略来扩大搜索空间。最后通过对6个不同规模算例求解验证该算法在解决此类问题的有效性。A container vehicle routing problem with working time constraint load is studied in this paper. This problem consists of two sub-problems： the classical routing problem and the generalized assignment problem, but the composition of two optimal solutions of sub-problems may not be the optimal solution of primal problem. A mixed-integer nonlinear programming mode of this problem is firstly given and then a mixed tabu search algorithm based on variable neighborhood strategy is proposed. This tabu search employs a two-vector representation and variable expansible tabu length to detect and escape from a chaotic attractor basin. The heuristic procedure is compared to Lagrangian relaxation-based method and Lingo software on six random created testing problems. The results demonstrate that the procedure developed here is efficiently in solving large scale problems.

关 键 词：禁忌搜索 变邻域策略 集装箱专用车辆调度问题 变禁忌步长 

分 类 号：U491[交通运输工程—交通运输规划与管理]