多分配枢纽站最大覆盖选址问题

The Multi-allocation Hub Maximal Covering Problem

讨论了多分配枢纽站最大覆盖选址问题(MAHMCP),即要求每一条被服务的O-D流能够在规定的时间、费用或距离内从起点任意经过一个或两个枢纽站后到达终点,如何选择个枢纽站以使被服务的O-D流达到最大。由于是强NP困难问题,一般难以在满意时间内求解30个节点规模的问题。通过建立MAHMCP的改进模型,设计了求解该问题的禁忌搜索算法,经过基于澳大利亚邮政(AP)枢纽中心选址数据包计算实验,发现禁忌搜索算法在求解MAHMCP时具有很好的计算效果,并且相比分枝定界算法能够节约大量的计算时间。经计算,这一算法可以用来求解82个节点规模的中国航空枢纽港选址问题。

We consider the multiple allocation hub maximal covering problem （MAHMCP）. considering a serviced O-D flow was required to reach the destination optionally passing through one or two hubs in a limited time, cost or distance, what is the optimal way to locate hubs to maximize the serviced flows. The paper first proposes a new model for the MAHMCP. Then, provides tabu search to solve MAHMCP. At last, we present a computational instance on AP data set and a special case on hub airports location of Chinese aerial freight flows between 82 cities in 2002. By the computational experiment, we conclude that TS woks well for MAHMCP both in terms of quality of solutions and of required computation times.