Combinatorial Heuristics for Inventory Routing Problems
针对有限时间内的确定性库存路径问题，提出基于奖励收集斯坦纳树的快速启发式算法，在有容量和无容量两种情况下均能快速找到接近最优的解，大幅缩短计算时间。
We consider the deterministic inventory routing problem over a discrete finite time horizon. Given clients on a metric, each with daily demands that must be delivered from a depot and holding costs over the planning horizon, an optimal solution selects a set of daily tours through a subset of clients to deliver all demands before they are due and minimizes the total holding and tour routing costs over the horizon. In the capacitated case, a limited number of vehicles are available, where each vehicle makes at most one trip per day. Each trip from the depot is allowed to carry a limited amount of supply to deliver. We develop fast heuristics for both cases by solving a family of prize-collecting Steiner tree instances. Computational experiments show our heuristics can find near-optimal solutions for both cases and substantially reduce the runtime compared with a pure mixed integer programming formulation approach.