ISSN 
-
带模糊时间窗的多配送中心车辆路径问题(multi-depot vehicle routing problem with fuzzy time windows, MDVRPFTW)是经典车辆路径问题(vehicle routing problem, VRP)的扩展问题之一，同样属于NP-hard问题。MDVRPFTW主要是指配送中心数量为多个，模糊化处理开始服务时间窗，加入了客户最大容忍时间窗，优化目标不仅有车辆配送的总成本，还有客户对服务时间的满意度。与传统的车辆路径问题相比，MDVRPFTW更贴合实际。随着物流运输业的兴起，车辆路径问题演化为多种类型，对于多配送中心车辆路径问题(multi-depot vehicle routing problem, MDVRP)，学者们应用不同的群智能算法寻找MDVRP的近似最优解。文献[1]设计了一种改进多蚁群算法来求解带时间窗的半开放式MDVRP，引入2-opt邻域搜索算法更新可行解并作为初始解。文献[2]设计一种混合遗传算法，并提出一种自适应搜索范围策略，为求解联合MDVRP提供一种新思路。文献[3]针对MDVRP的4个扩展问题，设计混沌遗传变邻域搜索算法、改进的蚁群算法、两阶段禁忌搜索算法求解模型。文献[4]针对带软时间窗的开放式MDVRP，提出了一种新改进的离散萤火虫算法。文献[5]针对问题和模型特点，设计了基于双层编码模式的改进遗传算法求解随机需求下带时间窗的动态MDVRP。文献[6]通过结合2-opt局部优化算法的自适应多态蚁群算法求解基于车辆共享的MDVRP。文献[7]根据MDVRP的具体特征，模拟狼群捕食行为并设计了求解该问题的狼群算法。文献[8]将基本的蚁群优化与具有快速全局搜索能力的遗传算法相结合，构成一种混合自适应蚁群优化算法解决基于VIP客户的MDVRP。文献[9]通过对遗传算法改进求解MDVRPTW，结果表明改进的遗传算法对求解此类优化问题有很大的提高。文献[10]研究了一个多车场多配送中心半开放式满载车辆路径问题，给出了该问题的数学模型和求解算法。
多元宇宙优化算法(multi-verse optimizer, MVO)是文献[11]于2016年设计的一种基于物理学中多元宇宙理论的群智能优化算法。通过模拟白洞、黑洞和虫洞之间的相互作用来完成寻优过程的数学建模。由于该算法具有框架简单、易于理解、参数较少、性能稳定、搜索效率高等优点，受到关注。但传统多元宇宙算法是针对连续问题设计的，无法直接应用于离散车辆路径问题。因此，本文提出一种离散多元宇宙算法，重新定义了对于离散车辆路径问题下的更新策略，寻找更优解。
-
模糊时间窗约束下多中心车辆路径问题可以描述为：拥有多个配送中心，车辆从配送中心出发，拥有客户最大容忍时间窗，客户点的需求量已知，需要合理的规划路径使目标函数最优。模糊时间窗约束下多中心车辆路径问题考虑如下假设：1) 配送中心到客户节点距离以及客户点之间的距离是已知的；2) 配送车辆必须以所属配送中心为起始点，任务完成后以所属配送中心为返回点；3) 每辆车可以对多个客户节点进行服务，但每个客户节点有且仅有一辆车为其服务；4) 物流配送中心和客户节点之间以及客户节点之间都是可以连通的道路；5) 客户节点货物需求量小于配送车辆的最大承载量。6) 配送路径数不能大于配送中心配送车辆总数；7) 配送车辆的到达时间不能早于和晚于客户最大容忍时间窗。
-
在MDVRPFTW中，
$P = \{ 1,2,\cdots,p\}$ 为配送中心的集合；$N = \{ 1,2,\cdots,n\}$ 为所有客户节点的集合；${K_p}$ 为配送中心p的车辆数；${K_{{\rm{total}}}}$ 为车辆总数；${q_i}$ 为客户节点$i$ 的货物需求量，$i \in N$ ；$Q$ 为配送车辆的最大容量；${c_1}$ 为单个配送车辆完成配送任务的固定费用；${c_2}$ 为单位距离的行驶成本；${c_3}$ 为由于客户不满意带来的业务损失成本；${d_{ij}}$ 为节点$i$ 到节点$j$ 之间的距离；${S_i}$ 为开始服务时间；${K_{pm}}$ 为配送中心p参与配送车辆数。本文采用的模糊时间窗[12][EET, ET, LT, ELT]相应隶属函数图像如图1所示。
图 1 梯形模糊时间窗隶属函数
多配送中心情况下的客户满意度函数[13]可把客户
$i$ 对配送服务的满意度定义为其服务开始时间的隶属度函数：$${\mu _i}({S_i}) = \left\{ \begin{aligned} & 0\;\;\;{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;S_i} \in [0,{{\rm{EET}}_i}] \\ & \left( {\frac{{{S_i} - {{\rm{EET}}_i}}}{{{{\rm{ET}}_i} - {{\rm{EET}}_i}}}} \right)\;\;\;{S_i} \in [{{\rm{EET}}_i},{{\rm{ET}}_i}] \\ & {\rm{1 }}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{S_i} \in [{{\rm{ET}}_i},{{\rm{LT}}_i}] \\ &\left( {\frac{{{{\rm{ELT}}_i} - {S_i}}}{{{{\rm{ELT}}_i} - {{\rm{LT}}_i}}}} \right)\;\;\;{S_i} \in [{{\rm{LT}}_i},{{\rm{ELT}}_i}] \\ & 0\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{S_i} \in [{{\rm{ELT}}_i}, + \infty ]{\rm{ }} \end{aligned} \right.$$ (1) MDVRPFTW具体的数学模型如下：
$$\min M = {c_1}\sum\limits_{p = 1}^P {\sum\limits_{{k_p} = 1}^{{K_{pm}}} {x_{ij}^{pk}} } + {c_2}\sum\limits_{i = 1}^{{N_p}} {\sum\limits_{j = 1}^{{N_p}} {\sum\limits_{p = 1}^P {\sum\limits_{{k_p} = 1}^{{K_{pm}}} {{d_{ij}}x_{ij}^{pk}} } } } $$ (2) $${\rm{MaxSat}} = \frac{{\displaystyle\sum\limits_{i = 1}^n {{\mu _i}\left( {{S_i}} \right)} }}{n}$$ (3) $$\min \;{M_{{\rm{total}}}} = \min \;M + {c_3}(1 - {\rm{MaxSat}})$$ (4) 式中，
$$\sum\limits_{i = 1}^{{N_p}} {\sum\limits_{j = 1}^{{N_p}} {{q_i}x_{ij}^{pk} \leqslant Q{\rm{ }}} } $$ (5) $$\sum\limits_{i = 1}^{{N_p}} {\sum\limits_{{k_p} = 1}^{{K_p}} {x_{ij}^{pk} = \sum\limits_{j = 1}^{{N_p}} {\sum\limits_{{k_p} = 1}^{{K_p}} {x_{ij}^{pk}} } = 1{\rm{ }}\;\;{\rm{ }}\forall j \in {N_p}{\rm{,}}\forall i \in {N_p}{\rm{ }}} } $$ (6) $$\sum\limits_{p = 1}^P {{K_p} \leqslant {K_{{\rm{total}}}}} $$ (7) $$\sum\limits_{i = 1}^{{N_p}} {x_{ij}^{pk} = \sum\limits_{i = 1}^{{N_p}} {x_{ji}^{pk} \leqslant 1\;\;j \in P{\rm{ }}} } $$ (8) $$x_{ij}^k \in \left\{ {0,1} \right\}\;\;\forall j \in N{\rm{,}}\forall i \in N,\forall k \in K$$ (9) 其中，式(2)表示目标函数是配送总成本的最小化；式(3)表示平均顾客满意度的最大化；式(4)表示总的优化目标为配送总成本最小化与客户不满意度最小化的和；式(5)表示车辆k的载重量不允许超过该车辆的额定载重量；式(6)表示每一个顾客点都被服务到且只被服务一次；式(7)表示使用的车辆总数不超过配送系统中所拥有的车辆数；式(8)表示车辆服务完客户后，必须返回其所出发的配送中心；式(9)表示决策变量为0-1变量。
-
多元宇宙算法[14]是2016年提出的一种新型智能优化算法。而MVO算法主要是模拟多元宇宙的种群在黑洞、白洞和虫洞共同作用下的运动行为。与其他算法相比，MVO算法主要分为探测和开采两个阶段。多元宇宙个体的位置由内部物体的运动改变。构建数学模型时，一个宇宙被视为优化问题的一个解，每个宇宙中的物体可作为相应解的分量。定义单个宇宙的膨胀率为候选解的适应度值。宇宙膨胀率，即适应度的计算方法在不同问题中有不同的定义，在本文MDVRPFTW中，适应度函数定义为总成本函数式(4)的倒数。
初始化宇宙种群U，公式如下：
$${\boldsymbol{U}} = \left[ \begin{array}{l} x_1^1\quad x_1^2\quad \cdots \quad x_1^d \\ x_2^1\quad x_2^2\quad \cdots \quad x_2^d \\ \vdots \quad \quad \vdots \quad \;\;\; \vdots \quad \;\;\;\vdots \\ x_n^1\quad x_n^2\quad \cdots \quad x_n^d \end{array} \right]$$ (10) 式中，
$d$ 表示搜索空间的维度；$n$ 表示多元宇宙个体数目；${U_i} = \left( {x_i^1,x_i^2, \cdot \cdot \cdot ,x_i^d} \right)$ 表示第$i$ 个宇宙；$x_i^j$ 表示第$i$ 个宇宙的第$j$ 个分量。MVO算法在每次迭代时首先通过轮盘赌原则，根据排序后宇宙种群的膨胀率，选择一个宇宙通过黑洞从产生白洞的宇宙中吸收物质，公式如下：
$$x_i^j = \left\{ \begin{array}{l} x_k^j\;\;{{{r}}_{\rm{1}}}{\rm{ < NI}}\left( {{U_i}} \right) \\ x_i^j\;\;{{{r}}_{\rm{1}}} \geqslant {\rm{NI}}\left( {{U_i}} \right) \end{array} \right.$$ (11) 式中，
${r_1}$ 为[0, 1]范围内随机数；$x_k^j$ 表示通过轮盘赌选择出来的第$k$ 个宇宙的第$j$ 个分量；${\rm{NI}}( {{U_i}} )$ 表示第$i$ 个宇宙的归一化膨胀率。白洞/黑洞转移是将物体从高膨胀率的宇宙发送到低膨胀率的宇宙中。因此在整个迭代过程中，宇宙种群的平均膨胀率会不断提高。为了保证宇宙种群的多样性和改进宇宙个体自身膨胀率，宇宙个体会通过虫洞和最优宇宙之间进行物质传输，公式如下：
$$x_i^j = \left\{ \begin{array}{l} \left\{ \begin{array}{l} {x_j} + {\rm{TDR}} (({{\rm{ub}}_j} - {{\rm{lb}}_j}) {r_4} + {{\rm{lb}}_j})\;\;\;{r_3} < 0.5 , {r_2} < {\rm{WEP}} \\ {x_j} - {\rm{TDR}} (({{\rm{ub}}_j} - {{\rm{lb}}_j}) {r_4} + {{\rm{lb}}_j})\;\;\;{r_3} \geqslant 0.5 ,{r_2} < {\rm{WEP}}\\ \end{array} \right.\;\; \\ x_i^j\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{r_2} \geqslant {\rm{WEP}}{\rm{ }} \\ \end{array} \right.$$ (12) 式中，
${r_2}$ 、${r_3}$ 、${r_4}$ 为[0,1]范围内随机数；${{\rm{lb}}_i}$ 和${{\rm{ub}}_i}$ 指$x_i^j$ 的下限和上限；${x_j}$ 表示当前最优宇宙的第$j$ 个分量；${\rm{WEP}}$ 为虫洞存在的概率；${\rm{TDR}}$ 为物体向当前最优宇宙移动的步长。更新公式为：$${\rm{WEP}} = {{\rm{WEP}}_{\min }} + l \times \left( {\frac{{{{\rm{WEP}}_{\max }} - {{\rm{WEP}}_{\min }}}}{L}} \right)$$ (13) $${\rm{TDR}} = 1 - \frac{{{l^{1/p}}}}{{{L^{1/p}}}}$$ (14) 式中，
$L$ 为最大迭代次数；$l$ 为当前迭代次数；${{\rm{WEP}}_{\min }}$ =0.2；${{\rm{WEP}}_{\max }}$ =1；$p$ 为开发准确性，值为6。WEP在迭代过程中线性增大，保证了在迭代后期进行更多的开采。TDR在迭代过程中非线性减小，减小速率先快后慢。这是因为迭代前期选出最优宇宙的适应度不高，需要用更大的移动距离来加快开采速度，而在迭代后期，最优宇宙具有较高的适应度，所以需要减小移动距离来增加开采的精度。 -
标准多元宇宙算法只适用于在连续的解空间中寻优。但VRP的解空间是离散的，需要将MVO进行离散化，使其适用于求解车辆路径问题。
-
应用多元宇宙求解MDVRPFTW时，每个宇宙代表了一种配送方案，宇宙中的分量代表节点的编号。客户点、配送中心和车辆等节点的编号是离散且唯一的，为了便于理解和表示，用连续的自然数对节点进行编号。假设有n个配送中心，每个配送中心有ki辆车，客户数为m。具体编码解码规则如下：
首先为所有节点进行编号。配送中心的编号从0开始到n−1结束。符号0即代表第一个配送中心；配送车辆节点的编号从n开始到n+(k0+···+kn−1)−1结束。隶属于第一个配送中心的车辆的编号从n开始到n+k0−1结束，以此类推；客户点编号从n+(k0+···+kn−1)开始到n+(k0+···+kn−1)+m−1结束。每个解中只包含车辆节点和客户节点，即解的长度由配送车辆总数和客户点总数确定。然后先将配送车辆随机排列，再把客户点随机插入形成一个初始解。配送车
$i$ 的配送路径中包含的客户点为配送车$i$ 与配送车$i$ −1之间的所有客户点，并在客户点两端加上配送车$i$ 所属的配送中心编号构成完整配送路径，配送顺序即客户点排列顺序。例如有n=2，k0=2，k1=2，m=7，则初始编码为：
其中编号为2,3的配送车辆属于0号配送中心，编号为4,5的配送车辆属于1号配送中心。随机顺序为：
则所有配送路径为：{0, 8, 10, 11, 12, 0}, {1, 6, 1}, {1, 7, 9, 1}。
通过配送车辆的编号可推出所属的配送中心，配送车辆在解中的位置可推出该配送车的配送路径，所以目标函数值的计算不会受乱序的影响。同时每一辆配送车辆的配送路径由一段连续片段指定，给邻域搜索策略的设计提供了思路。
-
1) 白洞/黑洞转移
在标准多元宇宙算法中，对于
${U_i}$ 的第$j$ 个分量，如果随机数${r_1}$ 小于${U_i}$ 的归一化膨胀率，则用${U_k}$ 的第$j$ 个分量取代${U_i}$ 的第$j$ 个分量。但这种更新方式在车辆路径问题中会使更新后的解不合法，因为节点编号是唯一的。对于离散车辆路径问题，在${U_i}$ 的第$j$ 个分量更新后，需要与对应的分量进行交换，以保证解的合法性，具体操作如下：
2) 向最优宇宙移动
在标准多元宇宙中，通过向最优宇宙移动来保持群多样性和激发每个宇宙的膨胀率。但标准多元宇宙中的移动距离为实数，不适用于车辆路径问题。所以将移动距离取整。如果
${U_i}$ 的第$j$ 个分量更新后的值超出了最大节点编号，则将其置为最大节点编号。为了保证解的合法性，需要在更新后对解进行调整。离散后的向最优宇宙移动公式如下：$$x_i^j = \left\{ \begin{aligned} & \left\{ \begin{aligned} &{x_j} + \left\lceil {{\rm{TDR}} (({{\rm{ub}}_j} - {{\rm{lb}}_j}) {r_4} + {\rm{l}}{{\rm{b}}_j})} \right\rceil \;\;{r_3} < 0.5 , \;\;{r_2} < {\rm{WEP}}\\ & {x_j} - \left\lceil {{\rm{TDR}} (({{\rm{ub}}_j} - {{\rm{lb}}_j}) {r_4} + {\rm{l}}{{\rm{b}}_j})} \right\rceil \;\;{r_3} \geqslant 0.5 , \;\;{r_2} < {\rm{WEP}}\\ \end{aligned} \right. \\ & x_i^j\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\;{r_2} \geqslant {\rm{WEP}} \end{aligned} \right.$$ (15) -
在标准多元宇宙的离散化中，白洞/黑洞转移过程中直接用
$U_k^j$ 替换$U_i^j$ ，这种策略会导致$U_i $ 过快地被${U_k}$ 同化，使宇宙种群早熟收敛。在向最优宇宙移动过程中，没有在最优宇宙的邻域进行搜索，导致更新后宇宙与最优宇宙整体相差过多，无法达到激发自膨胀率的目的。针对以上问题，多元宇宙更新规则如下： -
首先定义宇宙交换物体的原子操作。无论是白洞黑洞转移还是向最优宇宙移动，都是基于原子操作。本文将原子操作分为3种：交换、插入和反转。
1)交换操作
在配送方案中随机选取两个节点
$i$ 、$j$ 进行交换：
2) 插入操作
在配送方案中随机选取两个节点
$i$ 、$j$ ，将节点$j$ 插入到节点$i$ 之后：
3) 反转操作
在配送方案中随机选取两个节点
$i$ 、$j$ ，将节点$i$ 到节点$j$ 之间的所有节点反转：
-
为了改善宇宙种群早熟收敛，在
${U_k}$ 向${U_i}$ 传输物质时不用直接替换，而是利用随机策略，使得${U_i}$ 在概率上会逐步接近${U_k}$ 。具体来说，如果随机数r1<${\rm{NI}}({U_i})$ ，则遍历${U_k}$ 与${U_i}$ 的所有分量，直到遇到第一个不同的分量$U_i^j$ 时停止，然后在$U_i^{j + 1}$ 到${\rm{length}}({U_i})$ 中随机选择一个分量$U_i^r$ ，对$U_i^j$ 和$U_i^r$ 执行原子操作。以反转操作为例，具体过程如下：
-
为保证在最优解的邻域进行开发，结合2.2.1节的编码方式，设计新的邻域搜索机制。在
${U_{{\rm{best}}}}$ 中随机选择一个配送车辆，并在其配送路径中随机选择两个顾客节点进行原子操作，如果更新后解的膨胀率比${U_i}$ 大，则将${U_i}$ 替换掉。以交换操作为例，具体过程如下：
其中{8, 10, 11, 12}是编号为3的配送车的配送路径。
-
1) 初始化多元宇宙种群，初始化
${{\rm{WEP}}_{\min }}$ 、${{\rm{WEP}}_{\max }}$ 、开发精度$p$ 、最大迭代次数${\rm{MaxIter}}$ 、当前迭代次数${\rm{CurIter}}$ 等参数；2) 计算每个宇宙个体的适应度，宇宙个体归一化膨胀率
${\rm{NI}}(U)$ ，用轮盘赌机制选择一个宇宙个体${U_k}$ ；3) 遍历每一个宇宙个体
${U_i}$ ，计算${\rm{WEP}}$ 和${\rm{TDR}}$ ，生成随机数${r_1}$ 、${r_2}$ ；4) 如果
${r_1}$ <${\rm{NI}}({U_i})$ ，则根据白洞/黑洞转移规则生成$U_i'$ 。比较${U_i}$ 和$U_i'$ 的膨胀率，取较大者替代${U_i}$ 。如果${r_1}$ ≥${\rm{NI}}({U_i})$ 则执行下一步；5) 如果
${r_2}$ <${\rm{WEP}}$ ，则根据向最优宇宙移动的规则生成$U_i'$ 。比较${U_i}$ 和$U_i'$ 的膨胀率，取较大者替代${U_i}$ 。如果${r_2}$ ≥${\rm{WEP}}$ 则执行下一步；6) 比较
${U_i}$ 和当前最优宇宙${U_{{\rm{best}}}}$ 的膨胀率，取较大者替代${U_{{\rm{best}}}}$ ；7) 如果达到最大迭代次数，输出最优解，算法结束；否则，返回步骤2)。
-
本文使用Solomon数据集[15]对标准多元宇宙算法(MVO)、鲸鱼算法(whale optimization algorithm, WOA)[16]、海鸥算法(seagull optimization algorithm, SOA)[17]、粒子群算法(particle swarm optimization, PSO)[18]、飞蛾扑火算法(moth-flame optimization, MFO)[19]、灰狼优化算法(grey wolf optimization, GWO)[20]以及本文提出的离散多元宇宙算法(discrete multi-verse optimizer, DMVO)进行了对比实验。由于Solomon标准数据集的时间窗为硬时间窗且只有一个配送中心，所以对Solomon数据集进行了扩展。配送中心数目增加至3，另新增了左、右容忍时间窗。考虑到顾客对于不同货物的期望服务时间窗不同，其最大容忍程度也不尽相同，设置顾客可提前接受服务的时间窗
$[{{\rm{EET}}_i},{{\rm{ET}}_i})$ 和顾客可延迟接受服务的时间窗$({{\rm{LT}}_i},{{\rm{ELT}}_i}]$ 分别为顾客期望接受服务的时间窗$[{{\rm{ET}}_i},{{\rm{LT}}_i}]$ 的一半，能更加客观地描述实际顾客的等待情况。容忍时间窗按如下公式得出：$${{\rm{EET}}_i} = \max \left\{ {0,{{\rm{ET}}_i} - \frac{{{{\rm{LT}}_i} - {{\rm{ET}}_i}}}{2}} \right\}$$ (16) $${{\rm{ELT}}_i} = {{\rm{LT}}_i} + \frac{{{{\rm{LT}}_i} - {{\rm{ET}}_i}}}{2}$$ (17) 式中，EET为左容忍时间窗；ELT为右容忍时间窗；ET为左时间窗；LT为右时间窗。
实验中的最大迭代次数为2 000，种群数量为300。表1为各个算法在Solomon数据集上的总成本对比结果。总成本为固定成本、距离成本与时间惩罚成本之和。为了避免不同初始化对算法造成的影响，随机生成了10组初始种群，取10组数据的平均值作为对比结果。
表 1 实验结果
算例 总成本 DMVO MVO PSO SOA WOA GWO MFO C101 5896 6425 9958 7334 8607 9994 10001 C102 4576 5114 8250 5886 7114 8289 8311 C103 3606 4117 6847 4798 5801 6861 6906 C201 9275 9823 12237 10354 11144 12243 12252 C202 7280 7746 10084 8308 9029 10138 10162 C203 5268 5541 8028 6263 6989 8033 8025 R112 1233 1261 5365 2625 3814 5302 5346 R201 4880 5236 9238 6274 7296 9195 9293 R202 3997 4308 7770 5246 6220 7750 7868 R203 3160 3553 6249 4130 4989 6308 6250 R205 4251 4802 9024 5851 7041 9149 9171 R207 2924 3341 6163 3941 4789 6256 6288 RC108 1508 1592 6617 3287 5370 6603 6647 RC201 5363 5773 10012 6927 8336 10053 10070 RC202 4442 4862 8588 5803 7105 8595 8599 RC203 3572 3925 7177 4739 5852 7177 7172 RC208 3855 4356 8690 5422 6883 8702 8720 通过表1结果可以看出，改进后的离散多元宇宙算法在求解带模糊时间窗的多配送中心车辆路径问题时，与MVO相比结果更优。而MVO总成本普遍优于PSO、SOA、WOA、GWO和MFO算法。为了直观地展示迭代过程中成本的变化情况，下面以Solomon数据集中的C101、C102、R205、R207、RC202、RC208为例，展示总成本和用户满意度在迭代过程中的变化曲线图。
通过图2～图13可以看出，总成本和客户满意度随着迭代次数的增加都在不断得到优化。由于在迭代过程中要综合考虑成本与客户满意度，导致图像曲线出现波动。但随着迭代次数的增加，结果达到平衡，整体损失趋于收敛。
图 2 C101总成本迭代图
图 3 C102总成本迭代图
图 4 R205总成本迭代图
图 5 R207总成本迭代图
DMVO与MVO相比，在迭代前期收敛速度略低。这是因为对于求解MDVRPFTW，MVO算法在向最优宇宙移动时，
${U_i}$ 的第$j$ 个分量有可能变为任一分量。而改进后的DMVO在向最优宇宙移动时，分量变化被限定在某个配送车的配送路径中，相当于在最优宇宙的邻域进行搜索。在迭代前期，随机搜索有助于MVO可以快速跳出局部最优，收敛较快。而改进后的DMVO由于前期的最优宇宙的适应度不高，在其邻域难以搜索到更优解，导致收敛较慢。但随着迭代进行，最优宇宙的适应度逐渐提高，最优宇宙邻域搜索的优势逐渐大于随机搜索，所以改进后的DMVO具有更强的寻优能力。
图 6 RC202总成本迭代图
图 7 RC208总成本迭代图
图 8 C101满意度迭代图
图 9 C102满意度迭代图
图 10 R205满意度迭代图
图 11 R207满意度迭代图
图 12 RC202满意度迭代图
图 13 RC208满意度迭代图
为了确定不同配送中心数目和客户节点数对各个算法的影响，将Solomon数据集进一步扩展，生成了一组新数据集。新数据集的配送中心数目和客户节点数分别为(3, 50)、(3, 80)、(3, 200)、(1, 100)、(5, 100)、(10, 100)。以C101，C201，R201，R202，RC208为例，各算法在新数据集上的对比结果如下。
通过表2和表3可以看出，在不同配送中心数目和不同客户节点数目的情况下，改进后的离散多元宇宙算法的寻优能力都优于标准MVO、PSO、SOA、WOA、GWO和MFO等算法，证明了DMVO在求解MDVRPFTW问题时具有很好的鲁棒性。
表 2 不同客户点实验结果
算例 总成本(3个配送中心) DMVO MVO PSO SOA WOA GWO MFO 50个客户点 C101 4262 4813 7713 4998 5878 7877 7723 C201 8200 8727 10212 8565 8988 10365 10212 R201 3023 3085 6792 3579 4642 6815 6742 R202 2154 2468 5571 2818 3822 5037 5299 RC208 2221 2359 6333 2792 4009 6264 6449 80个客户点 C101 5160 5897 9512 6421 7717 9477 9608 C201 8585 9184 11450 9360 10045 11383 11473 R201 3831 4358 8389 5293 6565 8654 8441 R202 3289 3819 7386 4565 5627 7414 7013 RC208 3245 3732 7849 4559 6119 8305 8024 200个客户点 C101 10253 10477 61255 13026 14273 61688 62803 C201 12051 12212 58295 15031 16294 61071 67162 R201 8810 9284 18387 11302 11866 18198 20889 R202 8387 8788 19781 10847 11729 19713 21970 RC208 8367 8771 29619 11658 12678 28118 30348 表 3 不同配送中心实验结果
算例 总成本(100个客户点) DMVO MVO PSO SOA WOA GWO MFO 1个配送中心 C101 5850 6434 15615 7219 8068 16170 15915 C201 9488 9951 17183 10283 10848 19072 17867 R201 4700 5364 8576 6157 6923 8425 8489 R202 4065 4396 7326 5183 5718 7101 7506 RC208 4002 4439 8726 5395 6299 9722 9802 5个配送中心 C101 5747 6391 10934 7539 8624 10988 11032 C201 9250 9806 12907 10436 11200 12912 13085 R201 4812 5197 9919 6441 7348 10134 9679 R202 4143 4266 8464 5525 6549 8526 8394 RC208 3772 4513 9734 5684 7017 9924 10118 10个配送中心 C101 5720 6276 10853 7980 8917 11684 11103 C201 9338 9925 13759 10652 11360 13494 13457 R201 4956 5247 10627 6902 7540 10354 9507 R202 4144 6177 8857 5873 6657 8644 8324 RC208 4002 4319 10238 6240 7273 10420 10189 -
本文在解决模糊时间窗约束下的多配送中心车辆路径问题时，以总成本最低、顾客满意度最大为多目标函数，构建出相应的模型。将连续多元宇宙进行了离散化，并改进了多元宇宙的更新策略。通过离散多元宇宙算法来求解Solomon数据集中部分算例，更具有参考价值。而对于车辆路径问题，仍然有很多不确定因素，接下来将继续研究多元宇宙算法在其他车辆路径问题上的应用。
Solving Vehicle Routing Problem with Fuzzy Time Window Based on Discrete Multiverse Algorithm
-
摘要: 针对现实生活中车辆配送的实际情况以及客户对服务时间的具体要求，该文提出了一种离散多元宇宙算法来求解在模糊时间窗约束下的多配送中心车辆路径问题(MDVRPFTW)。以总成本最低、顾客满意度最大为多目标函数，针对MDVRPFTW构建出相应的数学模型。该算法在传统多元宇宙算法基础上，重新定义了在离散车辆路径问题下的更新策略。实验结果表明，该算法能更好地解决在模糊时间窗约束下的多配送中心车辆路径问题，优于其他几种对比算法，具有较强的寻优能力和应用价值。
-
关键词:
- 离散多元宇宙算法 /
- 模糊时间窗 /
- 多配送中心车辆路径问题 /
- 多目标
Abstract: Aiming at the actual situation of vehicle distribution in real life and the specific requirements of customers for service time, this paper proposes a discrete multiverse algorithm to solve the multi-depot vehicle routing problem with fuzzy time windows (MDVRPFTW) under the constraint of fuzzy time windows. Taking the lowest total cost and the largest customer satisfaction as the multi-objective function, a corresponding mathematical model is constructed for MDVRPFTW. Based on the traditional multiverse algorithm, this algorithm redefines the update strategy under the discrete vehicle routing problem. The experimental results show that the algorithm can better solve the vehicle routing problem of multiple distribution centers under the fuzzy time window constraint, and the result is better than other comparison algorithms, which proves that it has a strong optimization ability and practical application value. -
表 1 实验结果
算例 总成本 DMVO MVO PSO SOA WOA GWO MFO C101 5896 6425 9958 7334 8607 9994 10001 C102 4576 5114 8250 5886 7114 8289 8311 C103 3606 4117 6847 4798 5801 6861 6906 C201 9275 9823 12237 10354 11144 12243 12252 C202 7280 7746 10084 8308 9029 10138 10162 C203 5268 5541 8028 6263 6989 8033 8025 R112 1233 1261 5365 2625 3814 5302 5346 R201 4880 5236 9238 6274 7296 9195 9293 R202 3997 4308 7770 5246 6220 7750 7868 R203 3160 3553 6249 4130 4989 6308 6250 R205 4251 4802 9024 5851 7041 9149 9171 R207 2924 3341 6163 3941 4789 6256 6288 RC108 1508 1592 6617 3287 5370 6603 6647 RC201 5363 5773 10012 6927 8336 10053 10070 RC202 4442 4862 8588 5803 7105 8595 8599 RC203 3572 3925 7177 4739 5852 7177 7172 RC208 3855 4356 8690 5422 6883 8702 8720 
下载: 导出CSV
表 2 不同客户点实验结果
算例 总成本(3个配送中心) DMVO MVO PSO SOA WOA GWO MFO 50个客户点 C101 4262 4813 7713 4998 5878 7877 7723 C201 8200 8727 10212 8565 8988 10365 10212 R201 3023 3085 6792 3579 4642 6815 6742 R202 2154 2468 5571 2818 3822 5037 5299 RC208 2221 2359 6333 2792 4009 6264 6449 80个客户点 C101 5160 5897 9512 6421 7717 9477 9608 C201 8585 9184 11450 9360 10045 11383 11473 R201 3831 4358 8389 5293 6565 8654 8441 R202 3289 3819 7386 4565 5627 7414 7013 RC208 3245 3732 7849 4559 6119 8305 8024 200个客户点 C101 10253 10477 61255 13026 14273 61688 62803 C201 12051 12212 58295 15031 16294 61071 67162 R201 8810 9284 18387 11302 11866 18198 20889 R202 8387 8788 19781 10847 11729 19713 21970 RC208 8367 8771 29619 11658 12678 28118 30348
下载: 导出CSV
表 3 不同配送中心实验结果
算例 总成本(100个客户点) DMVO MVO PSO SOA WOA GWO MFO 1个配送中心 C101 5850 6434 15615 7219 8068 16170 15915 C201 9488 9951 17183 10283 10848 19072 17867 R201 4700 5364 8576 6157 6923 8425 8489 R202 4065 4396 7326 5183 5718 7101 7506 RC208 4002 4439 8726 5395 6299 9722 9802 5个配送中心 C101 5747 6391 10934 7539 8624 10988 11032 C201 9250 9806 12907 10436 11200 12912 13085 R201 4812 5197 9919 6441 7348 10134 9679 R202 4143 4266 8464 5525 6549 8526 8394 RC208 3772 4513 9734 5684 7017 9924 10118 10个配送中心 C101 5720 6276 10853 7980 8917 11684 11103 C201 9338 9925 13759 10652 11360 13494 13457 R201 4956 5247 10627 6902 7540 10354 9507 R202 4144 6177 8857 5873 6657 8644 8324 RC208 4002 4319 10238 6240 7273 10420 10189
下载: 导出CSV
-
[1] 辜勇, 袁源乙, 张列, 等. 带时间窗的多中心半开放式车辆路径问题[J]. 中国机械工程, 2020, 31(14): 1733-1740. doi: 10.3969/j.issn.1004-132X.2020.14.013 GU Y, YUAN Y Y, ZHANG L, et al. Multi-depot half open vehicle routing problem with time windows[J]. China Mechanical Engineering, 2020, 31(14): 1733-1740. doi: 10.3969/j.issn.1004-132X.2020.14.013 [2] 范厚明, 徐振林, 李阳, 等. 混合遗传算法求解多中心联合配送路径问题[J]. 上海交通大学学报, 2019, 53(8): 1000-1009. FAN H M, XU Z L, LI Y, et al. Hybrid genetic algorithm for solving multi-depot joint distribution routing problem[J]. Journal of Shanghai Jiaotong University, 2019, 53(8): 1000-1009. [3] 杨翔. 多中心开放式VRP拓展问题建模及算法研究[D]. 大连: 大连海事大学, 2019. YANG X. Multi-depot open vrp expansion problem modeling and algorithm research[D]. Dalian: Dalian Maritime University, 2019. [4] 孙俊成, 李丹. 基于改进萤火虫算法的开放式车辆路径问题[J]. 数学的实践与认识, 2018, 48(4): 182-190. SUN J C, LI D. Open vehicle routing problem based on improved firefly algorithm[J]. Mathematics in Practice and Knowledge, 2018, 48(4): 182-190. [5] 朱琳. 随机需求下带时间窗的多中心动态车辆路径问题研究[D]. 大连: 大连海事大学, 2017. ZHU L. Research on multi-depot dynamic vehicle routing problem with time windows under random demand[D]. Dalian: Dalian Maritime University, 2017. [6] 文军. 基于车辆共享的多配送中心车辆路径问题研究[J]. 物流工程与管理, 2019, 41(2): 75-77. doi: 10.3969/j.issn.1674-4993.2019.02.028 WEN J. Research on multi-distribution center vehicle routing problem based on vehicle sharing[J]. Logistics Engineering and Management, 2019, 41(2): 75-77. doi: 10.3969/j.issn.1674-4993.2019.02.028 [7] 叶勇, 张惠珍. 多配送中心车辆路径问题的狼群算法[J]. 计算机应用研究, 2017, 34(9): 2590-2593. doi: 10.3969/j.issn.1001-3695.2017.09.006 YE Y, ZHANG H Z. Wolf pack algorithm for multi-depot vehicle routing problems[J]. Application Research of Computers, 2017, 34(9): 2590-2593. doi: 10.3969/j.issn.1001-3695.2017.09.006 [8] 王华, 蔡延光, 汤雅连, 等. 基于VIP客户的多配送中心车辆路径问题的优化[J]. 广东技术师范学院学报, 2015, 36(2): 55-60. WANG H, CAI Y G, TANG Y L, et al. Optimization of multi-distribution center vehicle routing problem based on VIP customers[J]. Journal of Guangdong Polytechnic Normal University, 2015, 36(2): 55-60. [9] 高珊珊. 改进遗传算法在多配送中心VRPTW中的应用[D]. 兰州: 兰州财经大学, 2015. GAO S S. Application of improved genetic algorithm in vrptw of multiple distribution centers[D]. Lanzhou: Lanzhou University of Finance and Economics, 2015. [10] 孙蕊. 多车场多配送中心满载车辆路径问题研究[D]. 沈阳: 沈阳师范大学, 2016. SUN R. Research on fully loaded vehicle routing problem with multiple depots and multiple distribution centers[D]. Shenyang: Shenyang Normal University, 2016. [11] MIRJALILI S, MIRJALILI S M, HATAMLOU A. Multi-verse optimizer: A nature-inspired algorithm for global optimization[J]. Neural Computing & Applications, 2016, 27(2): 495-513. [12] 程凯. 考虑碳排放的带模糊时间窗约束的冷链配送路径优化研究[D]. 杭州: 浙江工业大学, 2017. CHENG K. Research on cold chain distribution route optimization with fuzzy time window constraints considering carbon emissions[D]. Hangzhou: Zhejiang University of Technology, 2017. [13] 闫芳, 王媛媛. 多模糊时间窗车辆路径问题的建模及求解[J]. 交通运输系统工程与信息, 2016, 16(6): 182-188. doi: 10.3969/j.issn.1009-6744.2016.06.028 YAN F, WANG Y Y. Modeling and solving the vehicle routing problem with multiple fuzzy time windows[J]. Transportation System Engineering and Information, 2016, 16(6): 182-188. doi: 10.3969/j.issn.1009-6744.2016.06.028 [14] 刘京昕. 多元宇宙优化算法的改进及应用[D]. 南宁: 广西民族大学, 2019. LIU J X. Improvement and application of multiverse optimization algorithm[D]. Nanning: Guangxi University for Nationalities, 2019. [15] QI Y, HOU Z, LI H, et al. A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows[J]. Computers and Operations Research, 2015, 62(C): 61-77. [16] MIRJALILI S, LEWIS A. The whale optimization algorithm[J]. Advance in Engineering Software, 2016, 95: 51-67. doi: 10.1016/j.advengsoft.2016.01.008 [17] DHIMAN G, KUMAR V. Seagull optimization algorithm: Theory and its applications for large-scale industrial engineering problems[J]. Knowledge-Based Systems, 2019, 165(1): 169-196. [18] YANG X S. A new metaheuristic bat-inspired algorithm[J]. Computer Knowledge & Technology, 2010, 284: 65-74. [19] 金嘉毅. 改进的飞蛾扑火算法研究[D]. 阜新: 辽宁工程技术大学, 2019. JIN J Y. Research on improved moth suppression algorithm[D]. Fuxin: Liaoning Technical University, 2019. [20] 王习涛. 一种优化局部搜索能力的灰狼算法[J]. 计算机时代, 2020, 12(3): 53-55. WANG X T. A gray wolf algorithm with optimized local search ability[J]. Computer Times, 2020, 12(3): 53-55. -
点击查看大图
图(13) / 表(3)
计量
- 文章访问数: 4312
- HTML全文浏览量: 1463
- PDF下载量: 66
- 被引次数: 0
