需求可拆分车辆路径问题的禁忌搜索算法

作     者：孟凡超 陆志强 孙小明 MENG Fanchao;LU Zhiqiang;SUN Xiaoming

作者机构：上海交通大学机械与动力工程学院上海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模型中不允许配送点需求量超出装载量的限制,而且通过相应配送点需求量的拆分和重新组合,可节省车辆数目、缩短路线长度、提高车辆装载率.