基于禁忌搜索算法求解定位-运输路线安排问题概要VIP免费

基于禁忌搜索算法求解定位－运输路线安排问题林晖钢1，胡大伟1，徐丽蕊1，21长安大学汽车学院，西安（710064）2陕西工业职业技术学院工商管理系，陕西咸阳（712000）E-mail：lhgzhl@163.com摘要：定位—运输路线安排问题（locationroutingproblems,LRP）是集成化物流系统分销网络设计和管理决策中的难题，也是任何一个大型物流配送企业必须要面对的问题。由于LRP的NP—HARD属性，其求解方法目前大多局限在将定位—配给问题（locationallocationproblems,LAP）的输出作为车辆路线安排问题（vehicleroutingproblems,VRP）的输入而求解。然而，在LAP最优的前提下求出的VRP的最优并不一定就是LRP的最优解，从而导致这样的处理方式不可避免的会陷入局部最优解的状态。本文针对多站点定位—运输路线安排问题（multi-depotlocationroutingproblems,MDLRP）数学模型，用Lingo软件对小规模测试数据情形进行了验证,然后采用禁忌搜索法(TS）分别求解LAP和对应的每一个设施的VRP，并将VRP的结果作为LAP的输入，再将LAP解及其邻域解作为VRP输入不断反复循环求解MDLRP，并在此基础上对较大规模测试数据进行了仿真运算。结果表明采用禁忌搜索方法求解一定规模的MDLRP快速有效。关键词：定位—运输路线安排问题；定位—配给问题；车辆路线问题；禁忌搜索1.引言设施定位、车辆路线各自作为单独的问题，国内外已有较多学者进行了研究，其理论也已比较完善，这些研究为物流管理的优化决策奠定了坚实的基础。国外一批学者对LRP进行了一系列的研究[1]。LRP的概念认为：在设施（制造厂、库存点或分销中心）相对于客户的位置、货物的配给、货物运输的车辆路线安排之间存在相互依赖的关系，根据这种关系来进行综合优化与管理；相比单一的物流系统优化问题，LRP更加贴近目前物流系统复杂的实际特征，对进一步优化整个物流系统，降低系统成本具有一定的理论价值和现实意义。而当前大部分学者对LRP的研究都局限在将LAP的输出作为VRP的输入而进行求解，这种方法得出的LRP解往往并不是最优的。基于这样一个现实情况，本文将LAP和VRP综合统筹考虑，得出了相应的MDLRP优化解，首先用C++编程软件与Lingo软件对小规模数据集（8点数据集）进行了计算及其对比验证本文算法计算结果的精确性，然后对较大规模数据（25点、50点、100点数据集）用本文算法求出了相应的优化解，证明了本文算法对求解MDLRP问题的有效性和准确性。2.MDLRP参数定义及其数学模型与验算本文研究的LRP模型基于如下假设：①客户数量、位置及需求已知；②候选设施位置及容量已知；③各客户需求均能得到满足且每个客户只由一辆车服务；④每辆车在完成全部运输任务后回到出发点；⑤各线路的总需求小于或等于车辆的容量；⑥车辆类型给定。2.1参数定义ijkx在路线k上，如果点i在j之前值为1，否则为0；iy如果建立i设施则值为1，否则为0；ijz如果客户j由设施i来服务则值为1，否则为0；R配送设施点潜在位置的集合；J所有客户点的集合；V所有车辆集合；N代表客户的数量；ijCi，j两点之间的距离（作为i，j两点间的运输费用）；SRJ=U所有客户点和潜在设施点的集合；rG设施r建设和运行的固定成本；kF使用车辆k的固定成本；rV设施r的最大容量；jq客户j的需求量；kQ车辆k的容量；2.2多站点定位－配给问题的数学模型Min∑∑∑∑∑∑∑∈∈∈∈∈∈∈++RiJjijkVkkijkSiSjVkijrRrrxFxCyG.st：∑∑∈∈=VkSiijkx,1Jj∈，（1）,kSiJjijkjQxq≤∑∑∈∈Vk∈，（2）RryVzqrrJjrjj∈≤-∑∈,0，（3）∑∑∈∈=-SiSjpjkipkxx,0Vk∈，,Sp∈ij≠（4）∑∑∈∈≤RrJjrjkx,1Vk∈，（5）(1rlkljkrjlSxxz∈+≤+∑，Rr∈，Jj∈，Vk∈（6）10或=ijkx，,,,,jiVkSji≠∈∈（7）10或=ry，,Rr∈（8）10或=ijz，,Ri∈Jj∈（9）在上述这个模型中，目标函数为总成本（包括设施建设和运作成本、运输成本以及车辆投入及其使用成本）最小。约束（1）保证每一个客户只由一个运输车辆服务；约束（2）为运输车辆容量约束条件；约束（3）为仓库的容量限制条件；约束（4）保证路线连续；约束（5）保证每一个运输工具的路线只能从一个设施驶出；约束（6）保证客户只能由选中的设施提供服务；约束（7）...