摘要：在对配送线路优化的研究中，国内外学者从理论层面提出了大量算法：贪婪算法、遗传算法、神经网络等，但是由于这些算法需要大量的真实数据和先进的系统支持，而在配送实际过程中，管理人员和司机主要凭借经验判断和个人喜好来进行线路选择。因此，这些算法应用起来在配送实际运作过程中很难快速地适应经常变化的外部因素。针对实际应用，本文提出了一种基于Sierpinski曲线（希尔平斯基曲线）的配送线路优化算法，利用Sierpinski曲线的构造原理可以方面有效地确定配送到每个需求点的先后顺序，然后根据现实地交通状况相对调整进而快速寻找一条满足约束条件的优化路径，避免了实际中司机寻找最优路径的盲目性，降低企业的配送成本。此外，文中还应用Sierpinski曲线算法对武汉中百集团在武汉市青山区的配送线路进行了优化。

关键词：配送线路优化；Sierpinski曲线；空间填充曲线；中百集团

1 引言

近年来，我国国民经济一直持续稳定增长，居民消费需求发生了深刻变化，这种经济环境形成了连锁超市发展的温床，使得我国的连锁超市迅速而且蓬勃的发展起来。连锁超市是否能够成功经营，在很大程度上取决于配送成本的控制及与之相适应的配送模式。电子商务环境下，消费者对生活资料需求居多，而生活资料的品种规格繁多，每次需求量小，用户多，故要求多品种、小批量、多批次的配送，以实现自身零库存，增强市场应变能力。配送模式的柔性化，带来配送管理人员及司机对配送线路优化的困难。在实际应用中，配送线路选择往往取决于管理人员或司机的经验判断和直觉经验。但是对于超市连锁规模日益的扩大及消费者需求的不断提升，这种粗放的方式导致配送成本的难以控制及服务水平的下降。

正因如此，King等人研究表明，现实配送中距离的6%和时间的12%被浪费了^[1]。一般的配送线路优化问题的描述为：如何选择最优配送线路，使得投入的成本最低，又能满足客户的需求。实际上，由于客户数目的巨大，这一问题的可行解数目非常巨大，甚至不可能用类似于枚举方法在能够接受的时间范围内得到最优解或者较优解，并且客观约束条件复杂而繁多，因此该问题已经成为一个公认的物流难题。

2配送线路优化算法的选择

国外对配送线路优化问题作了大量而深入的研究，将此问题归结为或称之为Vehicle Routing Problems（VRP）和Traveling salesman Problem（旅行商问题，TSP）。该问题一般定义为：对一系列装货点和（或）卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程短、费用最少、时间尽量少、使用车辆数尽量少等）^[2]。如，1959年荷兰计算机科学家迪杰斯特拉（Dijkstra）提出的目前离散数学应用广泛的最短路径算法（Dijkstra's Shortest Path First Algorithm），是最适合网络拓扑中两结点间最短路径搜索的算法之一。它是一个适用于所有弧的权为非负的最短路算法，也是目前公认的求解最短路问题的最经典的算法。1975年 由John Holland首先提出遗传算法（Genetic Algorithm，GA）的概念，它是一种有效的解决最优化问题的方法。自此逐渐发展成为一种通过模拟自然进化过程解决最优化问题的计算模型。20世纪90年代初期，意大利学者Dorigo Macro等人通过模拟自然界中蚂蚁集体寻径的行为而提出了蚁群算法（Ant Colony Algorithm，ACA），这是一种基于种群的启发式仿生进化算法。该算法最早成功应用于解决著名的旅行商问题（TSP）。表1是目前已经开发并应用实践的配送线路优化及调度系统^[3]。