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

王名霞; 韩晓霞; 曹阳; 武晋德; 申亚迪

doi:10.16355/j.tyut.1007-9432.20200940

太原理工大学学报 ›› 2025, Vol. 56 ›› Issue (06) : 1101 -1109. DOI: 10.16355/j.tyut.1007-9432.20200940

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

王名霞, 韩晓霞, 曹阳, 武晋德, 申亚迪

作者信息 +

Author information +

文章历史 +

摘要

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