1 引言

随着电子商务的发展, 物流专业技术的提高, 城市快递配送业务得到了迅速的发展. 城市快递配送作为快递物流的“最后冲刺”, 是物流配送的重要环节, 因此, 城市配送路径的优化对提升快递服务起着关键的作用. 快递配送路径优化目标是高效率寻找成本最低、耗时最短的快递配送路线, 实现快递配送车辆的优化调度. 城市快递配送路径的优化不仅要关注配送路径的长度, 还要关注配送的时间、配送成本、配送车型及负载. 城市快递配送路径优化问题实质是一个非确定性多项式NP (Non-deterministic Polynomial)完全问题.

近年来, 仿生智能优化算法被广泛应用于解决快递路径的优化问题. 如, 遗传算法^[1]、禁忌搜索算法^[2,3]、启发式搜索算法、模拟退火算法、人工蜂群算法、爬山算法、蚁群算法^[1,4,5]、离散蝙蝠算法^[6]、粒子群算法等等.

遗传算法(Genetic Algorithm, GA)是由美国J.Holland 教授受生物进化论的启发而提出的一套较为完整的理论和方法, 是一种基于适者生存, 优胜劣汰遗传机制的自然选择和进化原理的全局搜索随机算法、该算法搜索能力强大, 遗传算法在选址问题、配送问题、调度问题、运输问题、布局问题方面具有重大的意义. 该算法利用自然选择规律和基因遗传机制来实现仿生运算, 它对适用条件几乎没有任何限制, 以概率论为基础自适应概率搜索, 具有强大的搜索能力, 在解的空间中进行随机化搜索, 得到全局最优解.

层次分析法(Analytic Hierarchy Process, AHP)是萨蒂教授提出的一种层次权重决策分析方法. 它将定性分析与定量分析相结合, 用数学的方法将人的思维过程层次化、数学化, 为决策分析提供量化指标, 但传统的AHP算法容易受到极端值影响.

本文构造的改进AHP-GA算法有效整合中位数AHP算法和遗传算法的优势, 消除了极端值的不良影响, 科学评价快递配送路径优化问题中各层次目标权重, 并给出最佳定量值. 同时利用改进遗传算法解决全局优化问题的优势, 提高了决策的时效性和有效性.

蒋国清^[1]等人提出的基于两阶段式的物流配送路径优化方法, 将遗传算法与蚁群算法相结合, 充分利用了遗传算法全局搜索速度快的优点进行第一阶段的路径搜索, 并将搜索结果作为第二阶段的初始值, 同时利用蚁群算法局部搜索能力强的优点进行第二阶段的路径优化. 刘恒宇^[7]研究了考虑拥堵和工作量的一致性车辆路径问题, 构建的混合整数规划模型考虑了车辆容量约束. 杨志清^[8]提出在多目标优化问题的基本遗传算法求解中, 可以通过使用权重系数变化法将多个子目标进行权重配比, 从而将多目标优化问题转化为单目标优化问题. 但是, 文中提到的权重系数变化法指的是根据实际情况进行设定和相应调整, 没有关注先验信息, 主观性较强. 本文研究的是带有软时间窗的多目标快递配送路径优化问题, 并提出利用改进AHP-GA算法对该问题进行优化, 利用中位数AHP算法关注先验信息, 并消除了极端值带来的不良影响; 利用改进GA算法进行全局优化搜索.

2 问题描述

快递配送的最优路径, 必须满足以下约束:

(1)配送中心的配送车辆的数量、型号一定;

(2)每一辆配送车的负载量必须大于等于所行驶路线上所有待服务客户需求货物的总重量, 配送车不得超载运行;

(3)每一辆配送车的配送时间有预定上限, 不得超时间运行;

(4)配送中心为多个, 并且每次仅由一个配送中心为某条路径上的客户配送货物, 并最终回到出发的配送中心.

(5)每一个客户存在且仅存在于一条配送路线上.

(6)满足客户要求的时间窗. 如果准时或提前将货物配送给顾客, 则不予惩罚; 否则, 要给予惩罚.

本文要解决的配送问题是在以上约束条件的基础上, 如何进行车辆调度, 以满足总配送成本最低, 总的配送时间最短, 配送车辆最少. 其中配送成本包括车辆在约定时间之前到达获得的机会成本、在约定时间之后到达的罚金成本以及车辆行驶的费用. 因此, 本文可归结为多目标优化问题.

3 数学模型构建

基于以上目标构建的数学模型如下:

$\min{P_1} = \sum \limits_i \sum \limits_j \sum \limits_k {c_{ij}}{x_{ijk}}$

(1)

$\min {P_2} = {m_1}\sum \limits_{i = 1}^n + {m_2}\sum \limits_{i = 1}^n \max \left( {{t_i} - L{T_i}, 0} \right)$

(2)

$\min{P_3} = \sum \limits_{k = 1}^K \sum \limits_{j = 0}^N {x_{0jk}}$

(3)

${\rm{s.t.}}\left\{\begin{array}{l} \displaystyle\sum \limits_i {g_i}{y_{ki}} \le q, \;\;\forall k\\ \displaystyle\sum \limits_k {y_{ki}} = 1, \;\;i = 1, \cdots , n\\ \displaystyle\sum \limits_k {x_{ijk}} = {y_{kj}},\;\;j = 1, \cdots , n \;\;\forall k\\ \displaystyle\sum \limits_k {x_{ijk}} = {y_{ki}},\;\;i = 1, \cdots , n \;\;\forall k \end{array}\right.$

${x_{ijk}} = \left\{ {\begin{array}{*{20}{c}} 0, \\ 1, \end{array}} \right.\;\; i, j = 0, 1, \cdots n;\forall k$ , 其中, ${x_{ijk}}$ 表示车辆k, 由i离开, 开往j.

${{{y}}_{{{ki}}}} = \left\{ {\begin{array}{*{20}{c}} 0, \\ 1, \end{array}} \right.\;\; {{i}} = 0, 1, \cdots {{n}};\forall k$ , 其中, ${y_{ki}}$ 表示由车辆k来完成客户i的需求.

${c_{ij}}$ 表示从点i到点j的费用; $[E{T_i}, L{T_i}]$ 表示该任务执行所允许的时间范围, ${m_1}$ 表示在 $E{T_i}$ 之前到达任务点等待的单位时间成本, ${m_2}$ 表示在 $L{T_i}$ 之后到达点i, 所交的罚金成本. 目标函数(1)表示运输成本, (2)表示时间惩罚与机会成本, (3)表示车辆数目最少. 将目标函数进行归一化处理, 使其取值范围在[0, 1]之间.

$ {P_1}' = \frac{{{P_1} - {P_1}_{\min}}}{{{P_1}_{\max} - {P_1}_{\min}}} $

(4)

$ {P_2}' = \frac{{{P_2} - {P_2}_{\min}}}{{{P_2}_{\max} - {P_2}_{\min}}} $

(5)

$ {P_3}' = \frac{{{P_3} - {P_3}_{\min}}}{{{P_3}_{\max} - {P_3}_{\min}}} $

(6)

$ f\left( {{P_1}', {P_2}', {P_3}'} \right) = {w_1}{P_1}' + {w_2}{P_2}' + {w_3}{P_3}' $

(7)

式(7)中 ${w_1}$ , ${w_2}$ , ${w_3}$ 分别为3个目标函数的系数权重.

4 构建评价指标权重子集

根据式(7)的目标函数, 需要构建一个各项指标权重子集, 本文采用中位数AHP层次分析法^[9], 有效的摒除了极端值的影响, 提高了客观性, 在运用中位数AHP方法进行评价和决策时, 可分为以下4个步骤^[9]:

(1)分析模型, 建立递阶层次结构, 如图1所示.

(2)根据专家打分, 对准则层进行指标重要性排序.

(3)中位数是指在变量数列按照有序(升序或者降序)排列的时候, 位于中间位置所对应的变量值^[3]. 故中位数不受分布数列的极大值和极小值的影响, 从而在一定程度上提高了中位数对分布数列的代表性. 因为中位数不易受极端值影响且与所有评价值距离最短的优点^[9], 故采用中位数确定指标权重, 通过归一化处理使得所有指标的中位数权重之和等于1.

如5位专家分别对 ${{{P}}_1}{{{S}}_1}$ 、 ${{{P}}_1}{{{S}}_2}$ 、 ${{{P}}_2}{{{S}}_2}$ 、 ${P_2}{{{S}}_3}$ 、 ${P_3}$ 5个指标项权重评分分别为:

P₁S₁: (0.117, 0.542, 0.232, 0.312, 0.810);

P₁S₂: (0.223, 0.479, 0.978, 0.202, 0.526);

P₂S₂: (0.187, 0.189, 0.002, 0.098, 0.198);

P₂S₃: (0.141, 0.132, 0.147, 0.201, 0.151);

P₃: (0.478, 0.232, 0.131, 0.125, 0.007).

则计算的中位数分别为

$ \left( {0.312, 0.223, 0.187, 0.147, 0.131} \right) $

因为0.312+0.223+0.187+0.147+0.131=1, 所以此时无需进行归一化处理, 因此确定P₁S₁、P₁S₂、P₂S₂、P₂S₃、 ${P_3}$ 五个指标项的权重分别为: 0.312, 0.223, 0.187, 0.147, 0.131.

在此步骤中, 采用了中位数方法来求取各项指标权重, 较之传统的AHP方法, 无需构造判断矩阵, 避免了采用不同的标度构造的判断矩阵所产生的一致性矛盾. 无须进行一致性检验, 避免了大量的计算. 且中位数不受极端值的影响. 经过简单的代数变换得到, 在变量数列中变量值与中位数离差的绝对值的总和为最小^[9].

(4)计算各层要素对系统目的(总目标的合成(总)权重, 选择最优方案. 由(3)可得因素层指标项所占整个指标体系的权重.

$\begin{aligned} ({w_{P_1S_1,}}{w_{P_1S_2}},{w_{P_2S_2}},&{w_{P_2S_3,}}{w_{P_3}}) = \\ &{\left( {0.312,0.223,0.187,0.147,0.131} \right)^{\rm{T}}} \end{aligned}$

(8)

将式(8)代入已经定义好的数学模型式(1)、(2)、(3), 将其加和, 得到目标函数.

5 改进遗传算法求解 5.1 编码设计

本文采用自然数编码的方式, 用0代表配送中心, 自然数1, 2, …, N代表客户点, 每个客户点采用k辆车进行配送, 以车辆数k=3, 待配送客户数=8为例, 可构造如下编码.

如图2所示, 通过遗传算法的编码, 初始化行车路线, 如第1辆车的行车路线为0--->3--->8--->1--->0, 第2辆车的行车路线为0--->4--->5--->7--->0, 第3辆车的行车路线为0--->2--->6--->0. 该染色体实质是一条忽略了车载容量约束和时间窗约束的广义路径.

由于遗传算法是一类借鉴生物界的适者生存, 优胜劣汰遗传机制的进化规律而演化而来的随机化搜索方法, 因此由传统的简单遗传算法出始化种群得出的适应度较低, 并制约算法的收敛速度^[10]. 本文采用贪婪算法对初始个体进行优化, 利用贪婪算法局部寻优的优势产生新个体. 其初始化种群步骤如下:

首先, 选择配送中心(0, 0)点加入个体, 然后选择离配送中心最近的一个配送点, 标记为A配送点, 并对A进行配送, 然后计算其它配送点距离A点的距离, 选择离A点最近的配送点, 标记为B, 并将B作为接下来的配送对象, 以此类推直至所有配送点全部加入, 由此可见, 由贪婪算法生成的初始种群不失随机性, 同时, 由于贪婪算法生成的初始化种群质量较高, 导致整体质量有所提高, 有助于加快寻优速度^[10].

5.2 选择操作

通过选择操作保留种群中的最佳个体, 本例中采用最佳个体保存策略, 采用轮盘赌策略进行基因选择和复制. 计算种群中每一个个体的适应度, 计算每个个体的适应度值与种群总体适应度值的比值, 并按照适应度值大小进行排序. 设计随机选择概率, 并按照大小进行排序. 将具有较大适应度的染色体进行复制.

5.3 交叉操作

为提高各个解交流到优秀基因的机会, 本文对选择操作产生的新种群(除第一条染色体外的其他染色体)进行交叉操作. 本文采用的交叉操作要确保每条染色体的合理性, 不能对某两个基因或片段进行简单的交叉, 而是要按照交叉概率, 对除配送中心外的配送点片段进行交叉. 本文设计的交叉规则是将染色体i的交叉片段移到另一条染色体的尾部, 配送中心保持不变, 将染色体j的其余数依次排开, 如图3所示.

其中, 交叉概率采用自适应调节机制, 以满足在初期适应度值较大时, 需要增大交叉概率, 在适应度值趋于稳定时, 需要适当降低交叉概率. 故交叉概率采用文献[10]提出的自适应调节机制.

${p_{ci}} = \left\{ {\begin{array}{*{20}{l}} {{p_{c\max}} \!-\!\! ({p_{c\max}} \!-\! {p_{c\min}})\left( {\displaystyle\frac{g}{{2G}} \!+\! \displaystyle\frac{{{f_i} \!-\! \bar f}}{{2\left( {{f_{\max}} \!-\! \bar f} \right)}}} \right), {f_i} \ge \bar f}\\ {{p_{c\max}},{f_i} < \bar f} \end{array}} \right.$

(9)

${p_{c\max}} = \left\{ {\begin{array}{*{20}{l}} {0.9, g \leqslant G/4} \\ {0.8, G/4 < g \leqslant 3G/4} \\ {0.7, \displaystyle\frac{{3G}}{4} < g \leqslant G} \end{array}} \right.$

(10)

其中, G: 最大迭代数; g: 当前迭代数; ${f_{\max}}$ : 当前所有个体的最大适应度值.

5.4 变异操作

变异操作是为了避免求解过程陷入局部最优解, 保证染色体的多样性. 在传统的二进制编码的遗传算法中, 通常都采用直接取反的方式来进行变异; 也有的采用直接删除节点或者重新加入节点的方式来进行变异. 由于本文是采用自然数对配送点和配送中心进行编码的方式, 所以必须保证染色体的合理性, 即各染色体中编码不能重复, 故本文采取对非0点进行交换的方式来完成变异操作, 如图4所示.

5.5 适应度评估

进化论中的适应度, 表示该个体繁殖后代、适应环境的能力. 遗传算法的适应度函数也叫评价函数, 是用来判断群体中的个体的优劣程度的指标, 它是根据所求问题的目标函数来进行评估的. 对于某个个体所对应的配送路径方案, 是否满足约束条件、配送成本是否最低、配送路径总长度是否最短这三者是评价其优劣的重要指标. 根据配送路径优化问题的特点所确定自然数编码方法, 满足了每个客户点都得到配送服务且每个客户点仅由一辆汽车配送的约束条件, 但不能保证满足每条路径上各需求点需求量之和不超过汽车载重量及每条配送路线的长度不超过汽车一次配送的最大行驶距离的约束条件. 因此, 对每个个体所对应的配送路径方案, 要对各条路径逐一进行判断, 看其是否满足上述两个约束条件.

6 实例分析 6.1 实例介绍

本文以大连市某快递配送案例为原型, 编写MATLAB程序进行仿真试验, 以此验证比较传统的GA算法和本文设计的基于改进AHP-GA算法的多目标配送路径优化算法的可靠性与有效性. 配送中心为1个, 配送中心选取为辽宁省大连市甘井子区高能街128号运输管理处, 客户点选取20个不同的位置, 设其相对坐标为(0, 0), 其余20个客户点均以此配送中心为参考原点换算出的坐标距离. 其坐标分别如表1所示. 软时间窗口为8:00~17:00.

GA算法与改进AHP-GA算法选取的种群数目均为50, 进化代数为50, 种群的交叉概率参照公式(9)和公式(10), 故交叉概率初始值为0.9 , 种群变异概率为0.1, 选择同型号车辆, 设置车辆数目为3, 车辆载重量为1 t, 设置平均车速为60 km/h. 罚金成本系数 ${m_2} = 10.00$ .

6.2 实验结果

本文分别利用传统的GA算法和改进AHP-GA算法对表1中的数据执行100次得到GA优化调度成本结果如图5所示、改进AHP-GA优化调度成本结果如图6所示, 由改进AHP-GA规划路径结果如图7所示.

由仿真结果可见, 本文提出的基于时间窗的多目标快递配送路径的数学模型利用GA算法进行优化时, 当迭代到50代时, 搜索到最优值约为1152.53. 而利用改进AHP-GA算法进行优化本文提出的基于时间窗的多目标快递配送路径的数学模型, 当迭代到50代时, 搜索到最优值约为672.65. 传统的GA算法在初始种群为50, 进化代数为50时, 很难跳出局部最优解. 而在相同条件下, 本文提出的算法在设置个体种群为50时, 能够通过该算法很强的局部搜索能力跳出局部最优解, 在进化代数为50时, 能尽可能的搜索到全局最优解, 收敛效果远远优于传统的GA. 因此, 采用改进AHP-GA算法优化调度成本效果远远优于传统GA算法, 采用改进AHP-GA算法优化基于时间窗和拖期惩罚成本的多目标快递配送路径如图7所示.

7 结论

为提高物流配送效率, 控制配送成本, 提高顾客满意度, 本文提出了基于改进AHP-GA算法优化带有软时间窗的多目标快递配送路径问题. 本文利用改进的AHP方法具有科学评价快递配送路径优化问题中各层次目标权重的优势且有效改善了构建评价指标权重子集的主观性; 而改进的遗传算法具有强大的搜索能力, 自适应调节能力以及优化NP问题的能力, 本文将二者有效的结合, 有效解决了本文提出的带有软时间窗的快递配送路径多目标优化问题. 此种方法在探究物流配送路径改善方面具有显著的优势, 并能够获得理想的配送路径, 具有一定的实用价值意义. 可为物流配送优化调度问题提供参考.