一类具有载量限制的软时间窗车辆路径规划问题研究  

Research on a Class of Soft TimeWindow Vehicle Routing Algorithm with Capacitated Load

作　　者：廖雄雄 邵永运 LIAO Xiongxiong;SHAO Yongyun(College of Software,Shenyang Normal University,Shenyang 110034,Liaoning Province)

机构地区：[1]沈阳师范大学软件学院,辽宁沈阳110034

出　　处：《沈阳工程学院学报（自然科学版）》2024年第4期81-87,共7页Journal of Shenyang Institute of Engineering:Natural Science

基　　金：教育部高等教育司产学合作协同育人项目(202002097034)。

摘　　要：考虑载量受限、软时间窗和行程持续时间限制约束,研究了一类具有载量限制的软时间窗车辆路径规划问题(CVRPSTW)。首先,采用罚函数法建立以总运输成本为目标的CVRPSTW混合整数模型,使其更符合实际;其次,为解决禁忌搜索算法在求解该问题时耗时长、易陷入局部最优等问题,设计了一种混合禁忌搜索算法(SATS),并利用A*算法构造优质初始解和多种移动机制来寻找候选解,提高算法的有效性;再次,为评估算法性能,在Solomon实例上进行了大量实验,结果显示SATS算法的综合求解能力显著优于其他方法;最后,验证了算法在某地区物资配送问题上的可行性。In this paper,it is studied that a class of capacitated vehicle routing problem with soft time window(CVRPSTW)with load limitations,soft time windows and trip duration constraints.First,the penalty function method is used to establish a mixed-integer model of CVRPSTW with the objective of total transportation cost.Second,in order to solve the problems such as the tabu search algorithm is time-consuming and easy to fall into local optimization when solving this problem,a hybrid tabu search algorithm(SATS)is designed and the A*algorithm is utilized to construct a high-quality initial solution and a variety of moving mechanisms to find the candidate solutions,which can improve the effectiveness of the algorithm.To evaluate the performance of the algorithm,the extensive experiments on Solomon instances are conducted.The results show that the SATS algorithm significantly outperforms other methods in terms of its comprehensive solution capability.Finally,the feasibility of the algorithm is verified under the problem of material distribution during an epidemic quarantine in a region.

关 键 词：CVRPSTW 罚函数法 混合整数模型 SATS算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]