禁忌搜索算法求解带时间窗和多配送人员的车辆路径问题  

Tabu Search Algorithm for the Vehicle Routing Problem with Time Windows and Multiple Deliverymen

作　　者：苏欣欣 秦虎 王恺[2] SU Xinxin;QIN Hu;WANG Kai(College of Management,Huazhong University of Science and Technology.Wuhan 430074;College of Economic and Management,Wuhan University,Wuhan 430074,China)

机构地区：[1]华中科技大学管理学院,武汉430074 [2]武汉大学经济与管理学院,武汉430074

出　　处：《重庆师范大学学报（自然科学版）》2020年第1期22-30,共9页Journal of Chongqing Normal University:Natural Science

基　　金：国家自然科学基金创新研究群体项目(No.71821001);国家自然科学基金面上项目(No.71971090,No.71571077)。

摘　　要：【目的】为了求解带时间窗和多配送人员的车辆路径问题,建立了该车辆路径问题的数学模型,并采用禁忌搜索算法进行求解。【方法】首先松弛车辆载重和顾客时间窗约束,在目标函数里面引入相应的惩罚成本;接着,使用贪婪算法生成初始解;最后,设计禁忌搜索算法求解该问题。在禁忌搜索中,使用了插入、删除、移动、交换等算子搜索邻域解空间,并使用扰动算子进一步加大搜索范围。为了验证禁忌搜索算法的有效性,对修改的Solomon标准测试问题进行求解,并与CPLEX的优化结果进行比较。【结果】在小规模算例求解中证实了禁忌搜索算法的准确性,在标准规模算例求解中证实了该算法的高效性。【结论】所提出的禁忌搜索算法能够有效解决带时间窗和多配送人员的车辆路径问题。[Purposes]It investigates the vehicle routing problem with time windows and multiple deliverymen,which is a general extension of the traditional vehicle routing problem with time windows.[Methods]To solve this problem,an integer programming model is formulated and a heuristic approach is proposed to solve it.First,it relaxes the capacity constraint of the vehicle and the time window constraint of the customer,and adds the corresponding penalty costs in the objective function.Second,a randomized greedy construction method is employed to gen erate an in itial solution.Finally,it develops a tabu search algorithm which applies seven neighborhood search operators and a shaking operator.[Findings]It evaluates the performance of our tabu search algorithm based on both modified and standard Solomon's VRPTW test instances and compares it with CPLEX.[Conclusions]Computational results indicate the effectiveness and efficiency of our proposed tabu search algorithm.

关 键 词：车辆路径问题 时间窗 多配送人员 禁忌搜索算法 

分 类 号：O224[理学—运筹学与控制论] U116.2[理学—数学]