带时间窗的多中心半开放式车辆路径问题

摘要

针对多中心协同配送下的车辆路径问题,建立了总成本最小化模型,所建模型满足多中心、多需求点和半开放式的特征.考虑到问题的复杂性,设计了一种三阶段求解算法:将K-mediods聚类算法用于原始数据分解,将原规模较大的多配送中心路径问题转换成多个单配送中心路径问题;设计了改进多蚁群算法来求解单配送中心路径问题,得到初始方案;在调整阶段,利用节约算法优化初始方案.分析了算例,并同其他文献的算法求解结果进行对比,结果表明,所提算法比GA-ACO算法求解得到的单中心配送最优路径值减小32.16％,总成本减小30.42％;比狼群算法解得的最优路径值和总成本均减小8.99％;比蚁群算法求得的最优路径值减小24.76％,最小配送成本减小3.40％,从而验证了所建模型的合理性和所设计多阶段算法的有效性.