Integer-Programming Based Algorithms and Computational Performance for Terminal-Drop Zone Assignment Problems

摘要

The distribution of oil products usually occurs at two levels. In primary distribution, large quantities are transported from refineries to terminals (or depots) by bulk transportation methods (e.g. rail, ship, pipeline, or virtual exchange). In secondary distribution, smaller quantities are transported from terminals (or depots) to the customer (usually by road). Firms in the oil products sector often have a very large number of individual customers, each with an associated demand. For logistics planning purposes, the demands of customers are commonly aggregated into 'demand zones' or 'drop zones'. This reduces complexity and also improves forecast accuracy without greatly diminishing logistics performance. The assignment problem which considers which drop zone to assign to which terminal, such that a drop zone is only assigned to one terminal, is an important part of the logistics planning in the oil products sector. The terminal-drop zone assignment is a cost minimisation problem often solved using either linear programming or heuristic methods in preference over integer programming due to perceptions of high computational costs. Both commonly used methods are undesirable, the former due to the possibility of 'split-feeding' which complicates operation; whilst the latter due to non-optimal assignments. The trend of facility rationalisation within the industry has made the problem much harder to solve. As oil companies reduce the number of their terminals by factors of two or greater, the throughput capacity utilisation for terminals has grown to over 90percent. In these cases, heuristics grow increasingly poor in terms of performance, and linear programming approaches with heuristic 'split-feeding' resolution could become infeasible. In this paper, the terminal-drop zone assignment problem is solved using an integer programming formulation to avoid the undesirable aspects mentioned above. Representative data for a small problem is used to generate larger data sets in several numerical experiments. Attention is focused on the computational performance of the integer programming formulation for large problem sizes. In addition, a problem specific preprocessing procedure is considered together with its effects on performance benefits and optimality degradation. The models are solved using commercially available solvers. Problem sizes of up to 10,000 drop zones and 100 terminals are solved with a reasonable computational effort. Finally, on the basis of the results, a new algorithm is proposed for this problem.