TSP是一个复杂的组合问题,包括了CTSP(Classical traveling salesman problem,经典旅行商问题)和ATSP(Asymmetric Traveling Salesman Problem,非对称旅行商问题)。TSP是VRP中每辆车配送完所有门店后的一个闭合回路。在某种意义上,VRP包含了多个TSP,从而求解VRP需要求解多次TSP。随着求解VRP中TSP次数的不断地递增,求解时间也会呈爆炸性增长。因此,如何确定一种耗时短、稳定性高的求解VRP中TSP的算法,是物流配送领域内一个亟待解决的问题。本文主要对物流配送VRP中TSP的算法选择进行了深入研究,具体研究内容包括:(1)阐述了VRP问题与TSP问题的相关理论、研究现状及常用的求解方法。同时,利用排列组合和容斥原理计算车型组合数、门店组合数及路径排列数。(2)CTSP是TSP问题中最基本也最重要的问题,根据不同的实际情况,以它为基础扩展出了各类TSP。因此,本文从TSPLIB标准数据库中选出100个点以内的实例,分别采用角平分线插入算法、其他插入算法和遗传算法进行CTSP实验。实验结果表明求解规模小时,角平分线插入算法的运行效率和解的精度都更优越,随着求解规模增大,遗传算法无论在时间上还是精度上都比其他算法更具有优势。(3)在物流配送领域内,由于各门店之间距离的不对称性,使得确定车辆的配送路线是属于求解ATSP问题。因此,本文从TSPLIB标准数据库中选出部分ATSP实例,分别采用角平分线插入算法、最远插入算法和遗传算法进行ATSP实验。实验结果表明与其他算法相比,角平分线插入算法能够在较短的时间内使计算结果更理想。(4)本文以“步步高”商业物流管理项目为例,采用项目中实际配送数据,分别运用遗传算法、最远插入算法和角平分线插入算法进行VRP实验。实验结果表明角平分线插入算法比遗传算法和最远插入算法具有更明显的优势,能够减少算法运行时间并且具有良好的稳定性。对于VRP问题而言,在寻找最优解的过程中,需要多次计算VRP中的TSP,反复对比计算结果,所以计算结果需要有较好的稳定性。此外,VRP中计算的TSP是ATSP,并且车辆由于装载量的限制,使其配送的门店数量较少,即属于求解小规模ATSP。针对以上的VRP特性,本文选择了角平分线插入算法来求解VRP中的TSP,能够有效的提高计算效率,且具有稳定性。