定位2运输路线安排问题的两阶段启发式算法

重点研究了集成化物流中一类特殊的定位一运输路线安排问题(LRP)的解决方法．LRP问题包括设施定位和运输路线优化两方面决策，属于NP-hard难题．由于问题的复杂性，提出基于假设前提的LRP模型及其两阶段启发式求解算法．该方法分两步实现：首先，采用基于最小包络聚类分析的启发式方法确定被选择的潜在设施及由每一个选中的设施所要提供服务的客户群；其次，运用带有控制开关的遗传算法求解每一确定客户类中的优化运输路线．提出利用两阶段启发式算法求解LRP问题，此方法实现容易、运算简单，一定程度上避免了遗传算法中的“局部最优现象”．仿真实验证明了该算法求解单目标LRP的有效性和准确性．

A two-phase heuristic approach to the location routing problem

A special LRP including many candidate facilities and customers with different demands in integrated logistics is studied. A model of LRP is given based on some hypotheses. A two-phase heuristic approach for solving this LRP is proposed. First, the candidate facilities and their customers are determined on basis of minimum wrap-net method by using heuristic technique. Second, genetic algorithm (GA) is used to search the optimal routes. This two-phase heuristic approach integrates facility location and routing problem, which architecture makes it possible to search the solution space easily and effectively without overpass computation. A computer simulation shows that this two-phase heuristic algorithm achieves significant improvement over a recent LRP heuristic.