张令甜，敖飞翔，涂传清 ZHANG Lingtian， AO Feixiang， TU Chuanqing

（1. 江西农业大学 经济管理学院，江西 南昌330045；2. 江西农业大学 计算机与信息工程学院，江西 南昌330045）

0 引 言

近年来，中国生鲜电商市场规模发展迅速，但生鲜产品保质期短、易损耗的特征使其对物流配送要求较高，物流成本在生鲜电商的成本结构中占比巨大，因此，物流配送成为影响生鲜电商发展的重要制约因素[1]。提高配送效率、降低物流成本是所有生鲜电子商务公司需要解决的关键问题，而优化配送车辆行驶路径是提高配送效率的重要手段。

同城生鲜配送线路优化问题可以看作是一个经典的旅行商问题（TSP）。而旅行商问题是一个NP 完全问题，当被访问的点（配送点） 数量较多时，如果通过搜索全局，精确地求得最优解，其复杂度将会极高，所以此类问题通常是运用智能优化算法（又称启发式算法） 求得近似解。高海昌等（2006） 对常见的用于求解TSP 问题的智能优化算法进行了综述，他们分析了蚁群算法、遗传算法、模拟退火算法、禁忌搜索算法、Hopfield 神经网络、粒子群优化算法、免疫算法等7 种算法在解决TSP 问题时各自的优缺点以及改进建议[2]。后续学者们对同城生鲜配送线路优化问题的研究基本上都是对上述智能算法的应用与改进，文献[3]-[11]分别运用蚁群算法、遗传算法和节约算法求解配送车辆路径优化问题，并通过算例分析论证计算结果的有效性。这些研究成果对我们具有极大的启发意义，但是当我们想将他们设计的算法直接套用到本文面临的问题——为某生鲜电商公司100 多位客户指派送货车辆和规划配送路线时，发现上述研究存在以下不足：（1） 对蚁群算法的改进虽然解决了蚁群算法的收敛速度慢的问题，也增强了蚁群算法的鲁棒性，未解决此算法容易陷入局部最优的问题；（2） 未能很好地改进遗传算法局部寻优能力不足的缺点；（3） 节约算法在求解小规模的配送线路优化问题上能够得到较理想的结果，其特点是运算速度较快，但是当需要配送的站点数量较多时，则获得结果不大理想。另外，上述研究还存在一个共同的问题就是算例过于简单，因此不能发现当配送站点数量扩大10 倍时可能引发的问题，且未解决快速获取各个配送站点之间距离的问题。

针对现有研究存在的不足，结合本文所关注的南昌市某生鲜电商公司为100 多个企事业单位食堂提供生鲜农产品配送服务时所面临的实际问题——由工作人员凭经验和手工计算进行配送车辆调度和配送路线安排，因而导致配送效率低下。具体表现为不能根据客户需求变化及时调整配送路线导致配送车辆满载率低、配送距离长；本文拟从满足实际配送需求出发，以减少配送车辆和节约配送路程为目标；不设置单个时间窗，只要求在客户上午开始准备午餐之前将生鲜农产品送到即可，因此只是统一设置最晚送达时间点；由于完成整个配送工作的时间较短，所以不考虑生鲜农产品的损耗问题，并据此建立数学模型；然后将具有较强局部寻优能力的爬山算法嵌入到全局寻优能力优良的遗传算法中用于对模型求解，取得了非常好的实际效果。

1 同城生鲜配送线路优化问题数学模型

问题描述：生鲜电商公司专门为企事业单位提供生鲜农产品采购和配送服务，企事业单位每天下午六点以前告知电商公司第二天需要的食材种类和数量，晚上八点电商公司所属配送中心根据每个客户的需求对生鲜食材进行分拣，并装入规格统一的塑料筐，每个客户所需的物品不合用同一个塑料筐；早上六点开始，电商公司用多台型号相同的车按事先规划好的路径为客户送货，完成配送任务后所有车辆回到配送中心。要求合理安排所有投入运行车辆的配送线路，即确定每辆车依次为哪些客户送货，使得所有车辆行驶里程总和最小，并满足以下条件：（1） 每条配送线路上客户的需求量之和不超过车辆的装载数量；（2） 每个客户的需求只由一辆车进行配送，且每天只送货一次；（3） 车辆在配送途中不进行加油服务，受油箱容量的限制，车辆有最大的行驶距离，故规定每条配送路线上各点的距离之和不大于车辆的最大行驶距离；（4） 所有配送车辆在规定的时间T内完成各自的配送工作后回到配送中心。

为建立此问题的数学模型，本文做如下符号假设：①给配送中心和各个客户进行编码。设企业需要给n个客户配送，配送中心编码为“0”，各个客户的编码为1，2，…，n。②qi（i=1，2，…，n）为每个客户的需求量；dij（i,j=0，1，2，…，n）表示从客户i（或配送中心） 到客户j（或配送中心） 配送车辆所需行驶的距离；tij（i,j=0，1，2，…，n）表示从客户i（或配送中心） 到客户j（或配送中心） 配送车辆所需行驶的时间。③参与配送工作车辆的装载量为Q（装载数量的单位为筐，因为在实际操作中，将每个客户需求的物品全部装入统一规格的塑料筐中进行配送），每天实际投入运营的配送车辆数为K。④每辆车的最大行驶距离为L。⑤配送车辆为每个客户送货时卸货所需时间为t。⑥设决策变量xijk（i，j=0，1，2，…，n，k=1，2，3，…，K）为逻辑变量，当xijk=1 时，表示第k辆车送货从客户i（或配送中心） 到客户j（或配送中心），否则xijk等于0；设决策变量yik（i=1，2，…，n，k=1，2，3，…，K）为逻辑变量，当yik=1 时，表示客户i由第k辆车完成配送，否则yik=0。每辆车在T时间内完成配送并回到配送中心。⑦完成配送工作后，所有车辆的总旅程数为D。

式（1） 为目标函数，求配送车辆总旅程的最小值；式（2） 确保车辆在时间T内完成配送并回到配送中心；式（3） 约束每辆车行驶的距离不超过其最大的行驶里程数L；式（4） 保证每辆车的装运量不大于其最大装载量Q；式（5） 确保每个客户的需求只由一辆车进行配送；式（6） 确保每个客户的需求都有车辆进行配送。另外，需要说明的是，在建模时没有将公司现有配送车辆数M作为一个硬约束，因为在实际运作中如果配送任务重，公司很容易临时在市场上找到车辆来完成配送任务，而且可以合理地推断将目标函数设置为求所有配送车辆总行程的最小值，通常可以保证投入运行的配送车辆数最少。

2 混合遗传算法设计

遗传算法（Genetic Algorithm） 是一种启发式算法，是Holland[3]在1973 年模拟达尔文生物进化论中的“自然选择”和“遗传学机制”首次提出的。在20 世纪90 年代初遗传算法被引用到求解TSP 问题中，将一条路线抽象地看着是一条染色体（个体），而路线中的点抽象成染色体（个体） 上的基因。在求解TSP 问题中，遗传算法中的选择操作、交叉操作和变异操作都是对路线上的点进行操作。标准的遗传算法中包括染色体编码、生成初始种群、计算适应度、选择操作、交叉操作和变异操作。在求解TSP 问题上，相较于其他启发式算法，遗传算法具有编码简单，易懂的特点。自然数编码以一种直观的方式展示点在路线中被访问的顺序。随机地产生一定数量的无序数列，即生成一个初始种群。适应度值可以通过计算路线距离的倒数获得，然后对个体的适应度进行评估，选择出较优良的个体遗传到下一代，进而将选择出来的个体进行交叉和变异操作。随机地交叉操作和变异操作为路线的选择提供了更多的可能性。交叉操作是模拟生物有性繁殖过程中基因重组机制，而变异操作则是模拟生物在遗传环境中因偶然因素引起的基因突变。经过一代接一代地选择、交叉、变异使种群向越来越优（种群个体适应度越来越高） 的方向进化，直至终止条件结束遗传算法操作，最后输出适应度最高的个体，则该个体为当前最优解，终止计算。

遗传算法具有内在的隐并行性和更好的全局寻优能力的特点。其缺点是在求解结构复杂的组合优化问题中，因为搜索空间大，搜索时间长，往往会出现“早熟”的情况，局部寻优能力较弱。而爬山算法具有优良的局部择优能力。爬山算法从当前位置出发，与邻域位置的高度（适应度） 比较，若发现邻域位置的高度大于当前位置的高度，则将该邻域位置取代当前位置，否则留在原位，以此方式向高处攀登。爬山算法局部择优能力强的特点能够弥补遗传算法局部寻优能力较弱的缺陷。此外，本文采用期望值轮赌选择法执行选择操作，轮赌选择法能够避免种群中一个性状优良的个体被选择多次，从而让更多的个体被选择进入到下一代，以提高种群的多样性。因此，轮赌法可以缓解遗传算法容易出现“早熟”的情况。

（1） 染色体编码。考虑到配送线路优化问题的特点，本文采用自然数编码方式给每个客户按顺序进行编码，客户依次编码为：1，2，3，…，n。由1…n之间的自然数随机地生成一个无重复数字的序列，然后根据约束条件将配送中心的编码“0”插入到序列中得到新的序列。例如完成9 个客户的配送，随机产生一个序列“872134956”，根据约束条件将“0”插入到序列中，得到新的序列“087213049560”。具体如何根据约束条件插入编码“0”，将在下文中的确定适应度函数部分中阐述。因为编码“0”代表配送中心，所以新序列“087213049560”意味着需要调用2 辆车投入配送工作。客户8，7，2，1，3 由车辆1 完成配送，行驶线路为“0-8-7-2-1-3-0”；客户4，9，5，6 由车辆2 完成配送，行驶线路为“0-4-9-5-6-0”。本文混合遗传算法中的选择操作、变异操作、交叉操作和爬山操作都是对未插入“0”的序列进行操作，而计算个体和种群的适应度则是使用插入“0”后的新序列。

（2） 生成初始种群。根据上文染色体编码的过程重复地生成U（U是设定的初始种群的个体数量） 个序列。一个序列就代表了一个个体，这U个序列组成一个初始种群。

（3） 确定适应度函数。遗传算法通过计算个体的适应度值来衡量个体的优劣。依据个体的适应度值对个体做选择操作，个体的适应度值越高，其被选择保留到下一代的概率就越大。本文通过对所有车辆的总旅程数D进行数值变换得到种群个体的适应度值。

计算所有车辆的总旅程数时，车辆完成配送需要满足以下约束条件：①每辆车需要在时间T内从配送中心出发，完成各自的配送任务后再回到配送中心；②每辆车配送的客户的需求量之和不大于其最大装载数量Q；③每辆车沿特定线路为客户配送货物所行驶的距离之和不大于其最大行驶距离L。根据以上三个约束条件将配送中心的编码“0”插入到序列中，产生新的序列。其插入步骤如下：设“872134956”为一个序列。①在序列的第一个客户编码前插入配送中心“0”，得到“0872134956”。②再将一个“0”插入到第一个客户编码的后面，得到“08072134956”，判断配送线路“0-8-0”是否满足上面三个约束条件；若满足，则将“0”右移一位得到“08702134956”，判断配送线路“0-8-7-0”是否满足约束条件；若还是满足，将“0”再右移一位，得到“08720134956”，继续判断配送线路“0-8-7-2-0”是否满足约束条件；若还是满足，又将“0”右移一位得到“08721034956”，判断配送路线“0-8-7-2-1-0”约束条件；设此时不满足，则将“0”左移一位得到“08720134956”，由此得到第一辆车的配送线路“0-8-7-2-0”。③插入第三个“0”得到“087201034956”，此时判断“0-1-0”是否满足约束条件。以这样的方式进行下去，直至最后一个客户编码的后面插入了“0”，得到若干条配送路线，这若干条配送线路组成了一个配送方案。设得到配送线路的条数为K，因此这个配送方案需要使用K辆车完成配送工作。计算每辆车的行驶距离，然后将每辆车的行驶距离相加，求得总和为D。式（7） 对D进行数值变换得到个体的适应度函数fi，其中Di表示的是个体i的所有参与配送工作车辆行驶距离的总和。

（4） 选择操作。标准的遗传算法中，选择操作通常使用轮赌选择法，而轮赌法在种群进化到一定的代数后，种群中各个体间的适应度差距很小，被选择的概率相差微乎其微，因此传统的轮赌法很难体现出择优的特性，并且再次进行选择时，被选择过的较优个体可能再次以较大的概率被选中。此乃遗传算法出现“早熟”现象的重要原因之一。本文将期望值嵌入到轮赌选择中，这种选择方式使较优个体以更大的概率被选择保留下来，并且当再次执行选择操作时，被选择过的个体将以更小的概率被选择，以此改进传统轮赌选择法的不足。期望值轮赌选择法通过降低被选择个体的期望值的方式，使下一次做选择操作时，被选择过的个体将以较低的概率再一次被选中，进而提高新种群的多样性。期望值轮赌选择法的应用步骤如下：

①计算当前种群中每个个体的生存期望值，计算个体i的生存期望值Ei见公式（8），U是种群中个体的数量，fi为个体i的适应度值。

②根据个体的期望值，使用轮赌法选择出1 个个体，判断被选择个体的生存期望值是否小于0，若小于0 则使用轮赌法重新选择。如果种群中所有个体的期望值都小于0，那么就选择期望值最大的个体。

③将被选择的个体的期望值都减去0.5。例如，当个体的期望值为0.3 时，被选择后，其期望值为-0.2，下一次执行选择操作时该个体将不会被选中（种群中所有个体的期望值都小于0 时例外）。

④重复步骤②、③，再选择1 个个体出来，得到2 个个体。将选择出来的2 个个体进入交叉操作。

（5） 交叉操作。对选择出来的2 个个体进行交叉操作。本文用的是部分匹配交叉法（PMX）。具体步骤结合图1 说明如下：

①根据给定的交叉概率Pc判断是否对选择出来的两个个体进行交叉，若交叉则进行交叉操作，若不交叉则直接保留这2 个个体做下一步变异操作。

②假设需要进行交叉的两个序列分别是：A=4598320671，B=1487965032。随机产生2 个不同序号的交叉位，假设随机交叉位是3 和6。

③交叉区域为：A=45|98320|671，B=14|87965|032。将A 中的交叉区域与B 中的交叉区域互换，交叉后的序列为A=45|87965|671 和B=14|98320|032。

④对于交叉后的序列A=45|87965|671 中交叉区域以外的序列中出现的重复编码，取A 序列中交叉区域内的编码位置所对应B 序列的位置上的数字做替换。A 序列中只替换交叉区域外的编码，交叉区域内的编码不做替换。本例中，A 中出现的重复编码有“7”、“6”、“5”。交叉区域的编码不动，交叉区域以外的编码段做替换：7→8；6→2；5→0。执行上述操作后得到：A=40|87965|281。继续检查到A 序列存在重复编码“8”，做替换8→9，得到A=40|87965|291。再次检查到A 序列中存在重复编码“9”，做替换9→3，得到A=40|87965|231。此时A 序列中没有重复的编码了。同样也对B=14|98320|32 重复编码进行检查并做替换。

（6） 变异操作。对执行完交叉操作后的个体进行逆转变异操作。逆转变异操作是对单个个体的部分序列进行重新排序操作。逆转变异操作一方面可以提高了遗传算法的局部搜索能力，另一方面在一定程度上丰富种群的多样性。逆转变异操作具体步骤是：

①根据给定的变异概率Pm判断是否对个体进行变异操作。对于不做变异操作的个体直接保留下来。对于执行过变异操作的个体，进行变异操作后再保留下来。

②随机生成两个范围在1，…，n且不相等自然数，将这两个自然数作为变异的逆转点，然后翻转两个逆转点之间的编码值。例如：随机生成的逆转点是3 和6，A=87|2314|956。逆转变异后，A=87|4132|956。

（7） 嵌入爬山算法。当前种群所有个体执行完选择、交叉和变异操作后，重新计算种群中各个体的适应度值，选出适应度值最高（最优） 的个体进入如下的爬山操作。①随机生成两个不相等自然数且取值范围在1，…，n。将这两个自然数作为交换位，并交换这两个自然数对应序列位置上数值。②利用适应度函数计算交换位置后的个体的适应度值是否增加，若增加则将交换位置后的个体替换当前最优个体。否则，不进行替换。③重复①、②操作，直至达到设定的循环次数ClimbNum（ClimbNum为设定的爬山次数）。

（8） 记录最优个体。设置一个记忆器，将做完爬山操作的个体记录下来（做完爬山操作后的个体，其适应度值是当前种群中适应度值最高的个体）。该操作能够将每一代种群中最优个体保留下来。

执行完上述选择、交叉、变异操作和爬山操作后得到了一个新的种群。对新的种群循环执行选择、交叉、变异操作、爬山操作和记录最优个体，直至达到循环终止条件。本文设定当种群进化到最大代数Gmax作为循环终止条件。终止条件结束后，选择出记忆器中的最优个体，即得到混合遗传算法的最优解。上述混合遗传算法的过程可以用图2 来描述。

图1 交叉实例操作流程

图2 混合遗传算法流程

3 算例分析

3.1 需求描述

本文以南昌某生鲜电子商务公司的日常生鲜农产品配送工作为案例，进行算例分析。该公司有一个配送中心，某日需要对95 个客户配送生鲜农产品。配送时使用塑料筐的尺寸为：长85cm、宽60cm、高45cm。每个客户的需求量见表1。统一使用江铃全顺8 座GLX型车辆进行配送，车辆最大装载量为Q=19 筐，车辆的最大行驶距离为L=600 公里。所有客户的订单在前一天晚上完成打包装筐。配送车辆于早上6:00 出发，在上午10 点前完成配送并回到配送中心。因此配送车辆需在240 分钟时间内从配送中心出发完成配送，并回到配送中心，即T=240 分钟。

3.2 实验前准备工作

本文通过百度坐标拾取系统获取每个客户的经纬度，然后利用经纬度通过百度地图“JavaScript API v3.0”接口编写JavaScript 语言程序批量获取配送中心到每个客户以及每两个客户之间的车辆行驶距离和行驶时间。因为在实际配送中，车辆从A 点到B 点和从B 点到A 点行驶的可能不是同一条道路，即车辆从A 点到B 点和从B 点到A 点的行驶距离和时间是不同的，故本文需要获取双向距离和时间。本文获取的行驶距离和行驶时间数据为早上7～8 点百度地图导航提供的数据，此时间段正好是配送时间；但获取车辆行驶距离和行驶时间信息涉及的数据量较大，篇幅受限，故此过程不在文中展示。本文使用Java 语言编写程序，实现混合遗传算法。执行算法使用的是普通桌面办公台式计算机，性能中等，搭载的是Windows7 操作系统。

表1 客户的需求量 单位：筐

3.3 实验数据分析

给配送中心和95 个客户依次编码为0，1，2，3，…，95。设初始种群数量U=10 000，最大进化代数Gmax=1 000，交叉概率Pc=0.3，变异概率Pm=0.3，爬山操作的循环次数ClimbNum=90，车辆在每个配送点停留t=5 分钟，在220 分钟内完成配送，预留20 分钟预防突发事件的发生。

根据以上参数多次执行算法，都能够得出较优的配送方案，配送距离分布在600～700 公里之间，使用车辆数在11～13 台之间，算法执行时间耗时220 秒左右。表2 给出的是使用车辆数最少的一次计算结果。表3 是该公司当天实际使用的配送方案，该方案是公司配送人员通过多次送货经验总结出来的线路。对比两套配送方案可见，使用混合遗传算法得出的配送方案少使用了3 辆车，车辆的总里程也缩短了285.6 公里，并且配送时间最长的车耗时218 分钟，即所有车辆均可在上午9:40 之前完成配送任务，并回到配送中心；而该公司实际使用的配送方案中，配送时间最长的车耗时255 分钟，比混合遗传算法得出的配送方案多了37 分钟，并且不能在上午10 点前回到配送中心。

4 结论与展望

本文从分析南昌市某生鲜电商公司面临的同城生鲜农产品配送线路优化问题入手，建立了该问题的数学模型，并创造性地设计了一种混合遗传算法用于对同城生鲜农产品配送线路优化问题求解。此算法的新颖之处在于：（1） 局部寻优能力较强的爬山算法嵌入到遗传算法当中，从而改善了遗传算法局部寻优能力不足的缺点；（2） 使用期望值轮赌法执行遗传算法中的选择操作，有效避免了遗传算法中的早熟现象。

笔者根据此算法开发了一个WEB 应用程序。该系统可以根据生鲜农产品电商公司的实际业务发展情况，添加和删减客户，修改客户的需求量。在新增客户时，先通过百度坐标拾取系统获取客户位置的经纬度，然后将客户的准确经纬度添加进数据库，系统就能通过百度地图导航系统快速地获取配送车辆从配送中心到新客户以及新客户与其他客户之间的行驶距离和行驶时间，根据这些新数据，设置相应的参数就能够迅速地重新规划出新的送货线路。将通过混合遗传算法求得的配送路线与公司当前实际采用的配送路线对比，发现按照混合遗传算法求得的路线进行配送，既可以减少投入运行的配送车辆，又可以节约配送车辆的行驶距离，从而帮助生鲜电商公司节省配送成本。

最后，需要指出的是，虽然本文提出的数学模型和混合遗传算法能够快速地帮助生鲜电商公司提供配送线路优化方案，但是还存在以下两个问题需要进一步探讨：①种群数量、繁殖次数、变异率和交叉率等参数是如何影响算法寻优能力的？要如何根据客户的数量来设置恰当的种群数量、繁殖次数、变异率和交叉率等参数才能提高算法的执行效率并使算法有较强的寻优能力？②如何在算法中整合进路况信息，以便使系统更加适合企业的实际情形？因为经常存在某些路段出现临时修路的情况，这时通过百度地图获得的数据往往与实际配送情况不符。能否让送货司机记录实际的送货时间和车辆码表行驶的里程数，并将这些数据更新进系统，作为计算配送线路的依据。

表2 混合遗传算法得出的优化结果

表3 现公司使用配送方案