需求可拆分车辆路径问题的禁忌搜索算法
Taboo search algorithm of split delivery vehicle routing problem作者机构:上海交通大学机械与动力工程学院上海200240
出 版 物:《计算机辅助工程》 (Computer Aided Engineering)
年 卷 期:2010年第19卷第1期
页 面:78-83页
学科分类:08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:国家自然科学基金(70771065) 上海市浦江人才计划科研项目(07PJ14052)
主 题:需求可拆分车辆路径问题 禁忌搜索算法 邻域搜索
摘 要:为解决实际配送运输中的车辆路径问题(Vehicle Routing Problem,VRP),通过改进传统的数学模型,解除每个客户需求只能由1辆车配送的约束,建立改进的可拆分车辆路径问题(Split Delivery VRP,SDVRP)数学模型,并利用禁忌搜索算法(Taboo Search Algorithm,TSA)进行求解.在TSA的设计中,根据SDVRP模型的特点对初始解、邻域搜索和解的评价等进行特殊处理.算例表明,该模型不仅可以解决VRP模型中不允许配送点需求量超出装载量的限制,而且通过相应配送点需求量的拆分和重新组合,可节省车辆数目、缩短路线长度、提高车辆装载率.