由于不同类型的货物化学、物理特性不同,不同货物类型存在无法装同一辆车的情况,该类物流配送车辆路径问题称之为货物类型约束车辆路径问题（heterogeneous fleet vehicle routing problem with commodity type constraints,HVRP-CTC）。HVRP-CTC属于多重组合NP-Hard问题,对于区域加盟店物流配送,商店类型多样且货物类型繁杂,即约束变量多约束关系复杂,它比通常的时间窗约束、装载量约束以及时间和装载量同时约束等车辆路径问题求解难度大,目前尚未查阅到有关研究文献,研究货物类型约束车辆路径问题具有理论意义和实际应用价值。论文主要的工作如下:1、根据货物是否可装于同一辆车上,把区域待配送货物类型划分为相容货物类型集合和不相容货物类型集合,分析货物类型集合元素之间的关系,提出了最大不相容集合描述货物类型装车的约束关系,并设计了求解最大不相容集合和相容货物类型集合的算法,根据货物类型的约束关系,把区域内的客户划分为独有客户、必经客户、可去可不去客户,分析各类客户配送特征及其主要算法的时间复杂度,为设计HVRP-CTC方法提供理论依据。2、根据区域客户待配送货物类型及其约束关系,提出了基于相容货物类型集合的构造启发式车辆路径规划方法,该方法的基本思想:在求解组合问题方面,先确定区域所需车辆组合、其次为同一车辆配送的客户组合、后为货物组合;在求解精度方面,先求取粗略解、后调整获得精确解;在客户派车次序方面,先处理含有强约束货物类型的客户、后弱约束货物类型客户。该方法主要由以下自主设计的算法组成:（1）货物类型约束下的区域多车型的车辆分配算法;（2）基于梭形扫描方法的不同约束类型的货物装载算法;（3）货物类型约束下的车辆超载处理算法;（4）考虑区域均衡的公共相容货物调整算法。3、利用Augerat的CVRP位置信息结合实际物流公司货物数据,进行了基于相容货物类型集合的车辆路径规划方法（CCTS-VRPA）与搜索禁忌算法（TS）对比实验,实验结果表明:CCTS-VRPA方法的求解精度略低于TS方法,其方法用时比TS方法有明显的优势,并且随着货物类型约束增加,CCTS-VRPA方法的精度变化不明显,其时间优势越来越突出。CCTS-VRPA方法是一种有效的求解货物类型约束车辆路径问题的方法。