4 LRP的解决方法
国外许多学者对LRP的解决方法进行了有益的探讨，所采用的方法可以分为两种：精确算法和启发式算法。
4.1 解决LRP的精确算法
基于运筹学的优化算法，解决LRP的精确算法可以分为以下四种：
(1) 直接树状搜索[1]；
(2) 动态论文范文http://www.chuibin.com/ 规划[1][17]；
(3) 整数规划[18][19]；
(4) 非线性规划[20]。
在以上算法中，最为常用的是整数规划（包括混合整数规划）,而具体解决时效率最高的方法是分支—定界法。它可以在不很长的计算时间内解决多至80个节点的LRP，但是采用分支—定界法的LRP必须在其模型中限制设施的数量。一旦所涉及的LRP的规模扩大，精确算法就不实用了。
4.2解决LRP的启发式算法
由于LRP结合了LA问题和VRP，而后两者都是NP-Hard (Non – deterministic Polynomial hard)问题，所以，在大多数情况下，要用精确算法来解决LRP是十分困难的。例如，在一个物流系统中，有3个潜在的中心点，8个分布的客户点，3条行车路线，如果用整数规划来解决，要涉及的变量会达到333个[16]。实际上，以上的物流系统是十分小的，在实践中遇到的系统规模往往会远超过它。很多情况下要引入启发式算法。
LRP往往是十分复杂的，需要采用多级分解方法对其简化。目前解决LRP的启发式算法多采用以下四种方法或是它们的组合：
（1） 先解决定位一配给问题，然后解决运输路线安排问题[15, 21]；
（2） 先解决运输路线安排问题，然后解决定位一配给问题[22]；
（3） 费用降低/插入算法[23, 24]；
（4） 路线扩展交换算法。
很多情况下精确的优化算法仅仅是作为一种参照的基准，在研究LRP时比较各种启发式算法的优劣。而在解决实际规模问题时一般要采用启发式算法。
上一页 [1] [2] [3] [4] [5] [6] [7] 下一页