摘  要：提出解决单回路物流配送问题的一个新启发式算法——吞圈法，通过实验证明，该方法的求解性能稳定，运算次数少，且求解质量较高，优于经典的最近邻点法和最近插入法，也优于大部分智能化算法，是求解单回路物流配送问题的有效方法。

关键词：物流；旅行商问题；吞圈法；启发式算法

0 引言

交通运输是社会正常运行的重要基础，其主要内容是进行人和货物的运载和输送，这也是物流系统规划所关心的问题，它涉及了运输方式选择和运输线路优化两方面的内容。单回路物流配送问题即单一车辆的路径安排问题，是线路优化模型理论中最为基础的问题之一，该问题与旅行商问题（Traveling Salesman Problem,TSP）相同，目的是选择一条合适的路径使之遍历所有节点，因此数学模型也完全相同，适用于TSP问题的求解方法同样也适用于此问题的求解。这是一个典型的NP-Hard（Non-deterministic Polynomial）问题，对于大规模的路径优化问题无法获得最优解，只有通过启发式算法获得近优解。目前已发表的文献中关于求解TSP问题的启发式算法很多，主要有最近邻点、最近合并、最远插入、最近插入、贪婪插入、极小代数法、模拟退火、遗传算法、禁忌搜索和粒子群算法^[1-12]等。综合来看，最近邻点、最近合并、最远插入、最近插入、贪婪插入和极小代数法尽管求解速度快，但其解的质量较差；近年来不断发展的智能优化方法，如模拟退火、遗传算法、禁忌搜索及粒子群算法等优化性能虽然较好，但计算量较大，且难以确定合适的算法参数。本文从分析最近邻点法和最近插入法的求解思想出发，以克服传统方法求解质量差和智能优化方法求解参数较难确定且计算量大等缺点为目标，提出了解决此类问题的新方法-吞圈法，实验表明该算法计算结果稳定且求解效果较好。