随着我国物流行业进入“降本增效”发展新阶段,企业对于物流成本控制的重视程度与日俱增。为降低物流成本,烟草工业企业采用“外包物流+自主决策”的物流模式,此模式的核心特征在于采用阶梯运价计费、存在订单拆分需求和单车最大运输客户数限制,且配送车辆异质、有限。其中,阶梯运价为分段函数,现有文献对此类问题的研究较少,研究阶梯运价下异构车队车辆路径问题兼具理论和现实意义。本文以烟草工业企业成品烟干线物流为背景,分别研究订单不可拆分的阶梯运价异构车队车辆路径问题SC-HFFVRPTW和订单可拆分的阶梯运价异构车队车辆路径问题SC-HFFVRPTWSD。针对SC-HFFVRPTW,以最小化总成本为目标,建立了混合整数规划模型,基于问题特征分析提出并证明了两条关键定理,根据定理提出了启发式算法（SCH-Ⅰ）,在此基础上设计了改进的分支定价算法（IBAP）和变邻域搜索算法（VNS-Ⅰ）。在用于精确求解的改进分支定价算法中,设计了弧分支和车辆分支两类分支策略,提出了对子问题求得解最大化利用和子问题求解算法顺序调用两项加速措施。针对大规模问题求解的变邻域搜索算法（VNS-Ⅰ）中,根据阶梯运价特点提出了包括客户序列和车辆序列编码的五个邻域结构。针对SC-HFFVRPTWSD,同样以最小化总成本为目标建立了混合整数规划模型,在两条关键定理的基础上提出了订单拆分规则,并据此设计了规则拆分的启发式算法（SCH-Ⅱ）和包含六个邻域的变邻域搜索算法（VNS-Ⅱ）。为验证模型和算法的效果,本文分别以理论算例和实际案例对两类问题进行计算实验。实验结果表明,三类算法均能有效求解Solomon案例集的拓展理论算例,对于HBZY工业有限公司的实际案例也具有显著的成效,可为企业节约9%-15%的物流成本。三类算法求解SC-HFFVRPTW时,IBAP算法在中小规模和部分大规模案例中均能获得最优解,且算法的两项加速措施和弧分支策略效果显著。相比之下SCH-Ⅰ和VNS-Ⅰ在求解质量上虽不及IBAP,但时间优势明显,且在大规模问题中VNS-Ⅰ比SCH-Ⅰ更有优势。在求解SC-HFFVRPTWSD时,VNS-Ⅱ求解质量明显高于SCH-Ⅱ,但SCH-Ⅱ却具有时间优势。