本文研究了一个新的瓶颈运输问题，它推广了经典的瓶颈运输问题。新模型叙述如下:在一个具有单一供货点s和单一收货点t的有向运输网络中，s和t外的所有点均称为转运点，现要从供货点s向收货点t运送k个单位的一批货物，目标是使得各弧上运送一定货物时所对应运输费用的最大值max{cijfij|(i,j）∈A}达到最小，这里k是一个固定的常数。对于新瓶颈运输问题，本文设计了一个时间复杂度为（O）（m2nU)的伪多项式时间最优算法解决瓶颈运输问题，这里U=max{bij|(i,j)∈A};对于该问题的一个特殊情形，即费用为整数的新瓶颈运输问题，设计出了一个时间复杂度为(O)(m2n log2(kC)）的多项式时间最优算法，这里C=max{cij|(i,j)∈A}。最后给出了相应的程序设计。