基于改进遗传算法的企业物流配送网络的构建

林　森，洪　伟

（1.福建农林大学 交通与土木工程学院，福建 福州 35002；2.福建农林大学 林学院，福建 福州 350002）

基于改进遗传算法的企业物流配送网络的构建

林森1，洪伟2

（1.福建农林大学 交通与土木工程学院，福建 福州 35002；2.福建农林大学 林学院，福建 福州 350002）

摘要：以居家通企业的订单数据和配送网络为研究对象，采用改进的遗传算法对其合作店铺的服务网络计算，获得最短配送路线与实际配送路线、标准遗传算法计算的路线进行对比并通过GIS地图标注，同时研究当企业规模扩大，合作店铺需配送的酒店数量增加后在改进遗传算法计算下的配送路径。结果表明：实际配送路线为5.33 km，标准遗传算法路线为5.04 km，改进遗传算法路线结果在GIS地图上表现最优为4.33 km，并且当增加5个配送节点后，配送路线长为8.5 km。

关键词：居家通企业；改进遗传算法；Mat1ab

物流配送是商品流通中至关重要的环节，是物流企业的运作主体，掌握市场的起伏变动，直接接触客户最满意的需求，从而实现整个物流网络价值，其效率是判断企业效率高低的重要指标[1]。了解客户最终需求，企业通过构建一个较为齐全的物流配送网络以便更好的为客户提供服务。以物流节点为网络运营货物的集散载体，运输路径为网络运营货物的连接桥梁，二者紧密合作，将货物从供应商到客户之间形成一条科学合理的动态运输链[2]。根据我国2014年统计的5.6万亿元的运输费用，其中我国总物流费用约占52.9%，而发达国家对物流流程进行优化后，可节约5%～20%的总运输成本[3]。因此，是否合理安排配送路径会影响到企业的整体效益和客户满意度，企业也急需时效性强、成本低、服务质量高且能快速规划路线的物流配送平台。

1　“居家通”商旅服务平台

“居家通”商旅服务平台是专门为商旅人士打造的服务性平台。它由庞大商旅消费群体和酒店周边能够提供高产品、快配送、优服务的商家组成。入住酒店的客户可从酒店提供的客户端在酒店下单，形成委托配送任务，业务员进行接单汇总处理，通过配送网络分析客户的相关信息并且通知周围的店铺，由店铺通过本身所具有的货物种类进行进货储存、分拣、装载货物和路线的选择等安排配送，在客户需求在规定时间内将货物送达到地点后，由最终客户进行确认签收。

通过调查2014年3—10月居家通企业的各个店铺订单统计总量（见图1），总订单量有406份，而与居家通企业合作店铺约97家，合作商旅酒店约394家。目前虽然客户通过居家通平台下单情况还未达到较大规模，但每月均呈现上升趋势，该企业正在快速成长阶段。居家通企业做为首家商旅服务企业仍旧拥有不足之处。

图1　2014年居家通企业每月订单数量

1.1配送的产品多品种、小批量

由于店铺提供的商品多种多样，而且顾客是来自不同地区的商旅人士，所以对商品需求是多样的，而且能带产品重量是有限，这就是“消费多样化、需求多样化”，这导致订单较为分散，每个酒店旅客需要多样化服务，向不同的店铺订购产品，这也对配送提出较高要求。

1.2配送时间不定

根据订单分析可知订单的时间不均衡且数量少，每家店铺平均每天不到一份的订单，为了能提供优服务将产品即时的送到顾客手上，店铺以“客户第一”为宗旨，再加上顾客下单时间不确定，就导致店铺配送的时间不确定。因此，店铺只能根据经验提供配送服务。

1.3未规划配送路径

调研过程中发现在产品配送过程中，部分配送人员对配送路径没有规划，甚至部分配送人员根据订单顺序先到一家宾馆后，然后再查找去下一家宾馆路径。这不但增加配送成本，还会导致物流配送路径变长，加重交通负担，造成倒流运输、迂同运输、单程运输和空驶等现象[4]。

物流配送是实现居家通企业规模效益的关键因素，居家通企业应认识到自身配送尚未形成规模，抓住我国物流企业发展趋势的机遇，解决物流配送问题，提高配送效率。因此本文从居家通及与其合作店铺的配送现状出发，对配送网络的需求进行研究，构建物流配送网络模型结合改进遗传算法及实际路线状况，寻求到了多个配送宾馆之间的最短配送路径，这将有效提高提升居家通企业的综合竞争力。

2　基于改进遗传算法构建居家通企业物流配送路线模型

2.1构建目标函数

该企业的配送路线模型思路为：在每个店铺接到订单后，从店铺中选取车辆装上商品，将商品送到n个不同的酒店中，再进行酒店内各个消费者的配送，最终回到出发点，因此该配送路线为巡回路径，采用Grefenstette等提出巡回路径的整数编码方法[5-6]。

假设路线中的全部酒店构成列表K，店铺与每位酒店分别记为1-n并按其顺序排列放到表K中，所以该路径的配送顺序是H=（h0，h1，h2，…hn）并规定每次配送完一个酒店后就在列表K中把该点除去，用第i （i=1，2，…，n）个所配送酒店，hi在所有未配送酒店列表K-{h0，h1，h2，…hi-1}对应的位置序列号bi（1≤bi≤ni+1）就可表示为具体配送给哪个酒店，由此直到将K中的需求点全部送完，bi按照配送的先后顺序构成新的列表：B=（b1，b2，…，bn），就是可表示一条巡回配送路线，即为遗传算法中一个个的基因。按此规则侦查所有的路径长度，寻求最短的配送路线其目标函数为：

其中：b0为店铺（配送中心）；bi（i=1，2，…，n）为第i个酒店；d（0，1）为店铺到第1位酒店之间的距离；d（n，0）为第n个酒店到店铺的距离；d（i，j）（i= 1，2，…，n）为i到j之间的距离，且d（i，j）=d（j，i）。

2.2改进遗传算法模型架构

（1）初始群体的生成。经过编码将数据转换成染色体的基因链形式，并对种群规模进行确定，设进化的代数计数器h=0，最大代数为H，然后随机产生M个不同的染色体构成算法的初始解P（0），并把其当成开始迭代的初始点。

（2）评价适应度函数值。从P（h）群体中进行全局搜索，并从中找出适应度最高或接近最优的个体。

（3）选择。从现有的种群中选出对自然环境适应能力强大的个体，将其作为父代进一步繁衍后代。为了能够收敛全局得到最优解的个体，选取最佳个体保留与赌轮选择的方法相互结合，得到下一代个体。

Step 1：采用改良圈的近似算法，求得一个初始种群P（h）。

Step 2：从初始化群体中P（h）找出适应度最大的个体，保证父代种群中最优良的特性遗传给子代，用b表示。

Step 3：假如种群中的个体q经过赌轮选择的方法求出的选择概率为P（q）：

Step 4：设Z（0）=0，Z（q）=Z（1）+Z（2）+…+Z（q），（q=1，2，…，n）

通过以上操作后，在[0，1)区间内生成n-1个均匀分布的随机数列Ai（i=1，2，…，n-1），每一个随机序列与群体的各个个体相对应，并对n-1个个体按顺序进行选择检测，假如Z（q-1）≤Ai≤Zq，则q被选中当成下一个个体。

（4）改进型的单点交叉操作。经选择操作产生新的种群之后，并利用生物学中的有性繁殖的基因重组原理，选择改进型的单点交叉操作方法，通过染色体配对后产生基因交换，将优良基因遗传到子代个体。

Step 1：以“门当户对”为原则，对父代个体进行配对并按目标函数值进行排序，目标函数值最小的与小的配对，反之，大的目标函数值与大的进行配对。

Step 2：应用混沌序列确定交叉点的位置。

Step 3：对确定的交叉项基因进行交叉操作。

通过改进遗传算法，可避免和削弱在算法交叉强度大时而产生的寻优抖振问题，提高算法的收敛精度。

（5）改进的变异操作。个体的少数基因随机发生改变其结构或位置，变动的几率较小，一般在0.001到0.1之间。从初始种群P（h）随着遗传算子的不断进化迭代后中得到新的种群P（h+1），不断进行繁衍优化。遗传算法经过变异实现种群多样性的一种手段，在遗传操作过程中保留最优良的个体，个体上各个基因位进行变异，使个体的排列顺序发生较大的变化，而配送路径上的配送点顺序对应种群的各个个体也会产生很大的变化，所以其相应的基因值也不同[7]。按照给定的变异率，对选定的变异个体，随机选取三个整数，1

（6）终止条件。若h≤H,则h=h+1，转到步骤（2）；若h＞H则已经达到最大的种群迭代数的终止原则，将此作为最优解，即最短配送路径。

3　居家通店铺配送路线仿真

选取居家通企业其中一个合作店铺Pizza芝根芝底为例，该店铺以订单达到29元为起送价格，以此店为配送中心向周边酒店实施配送，该店到各个酒店的实际距离（见表1），假设该店铺只有一辆车和一名配送员工并且能装下一次巡回路线送的所有订单。表2为居家通企业合作店铺Pizza芝根芝底(59)、南公快捷酒店(37)、如家快捷酒店(74)、纸业大酒店(82)、丽嘉宾馆(211)、小希尔顿源利明珠店(212)、榕盛商务宾馆(213)、速8酒店(215)、汉庭酒店(216)。

表1　配送中心、各配送点之间的实际距离　单位：m

3.1店铺实际配送路径

经调查店铺一般以10分钟为时间段，结合实际交通拥堵情况和客户下单时间对各配送点进行配送。配送路径基本固定为1-3-2-9-5-7-6-4-8-10，即Pizza芝根芝底(59)-如家快捷酒店(74)-南公快捷酒店(37)-汉庭酒店 (216)-丽嘉宾馆 (211)-榕盛商务宾馆(213)-小希尔顿源利明珠店(212)-纸业大酒店(82)-速8酒店(215)-PIZZA芝根芝底(59)的巡回路径，总路径长度为5.330 km。

3.2遗传算法模拟居家通店铺配送路径

利用遗传算法，各参数设置为：种群规模为50，迭代次数为100，交叉率为1，变异率为0.02。经Mat1ab分别计算标准遗传算法和改进的遗传算法的最短配送路径(见表2)并将配送结果用GIS地图标注(见图2)以便将来GPS导航系统的开发。

表2　实际配送路线与算法配送路线对比

图2　遗传算法(左)和改进遗传算法(右)求得的配送路径（按1:200比例）

从表2和图2可知改进遗传算法求得的路线长度最短为4.33 km并且在GIS地图上可以明显看出其回程的路线更短则有效减少运输返程的空载，更合理的安排配送路径，缩短配送时间。

3.3企业规模增加，修改配送路径

随着居家通企业的快速发展，不断有新的酒店采用该平台时，即周围再增加新银河酒店公寓(45)、福州华亿宾馆(262)、速8酒店（工业路宝龙店）(276)、福州盐业快捷酒店(303)、福州汇雄商务宾馆(307)五个酒店时，如表3为增加的配送点的位置坐标。

表3　新增配送点的坐标

结合表1和表3，当店铺在表1订单8个配送点的基础上再新添5个配送点时，用Mat1ab编程求出配送的最短路径为8.50 km，配送路径为1-8-10-12-14-11-6-4-7-5-13-9-2-3-1的巡回路径（见图8）。

图3　配送路径地图（按1:200比例）

由图3可知，当店铺配送范围内出现新的配送点时，原有的单巡回路线则会变长，造成空载时间长、运输距离长、配送时间增加等现象，影响订单配送时效承诺。此时，店铺在配送时需根据订单情况，适当增加配送人员和运输车辆，然后对配送路线进行重新规划，实现多批次、小批量的配送，尽最大限度满足客户对时效的需求。

3.4结果分析

（1）完善配送网络，联合居家通企业共同配送。

由企业现有状况来看，在这个区域范围内，当每个店铺订单数量较少时，可通过该区域范围内的店铺进行合作或交给居家通企业统一配送，先由每个店铺构成一条取货路线收集各个店铺的订单产品，再规划各个酒店配送的一条巡回路线。

未来随着企业发展，合作的酒店和店铺不断增加时，会产生大量的订单，店铺自营物流较难完成居家通企业的“15或30分钟送达”送货时间承诺，影响配送服务质量。这时，居家通企业应当建立配送团队和配送中心帮助店铺完成订单配送服务，实现双方的共赢，提高配送服务质量。

（2）对订单定时段进行统计分析，增加目标函数的约束条件

企业在以客户为考虑起点的同时也要对店铺和酒店的利益方面考虑，在实际情况中并不能单方面考虑客户需求，损失店铺及旅店的利益。所以居家通在接到客户订单的时候，在一定的时间段内对订单进行统计分析，并将信息传递给给店铺统计可同时配送的订单，不至于影响配送效率。同时对于模型中目标函数可加入车辆配送限制载重和时效要求的约束条件，以寻找最适合的配送路径。

4　结论

本文以居家通企业为例展开分析，针对该企业的路径问题，构建居家通企业配送网络的路线，建立相应的改进遗传算法模型，避免种群在追求最优解时产生寻优抖振问题，加速收敛速度。最后，结合居家通合作企业的实际配送状况进行模拟分析，实现快速配送，达到供需的双赢。但对于构建企业物流配送网络应该考虑到的因素还不够完全，尤其未来当企业规模扩大时，本文构建模型的约束条件还不能满足于企业的发展，将来的研究方向应当考虑到批量配送点、时间效能、车辆配载、绩效评价等配送因素，模型将更符合企业的实际运作，提高企业的物流配送效率，有效降低物流成本，提高企业的综合竞争力。

参考文献:

[1]许婧.电子商务环境下物流配送体系研究:以特能中国公司为例[J].经营管理者,2011(19):296-296.

[2]张旭凤.第三方物流企业配送网络演化规律及路径优化研究[D].北京:北京工业大学,2012.

[3]刘洋.城市路网中的集送货一体化车辆路径问题研究[D].重庆:重庆交通大学,2013.

[4]徐军辉.基于核心竞争力的绿色物流管理研究:以CW公司为例[J].商业经济,2011(23):37-39.

[5]叶欢,经亚枝.Grefenstette编码法的MATLAB实现[J].中国测试技术,2004(2):58-60.

[6]孙慧平,李健,郭伟刚.改进遗传算法求解旅行商问题[J].数学的实践与认识,2009(4):127-133.

[7]王会云,肖建禄,刘登泰,等.基于遗传算法的配送路线优化[J].后勤工程学院学报,2008(3):91-94.

（责任编辑：叶丽娜）

中图分类号：F253.9

文献标识码：A

文章编号：1674-2109(2015)12-0084-05

收稿日期：2015-10-26

作者简介：林森（1986-），男，汉族，博士研究生，助教，主要从事现代物流管理研究。

通讯作者：洪伟（1947-），男，汉族，博士生导师，教授，主要从事数理统计、系统工程研究。

Construction on Lmprovement-based Genetic Algorithm of Enterprise Logistics Distribution Network

LIN Sen1，HONG Wei2

(1.Schoo1 of Transportation，Fujian Agricu1ture and Forestry University,Fuzhou，Fujian 350002; 2.Forestry Co11ege，Fujian Agricu1ture and Forestry University,Fuzhou，Fujian 350002)

Abstract:To the order data of JOJTOM enterprise and distribution network as the research object,using the improved genetic a1gorithm for the cooperation the store service network ca1cu1ation,get the shortest de1ivery route and the actua1 distribution route,the standard genetic a1gorithm is app1ied to ca1cu1ate the route of the contrast and through GIS maps.When enterprise sca1e,the cooperation after the shops need to increase in the number and distribution of hote1 under the improved genetic a1gorithm is the distribution of path.Resu1ts show that the actua1 distribution route is 5.33 km,the standard genetic a1gorithm(ga)route is 5.04 km,improved genetic a1gorithm performance optima1 route resu1ts in GIS map of 4.33 km,and after five distribution nodes are added,the distribution of path is 8.5 km.

Key words：JOJTOM enterprises;improved genetic a1gorithm;Mat1ab