带多软时间窗VRP及其禁忌搜索算法

来源：计算机工程与应用杂志2019年第6期北京时间：

作者：谢九勇，符 卓，邱 萌，夏扬坤

单位：中南大学 交通运输工程学院，长沙 410075

摘要：分析了带多软时间窗VRP实际应用背景和特点，以使用的车辆数、行驶费用和偏离时间窗的惩罚费用为优化目标，结合车辆载重、最大路长等限制，建立该问题的数学模型，并设计求解该问题的自适应禁忌搜索算法。为增强算法的全局寻优能力，设计了多邻域结构并在算法中嵌入一种有限地接受不可行解的自适应机制。分别用文献中的算例和以Solomon标准算例为基础构建的新算例测试该算法，并将结果与其他方法进行对比分析。对比结果表明，所提出的算法性能较好，能在可接受的时间内求出运输成本更少、满意度更高的解。

关键词：车辆路径问题,多软时间窗,禁忌搜索,物流配送