基于遗传算法的生鲜同城配送路径优化研究

唐佩佩 冯晓威 宫英丽

（同济大学 经济与管理学院，上海 201800）

1 研究目的

在同城配送中，运输成本是总配送成本的一大部分。目前，电子商务下生鲜同城配送取得了一些成就，但同时由于受经营管理、城市配送条件、小批量、多频次、生鲜易腐等特点的制约，导致生鲜同城配送存在一些问题，影响着同城配送的进一步发展。

（1）不能满足客户时间窗的需求

客户通过网络在电子商务平台订购生鲜品，很多情况下客户都无法在配送网点长时间等待，一般是约定某一时间段内将农产品送到，但企业由于车辆调度、路况异常、同一时间段内要求配送订单较多等原因，往往无法满足客户的时间窗需要。这会造成客户的满意度问题，长此以往将会造成客户流失，影响企业的品牌形象。

（2）单位配送成本高

这种模式一般来说在一个城市只有一个配送中心，而城市的半径往往达到几十公里、上百公里，在农产品电子商务化刚刚起步的今天，由于平均每天收到的订单不多，而且配送点很可能在城市的各个角度，这就增加了车辆路程，从而提高了生鲜的配送成本，降低了企业的经济效益。

（3）生鲜农产品的食品质量问题

在农产品电子商务同城配送的过程中，配送车辆一天很可能只出车一次。在这种情况下，有些客户的需求送达时间较晚，而配送车辆出发时间较早；客户所需要的生鲜品存放在车辆的储藏箱中，有些生鲜品具有易腐、易蚀、易烂的特性，经过一天的运输，送到客户手中时，往往不是很新鲜，食品质量达不到客户的需求，影响客户的满意度。

（4）车辆平均负载率低

在安排电子商务的配送路径时，需要考虑顾客的时间窗、食品质量等问题，往往有些车辆负载率很高，另一些车辆负载率很低，是因为企业缺乏对整个运输路径的总体规划。因此，要对电子商务下生鲜品同城配送路径进行优化，得出符合企业需求的配送车辆行驶路径。

在尽量满足客户需求的前提下降低配送成本是生鲜同城配送中急需解决的问题，本研究进行同城配送路径优化，同时考虑时间窗要求，旨在降低生鲜同城配送成本，以使电子商务环境下生鲜同城配送能够更好地发展。

2 生鲜同城配送路径优化模型的构建

2.1 问题概述

本文研究生鲜物流配送中心将生鲜产品送达各收货方的路径选择问题，由于生鲜产品需要保证一定的新鲜度，各收货方也有自己的收货时间规定，运输车辆必须在规定的时间将产品送到，否则就会因为产品过保鲜期或是错过收货方要求送达时间而产生额外的损失，包括产品腐烂损失、收货方因缺货导致的损失、服务和信誉损失、车辆等候造成的人员闲置成本和机会成本损失等。因此，本文在构建物流配送路径优化模型时，选取的是有时间窗限制的车辆路径优化问题（Vehicle Routing Problem with Time Windows，VRPTW）。

在有时间窗约束的配送路径优化问题中，所关注的成本分为三部分：一是配送车辆的运输成本，这一部分与配送距离相关；二是因违反客户时间窗约束的惩罚成本，这一部分与到达客户处的时间有关；三是时间的推移和装卸过程造成的不可避免的损耗。

2.2 目标描述

配送路径合理与否对配送速度、成本、效益的影响颇大，无论采取何种优化方法，我们首先都要明确物流配送路径的优化目标，才能有效地针对目标进行优化。因此，采用科学合理的方法确定配送路线是配送活动中非常重要的一项工作。

根据配送的具体要求、配送中心的实力及客观条件制定配送目标，目标有多种选择：效益最高、成本最低、路程最短、吨公里最小、准时性最高、运力利用最合理等。针对不同的物流配送问题，要根据具体情况选择优化目标。

本文研究的是市域连锁业的冷链物流，冷链物流本身具备其特殊性，不能简单地只考虑配送路径问题，还应该考虑时间问题。因此，本文选取了3个关键的配送目标：运输费用最低、配送服务水平最优和货损最小，并都转换成关于费用的函数形式，最后优化成一个目标，即总费用最小。

2.2.1 运输费用

运输需要用到车辆和人员等，这部分产生的费用包括固定费用和变动费用。其中，每台车辆的固定损耗、驾驶员的工资成本等，基本是不随路线、时间等因素的改变而改变的，因此被称为固定成本。合理地安排配送车辆的配送路径可以节约运输变动成本，包括油耗、过路费、维修费、保养费等，基本和车辆行驶的距离成正比。由于车辆的折旧往往主要与行驶距离相关联，可近似于成正比，驾驶员工作时间也可以换算成与距离成正比的函数，为了简化运输，我们根据以往经验将固定成本也换算成与距离成正比的函数。最后，总的运输费用可表示为距离与单位运输费用的乘积。

2.2.2 配送服务水平

由于冷链产品有保质期限，各收货方也有自己的收货时间规定，运输车辆必须在规定的时间将产品送到，否则就会因为产品过保鲜期或是餐饮企业、超市这类的收货方因过了其销售的高峰期而产生额外的损失。因此，每个收货方都会有一个规定货物送达的时间窗，合理安排配送时间，提高顾客满意度是冷链配送的一个重要目标。如果超过时间窗限制，则要考虑惩罚成本，在这里我们用惩罚成本来衡量这一目标实现的优劣。

对于收货时间的限制，本文考虑的是软时间窗限制。在规定的时间段内送达，满足了客户的时间需求，则惩罚成本为0；如果产品的送达时间提前或是推迟，但是在一定允许时间范围内，其惩罚值会随时间跨度增大，相应的惩罚成本也会增加；当产品的送达时间超过了产品保鲜期或收货方所能容忍的范围时，超市可以拒绝接收产品并加以重罚，其惩罚值趋向于无穷大。在多数情况下，惩罚成本的额度是按照配送中心和超市双方之间约定的合同而定的。本文将在时间跨度内的惩罚函数定位线性增加函数，是为了降低问题的研究难度，如图1所示。

图1 惩罚费用与送达时间的分段线性函数图

图1中，M为最大惩罚成本，区间［b，c］为客户规定的货物送达时间段，区间［a，d］为客户可接受的送达时间段，当送达时间超出客户的可接受送达时间段时，惩罚成本最大。

2.2.3 货损成本

冷链产品因其本身具备特殊性而和其他普通货物不一样，在配送过程中，冷链食品会因为时间、保存温度、空气的氧含量、产品水分活性、产品p H值，及腐败过程中引起的代谢产物、运输过程中道路颠簸程度等因素导致腐烂变质，造成了一定程度上的货物质量和数量的损失，我们将这种损失称为货损成本。导致货损成本发生的原因有很多，但是我们为了研究的方便，其他因素均不考虑，仅选取最大的影响货损成本两个因素：一是配送时间的长短；二是装卸过程中的货损。

2.3 模型的建立

2.3.1 假设条件

结合配送的具体流程和实际情况，本文对具体模型作出以下假设：

（1）只考虑单一配送中心的情况，所有配送车辆均从配送中心出发，完成配送任务后返回配送中心；

（2）配送中心及各个客户的地理位置已知，由此配送中心到各客户，以及各客户之间的距离已知；

（3）每个客户的需求量是已知的且不会发生改变，每个客户的需求必须得到满足；

（4）配送中心的库存量可以满足客户的需求，不会出现缺货的现象；

（5）只考虑车辆对货物的配送情况；

（6）配送中心有一定数量的配送车辆，且每辆车的载重量一定，在配送过程中不能发生超载现象；

（7）每辆车可以为多个客户配送，但每个客户的配送仅由一辆车来完成，不考虑多辆车同时为一个客户配送的情况；

（8）每一条路线上客户的总需求量不超过配送车辆的最大载重量；

（9）每条路径由一辆车辆进行配送，且每辆车只配送一条路线，如果某路径货物超过车辆载重量，则需另开辟配送路径，新增车辆完成配送任务，如果某客户需求量过大，需要两台配送车辆，则可视为同一地理位置的两个客户对货物有配送需求，其中，一台车辆满载，配送后立即返回配送中心，另一台车辆可搭载其他客户的货物；

（10）每个客户都有其接受配送的时间窗且时间窗已知，每个配送车辆送达货物的时间要在客户指定的时间窗内；

（11）在车辆对各客户进行配送的过程中，不考虑天气恶化、车辆故障等突发因素的影响；

（12）在对各客户进行配送时，配送路线上的繁华地段不会出现交通堵塞、城市道路改建等现象，而配送车辆在各客户之间的运输过程中，配送路线上不会出现道路中断等突发现象。

2.3.2 参数定义

m：配送中心可以使用的车辆数目；

k：可配送的车辆集合k=（1，2，L，m）

Gk：车辆k的载重量；

n：客户数量；

i，j：客户集合i，j=（1，2，…，n），i=0表示配送中心；

c：每辆车每公里的行驶费用；

gi：客户i的需求量；

dij：客户i，j之间的距离；

r：配送的冷链产品的单位成本；

M：足够大的处罚成本；

nk：第k辆车所配送的客户数量；

θ1：冷链产品在运输途中的货损比例；

θ2：冷链产品在装卸途中的货损比例；

［ai，di］：客户i可接受的货物送达的时间窗；

［bi，ci］：客户i理想的货物送达的时间窗；

p：车辆提前到达客户处发生的等待单位时间成本；

q：车辆晚于理想时间窗到达客户处发生的单位时间惩罚成本；

tk0：车辆k从配送中心出发时刻；tk00：车辆k返回配送中心的时刻；

2.3.3 目标函数

（1）运输费用

运输费用与运输距离成正比，总的运输费用可表示为：

（2）惩罚费用

该部分费用是对配送中心未能在规定的时间窗范围内送达的客户付出的惩罚费用，惩罚成本的最大值为M，由客户和配送中心协商决定数值。p（tki）为车辆k在tki时刻到达客户i的惩罚成本。由图1可得出下列分段函数：

则总的惩罚费用可表示为：

（3）货损成本

车辆k从服务完客户i去往客户j并完成服务所造成的冷链产品的货损成本为：

则总的货损成本Z3为：

将多目标问题化为单目标问题，目标函数如下：

2.3.4 约束条件

（1）车辆载重量约束。每台车上所配送的总货物量不超过配送车辆的最大载重量：

（2）配送车辆约束。在配送过程中，每辆车可以给多个客户进行配送，但每个客户有且仅有一辆配送车辆进行配送。

（3）客户数量约束。每辆车所配送的客户数量小于总的客户数量：

（4）每台车辆都必须从配送中心出发：

（5）每次配送活动结束后车辆必须回到配送中心：

3 生鲜同城配送路线优化实证分析

以某地某生鲜农产品配送中心为实例来验证算法的合理性。我们通过网上调查、查阅相关资料，了解该配送中心的实际情况并收集、整理相关数据。另外，通过MATLAB语言进行编程，以期得出一个优化结果，并通过对优化结果的分析，来考察模型和算法的实效性，希望生鲜配送中心在生鲜产品物流配送路线规划中有所借鉴。

3.1 数据收集

本文选取了该配送中心配送范围内的16家餐饮企业为研究对象进行研究分析，并对所获取的数据进行处理、整理以方便研究的进行。

配送中心和客户的编号、地理位置以及客户的需求量如表1所示。

表1 各门店及配送中心地理位置及需求量表

在很多研究中，客户点之间的距离采用直线距离，采用客户X与Y坐标来计算两点距离。而在实际生活中客户之间、客户与配送中心的距离通常会因为地上建筑物、路线等的影响大于直线距离。本文测量距离的方法是，通过将配送中心及各客户的（x，y）位 置 标 注 出 来，通 过 公 式 dij=计算各门店与配送中心以及各门店间的距离。结果如表2所示。

表2 各门店与配送中心及其他门店间的距离（单位：m）

16个客户具体的时间窗要求及服务时间如表3所示。

表3 各分店时间窗信息表

计算需要用到的相关数据如下：

车型：厢式冷藏车；

车辆最大装载量：2吨；

每辆车每公里的运输费用：3元；

车辆平均速度：50km／h；

最早发车时间：3∶00；

配送的生鲜产品的平均单位成本：10元；

冷链产品在运输途中的货损比例：1%；冷链产品在装卸过程中的货损比例：0.5%；

车辆提前到达客户处的等待费用为30元每小时，客户延迟费用为90元每小时。

3.2 基于遗传算法利用MATLAB求解结果及分析

根据求解结果，可得出该生鲜农产品配送中心为16家餐饮企业进行配送活动所消耗的最小总配送成本为857.98元，由4辆载重量为2吨的厢式冷藏车进行配送，各路线信息如下：

图2 MATLAB迭代逼近真值图

第一条路线：0-4-5-12-9-0

第二条路线：0-1-3-13-0

第三条路线：0-15-16-11-8-0

第四条路线：0-2-6-7-10-14-0

运用CAD绘制了配送路线示意图，如图3所示。其中，路线1、2、3、4分别用红色、绿色、蓝色、白色表示。

图3 配送路径图

各路线具体运行情况如表4所示。

表4 配送时间核对表

由表4可知，第一辆配送车①于早上3：00出发从配送中心0出发，3：09到达目的地4，停留10min后（配送车从到达直到离开持续10min，主要用于完成装卸货物等工作），于3：42从目的地5出发；3：52到达目的地12，停留11min后，于4：03从目的地1出发；4：09到达目的地9，停留10min后返回配送中心0，配送车辆②、③、④按照类似的形式配送产品。

如表5所示，四辆车的装载量均超过了90%，资源得到了极大的利用，反映了使用遗传算法对路径优化问题的解决具有一定的实际意义。

表5 车辆载重量情况

4 总结及不足

车辆路径问题（VRP）是物流配送过程中的关键环节，配送路径是否合理直接影响到配送速度、成本和效益。带有时间窗约束的车辆路径问题是典型的组合优化问题，具有很大的计算复杂性。本文对时间窗车辆路径优化问题（VRPTW）进行了探索和研究。

虽然本文在构建生鲜同城配送的路径规划模型时，将时间、成本以及货物的新鲜度都考虑其中，且根据遗传算法成功求解，但是，由于时间和理论水平的局限，本文的研究还存在一些不足之处，可作为未来改进的方向：

（1）虽然本文研究时考虑了车辆载重及时间窗限制，比一般车辆路径问题更接近现实，但总体来说与实际问题还存在一定差距。在实际配送活动中，经常会遇到随机型的物流配送问题，如客户需求的不确定（如临时更改订货量或收货时间等）以及车辆行驶时间的不确定（如交通拥堵、车辆故障等）、不同车型车辆的载重量不同等。因此，今后应针对随机型的车辆路径问题开展深入研究。

（2）在实际的车辆路径问题中，对于不同等级的客户响应服务的速度是有差别的，如必须优先服务某些VIP客户，这就是具优先次序的车辆路径问题，应以适当的模型加以表达。

（3）构造数学模型中的时间惩罚函数时，为简化问题，仅构造了一线性分段函数来粗略表示，但实际上，时间惩罚函数应该呈抛物线或指数关系或其他函数关系增长，而不是单纯的线性关系，日后也可将在一定的客户服务软时间窗前提下，惩罚成本与送达时间的函数关系作为研究点。

（4）在计算物流中心与客户以及客户与客户之间的距离时较为粗糙，仅根据位置坐标算出两者之间的直线距离，然而在实际生活中，由于城市路网规划，实际行驶距离要远大于两点间的直线距离，而且某些路段的往返配送距离也是不等的。在今后的研究中，应该采用实际路线的行驶距离或者根据一定的模型加以修正。

（5）本文采用了原始遗传算法，由于能力与时间的限制，未能对遗传算法进行改进，也未将其与蚁群算法、模拟退火算法得出的结果进行对比，从而未得出解决该问题的最优算法。