我们的社会丰富多彩,包罗万象,生活在大数据时代,车辆运输连接着我们生活的方方面面。车辆路由问题是一个在物流运输和资源分配等方面都有着非常广泛的应用的组合优化问题,是旅行商问题的进一步扩展,主要研究的问题是如何对车辆运输的路径进行优化以及如何合理的调配车辆。随着工业设计以及科学研究领域的各类复杂优化问题的不断深入,使用传统的优化算法在解决复杂优化问题时遇到了很多的困难,在这种背景下,群体智能优化算法的产生为解决复杂优化问题提供了新的思路。在众多群体智能算法中,遗传算法因其强大的全局搜索功能、鲁棒性高、适应性强、计算过程简单、便于与其他算法结合等特征,已广泛应用于工程优化、系统识别、自动控制等领域,是解决NP难问题的更有效的全局方法。本文使用遗传算法,旨在从理论和实验两方面多角度的分析和验证染色体编码方案的设计对于遗传算法解决多旅行商问题的至关重要的地位,综合全局搜索和局部搜索的平衡机制解决问题。基于相对解空间概念,首先分析三种染色体编码方案对应的解空间在极限意义下的相对大小关系,接下来分析旅行商数与城市数在不同情形下解空间的近似相对大小关系。本文对搜索空间定量分析的理论结果对工程问题的求解可以提供科学的指导意义。从而将其应用于目前较为流行的车辆路由优化问题中,创造性地提出了一种基于两段式编码方案的遗传算法。同时,本文在研究过程中重点关注遗传算法中染色体编码方式对解空间大小的影响,以及这种影响对群体寻求最优位置的指导。提出了一种基于两段式编码的遗传算法,采用先路由后集群的方法改进初始解的构造过程,并使用C-W-saving算法优化车辆的路线,优化选择操作中的选择策略,优化解的选择方法,并调整插入算子,对所选父代染色体进行特定的交叉变异操作,使用最大重叠交叉对子代进行交叉操作。最后在小数据集上进行仿真测试算法的收敛速度,并在大数据集上,通过与原始算法作对比来表明该算法的有效性。