末端配送选址及路线优化案例研究

邓纳纳 孙晓燕 陈慧敏

(1.广西财经学院，广西 南宁530003，2.北京经济管理职业学院 ，北京 100102)

0 引言

互联网电商平台的发展，深刻影响了人们的购物消费行为和传统零售业的发展[1]。随着中国直播电商模式的兴起，以及健康生活理念的提倡，越来越多的生鲜农产品销售加入了电商行业，据数据显示，2019年中国生鲜市场交易规模约2.04万亿元，生鲜电商行业交易额为1 620亿元[2]，且数据还在迅猛增长，这就对物流行业带来了巨大的考验，因生鲜农产品存在时效性和易腐性的特性，电商物流除了加快冷链物流发展外，需要关注物流末端“最后一公里”配送。目前在电商物流环节中，末端“最后一公里配送” 存在配送成本过高且实效性差的问题，一定程度制约电商的收益和最终用户的用户体验。

本文以广西财经学院相思湖校区M直播平台校园末端配送为例，提出采用精确重心法，构建配送成本最小的数学模型，选出配送中心，然后模拟商旅问题(Salesman Traveling Problem，STP)，利用免疫算法的特点对其配送路径进行优化，以此求解合理具体合理的校园配送路线，为电商物流末端配送提供参考。

1 末端配送选址

1.1 选址模型构建

广西财经学院相思湖校区M直播平台在相思湖校区有A、B、C、D、E、F、G共7个主要目标市场，如图1所示。假定M平台配送中心的经纬度坐标为(x0，y0)，7个配送点A、B、C、D、E、F、G的经纬度坐标可以分别表示为(x1，y1)(x2，y2)(x3，y3)(x4，y4)(x5，y5)(x6，y6)(x7，y7)。

图1 配送中心与各配送点的实际位置分布

利用精确重心选址方法确定配送中心的地址。精确重心法模型的具体构建如下：

di=R×arccos[sin(p0)sin(pi)+cos(p0)

cos(pi)cos(w0-wi)]

(1)

其中，w0，p0，wi，pi为配送中心和各配送点的经纬度角度转化对应的弧度，转化的具体表达式为w0=x0π/180，p0=y0π/180，wi=xiπ/180，pi=yiπ/180，总的费用表达式为：

cos(pi)cos(w0-wi)]

(2)

第二步：根据总费用最小原则，通过极值求解，解出配送中心(x0,y0)的表达式为：

(3)

简化后得配送中心O的坐标点为：

(4)

式(4)被称为重心公式。

第三步：算法验证迭代，具体计算步骤为：

(1)初始时，假设配送中心坐标为(x0，y0)。根据公式(2)计算出A、B、C、D、F、G这7个配送点与配送中心(x0，y0)的总费用S0。

(3)计算A、B、C、D、E、F、G 7个配送点与(x(1)，y(1))相应的总费用S1。

(4)检验。将迭代后更新的配送中心与前一初始配送中心的总费用进行对比，即比较S1和S0，如果S1< S0，则返回步骤(2)继续计算配送中心的改善地点(x(2)，y(2))，如此反复计算下去，直到第k次迭代后得到Sk+1≥ Sk，此时得最优解(x(k)，y(k))，即最优的配送中心的位置坐标是(x(k)，y(k))。

1.2 选址模型求解

1.2.1 模型假设

(1)假设供应商到配送中心点费用忽略不计；

(2)假设配送中心配送的货物为单一品，以件量为计算，重量忽略不计；

(3)假设配送中心的货量，能够满足其服务范围内所有需求点；

(4)假设采用电车骑行配送，配送过程中配送人员的平均行驶速度保持一致；

(5)将需求点内学生公寓楼每个宿舍作为一个需求衡量基点；

(6)假设单位配送成本为1元/千米；

(7)配送点简化为一个点，便于算出具体信息。

1.2.2 数据来源

(1)根据百度地图可以测得每个配送点的经纬度坐标，并通过wi=xiπ/180、pi=yiπ/180计算其相应弧度。

(2)需求量ni依据M平台2020年11月销售量统计，通过整理得到求解模型所需的数据如表1所示。

表1 M平台在广西财经学院各配送点的实际数据

1.2.3 计算

(w*k-1-wi)]。

令k=1，得7个配送点A、B、C、D、E、F、G到配送中心的初始距离di,0(i=1,2,…,7)分别为268，186，166，134，15，216，275。

如图1所示，根据计算结果，将配送中心(图1中的五角星)和各配送点(图2中方块)坐标的实际经纬度坐标画到坐标系中，可以得到配送点与配送中心的分布情况，如图2所示。图中7个配送点对应的序号分别为：2→A，3→B，4→C，5→D，6→E，7→F，8→G以及配送中心1→O。

2 末端配送路径优化

2.1 路径优化模型

末端配送网点路线的优化问题可以转化成商旅问题(Salesman Traveling Problem，STP)进行求解。当已知各配送点的实际坐标位置时，假设配送人员从配送中心出发，向配送点进行配送，最后返回配送中心。为了节省时间，配送路线不重复，即每个配送点只配送一次，不回头配送。这样末端配送网点路线的优化问题可以归结为：求M平台配送中心O向7个需求点A、B、C、D、E、F、G送货时，如何安排配送路线，让整个配送路线距离最短。距离矩阵D=(dij)9×9，其中dij表示i，j两点的距离，i,j=1，2，…，8，9(1)，这里D为实对称矩阵。则问题是求一个从点1出发，走遍所有中间所有点，到达9(回到起点1)的一个最短路径。

2.2 免疫优化算法原理

免疫算法是模拟生物免疫系统抗原抗体而生成的一种新型智能计算方法[3]。免疫算法保留了生物免疫系统超强学习力、记忆力和自适应的优点，同时也弥补了遗传算法容易过度早熟收敛的不足。免疫系统由抗原、记忆细胞、抗体等组成。其运算原理是模拟了生物免疫系统中，如细胞通过分裂产生大量的抗体来抵抗各种抗原，借助自身优异的学习能力、识别能力、记忆能力以及具有保持群体多样性的特点，能够有效的辨别外界的有害信息，从而保证整个系统的安全稳定。免疫算法是一种对多峰值函数进行多峰值检索，经过多次迭代，寻找全局最优的算法[4]。优化算法[5]能够有效克服寻求最优解的过程中出现的问题，从而获得全局最优解。

2.3 算法流程图

算法的流程图如图2所示。

图2 免疫优化算法基本流程

2.4 算法步骤

免疫算法的具体实现步骤如下：

第一步：初始化免疫个体维数为配送点个数N(将配送中心O点也当成一个配送点)，将免疫种群个体数参数设计为NP=200，最大免疫代数为G=10(一般G取100～500，但考虑本研究问题所选取的坐标数据比较小)。为了便于观察，最大免疫代数相应取小，克隆个数为Ncl=10，导入数据，计算任意两配送点的距离矩阵。

第二步：在免疫算法中随机产生初始种群，然后计算相应个体的亲和度(即路径距离)，按亲和度进行升序排列。

第三步：在取亲和度前，对NP/2个个体进行克隆操作，并对每个源个体产生的克隆个体进行随机交换两个配送点的变异操作；然后计算亲和度情况，进行克隆抑制操作是为了保留亲和度最高的个体，从中得到新的免疫种群。

第四步：随机生成NP/2个个体的新种群，并计算个体亲和度；此时免疫种群和随机种群合并，按亲和度进行排序，下一步免疫迭代。

第五步：判断是否满足终止条件。如若满足，结束整个搜索过程，输出优化值；如若不满足，则继续进行迭代优化。

2.5 计算结果

初始种群的一个随机数，其具体路径为：1—>7—>3—>6—>2—>5—>8—>4—>1，轨迹如图3所示。计算得到初始配送路径总距离为2.2603千米。

图3 初始随机路线

采用免疫优化算法进行优化后，得到最短配送路径距离为1.1616千米，对应的最优路线是：1—>8—>7—>6—>5—>4—>2—>3—>1，其的路线轨迹如图4所示。亲和度进化曲线如图5所示。

图4 优化后的路径轨迹图

图5 亲和度进化曲线

从亲和度进化曲线可以看出，优化前后路径距离已经得到明显改进，且迭代速度非常快，在第2代以后路径距离已经维持不变了，可以认为此时达到了最优解，最优路径距离为1.1616千米，比初始路径距离减少了48.6%。由此可知免疫算法可以优化末端配送路径，为现实问题的应用进行客观的指导。

3 结语

物流配送作为电子商务线上销售后的最终环节，它面向着消费者，配送服务质量影响着消费者的购物体验，间接影响着消费者对网络购物的体验[6]。提高末端配送水平既可以提升客户满意度，也可以降低企业运营成本。数据表明，广西财经学院相思湖校区M直播平台，在校园末端配送中有效进行末端配送选址和优化配送路径后，能有效节省配送成本和提高配送效率，为电商物流末端配送研究提供借鉴参考。