一种求解货物配送问题的改进算法

包得海，管会生

（1．甘肃民族师范学院计算机与科学系，中国合作 747000;2．兰州大学信息科学与工程学院，中国兰州 730000）

一种求解货物配送问题的改进算法

包得海1，管会生2*

（1．甘肃民族师范学院计算机与科学系，中国合作 747000;2．兰州大学信息科学与工程学院，中国兰州 730000）

针对货物配送问题，建立问题的数学模型，提出一种基于禁忌搜索的蚁群算法．并结合超市配送问题，对算法进行测试，测试结果表明，该算法具有收敛速度快、不易陷入局部最优、求解精度高的特点，能够有效地解决超市配送问题．

超市配送问题;蚁群算法;车辆路径问题;禁忌搜索;局部搜索

传统的货物配送问题是在假定先送货后取货的情况下建立的数学模型，这与现时代的实际问题并不相符．本文以超市配送问题为例，如有些超市同时具有送货及取货的需求，又如，从一些超市取出的货物可以配送到另一些超市中．本研究针对传统的超市配送问题加以修改，允许先取货后送货，并把每个超市都设为具有送货、取货或者二者兼有，并允许货物被重复利用．

由于超市配送问题属于车辆运输问题，所以超市配送问题属于NP-hard问题［1］，当配送的超市点很多时，若仍使用传统的数学模型求解，其求解时间将呈指数级别增长．因此，本文构建新的超市配送问题的数学模型，并提出一种以蚁群算法为基础并加入禁忌搜法思想的改进蚁群算法．

在过去国内外学者相关研究中Clark-Wright［2］提出节省法研究……