基于改进遗传算法的农产品配送路径优化研究.docx

基于改进遗传算法的农产品配送路径优化研究 摘要以第三方物流企业为视角，在保证配送质量最高的情况下，将配送成本最低作为优化目标，构建多目标农产品配送路径优化模型。针对此类NP问题，结合改进的遗传算法，在Matlab2015环境下设计仿真实验。结果表明，改进的遗传算法在解决此类问题时，可行解能够快速收敛到帕累托最优，同时证明了模型和算法的科学性。 关键词遗传算法；农产品物流；多目标优化；VRP DOI1013939/jcnkizgsc201801136 1引言 当前，我国农产品流通过程中物流成本过高。一方面，在运输过程中，由于农产品自身的特点使得产品损失率较大，导致货损成本过高；另一方面，由于农产品呈现地域性特点，面对多网点的产地和销售点，传统的凭经验选择配送路线显得太不科学，造成了产品在途时间过长、迂回运输等现象。基于以上背景，文章以第三方物流企业为视角，在保证配送质量最高的情况下，将配送成本最低作为优化目标，构建多目标农产品配送路径优化模型。 文章研究的时间窗约束下的路径优化问题（VRP）属于多目标优化问题，对于这类问题很难用全局搜索法精确求解，目前解决这类问题大多数依靠启发式算法。例如，遗传算法、蚁群算法、粒子群算法、模拟退火算法等。Feng Xu Li通过分析农产品流通的现状，提出一种?时间窗约束下多类型车辆配送路径优化模型，创新性地考虑了在不同类型的车辆有不同的边际和成本费用，通过遗传算法解决；王飞军等人在分析农产品配送车辆调度问题的基础上，引入蚁群算法解决该问题。实验证明，蚁群算法能够快速收敛到帕累托最优解，研究对于实现车辆合理调度、缩短运输路程、降低运输费用有较大意义。张逊逊等人为了实现农产品配送系统的节能减排，将碳排放量考虑到VRP问题中去，构建碳排放量最低和最短路径决策模型，提出了基于相似性选择的演化算法，最后通过案例仿真验证了所提出算法的科学性。 2多目标VRP优化问题数学模型构建 21货损成本 因为农产品自身的特性，如易变质性、地域性等特点，加上我国冷链不完善、温度的波动以及流通环节中不专业操作等因素，从生产到销售这段时间内产生的货损成本。 22物流满意度 一般而言，将现实中货物在途时间分为两部分，第一部分是客户期望收到货物的时间，这段时间内客户的物流满意度为100%；第二部分是客户在可以接受的时间范围内接收货物，假设在这段时间内，客户的物流满意度与时间呈线性关系。 3VRP问题下改进的遗传算法 GA主要依靠选择、交叉、变异等遗传算子实现种群的优胜劣汰，对于二进制编码的染色体而言，当种群不具多样性，算法易陷入早熟、收敛；对于十进制编码的染色体，面对组合优化问题时，不能在任意基因位交叉染色体，交叉会使得新产生的染色体不是优化问题的解。PGA的遗传操作仅在两条染色体上进行“交叉”为主，在一条染色体上进行变异操作为辅，即通过单个个体繁殖后代，所以称为单亲遗传算法。PGA的选择算子功能和GA无异；不同的是，PGA利用基因重组算子实现了GA的交叉和变异功能。 31基因换位操作 GA主要通过交叉算子实现整个种群的迭代，但使用序数编码时候个别问题不能进行交叉操作，必须使用PMX、OX和CX等特殊的交叉算子。这些特殊的交叉算子操作复杂，并且执行效率不高。所以此处借助另一种遗传算子实现种群的更迭基因换位算子。PGA的基因换位算子是按一定概率p随机交换染色体中基因位的过程。基因换位可以分为单点换位和多点换位，单点换位一次只交换一对基因位；多点换位是对于预先给定的正整数u，取随机数i（1iu），一次交换i对基因位。当u取3，i取2，PGA的多点换位操作如下： R=2 5 8 7 4 1 3 6 9 R=2 7 8 5 4 9 3 6 1 32编码及解码方案 本文采用十进制编码，0表示配送中心，1，2，3表示目的地。首先，随机产生一组排列。假设有9个目的地，随机产生326481957的排列，具体编码思路如下： （1）从左向右依次累计目的地的需求量，一旦累计需求量超过货车的载重量就停止计数，设经过n次累计之后累积量超过货车的载重，记录此时的断点1为n-1，累积量清零。 （2）从排列的第n位开始继续重复第一步，假设再次超过货车载重量时，此时的累计次数为m，记录断点2为n+m-1， 累积量清零。 （3）重复上述步骤直至排列的最后一位，生成断点矩阵。 （4）依据断点矩阵，在排列对应基因位和首末位加上0，编码完成。 33适应度函数 适应度函数（ft）用于评价解集中的个体对于目标函数的优劣性，通常根据实际问题需要设定。在适应度函数的设计方面，常采用将目标函数映射成适应度函数的方法。本文选取（ft）=1/（Zmin+V?q）。V表示惩罚系数。 34算法流程 Step 1：确定编码方案，将待优化问题的潜在解表示成染色体。 Step 2：确定控制参数以及适应度函数。 Step 3：随机产生初始种群。 Step 4：计算种群中个体的适应度值和遗传概率。 Step 5：依据优胜劣汰规则，保留适应值较大的个体，淘汰适应值低的个体。 Step 6：依据选择概率复制最能适应环境的染色体，代替适应值较低的个体，保持种群规模基数不变。 Step 7：依据交叉概率和变异概率对种群重复Step 6。 Step 8：若满足终止条件，输出结果。若不满足重复步骤Step 5Step 7。 4案例仿真及结果分析 41案例描述 现某第三方物流企业计划从配送中心，坐标（00），向16个目的地配送农产品，配送采用单一型号的货车运输，汽车装载量为55吨，平均车速60km/h，车辆损失的机会成本为每小时15元，延迟费用80元。每天最早出发时间为6：00。单位路程运费率15，产品单位价值80，损失系数005。各网点的具体信息见上表。在Matlab2015程序下进行数值仿真，采用以下参数，选择概率pc=015，改进遗传算法的最大基因换位次数为6，初始种群个数20。 42结果分析 根据上述改进的遗传算法编写C语言程序，在Matlab2015环境下对该数学模型进行300次迭代寻优。在第110代左右时候寻得帕累托最优解。最终配送系统总成本2414575，目的地平均物流满意度为804%。仿真求得6?l使配送总成本最低的路径（车辆从配送中心出发，完成对各个目的地的配送之后返回配送中心的过程），分别为，路径一：0-15-14-4-0；路径二：0-2-1-0；路径三：0-16-6-8-0：路径四：0-10-7-3-0；路径五：0-9-13-11-5-0；路径六：0-12-0。适应度函数变化趋势见下图，具体配送方案及时间见表2。 可行解的适应值随迭代次数的进化过程 从种群的进化趋势来看，适应度函数值从30代左右开始逐渐变大，种群中个体对于环境的适应性能力越来越强，每经过一段时间种群的更迭，解集越接近帕累托最优。从适应度的变化可知，曲线多处垂直上升，整体收敛速度较快。在经过110次迭代之后，曲线变化趋于平缓，最终找到帕累托最优解，证明了改进的遗传算法良好的寻优性能。 5结论 本文通过探讨农产品流通环节中的广义物流成本，结合实际情况，采用单一的对农产品配送路径优化从而控制流通成本，将农产品在途时间作为评价第三方物流满意度的标准，建立数学模型。针对多目标优化问题，考虑到模型求解的复杂性，利用改进之后的遗传算法在Matlab环境下对目标函数进行迭代寻优。通过案例证明模型的科学性，同时从适应度函数的变化趋势图证明了算法的可行性。该研究能够满足一定阶段下农产品运输中的路径决策问题，对于降低流通成本具有较大意义。另外，本文的配送系统只考虑单一型号的车辆，有且只有一个配送中心问题，对于多种农产品混合运输问题没有涉及，这都是今后需要研究的方向。 参考文献： 罗勇，陈治亚基于改进遗传算法的物流配送路径优化J.系统工程，2012（8）：118-122 Feng Xu Li，Yue Fang Yang，Fei Wei，Feng WeiStudy on Multi-Vehicle Refrigerated Distribution of Agricultural Products with Soft Time Windows王飞军，吕建新，杨建伟基于蚁群算法的农产品配送车辆调度问题研