基于ISTASA算法的带软时间窗的车辆路径问题研究

作     者：王名霞 韩晓霞 曹阳 武晋德 申亚迪 

作者机构：中国海洋大学信息科学与工程学部 太原理工大学电气与动力工程学院 

出 版 物：《太原理工大学学报》 (Journal of Taiyuan University of Technology)

年 卷 期：2023年

学科分类：08[工学] 081104[工学-模式识别与智能系统] 0811[工学-控制科学与工程] 082302[工学-交通信息工程及控制] 0823[工学-交通运输工程] 

基　　金：国家自然科学基金资助项目（62176176） 

主　　题：车辆路径问题 软时间窗 总运输成本 罚函数法 改进状态转移模拟退火算法 

摘      要：带时间窗的车辆路径问题是一个经典的组合优化问题，是物流配送系统的关键。在实际物流配送中，企业常采用超时赔付的方法解决配送超时的问题，从而提高客户满意度。针对这一现象，本文提出了带软时间窗的具有容量限制的车辆路径问题（CVRPSTW），并采用罚函数法，建立一个以总运输成本最少为目标的CVRPSTW优化模型。不合理的寻优方法往往存在效率低、求解质量差等问题，为了更好地求解CVRPSTW，本文基于状态转移模拟退火（STASA）算法，提出了一个改进状态转移模拟退火（ISTASA）算法。本次研究以Solomon基准作为算例，分别采用ISTASA算法、STASA算法和一些经典的启发式算法对CVRPSTW进行求解，通过比较各算法的求解质量，验证算法的有效性。结果表明，在大多数Solomon实例上，ISTASA算法的求解质量显著优于其它方法。