基于禁忌搜索算法求解定位-运输路线安排问题
首发时间:2008-04-25
摘要:定位—运输路线安排问题(location routing problems, LRP)是集成化物流系统分销网络设计和管理决策中的难题,也是任何一个大型物流配送企业必须要面对的问题。由于LRP的NP—HARD属性,其求解方法目前大多局限在将定位—配给问题(location allocation problems, LAP)的输出作为车辆路线安排问题(vehicle routing problems, VRP)的输入而求解。然而,在LAP最优的前提下求出的VRP的最优并不一定就是LRP的最优解,从而导致这样的处理方式不可避免的会陷入局部最优解的状态。本文针对多站点定位—运输路线安排问题(multi-depot location routing problems, MDLRP)数学模型,用Lingo软件对小规模测试数据情形进行了验证,然后采用禁忌搜索法(TS)分别求解LAP和对应的每一个设施的VRP,并将VRP的结果作为LAP的输入,再将LAP解及其邻域解作为VRP输入不断反复循环求解MDLRP,并在此基础上对较大规模测试数据进行了仿真运算。结果表明采用禁忌搜索方法求解一定规模的MDLRP快速有效。
关键词: 定位—运输路线安排问题 定位—配给问题 车辆路线问题 禁忌搜索
For information in English, please click here
Solving Location Routing Problems with Taboo Search
Abstract:Location routing problem is one of the hard problems in distribution network designing and logistic management, which has been used solving every logistics distribution corporations. As a NP-hard problem, most of the algorithms for LRP at present confine to use the output of location allocation problems as the input of vehicle routing problems. However, on the condition of the best output of LAP the best output of VRP would be not the best solve of LRP, which absolutely leads to the situation that this solving manner would be limited into the best local solution. The paper uses Lingo software to validate LRP of test data in miniature, then using taboo search (TS) to solve LAP and each hub’s VRP, let the output of VRP as the input of LAP, and then let the solution and neighbor solution of LAP as the input of VRP repeat this process continuous to solve MDLRP, based on which large scale test data has been formulated. The result indicates that using TS solving MDLRP with certain scale data is speediness and effective.
Keywords: location routing problems, location allocation problems, vehicle routing problems, taboo search.
基金:
论文图表:
引用
No.2087522668012091****
同行评议
共计0人参与
勘误表
基于禁忌搜索算法求解定位-运输路线安排问题
评论
全部评论0/1000