需求可拆分车辆路径问题的三阶段禁忌算法

摘要：

需求可拆分车辆路径问题(SDVRP)是一类有待深入研究的车辆路径问题,其求解方法与需求不可拆分的VRP问题有较大的区别.针对该类问题,本文提供了一种新的求解思路——基于双层规划模型的三阶段禁忌算法.首先,将目标函数设定为大TSP路径成本加上切割增加路径成本,构建了SDVRP的双层规划数学模型;然后,根据双层规划的思路设计了三阶段禁忌启发式算法:先求包括车场和所有顾客的大TSP路径,再对大TSP进行切割和拆分,接着对备选方案进行子路径优化;最后,通过实验仿真,将所提出的三阶段禁忌算法与其他算法进行比较,结果表明了所提出的算法可以比较有效地求得需求可拆分车辆路径问题的优化解,是解决需求可拆分车辆路径问题的有效方法.

关键词：车辆路径问题、需求可拆分、双层规划模型、禁忌算法

所属期刊栏目：35

分类号：U492.3;TP311(交通工程与公路运输技术管理)

资助基金：国家自然科学基金71461007,71461006;中国博士后科学基金2014M560653;中南大学博士后基金126227

在线出版日期：2015-07-13（万方平台首次上网日期，不代表论文的发表时间）

页码：1230-1235