摘要
为解决实际配送运输中的车辆路径问题(Vehicle Routing Problem,VRP),通过改进传统的数学模型,解除每个客户需求只能由1辆车配送的约束,建立改进的可拆分车辆路径问题(Split Delivery VRP,SDVRP)数学模型,并利用禁忌搜索算法(Taboo Search Algorithm,TSA)进行求解.在TSA的设计中,根据SDVRP模型的特点对初始解、邻域搜索和解的评价等进行特殊处理.算例表明,该模型不仅可以解决VRP模型中不允许配送点需求量超出装载量的限制,而且通过相应配送点需求量的拆分和重新组合,可节省车辆数目、缩短路线长度、提高车辆装载率.
To solve the Vehicle Routing Problem （VRP） in distribution and delivery, the mathematical model is improved to release the constraint that only one vehicle can be used to meet the delivery requirement for one customer, the mathematical model of Split Delivery VRP（SDVRP） is built and Taboo Search Algorithm （TSA） is used to solve the model. According to the characteristics of the SDVRP model, TSA is designed by special treatments on initial solution, neighborhood search, and solution evaluation and so on. The examples indicate that the model can not only solve the constraint of not allowing requirements out of vehicle capacity in VRP model, but also save vehicle number, shorten routing distance and raise vehicle loading rate by the split and re-combination on the requirements.
出处
《计算机辅助工程》
2010年第1期78-83,共6页
Computer Aided Engineering
基金
国家自然科学基金(70771065)
上海市浦江人才计划科研项目(07PJ14052)
关键词
需求可拆分车辆路径问题
禁忌搜索算法
邻域搜索
split delivery vehicle routing problem
taboo search algorithm
neighborhood search
