随着现代物流行业的崛起,企业为了降低运输成本,越来越重视对车辆路径问题（Vehicle Routing Problem,简称 VRP）的研究。弧路径问题（Arc Routing Problem,简称ARP）与VRP问题一样,同样有着重要的现实意义和研究价值。二者的不同之处在于,VRP以点为服务对象,而ARP以边为服务对象。经典的弧路径问题只有一个仓库点,但实际应用中的很多问题需要利用多个仓库点的弧路径问题建立数学模型。因此,本文研究了多仓库带容量约束弧路径问题（Multi-depot Capacitated Arc Routing Problem,简称MCARP）,将经典的弧路径问题推广到更为实际的多仓库情形。针对MCARP的不同变形问题,我们提出了近似算法和多项式算法。本文主要分为以下七个章节。第一章介绍了研究背景并对组合最优化问题进行了简单描述,还阐述了本文相关问题的最新研究进展。第二章描述了本文所涉及的符号和概念。第三章介绍了非固定终点MCARP问题,给定一仓库点集D,每辆车可从任一仓库出发,最终可返回至任意仓库,目的是找到服务了所有需求边的若干条路径,使得总路径长度最短。将非固定终点多仓库带容量约束的车辆路径问题（Multi-depot Capacitated Vehicle Routing Problem,简称MCVRP）的算法进行推广,得到了非固定终点MCARP问题的近似算法。第四章研究了固定终点MCARP问题。给定一仓库点集D,每辆车从任一仓库出发,最终返回到该仓库,目标是找到服务了所有需求边的若干条回路使得总回路长度最短。我们推广了固定终点MCVRP的算法,得到固定终点MCARP问题的近似算法。第五章讨论了多仓库乡村邮递员问题（Multi-depot Rural Postman Problem,简称MRPP）,它是MCARP问题容量无限的特例。有一仓库点集D（?）V,其中|D|=k。目标是找到k条覆盖了所有需求边的回路,使得总回路长度最短。每条回路都对应一位邮递员的路径,他们必须从不同的仓库出发且最终返回至该仓库。此外,我们还研究了以极小化最长回路为目标的MRPP的一个变形问题,称为极小-极大乡村邮递员覆盖问题,并给出了改进的近似算法。第六章介绍了定义在线图上的MCARP问题,当需求一致时,证明该问题是多项式可解的;同时,我们还讨论了线图上的MCVRP问题,并给出了近似算法。第七章对本文进行了总结,给出今后可以进一步研究和改进的方向。