Heuristic Procedures for Practical‐Sized Uncapacitated Location‐Capacitated Routing Problems*
针对同时决定设施位置和多站车辆路径的选址-路径问题，提出一种近似方法，先利用路径长度估计器生成和改进选址/分配方案，再设计最小成本路径，计算表明该方法在车辆容量不太受限时能高效求解实用规模问题。
ABSTRACT Facility location and vehicle routing are two important logistical problems closely interrelated in many real‐world applications where locating facilities and determining the associated multi‐stop vehicle routes are required simultaneously. Previous research has found that using the classical facility location models on these location‐routing problems (LRPs) may lead to suboptimal solutions. We propose an approximate approach for the LRPs, which first generates and improves feasible location/allocation schemes with the associated multi‐stop routing costs approximated using some route length estimators. We then design the minimum‐cost routes based on the location/allocation results. We review two estimators that can provide accurate approximations to the multi‐stop route distances; define the uncapacitated location‐capacitated routing problem; and evaluate several heuristic procedures for approximately solving the problem. Computational results show that when vehicle capacities are not too restrictive, the sequential procedures that incorporate the two robust route length estimators can produce good solutions to practical‐sized problems with a reasonable amount of computational efforts.