具有容量约束弧路径问题（Capacitated Arc Routing Problem, CARP）产生于交通运输服务系统，因其广泛应用于城市街道清扫、垃圾回收、输电线路检查、物流配送等现实生活中，而得到了广泛的研究。本文主要研究CARP的一种新的扩展类型―具有容量约束的开放式弧路径问题（OpenCARP, OCARP），该类问题与CARP的主要区别在于车辆在服务完所有客户后无需返回车场。该类问题主要产生于第三方物流配送服务业，而且随着电子商务的日渐繁荣，第三方物流配送企业间的竞争也更加激烈，提升物流配送服务效率，较好地满足大城市及超大城市的密集型配送需求，降低物流配送成本，对第三方物流企业的存亡至关重要。本文详细描述了OCARP的图论模型及数学模型，分析了其现有的求解算法及求解效果，设计了两种算法用于求解OCARP，即禁忌搜索算法与改进的变邻域搜索算法。禁忌搜索算法基于局部搜索算法，通过接受劣解来避免算法陷入局部最优，同时使用禁忌表来避免循环搜索，最后配合破特赦则来允许算法向更好的区域搜索，该策略使得算法同时具有广度搜索与深度搜索的良好性能。变邻域搜索其基本思想是在局部搜索的过程中系统地改变当前解的邻域结构，以降低陷入局部最优的风险，经过多次迭代，最终达到收敛的目的。两种算法在81个基准数据集上的测试结果表明了它的有效性，TS算法在23个算例上达到了最优下界，并优化了51个算例的最优上界；IVNS算法在28个算例上达到了最优下界，并优化了55个算例的最优上界。