随着电子商务的不断发展,人们的购物方式将逐渐由传统的实体店消费转移到网络消费。网上购物的增多也必然会带动物流行业的快速发展。由于我国人口基数比较大,网络消费者比较多,所以众多的采购物品需要配送。这种趋势给我国物流行业的发展提供了机会,但是与此同时又给物流行业带来一项艰巨的挑战。配送车辆路径规划和货物装箱检验两个问题的结合更贴近现实物流运输情况,所以这个问题也吸引了越来越多的国内外学者的研究。如何能够在满足货物装箱约束的前提下降低配送车辆的运输成本,将是未来一直研究和关注的目标。本文将对配送车辆路径规划和货物装箱检验两个问题进行研究。本文中将整个算法分为两个模块:第一模块为配送车辆路径规划算法,在路径规划中,本文中采用改进的蚁群禁忌搜索混合算法并结合了节约里程算法来求解。并且在原有蚁群算法的基础上又引进了父蚂蚁和子蚂蚁的概念:用父蚂蚁来表示算法迭代次数,子蚂蚁来表示配送车辆数目。在父蚂蚁搜索路径的过程中,本文根据车辆的载重来选择是否需要启动一辆配送车。利用禁忌搜索算法中的禁忌思想来对路径中每个节点进行访问,再利用邻域搜索和节约里程算法对路径进行优化。第二模块是对规划好的路径进行装箱检验。在装箱检验过程中,采用了前人的关键点和极大空间的概念并且对极大空间进行及时更新。同时采用了使齐平值趋于最大化的货物装箱算法、使物品接触面积趋于最大化的装载算法、支撑底面约束等多种启发式算法来进行货物装箱。在算法有效性的验证方面,本文从研究此问题的网站中获得一组测试数据,并且针对这组数据进行了多次迭代实验,最后又与禁忌搜索算法相比较。实验结果表明了该混合算法的有效性。