Lagrangian Relaxation Methods for Solving the Minimum Fleet Size Multiple Traveling Salesman Problem with Time Windows
研究在时间窗约束下，从共同车场派出同质车队访问所有节点一次所需的最少车辆数，提出基于增广拉格朗日方法的最优求解算法，并对比了两种松弛策略的效果。
We consider the problem of finding the minimum number of vehicles required to visit once a set of nodes subject to time window constraints, for a homogeneous fleet of vehicles located at a common depot. This problem can be formulated as a network flow problem with additional time constraints. The paper presents an optimal solution approach using the augmented Lagrangian method. Two Lagrangian relaxations are studied. In the first one, the time constraints are relaxed producing network subproblems which are easy to solve, but the bound obtained is weak. In the second relaxation, constraints requiring that each node be visited are relaxed producing shortest path subproblems with time window constraints and integrality conditions. The bound produced is always excellent. Numerical results for several actual school busing problems with up to 223 nodes are discussed. Comparisons with a set partitioning formulation solved by column generation are given.