基于蚁群算法的配送路径优化研究

安晓雯 董福贵

随着信息技术的进步，电子商务也在迅速发展，当前制约电子商务发展的关键问题是物流配送成本过高、配送效率过低。合理的配送路径可以更好的缩减企业的成本，提高服务质量，因此对于电商企业配送路径优化的研究具有很大的价值。本文针对某电商企业，对路径优化问题展开了讨论。首先建立VRP模型，提出利用蚁群算法对VRP问题进行求解，借助MATLAB软件进行仿真实验，实例分析结果发现优化后的方案缩短了配送路径，减少了配送成本。

一、引言

信息技术的日新月异，促使电子商务迅速崛起，并带动了物流业快速发展，但是与此同时物流配送也成为制约电子商务发展的关键因素，因此优化配送路线，降低物流成本，提高顾客满意度是提高企业竞争力的关键。

罗梓瑄等在物流配送路径优化中，以成本最小化和最小碳排放量为目标构建了多目标优化模型，利用蚁群算法对其进行求解，他们认为蚁群算法能多点同时搜索独立解，具有较强鲁棒性。最后通过仿真，计算出最优配送路径。张晓娜等以果蔬配送路线最优、最大化保持果蔬新鲜为目标，构建路径优化模型，通过蚁群算法求解。吴雨婷等以配送路径最短、时间最少、成本最低、客户满意度最高为目标，构建基于蚁群算法的冷链物流配送路径优化研究模型。吴竞鸿先分析了上海某连锁商店配送中存在的问题，针对现状建立了VRP模型。最后借助MATLAB软件以及真实数据对模型进行了求解，提出配送路径优化方案。汪越等认为在配送过程中加入时间窗限制可以更好的减少配送成本，他在文章中采用路径长度和空载率两个指标对带时窗物流运输车辆路径进行优化，结果表明配送中心车辆调度效率提高了，为配送中心合理进行配送车辆调度提供借鉴。马贵平等在传统蚁群算法基础上加入运输时间、成本和道路通畅程度等约束条件，提出改进蚁群算法，并和CSAACO算法和ACO算法对比，结果显示改进蚁群算法寻优能力更强。张肖琳等在构建路径优化模型时考虑到了车辆在配送中对环境产生的影响，通过蚁群算法进行优化求解，结果证实了该模型可以达到路径最短和对环境影响最小的目的。万国海建立了以成本最小化为目标的电子商务配送路径优化模型，并在传统蚁群算法基础之上做出了改进，结果表明改进后的蚁群算法提高了物流配送效率，降低了成本。

本文在查阅资料基础之上，研究了针对某电商企业的路径优化问题。本文首先建立了VRP模型，通过蚁群算法对模型进行求解，实例分析结果显示蚁群算法在配送路线优化中的有效性。

二、物流配送路径优化数学模型

（一）问题描述

电商企业配送路径优化可描述为：已知某地区的客户数量、每位客户的坐标和需求量，由配送中心的配送车辆向客户配送所需量的货物。车辆从配送中心出发，每位客户只能由一辆配送车辆配送，且每个客户点只能被访问一次，最后配送车辆回到配送中心，实现路径最短、时间最少或成本最低等目标，同时还需要满足一些约束条件：车辆负载和配送时间等。

（二）物流配送路径优化模型

1.参数说明

M={1，2，…，m}表示客户点集合

n表示配送车辆的数量

q是配送车辆的最大负载

c表示配送车辆的固定成本

cij表示配送车辆从客户点i到客户点j的运输成本

qi表示客户点i的需求量

0-1变量

2.数学模型

以配送路径总成本最低作为目标函数：

上式表示每个客户点只能由一辆配送车辆进行配送

上式表示每辆配送车辆向客户点配送的时候载重量不能超过自身最大负载

上式表示到达客户点和离开客户点的配送车辆有且仅有一辆

（三）蚁群算法的最优路径设计

第t时刻，节点i上的蚂蚁数量为Bi（t），那么蚂蚁数量为，n是节点数，即客户数i，j节点距离为dij。蚂蚁没爬过时，初始信息素是相同的，τij（0）=C，第t时刻，节点i上的蚂蚁k向节点j转移的概率为：

allowedk是蚂蚁k选择的节点集合，α，β是启发因子和期望因子，表示节点i和j间的信息素和能见度。

蚁群优化具有正反馈机制，路径越短，信息素越多，蚂蚁每爬行一步，信息素就会进行更新。

ρ是信息素挥发系数，Δτij是i和j间的信息素增量。

三、实例分析

（一）测试环境

某电商企业有5辆配送车，车辆最大负载为4吨，由配送中心向15个客户点点进行配送，配送中心编号为0，客户点编号从1-15。配送点坐标及需求量如表1所示。

表1 配送点坐标及需求量

（二）测试结果

用MATLAB进行仿真实验时，设置最大迭代次数为100，蚂蚁个数为30，车辆载重为4吨。测试结果如图1所示，表2是MATLAB求解结果，路径变化如图2所示：

由表2可知通过蚁群算法优化之后的最优配送路径方案总共有三条：

路径1 由配送中心出发，经过1-2-3-4-5-6-8-7，最终回到配送中心，路径1总配送距离为184.411km，运输量为3.84t。

路径2 由配送中心出发，经过10-9-12-13-11，最终回到配送中心，路径2总配送距离为40.216km，运输量为3.76t。

路径3 从配送中心出发，经过14-15，最终回到配送中心，路径3总配送距离为50.836，运输量为1.04t。最终某电商企业的总配送距离为275.463km。

由上图和表可知，本文某电商企业的路径在蚁群算法优化之后由之前的336.6km，缩减到后来的275.4629km，减少了61.1371km。路径缩短，配送效率也提高了，可以看出优化效果还是很明显的。

四、结语

在物流快速发展的今天，物流配送的重要性不言而喻。运输成本作为物流成本中重要的一环，对企业的发展也存在一定的影响。本文首先建立VRP模型，然后通过蚁群算法对模型进行求解，最后针对某电商企业进行实例分析，结果表明蚁群算法可以优化配送路线，提高配送效率，且效果较为明显。我认为本文还存在一些不足之处，绿色发展已经成为各国大力追逐的目标，物流运输业作为一个不可或缺的行业理应承担起推动各国绿色发展的重任，因此在今后的研究中除了考虑配送路径和成本，还需要加入对碳排放量、时间窗、货车装载率等的考虑。

（作者單位：华北电力大学 经济与管理学院）

基金项目：华北电力大学哲学社会科学繁荣计划专项项目（2019FR003）。