基于节约遗传算法的电子商务配送中心选址

唐棣华，卫 欣

(1. 杭州电子科技大学，浙江 杭州 310018；2. 南京林业大学，江苏 南京 210037)

1 引言

信息通信技术和网络技术的飞速发展，在一定程度上加快了经济全球化和一体化的步伐。产品生命周期不断缩短，客户需求的个性化、多样化日益明显，企业间的竞争日趋激烈，现阶段传统的商业模式很难应对不断变化的市场需求。因此，企业的经营模式必须迅速适应这些变化。

电子商务是在这种形势下出现的一种新的商业模式。大量跨国公司的出现和全球采购模式的日益普及对电子商务的商业模式和服务效率提出了更高的要求。物流服务作为实现电子商务最终目标的重要组成部分，其质量和效率对电子商务企业的经营绩效有着重要的影响。研究有效的物流配送方法对于解决电子商务问题具有重要意义。

郝彩霞等人[1]提出一种基于电动物流车辆的充换电设施在充换电模式下的选址问题。分别建立了无充电行为的路径规划和车辆调度模型以及以最小化电费、车辆固定行程费用、机会费用和惩罚费用之和为目标的充换电设施选址模型。对收费交换模式下设施的选址决策和配送总成本进行了比较分析。提高收费速度或选择交换模式可以降低配送成本。胡利利等人[2]提出一种基于多冷链物流中心选址。根据冷链物流中心的时效性特点，对节点需求和辐射半径进行约束，以需求为距离权重，将其纳入目标函数，建立相应的选址分配数学模型。借助生物免疫系统的多样性和自我调节能力，利用部分匹配原理计算抗体之间的亲和力，设计了自适应惩罚机制、免疫变异和精英保留策略，以保持种群的多样性和优良性精英阶层。并与文献对比，证明了该算法的有效性。孟燕萍等人[3]提出一种基于灾害下应急物资的动态选址问题，通过衡量被害人候补材料的二次运输成本和心理惩罚成本，建立多目标混合整数规划模型，以雅安地震为背景，将灾后72小时划分为6个时段，每个时段应根据不同的道路恢复情况而有所不同，并确定了各时段应急物资的选址方案，验证了模型的实用性。

但是上述三种方法选址时间较长、耗费较高。提出一种基于节约遗传算法的电子商务配送中心选址方法。

2 节约遗传算法

电子商务的快速发展为企业和消费者搭建了良好的平台。现代物流配送模式可以实现配送模式的自动化、社会化、合理化和集约化，使货物畅通无阻，充分发挥货物的效用。它不仅可以减少库存，降低物流成本，加快资金周转，刺激社会需求，而且可以提高全社会的经济效益。然而，目前电子商务与物流配送体系的衔接不够、物流管理体系不完善等问题制约了电子商务环境下物流配送的进一步发展。

通过节约遗传算法能够获取到全局最优性能，并且在许多领域得到了广泛的应用。具体算法如下所示：

1)所需信息。根据订单分析，可以得到客户的配送需求，并设计程序计算出每个客户的配送需求两个客户之间的线性距离(用二维数组表示)以及每个客户点到配送中心的距离。

2)初始化填充。需要对N个客户提供排序，可以表示为0，1，…(N-1)。排序之后，生成一系列，共有Q个组。

3)适应度函数。可以根据适应度的大小来选择个体。在分布问题中，最短路径D是响应适应度函数的标准。D越大，适应度函数越小；D越小，适应度函数越大。

4)选择。根据适应度函数，选择每一代的新个体。在自然进化过程中，亲本通过选择和竞争对亲本的适应性进行排序。根据设定的种群规模，根据一定的选择概率，将一些优秀个体保留为下一代，这样的选择过程更容易保留优秀基因，使具有较大生存能力的个体按照自然规律进入下一代的概率更大化选择。

5)交叉路口[4]。按交叉概率随机选择当代人群中需要交叉的个体，分成X和Y两个组，将此作为亲本进一步实施交叉，会生成X′与Y′两个后代。本文针对遗传算法不能遍历所有用户的缺点实施了优化，其表达式下：

X=123|4567

Y=765|4321

(1)

经过交叉处理后获得子代的公式为

X′=123|4567

Y′=765|4321

(2)

该方法在很大程度上提高了算法的效率，可以遍历所有用户，并能尽可能地保留好的基因片段。

6)变异。选择随人口变化概率而变化的个体进行合理转换得到新的个体。在规划过程中，需要注意避免全局最优解收敛过快的现象，也就是保持种群的多样性。

7)在随机控制参数进行筛选过程中，需要充分考虑参数范围，以保证节约遗传算法的高效性[5]。一般来说，控制参数的范围是N=20～200，pc=0.5～1.0，pm=0～0.05。

8)重复选择、交叉、变异三个步骤，在最大进化函数之前完成，按照相应的规格实施合理排列，得到节约遗传算法表达式为

(3)

节约遗传算法的目的是在不受任何限制情况下解决车辆运行路径问题。为解决车辆路径问题提供了一种简单可行的基本方法。

3 电子商务配送中心选址

3.1 物流配送中心模式

伴随互联网的快速发展和居民消费习惯的改变，电子商务企业得到了突飞猛进的发展。物流配送中心具有多种功能，体现在物流服务的实现上。通过产生的实践，克服空间障碍，促进商务产品完成消费者所需的交易活动，实现配送中心商品的增值。消费者对物流配送中心有着不同的需求。由于所提供的服务不同，整个供应链的功能也会有很大的不同。但作为物流配送中心，其整体使用有关联。虽然功能不同，但应具备商品周转、仓储管理、流通加工等基本功能[6]。

现代物流运输组织的主要方式是在多式联运和门到门运输的基础上形成点对点的网络化物流运输。配送中心和物流中心能否成为网络化物流运输中的节点，在很大程度上取决于配送中心是否具有完善的物流服务功能。

电子商务配送中心选址是现阶段物流发展的首要任务，具有较好的空间与前景。在对物品配送时，大量的分销被用来减少分销的频率，从而降低分销的成本。传统企业主要制造产品来获取利润，对物流配送服务方面关注较少。

在电子商务模式下，选址是否合理，会严重影响物品配送的合理化和实时性，导致企业收益较低的现象发生。许多物流配送中心选址只考虑到选址的成本，以及总收益最大化，而不是关心消费者。但实际生活中，有很多消费者喜爱网络购物，并且分散地域十分广阔，配送效果需求旺盛，对配送中心的选址影响很大。需要确定物流配送中心选址方案确定最优选址策略的规划模型[7]。

图1 物流配送中心选址策略图

3.2 物流配送中心选址模型约束条件

配送中心选址作为某一区域内所有消费者的地址集[8]，选择一定数量的地址建立配送中心，从而建立出一系列的配送区域，实现各个需求点的配送任务，使在某一区域内建立的配送系统的总配送成本最小化选择点和每个需求点。因此，在现有的客观条件下，使整个系统的物流成本最低，使客户体验较好的服务效果。

所谓可变成本，通常来说是指物流配送中心在产品配送过程中所发生的管理成本。在许多模型中，把可变成本当作线性函数，由于物流配送中心的实际成本难以与实际情况相匹配，运算出的最优方案与实际的最优状态结果相差甚远，特别是在电子商务环境下，当物流配送批量较小且多批次时，可变成本将不作为线性函数[9]。

电子商务中心选址模型充分考虑了时间约束，能够在许多方面实现最优选择，也可以优化运营商的利益。进一步将商品的需求、流通和生产在正确的时间、地点、价格和方便的方式结合起来，以消费者为中心，最大限度地保护消费者的权益[10]。物流配送是制约电子商务发展的瓶颈。在某一地区的需求点的地址，其中，由已建成的物流配送中心和客户构成的物流配送系统总成本最小，以备选地址的数量为配送中心。总成本包括模型中物流配送中心及设施建设或租赁的一次性投资、配送中心可变成本、固定管道管理成本、运输成本等多层次物流配送中心选址，从工厂到配送中心的运输包括二次运输，即从工厂到物流配送中心的运输和物流配送[11]，即tij+Tki≤fk。

因此，对于电子商务环境下物流配送中心选址的重要性，对传统的多层次物流配送中心选址模型进一步实施改进，结合节约遗传算法，提出了一种适合电子商务环境下物流配送中心选址的非线性混合模型0-1编程，cij作为配送中心i至用户j的运输单价，hki作为k厂至i配送中心的运输单价，ui作为i配送中心的货物流通单价；fi作为i配送中心的固定运营成本，tij作为i厂至j物流配送中心的运输时间，Tjk作为i物流配送中心的运输时间j到用户k，fk作为用户k对配送时间的限制，aj作为用户j的需求；bi作为配送中心i的容量，ck作为工厂k的供给，m作为备用配送中心的数量，n作为用户数量，P作为备用配送中心的最大数量，l作为工厂数量，具体约束条件表达式如下

(4)

(5)

上述公式代表配送中心能够满足用户的需求。

(6)

式(6)代表配送中心的采购数量小于配送中心的能力

(7)

式(7)作为选择的配送中心数量不大于最大数量P。

(8)

(9)

上述公式描述了，货物从工厂K运出物流配送中心I内的货物数量应不超出其生产能力。

tij+Tjk≤fk

(10)

式(10)描述了从工厂到物流配送中心的运输时间和从物流配送中心到用户的运输时间之和，应小于或等于用户对产品的配送时间限制。

Xij≥0，wki≥0

(11)

Yi∈[0，1]

(12)

其中：i=1，2，…m，j=1，2，…n，k=1，2，…l。Xij作为配送中心i至用户j的运输量，wki作为k厂至配送中心i的运输量[12]。

4 实验分析

假设在一定的时间段内，从一个区域内随机选择的多个客户，接收到配送需求订单，最大迭代次数为200次。采用节约遗传算法对每个订单实施准确分析，从而实现配送中心最优选址。每个客户从零开始用十进制数字编号，每个客户的需求是已知的。

为了检验该算法的有效性，将文献[1]方法、文献[2]方法与所提方法的结果进行了比较，具体内容如下所示。

表1 所提方法计算结果

表2 文献[1]方法计算结果

表3 文献[2]方法计算结果

从表中可以看出，当用户数为30、60以及100时，其平均最优值和最优结果均小于文献[1]方法、文献[2]方法，说明所提方法获得最优路径的效果较好。所提方法的相对误差小于文献[1]方法、文献[2]方法，说明波动结果较小，更容易快速有效地确定优化的分布路径，减少了分布距离。

从电子商务环境下物流配送中心选址评价指标体系可以看出，各指标从不同角度反映了选址方案的合理性。客户数优化过程如下所示。

图2 客户数优化过程

从图2中可知，当用户数为N=30和N=60时，三种算法在迭代过程中的配送路径长度的收敛性。其趋势呈现逐渐收敛现象。所提方法的收敛次数比文献[1]方法、文献[2]方法更少。当所提方法运行到200次时，获得的最短路径有了显著的改进。得出节约遗传算法具有较高的进化起点，易于找到最优解

当客户数不同时，程序运行时间与随机选择的客户数的关系如下所示。

图3 程序运行时间与随机选择的客户数的关系

在图3中，从实际值的连接可以看出，程序的运行时间随着客户数量的增加而增加。因此，客户数量与程序的运行时间成正比。

5 结论

针对电子商务环境下物流配送中心的选址问题，其运算过程较为复杂，为了验证本文所提方法的高效性。依据节约型遗传算法对电子商务配送路径进行优化，得到全局最优路径。获取物流配送中心的具体模式，使其满足现实需求。构建电子商务配送中心选址模型，利用目标函数计算了配送中心的可变成本和时间约束，能够减少配送时耗费的成本。其对电子商务配送中心的模式进行了合理改进，使之更加实用化，可以大大提高物流配送系统的服务水平。实验结果表明该方法具有高效性和优越性。