求双目标配装方案的多项式近似算法

The Polynomial Algorithms for the Allocation Problem with Two Aims

在零担货物装车前，为充分利用车辆的载重能力及车箱的装载容积，要制定配装计划．配装问题是背包和装箱的混合问题，属NP困难问题．本文给出了一般的配装问题的数学模型，根据铁路运输特点并应用组合优化理论对序贯装车和同时装车问题分别设计了Ak算法和FirstFit算法，并对算法进行了算法复杂度分析和实例计算分析．实例计算表明，该算法运算速度快，计算结果好，目前已在实际应用中发挥了较大的作用．

In order to make full use of the carriage capacity and volum, the plan of allocation should be made before the bulk freight is loaded. The problem of allocation is a muxture problem of packing and loading,which belongs to the NP -hard problem. The general mathematical model of the problem on loading is given in this paper .According to the charactaristic of the railway transportation,Ak algorithm and First Fit algorithm are designed respcetively for loading orderly and simultaneously by using the theory of combination and optimization. The algorithms are made analysis of complexity and real example calculation. Calculaton exampes show that the algorithms are rapid in speed and excellent in result. At present, it has taken of great effect in practice.