基于扫描法的连锁超市生鲜配送路径优化

浙江万里学院 王钰祥中国社科院财经战略研究院 孙琪



基于扫描法的连锁超市生鲜配送路径优化

浙江万里学院 王钰祥
中国社科院财经战略研究院 孙琪

摘 要：本文根据生鲜品自身的特点，以及连锁超市在生鲜品配送中所面临的管理问题，建立VRP数学模型，通过扫描算法对原有的配送路径进行优化，得出最优的配送方案，为确保生鲜品质量安全、提高企业配送效率、满足客户高质量需求提供理论借鉴。

关键词：连锁超市 生鲜配送 扫描法 路径优化

近年来，外国零售业在中国不断发展，一方面为中国零售业的发展战略提供了借鉴，另一方面加剧了本行业的竞争。随着人们生活水平的提高，消费理念早已从过去的“吃得饱”转变为如今的“吃得好”，生鲜行业逐渐成为众多连锁超市的主要盈利点。而生鲜品具有易腐、易损耗、生命周期短等特点。据资料显示，一个细菌在常温下15小时后可以滋生10亿个细菌；而在10℃以下，15小时后只有1/4的细菌产生。因此，要保证生鲜品新鲜地抵达客户手中，就必须尽可能地做到全程冷链，从采购预冷到冷藏车运输，再到最后的制冷货架，在配送模式方面要做到多品种，少批量，高频次。综上，生鲜配送线路是否合理直接影响到配送的时间、效率和效益，扫描法就是针对多目标的回路运输问题，优化后的配送路径不仅可以降低企业配送成本，提高配送效率，还能提升消费者的消费体验，使得企业多盈利。

1　连锁超市生鲜品配送面临的问题

由于连锁超市自身的地理位置，以及生鲜品自身易腐易烂的特点，连锁超市的生鲜配送具有和其他消费品配送不一样的特点，衍生出以下三个问题。

1.1公共资源方面

众所周知，生鲜品的配送主要是汽车运输，依靠的是道路资源，因此也受其限制和影响。首先，在我国某些特大城市，配送车辆都受到了严格的交通管制，影响调度安排；其次，与发达国家不同，我国的大型连锁超市大部分处于城市人口密集地带，交通状况脆弱，车辆行驶速度变化大。因此，配送车辆的调度、作业在很大程度上受到交通管制和交通状况的影响，这也影响着配送的准时性和配送成本。

1.2企业资源方面

一方面，国内连锁超市的发展都是从单个小门店开始，然后扩大到广领域、多门店，而配送车辆也面临着旧有车辆和新型设备同时使用的状况。另一方面，由于连锁超市的门店大小各异，需求不同，产品种类多样，也需要多车型的配送。因此，企业经常面临多种类型运输设备同时使用的情况。

1.3客户需求方面

由于生鲜品讲究一个“鲜”字，绝大部分消费者都希望自己能够买到当天或者前一天的货物，大部分人会选择早市，但对于上班族来说只能去晚市，结果就只能买回一些剩余物品。如何保证所有的顾客都能买到新鲜的产品，这就要求生鲜配送要做到多品种、小批量、高频率。最好可以做到前一天晚上下单，次日早上配送，早晨过后上午下单，当天下午配送。这就对配送速度和配送成本产生了压力。

2　连锁超市生鲜配送的VRP模型描述

分析上述问题发现，连锁超市生鲜配送的问题主要来源于公共资源、企业资源、客户个性化需求三个方面，而这三个方面的阻力都可以通过配送车辆的调度和路径优化来削弱。

2.1多回路运输问题

多回路运输是现实配送中经常遇到的问题，特别是对于有诸多服务对象的大公司。针对此类配送问题，关键是对车辆进行正确调度。由此VRP（车辆路径问题）模型随之而生，成为解决多回路问题的一个重要方法。VRP模型在配送中的应用描述为：从物流配送中心同时向多个需求地（门店、客户）配送货物，每一个需求地的地理位置一定，需求量稳定，通过对运输车辆合理调度和配送路径优化，使得配送里程尽量短、时间尽量少、成本费用尽量低、车辆次数尽量少等。同时需要满足以下几个约束条件：（1）单条配送路线上需求地的总需求量小于等于每台配送车辆的核准载重量； （2）单条配送路线的总长度小于等于每台配送车辆的最大行驶距离； （3）每个需求地的需求必须满足并且只能安排一台车配送； （4）每台配送车辆从离开配送中心开始到完成任务回到配送中心形成一个回路。

2.2生鲜配送与VRP模型

连锁超市的生鲜配送是在配送中心允许的配送半径内，根据各超市门店提供的订货信息，对生鲜产品进行采购、预冷、分拣包装、冷藏运输等作业。其目的是尽可能地加快生鲜配送速度，保证生鲜品质量，满足客户的需求期望从而提高企业利润。

生鲜品的配送是一个典型的多回路运输问题。生鲜品自身具有生命周期短、易腐烂、运输损耗严重等特点，同时又是很常见的大众消费品，其安全关乎人们的身体健康，因此，生鲜品的配送有以下几点要求：配送环节少、速度快；配送设备齐全，从采购到入架全程冷链，保证安全；避免回收物流的出现，减少损耗，降低综合成本。综上，合理的配送至关重要，选择合理化的配送路线、优化配送顺序、降低配送成本具有重大的意义。VRP模型与其他的运输模型不同之处在于：客户群体大，单路径无法满足客户的配送需求，同时它可以解决配送中主体选择和配送顺序的问题。此外VRP模型就是为了实现配送里程最短、准时性最高、劳动消耗最低、运力掌握最合理等目标，使用VRP模型来解决生鲜配送问题十分合理。

3　基于扫描法的连锁超市生鲜品配送路径设计

3.1扫描算法的描述

扫描算法是求解VRP算法的启发式算法之一。其原理是：首先建立坐标系，以配送中心O为极坐标系的原点，以原点和任意客户点连线定义为角度O，再给客户群定义坐标。其次，从最小角度的客户开始，建立一个小组，按逆时针的方向依次把剩余的客户添加至小组中来，直到客户的需求量超过了运输车辆的载重量。建立新的小组，继续依次进行下去，直到所有的客户都被分完为止。最后，把各小组按照TSP（旅行商问题）模型的方法进行优化，选择一条合理的线路。

3.2配送路径优化设计案例

已知某连锁超市以A点为基点，分别向B点、C点、D点、E点、F点、G点、H点、I点、J点9个地区门店配送生鲜，该公司标配的冷藏车载重量为6t，并有足够多的车辆。设各个点之间的距离为C=｛Cij｜i，j=0，1，2…9｝，各点的需求量为Ni（i=1，2，…9），每台冷藏车的行车里程为Li≤600km，以A为中心，门店点分别为B，C，…J，对应1，2，…9。根据某公司物流配送资料显示，各个门店的生鲜需求量和配送距离及坐标值如表1所示。

表1　门店需求量及角坐标值

各个门店之间的距离及与配送中心之间的距离如表2所示。

表2　配送中心以及各个门店之间的距离

采用扫描算法对该公司配送路径进行优化，步骤如下。

（1）以冷链配送中心A点为扫描中心点，逆时针为扫描方向，取C点为扫描初始点，其与A点的连线为零角度，建立极坐标系。

（2）从角度为零的AC连线开始逆时针扫描，C的需求量load1=1.5t，继续扫描，下一个即将被划入小组的是A点，load1=1.5+2.5=4t＜6t，继续扫描。下一个即将被划入小组的是D点，如果D点被划入小组，load1=1.5+2.5+3=7t＞6t，将超出冷藏车载重量，根据扫描法分组规则需要新建一个小组，这样第一个小组有AB两点。重复以上的分组过程，可以得出第二小组有DGH三点，load2=6t，第三小组有EF两点，load3=4t，第四小组有IJ两点，load4=3.5t，中止扫描。

（3）小组内的线路优化过程。这样就利用扫描法将9个点分解成了四组单回路运输问题，可以通过TSP方法求解，然而，对于数量较多的TSP问题，通常无法求得最优解，只能通过启发式算法获得较为接近的最优解。TSP的解决方法通常有枚举法、最近点法和最近插入法。枚举法的列举次数一般为（n-1）！次（n表示门店的个数），工程量大一般不用，最近点法虽然计算快捷方便但是精确度极低，一般只用作计算初始解。下面使用最近插入法对四组单回路问题求解。

由上述分析可知第一组、第三组、第四组都只有两个门店，由对称性可得以上三组可直接构成三个回路。

对第二组进行优化，比较表2中从A点出发的所有路径大小：

Min｛C0i｜i∈N，1≤i≤9，且i≠0｝=C17=83.5

这样，有节点A，H构成了一个子回路，T=｛A，H，A｝，然后考虑剩下的节点D，G到A，H两点的最近距离：

Min｛C0i，C7i｜i∈N，1≤i≤9，且i≠0，7｝=C73=20

这样节点A，H，D就构成了一个新子回路，T=｛A，H，D，A｝，然后只剩下一个节点G有三个位置可以插入，现在分析将其插入哪个区间合适，θ表示加入G点多走里程：

插入到（A，D）之间，θ=C06+C63-C03=84+85-85=84；

插入到（A，H）之间，θ=C06+C67-C07=84+30-83.5=30.5；

插入到（D，H）之间，θ=C76+C63-C73=30+85-20=95。

比较上述三种情况的增量，插入到（A，H）之间增量最小，所以将G点插入（A，H）之间，结果为｛A，G，H，D，A｝。最终求得配送路径如图1所示。

图1　最终配送路径

4　结语

我国的超市生鲜配送业务最早出现在20世纪80年代的外资企业中。21世纪以来，略显规范化的本土生鲜配送行业开始发展，特别是现如今冷链技术发展方兴未艾，为生鲜配送提供了技术和设备支持。但是，在运行模式和物流管理方面，还与西方以及日本等发达国家存在较大差距，合理化的车辆调度和路径优化设计具有重要的现实意义。解决车辆路径问题的方法有很多，本文针对生鲜配送面临的问题以及车辆路径问题的特点，对车辆配送路径和生鲜配送进行了交叉研究，使用扫描法对连锁超市生鲜配送路径进行优化设计，高效率完成连锁超市生鲜配送服务，达到了节约物流成本的目的。

参考文献

［1］ 何炳华.物流系统规划设计与软件应用［M］.北京：清华大学出版社，2012.

［2］ 吕俊杰，孙双双.基于鲜活农产品冷链物流配送的车辆路径优化研究［J］.广东农业科学，2013（9）.

［3］ 孔阳，陈珊.层次分析法在生鲜物流配送路径选择中的应用［J］.中国市场，2015（33）.

孙琪（1974-），男，浙江宁波人，中国社会科学院财经战略

研究院博士后，浙江万里学院商学院副教授，主要从事经济管理等方面的研究。

中图分类号：F252

文献标识码：A

文章编号：2096-0298（2016）06（c）-001-02

作者简介：王钰祥（1991-），男，河南洛阳人，浙江万里学院在读硕士，主要从事全球采购与供应链管理方面的研究；