多车场车辆路径问题

2024-07-17

多车场车辆路径问题（精选3篇）

多车场车辆路径问题篇1

多车场车辆路径问题 (Multi-depot Vehicle Routing Problem, MDVRP) 是由车辆路径问题 (Vehicle Routing Problem, VRP) 衍生而来, 其将经典车辆路径问题中单个车场扩展为多个车场。MDVRP所要解决的是确定顾客由哪个车场服务及被访问的路径, 使总行驶路径最短。MDVRP广泛存在于多个行业之中[1], 对其研究不仅具有实际的应用价值, 更是研究供应链集成与协调的基础。由于MDVRP是NP难问题, 只有在顾客数目较小的时候才能得到精确解, 更多时候需要借助于启发式算法[2,3,4,5]求解, 如何有效求解该问题成为关注的焦点。目前国外学者对该问题研究相对较多, Chao等采用多阶段启发式来求解, 其首先使用简单启发式生成初始解, 然后通过将顾客移动到不同车场对初始解进行改进[6]。Renaud等采用4-opt*、λ交换等交换技术设计了三种基本搜索过程在禁忌搜索算法的各个阶段组合使用, 求解带能力约束及路径长度约束的多车场车辆路径问题, 该算法采用Benchmark问题测试, 部分结果为目前最好解[1]。Pisinger等提出了自适应大规模邻域搜索启发式, 求解包括MDVRP在内的五种不同车辆路径问题, 该算法更新了采用Benchmark问题测试得到的十五个目前最好解[7]。尽管如此, 不同的求解算法仍在不断地被尝试, 如何有效求解MDVRP依然是研究该问题的重要方向。国内学者针对该问题研究相对较少, 仅少数几个算法如遗传算法[8,9]、禁忌搜索[10]和蚁群算法[11]被提出, 且大部分文献只对随机生成的小规模问题进行测试, 很少采用Benchmark问题数据集测试, 不能很好地反映算法的求解效果。

分散搜索算法 (Scatter Search, SS) 是新近应用于求解组合优化和非线性优化问题并取得较好效果的亚启发式算法[12]。一些学者已经成功地将该算法应用到求解VRP问题中[13,14]。分散搜索算法框架灵活, 很容易和其他算法结合, 使得对解空间搜索更加有效。文献[14]的实验结果也证明该算法可以和目前求解该问题的最好亚启发式相媲美。但国内外采用分散搜索算法求解不同类型的VRP问题非常少见, 有鉴于国内目前对MDVRP的研究现状及分散搜索算法求解VRP相关问题的研究进展, 本文尝试采用分散搜索算法求解MDVRP。

1 MDVRP数学模型

1.1 问题描述及假设

在一个分销网络中, 某供货商拥有M个仓库为 N个零售商供应某一种商品, 每个仓库拥有一定数目的车辆, 被称为车场;零售商则可以看成要被服务的顾客点。若采用图来进行描述, 则假设G= (V, A) 为该分销网络, 其中顶点集V包括Vc和Vd两个集合, Vc={v1, v2, …, vN}表示顾客点集;Vd={vN+1, vN+2, …, vN+M}表示车场集合;弧集A={ (vi, vj) |vi, vj∈V, i≠j}为任意两点间的边。距离

矩阵D= (Dij) 为边 (vi, vj) 的长度, 假设D对称, 并且任意三点之间的距离满足三角不等式, 距离单位为公里。每个车场具有K辆同样型号、载重量为Q 吨的车辆, 每个车场的车辆数目都足够满足运输需求。每个顾客的需求为Qi吨 (i=1, 2, …, N) 且假设 Qi<Q.

MDVRP中车辆运行路径需要满足:①从某个车场出发的每辆车, 服务一些顾客点后, 必须回到出发车场;②每个顾客点都必须仅被一辆车访问且只访问一次;③每辆车的载重量不能超过该车的容量限制;④车辆不能从一个车场到另一个车场, 且路径中不能出现回环。

MDVRP需要解决的是如何将顾客划分到合适的车场并安排其访问路径, 使整个网络的运输距离最小。其中xpkij为决策变量, 当满足车场p的车辆k存在从i到j的路径 (i, j∈V) 时取1, 其他情况取0。

1.2 数学模型

本文基于文献[8]中的数学模型, 对MDVRP问题进行描述。该模型的目标函数如下:

$\min d i s = \sum_{i = 1}^{Ν + Μ} \sum_{j = 1}^{Ν + Μ} D_{i j} \sum_{p = 1}^{Μ} \sum_{k = 1}^{Κ} x_{i j}^{p k} (1)$

其约束条件具体如下:

$\begin{array}{l} \sum_{i = 1}^{Ν} Q_{i} \sum_{j = 1}^{Ν + Μ} x_{i j}^{p k} \leq Q, \\ p \in {1, 2, \dots, Μ}, k \in {1, 2, \dots, Κ} (2) \\ \sum_{j = 1}^{Ν + Μ} \sum_{p = 1}^{Μ} \sum_{k = 1}^{Κ} x_{i j}^{p k} = 1, i \in {1, 2, \dots, Ν} (3) \\ \sum_{i = 1}^{Ν + Μ} \sum_{p = 1}^{Μ} \sum_{k = 1}^{Κ} x_{i j}^{p k} = 1, j \in {1, 2, \dots, Ν} (4) \\ \sum_{j = 1}^{Ν} x_{i j}^{p k} = \sum_{j = 1}^{Ν} x_{j i}^{p k} \leq 1, \\ i \in {Ν + 1, Ν + 2, \dots, Ν + Μ}, \\ k \in {1, 2, \dots, Κ}, p \in {1, 2, \dots, Μ} (5) \\ \sum_{j = Ν + 1}^{Ν + Μ} x_{j i}^{p k} = \sum_{j = Ν + 1}^{Ν + Μ} x_{i j}^{p k} = 0, \\ i \in {Ν + 1, Ν + 2, \dots, Ν + Μ} \\ k \in {1, 2, \dots, Κ}, p \in {1, 2, \dots, Μ} (6) \\ \sum_{i \in S} \sum_{j \in S} x_{i j}^{p k} \leq | S | - 1, \forall S \subseteq V_{c}, 2 \leq | S | \leq n \\ p \in {1, 2, \dots, Μ}, k \in {1, 2, \dots, Κ} (7) \\ x_{i j}^{p k} = {0, 1}, \forall i, j \in {1, 2, \dots, Ν + Μ}, \\ p \in {1, 2, \dots, Μ}, k \in {1, 2, \dots, Κ} (8) \end{array}$

式 (1) 为目标函数, 最小化总的行驶距离;式 (2) 为车辆的容量限制;式 (3) 、式 (4) 保证每个顾客点只能被一辆车访问一次;式 (5) 确保任何车场的任一从该车场出发的车辆, 服务结束后返回该车场;式 (6) 使得车场与车场之间不存在路径;式 (7) 为排除子环约束;式 (8) 为决策变量的取值约束。

2 求解MDVRP的分散搜索算法

2.1 分散搜索算法框架及执行过程

分散搜索算法是由Glover于1977年提出的, 直到近些年该算法才被应用于求解车辆路径问题、图着色问题、调度问题等组合优化和非线性优化问题中。分散搜索算法基础源于最初用来求解组合决策规则和约束的策略, 属于一种通过组合其他解来构造解的基于种群的算法[15]。分散搜索算法具有统一的框架, 便于算法设计与实现, 框架中包括五种方法[16]:

①多样性产生方法:采用任意的一个临时解作为输入, 产生一个多样性的待选解集。

②改进方法:将一个待选解变换为一个或多个改进解。在分散搜索算法中无论是待选解还是改进解都可以是不可行解。若一个待选解没有被改进, 那么认为改进解为该待选解。

③参考集更新方法:建立和维持由b个 (通常b的取值很小, 例如b不超过20) “最好”解组成的参考集。从目标值来看, 一个“最好”解需要具有较高的质量;从多样性角度看, 即使该解的目标值较差, 但其具有较好的多样性, 那么该解仍然作为“最好”解。

④子集产生方法:作用在参考集上, 用来构建不同类型的参考集子集, 所有子集作为产生新待选解集的基础。

⑤解组合方法:将采用子集产生方法生成的子集通过设计的规则组合成一个或者多个新解。

分散搜索算法的求解过程如图1所示, 首先采用多样性产生方法生成待选解集并采用改进方法对待选解集中的解进行改进;其次在改进后的待选解集中选择一些高质量的和具有较好多样性的解建立参考集;然后在参考集的基础上采用子集产生方法生成子集;接下来将子集中的解采用解组合方法进行组合, 生成新解并采用改进方法改进新解;最后按照参考集更新方法判断改进后的新解能否更新参考集, 如果参考集被更新, 则进行新的搜索, 否则搜索过程结束。

分散搜索算法框架中的五种方法需要根据问题进行设计与实现, 这使得分散搜索算法具有很好的灵活性。不同于遗传算法等其他种群算法, 分散搜索算法种群规模即参考集中解的个数相对较小, 并且分散搜索算法以系统的方法选择解进行组合生成新解, 而不同于遗传算法对随机性有较强的依赖性。

2.2 分散搜索算法解编码

与其他基于种群的算法一样, 分散搜索算法首先需要对解进行编码, 然后按照算法实现步骤进行计算。在文献[8]的基础上设计了基于顾客的编码方式, 如图2所示。每个解包含n项, 对应于n个顾客点;其中每一项包含四个部分:顾客点号;服务顾客的车辆所属的车场号;服务顾客的车辆号;顾客在每条路径中的访问顺序。当解确定后, 一个顾客点i被访问的信息则可根据这四部分确定, 如图2中顾客点1被第4个车场的第2辆车第3个服务。该编码方式没有显性地给出路径, 但是通过依次对解的车场、车辆号及访问顺序进行排序, 则能得到路径。

2.3 多样性产生方法

分散搜索算法通过具有较好多样性的解来进一步扩大对解空间的搜索。为了提高待选解的质量及多样性, 基于扫描算法和最优划分过程设计了多样性产生方法产生待选解集。

该方法包括四步:①将顾客点分配给距离该顾客点最近或次近的车场, 即先设定一个顾客点与最近车场及次近车场距离的比值γ, 若超过该比值则随机分配到最近车场或次近车场, 若小于该比值则分配到最近车场;②令每个车场生成一个初始访问顺序, 即首先从划分到该车场的顾客点中随机选取一个作为起始点, 然后采用扫描算法进行排序, 生成一个初始的访问顺序;③分别对不同车场的初始访问顺序进行最优划分[17], 生成该访问顺序的最优车辆分配方案;④将所有车场生成的访问方案组合生成一个包含所有顾客点的初始解。

由该方法生成的初始解均为可行解, 将该过程重复运行p次 (p为待选解集的大小) , 其中保证每次随机初始点的选取均不重复, 以满足多样性要求, 将生成的待选解集记为P.

2.4 解改进方法

算法的解改进方法可以处理可行解及不可行解, 并产生一个改进解。

定义1 结构可行解:满足路径约束:①每个顾客点都必须仅被一辆车访问且只访问一次;②车辆起始于同一车场;③车辆不能从车场到车场, 且路径中不能出现回环;的解称为结构可行解。

本分散搜索算法中多样性产生方法生成的解均为可行解, 而通过组合方法生成的解中可能存在部分路径违反车辆能力约束仅为结构可行解。因此解改进方法对不可行解的可行化过程是对违反能力约束路径中的点作移出插入操作, 使每条路径满足能力约束。移出插入操作基于启发式, 其主要思想是从违反能力约束的路径中顺序移出插入代价最大的点, 直到满足能力约束为止。然后将这些移出的点插入到不违反能力约束前提下插入代价最小的位置。若不存在这样的位置, 则将所有不能插入的点采用最优划分方法构成新的路径。

解改进方法对可行解进行改进的主要思想是将2-交换[18]、2-交换*[18]及最坏移出-预测插入启发式[7]三种局部搜索策略相结合构成迭代下降算法对解进行改进。局部搜索策略速度快, 具有良好的局部寻优能力, 可以使分散搜索算法在不同搜索空间中获得更满意的解, 且三种算法均简单易行, 降低了算法的复杂性。

2.5 参考集更新方法

参考集更新方法包括建立初始的参考集和更新参考集两部分。

(1) 初始参考集构建

通常参考集Refset包括两个子集, 具有b1个高质量解的子集Refset1和具有b2个较好多样性的子集Refset2。首先从p个待选解中选择b1个目标函数值最好的解构成Refset1。其次根据问题拓征定义两个解之间的距离, 选择多样性解构建Refset2。

定义2 两个解之间的距离:设解X1含有E1条边, X2含有E2条边, 两个解共有Ec条公共边, 则两个解之间的距离公式为 $1 - \frac{2 E_{c}}{E_{1} + E_{2}}$ 。

从定义2可以得出两个解之间的距离分布在[0, 1]区间内, 当两个解完全不同时, 它们之间的距离为1, 此时距离最大;当两个解完全相同的时候, 他们之间的距离最小为0。计算目前不在参考集中的其他初始解, 即P-Refset集合中的解与参考集中解之间的距离。首先将P-Refset集合中的每一个解与参考集中解之间距离的最小值选择出来, 得到|P-Refset|个最小值, 然后从这些最小值中选出一个最大值, 该最大值对应的解为选择出的多样性解[15], 将此过程重复b2次, 完成初始参考集的构建。

(2) 更新参考集

更新参考集的方法很多, 本算法采用基本的静态更新方法[19]更新参考集, 即在参考集中的解和通过组合方法产生的新解中选取b1+b2个目标函数值最好解作为新参考集。

2.6 解组合方法

在求解MDVRP时, 子集采用四种类型的子集[15], 即二元组、三元组、四元组及包含最好r个元素 (5≤r≤b) 的子集。在基本分散搜索算法中, 通过组合方法可以产生一个或者多个解, 在本算法中组合方法使每个子集产生唯一解。该解组合方法基于弧组合方法, 通过选择公共弧和高质量弧来将不同解进行组合。

为了计算方便, 解组合方法将一个解转化成与其唯一对应的 (M+N) × (M+N) 0-1矩阵A= (aij) , i, j∈1, …, M+N, 当aij为1时表示存在从i行所代表的顶点到j列所代表的顶点间的弧, 否则aij为0。如图3所示, 假设3个车场, 10个顾客点得到的访问路径如图3 (a) , 则其对应的矩阵如图3 (b) 所示, 其中矩阵左上角框中的1′, 2′, 3′代表车场。路径与矩阵的转换方法则以图3 (a) 中路径0-8-3-0为例说明。在路径0-8-3-0中, 0表示车场3, 相应的图3 (b) 中a3, 11, a11, 6, a6, 3为1, 解中的其他路径也按此方法进行转换。

解组合算法的过程可以描述如下:

步骤1. 将子集中的所有解转化成矩阵Al= (aij) , l ∈[1, num], 其中num为子集中解的个数

步骤2. 将子集中所有解转化成的矩阵相加, $A^{'} = \sum_{l = 1}^{n u m} A_{l}$

步骤3. Fori=A′的第m+1行 toA′的第m+n行

将i行中aij值最大的列选出来, 保存在变量list中

If 同时存在多个最大值 then

选择具有最大值且弧长度dij最小的列, 更新变量list

End if

将该行list中记录的列置为1, 该行其他列置为0

End For

步骤4. Forj=A′的第m+1列 toA′的第m+n列

Ifj列中任何一位都没有被设定 then

将j列中aij值最大的行选择出来, 保存在变量row中

If 同时存在多个最大值 then

选择具有最大值且弧长度dji最小的行, 更新变量row

End if

将该列row中记录的行置为1, 该列其他行置为0

Else

保持该列中已被置1的行不变, 将该列的其他行置为0

End if

End For

步骤5. Fori=A′的第1行 toA′的第m行

If $\sum_{j = m + 1}^{m + n} a_{i j} \neq \sum_{j = m + 1}^{m + n} a_{j i}$ then

If $\sum_{j = m + 1}^{m + n} a_{i j} > \sum_{j = m + 1}^{m + n} a_{j i}$ then

Do 从i行中选择弧长度最大的aij, 将该弧移动到ai+1, jWhile $(\sum_{j = m + 1}^{m + n} a_{i j} \neq \sum_{j = m + 1}^{m + n} a_{j i})$

Else

Do 从i列中选择弧长度最大的aij, 将该弧移动到ai, j+1While $(\sum_{j = m + 1}^{m + n} a_{i j} \neq \sum_{j = m + 1}^{m + n} a_{j i})$

End if

End For

步骤6. Fori=A′的第1行 toA′的第m行

Forj=A′的第m+1列 toA′的第m+n列

Ifaij=1 then

遍历路径, 并记录访问过的顾客点

If 路径的结束车场与起始车场不同 then

将路径的结束车场改为起始车场

End if

End For

步骤7. 将没有访问到的顾客点之间的弧除去, 并分别构成这些点与其距离最近的车场的路径

该解组合方法过程首先将一个子集中的所有解转化成相应的矩阵 (对应于过程中的步骤1) , 再将这些矩阵相加 (对应于过程中的步骤2) , 然后对相加后的结果矩阵采用启发式规则选择弧来产生新解。启发式规则考虑了公共边及距离因素。首先对表示顾客点的行进行操作, 使每个顾客点的出度为1, 即每行只有一个位置值为1, 其他为0 (对应于过程中的步骤3) ;其次对表示顾客点的列进行操作, 使每个顾客点入度为1即每列只有一个位置值为1, 其他为0 (对应于过程中的步骤4) ;再次调整车辆与车场的所属关系 (对应于过程中的步骤5、步骤6) ;最后确保路径中不存在子环 (对应于过程中的步骤7) 。

解组合方法得到的解具有结构可行性。在上述过程中的步骤3、步骤4保证每个顾客点只能被一辆车访问一次;步骤5、步骤6确保任何车场任一从该车场出发的车辆, 服务结束后返回该车场;步骤7使得该解不包含子环。由于子集中的解都是可行解, 显然对相加后的矩阵来说必然满足车场与车场之间不存在路径, 即图3 (b) 中方框中的元素均为0。

3 实验及分析

测试环境:采用JAVA语言对算法进行编码, 在MS windows XP;CPU:Core (TM) 2, 1.83GHz;1GB内存环境下测试。

3.1 小规模数据测试

选取近几年国内求解MDVRP问题的文献[8,9,10]数据进行测试, 其测试数据均为随机产生的小规模数据。其中M表示车场的数目, N为顾客点的数目, C为车辆的载重量。分散搜索算法中待选解集的大小为10, 参考集大小为5, b1为3, b2为2。顾客点与最近车场及次近车场距离的比值γ=1, 迭代下降算法的迭代次数为10, 结果如表1、表2所示。

* 该结果是在PⅣ2. 0上运行得到。

* 表2中文献[10]数据结果的最优路径中的A、B、C分别对应于原文献中的车场16、17、18。

表1结果显示, 采用分散搜索算法得到的解均优于文献中的解, 其在解质量方面具有一定的优势, 具体路径列于表2。文献[8]与文献[9]采用不同的遗传算法求解同一组数据的MDVRP, 得到同样的结果。由于文献[8]、[9]、[10]中未明确给出算法的计算时间, 故无法精确衡量算法的速度差异, 但是从分散搜索算法的计算时间上看, 对于15个顾客点的小规模数据其计算时间不超过2秒, 与文献[10]中所述计算时间小于10秒相比, 其计算速度相对较快。

3.2 Benchmark问题测试

为了进一步验证分散搜索算法的有效性, 从http://neo.lcc.uma.es/radi-aeb/WebVRP/中选取中大规模的Benchmark问题进行测试。该Benchmark包括11个由Christofides、Eilon[20]及Gillett、Johnson[21]提出的经典问题, 12个由Chao[6]提出的新问题。在这23个实例中有11个仅有能力约束, 另外12个为能力和距离约束。本文选取具有能力约束的11个实例进行测试, 问题参数如表3所示。算法中参数γ在[0.5, 1]范围内取值, 其他参数与小规模数据测试相同。

* GAP= (分散搜索算法最优解-Benchmark目前最优解) /Benchmark目前最优解。

从表4可以看出, 分散搜索算法得到的最优解与目前最优解之间的差距均小于5%, 大部分测试算例均稳定在1.5%左右, 其中对于数据P01和P12求得的最优解与目前Benchmark最优解相同。本文选取了多阶段启发式[6]、禁忌搜索[1]及分治蚁群算法[11]与分散搜索算法进行比较, 结果表明分散搜索算法存在等于或优于前三种算法的结果。对于P15、 P18、 P21三个大规模数据, 分散搜索算法的结果要优于多阶段启发式和分治蚁群算法。对于P04、P05、P06、P07四个中等规模的数据, 分散搜索算法的结果要优于分治蚁群算法;与多阶段启发式算法相比, 虽然分散搜索算法的解并不具优势, 但是它们之间相差并不大。对于小规模问题, 分散搜索结果要差于其他三种算法, 其中仅在P03问题上与其他三种算法结果的差距为1.28%, 而在P02问题上与其他三种算法结果的差距为0.28%。总的看来, 任何一种算法都不可能完全优于其他算法, 包括Benchmark的目前最优解也是由多种算法求得。每种算法通常只对算例中的几组数据非常有效, 这与顾客点的分布状况, 车辆的载重能力及问题的规模有很大的关系。

由于上述三种算法其最优解的求解时间并未给出, 因此并未对时间进行比较, 仅给出分散搜索算法的求解时间。从求解的时间上看, 当问题规模增大时, 其求解时间增加较快, 对于大规模问题分散搜索求解时间较长, 但该时间通常也在可以接受的范围之内;对于小规模问题其求解速度相对较快。

4 结论

设计高效的MDVRP求解算法一直是MDVRP的重要研究方向。本文提出一种分散搜索算法求解MDVRP。该分散搜索算法中各部分均采用简单启发式, 使分散搜索算法较其他算法容易理解并便于实现, 为求解多车场车辆路径问题提供了一种新的求解思路。从计算结果来看, 分散搜索算法在合理的时间内获得的解质量较好, 证明了算法对MDVRP求解的有效性。与此同时, 该分散搜索算法框架中各部分的设计思想为采用分散搜索算法求解其他类型车辆路径问题提供了参考。

多车场车辆路径问题篇2

相较于国外, 在国内, 李军、郭辉煌[14]在其书中提到该问题, 并给出了数学模型, 并运用C-W节约算法对该问题进行了求解。霍振华、王新华[15], 王兆庚、李建庚、程世东[16], 屈援、汪波、钟石泉[17], 钟石泉、贺国光[18]对带有时间窗约束的集送货一体化车辆路径问题进行了扩展, 并对其进行了求解。霍佳震、张磊[19]对集送货一体化问题进行了进一步扩展, 不再限制每项任务只有一个集货点和一个送货点, 而是每项任务必须有一个集货点和一个或多个送货点, 并对此问题运用修正的C-W算法进行了求解。相较于单车场集送货一体化问题, 李臻、雷定猷[20], 钟石泉、王雪莲[21]则将单车场扩展为多车场, 对此类集送货一体化问题建立了数学模型, 并通过表上作业法、遗传算法给出了问题的解。本文将前面文献中研究的集送货一体化车辆路径问题进行了扩展, 即将单车场情形推广到多车场, 将每个任务只有一个送货点推广到任务可以有多个送货点的情形, 如此一来, 前人文献中的算法不适用于求解本文的问题, 因此本文给出一个遗传算法对其进行求解。

1 问题描述

由多车场发车执行货运任务的开放式带有里程约束的软时间窗集送货一体化车辆路径问题, 可描述为:某物流公司有l项货运任务, 表示为1, …, l, 第i (i, =1, …, l) 项任务均由1个集货点与hi (hi, ≥1) , 个送货点组成, 这些货运任务由m个车场出发的同一种车型的车辆完成, 每个集货点、送货点均有各自的时间窗限制, 且若以 (ET, LT) 表示每个集货点、送货点的时间窗限制, 则ET表示车辆到达该点的最早时间, 后文称时间窗上限, LT表示车辆到达该点的最晚时间, 后文称时间窗下限。已知每项货运任务的货运量为gi, 车辆容量为q, 并且满足1/2q<gi<q, 每辆车均有最大里程限制, 车辆行驶的平均速度为v, 车辆完成任务后不需回到车场, 需要安排车辆及其行驶路线, 使总费用最少。

2 遗传算法设计

2.1 染色体结构

本文中的每一条染色体都是所有任务的一个排序。

2.2 初始种群的产生

设种群规模为n (n为偶数) 。

step1将各个任务中的送货点按照时间窗进行排序, 即将时间窗下限小的排在前面, 如果时间窗下限相同, 则比较时间窗上限, 时间窗上限小的排在前面;

step2保持step1中各个的任务送货点的排序不变, 将所有任务编号为1, 2, …, l, 按该编号得到所有任务的一个排序, 即为一个染色体;

step3仍然保持step1中各个的任务送货点的排序不变, 随机生成1, 2, …, l的n-1个互不相同的排列 (这n-1个排列都与1, 2, …, l的自然排列不同) , 分别按这n-1个排列生成所有任务的n-1个不同的排序, 即得n-1条互不相同的染色体。

2.3 适应值函数的确定

要确定每条染色体的适应值, 首先要将该染色体改变成问题的一个解 (即在任务之间选适当的位置插入车场) , 之后计算该解的目标函数值z, 取1/z为该染色体的适应值即可。

2.3.1 将染色体修改成问题的解

用i i=, 1, …, l, 表示第i个任务, 那么如果i1i2…il是1, 2, …, l的一个排列, 则i1i2…il就表示一个染色体, 用j j=, 1, …, m, 表示第j个车场, 下面将该染色体修改成问题的一个解。

计算各车场与第一个任务i1的集货点间的最小距离, 设di1, j1=min, di1, j|j=1, …, m, , 在任务i1前插入车场j1, 让车辆从第j1个车场出发沿着i1i2…il的顺序前进 (其中各个任务的集货点及送货点的顺序已经排好) , 若该车辆在刚好完成第ik项任务时, 行驶距离达到最大里程 (即完成第ik项任务时该车总的行程小于或等于最大里程, 但若再完成第ik+1项任务时, 总的行程就会超出最大里程) , 将任务i1i2…ik交由该车辆完成, 将任务ik+1作为第一个任务, 对ik+1ik+2…il重复上述过程, 直到所有任务都被分配车辆为止。

2.3.2 目标函数值的确定

本文问题解的目标函数值是下列三部分之和:该解中所使用车辆的启动费用之和, 所使用车辆行驶费用之和, 所使用车辆到达各个任务的取货点和送货点所产生的违法软时间窗约束的惩罚费用之和。

设c0为单位车辆的启动费用, c1为单位车辆单位里程的行驶费用, 那么, 若一个解中所有货运任务需要r辆车完成, 则该解中总的启动费用为c0*r, 设该解中所使用车辆总的行程为d, 则该解中所使用车辆行驶费用之和为c1*d。

由于本文的时间窗约束为软时间窗约束, 故采取的是加入惩罚的措施, 即:对于一个解的每一个集货点或送货点i, 若车辆在该点规定时间窗内到达, 则不惩罚;若车辆到达该点时间早于该点时间窗的上限或晚于该点时间窗的下限, 则加入惩罚, 并且早到的惩罚要小于迟到的惩罚。即:若设F表示一个解的违法软时间窗约束的总的惩罚费用, 那么:

其中:si表示车辆到达第i个点的时刻, a与b分别表示车辆早到和晚到的单位时间惩罚费用。

2.4 遗传操作

(1) 选择复制

参考刘国华、包宏、李文超[22]有关文献中的选择复制方法, 在种群中, 首先计算各个染色体的适应值, 将适应值最大和最小的两条染色体挑选出来, 让适应值最大者保留下来进入下一代种群, 之后将它们从种群中删除, 然后对种群采用轮盘赌的方法选择能够进行交叉变异的染色体。

(2) 交叉操作

首先将要进入交叉操作的种群中的染色体随机两两配对, 得到 (n-2) /2对染色体, 对这 (n-2) /2对染色体中的每一对都产生0-1间的随机数, 如果该随机数小于或等于交叉概率pc, 那么这对染色体将进行交叉操作。

在要进行交叉操作的两条染色体中, 分别任意选取两项货运任务的基因段, 进行交叉, 从而产生两条新的染色体。如果新生成的子体中存在任务缺失, 则将缺失的任务加入新生成的子体之后, 如果新生成的子体中存在任务重复, 则将重复的任务删除。为说明交叉操作, 示例如下:

两个父体:任务1→任务2→任务4→任务3→任务5→任务6

任务2→任务5→任务4→任务6→任务1→任务3

将第一条父体的基因段任务2与第二条父体的基因段任务3, 以及将第一条父体的基因段任务5与第二条父体的基因段任务2进行交叉操作, 得到下一代的两条子体:

任务1→任务3→任务4→任务2→任务6→任务5

任务5→任务4→任务6→任务1→任务3→任务2

(3) 变异操作

step1生成n-2行l列的0-1随机数矩阵, 该矩阵各个位置的元素分别对应变异种群中各个染色体相应位置的任务;

step2对变异种群中每个染色体都进行下列操作:考察该染色体中的各个任务是否满足变异条件, 即看该任务对应的随机矩阵中的元素是否小于等于变异概率pm, 如果是, 则接着考察该任务是否有多个送货点, 如果是, 则任意选取2个送货点, 将其位置进行交换即可。

2.5 遗传算法步骤

step1输入各个车场、各个任务的集货点及送货点的坐标、时间窗;各个任务货运量;单位车辆的启动费用, 单位车辆单位里程的行驶费用;交叉概率及变异概率;种群规模;迭代次数;并将次优值设为无穷大, 次优解为空。

step2产生初始种群, 种群中包括n条染色体。

step3计算种群中各个染色体的适应值, 将其中适应值最大的和最小的都挑选出来, 更新次优解和次优值, 将适应值最大者保留进入下一代种群, 之后将这两个染色体从种群中删除, 转步骤4。

step4对步骤3最后得到的种群进行遗传操作:即进行选择复制, 交叉和变异操作。

step5将步骤3中适应值最大的染色体复制两次到经过步骤4后得到的种群中, 得到新的种群。

step6判断是否达到迭代次数, 若达到迭代次数, 则算法终止;否则, 对步骤5的新种群转step3。

3 例子

现有三个车场将其编号为1、2、3, 它们的坐标依次为 (40, 60) , (55, 30) , (80, 51) , 车辆从这三个车场出发共需要完成6项货运任务, 任务信息见表1。各个车场的车型都相同, 已知每辆车的载重量为q=10, 速度v=45, 最大行驶距离为180, 启动费用及单位里程行驶费用分别设为c0=10, c1=1, 另时间窗惩罚系数:早到单位时间的惩罚费用a=4, 迟到单位时间的惩罚费用b=7, 试安排车辆行驶路线, 使总费用最小。

用4, 5, 6, 7, 8, 9依次表示任务1~6的集货点;用自然数10表示任务1的送货点, 自然数11表示任务2的送货点, 自然数12, 13分别表示任务3的第1, 2个送货点20, 6530, 45, 自然数14表示任务4的送货点, 自然数15表示任务5的送货点, 自然数16, 17, 18分别表示任务6的第1, 2, 3个送货点 (75, 29) (66.15) (85, 18) 。根据本文所提供算法, 取交叉概率pc=0.6, 变异概率pm=0.1, 经过400次迭代后, 得到问题的次优解:1→6→12→13→5→11→9→17→18→16→7→14→3→4→10→8→15其次优值为:z=286.77, 该次优解含两条路径如表2所示:

4 结论

多车场车辆路径问题篇3

关键词：突发事件,车辆路径问题,道路通畅率,模拟退火算法

一些突发事件,如地震、海啸等可能在短时间内造成通行路段的中断或拥堵,因此,正常情况下的最短路径(距离最短或者时间最短)不一定是最优的应急物资配送路线。而且,由于突发事件的不确定性,通常使得道路的一些状况,如道路的通畅性、破坏程度等都是动态的。如何选择快速、经济的应急物资配送路线把救灾物资安全地配送到灾害区域是影响应急救援效率的关键所在。

在通常情况下,将救援物资从救援点运送到受灾点的路线不止一条,但是这又取决于应急态势下车辆路径选择的原则。突发事件发生后,决策者往往选择以最短的时间,最少的成本,最安全地将应急物资送到受灾点进行紧急救助。

首先,在应急救援的条件下,时间是最宝贵的资源之一,时间是任何紧急情况下不可忽视的决策属性;其次,无论是由于地盘隆起、摇撼或者土壤液化等破坏,都将直接或者间接地造成道路中断或者道路容量的降低。因此,在选择车辆路径时,必须考虑灾害造成建筑物破坏倒塌、阻断道路或者其他因灾害而破坏道路的情形。由于运输行程中各个路段的道路环境、地形地貌差异及事态严重程度不同,各路段的危险程度也就不同,通常用道路通畅率来描述。此外,由于应急物流系统的弱经济性,相对于时效性而言,经济性因素重要性相对较低,对车辆运输调度的决策影响居于次要因素地位。

1问题的描述

当灾害发生后,决策者得知有m个受灾点,启动n个救援点救助的车辆路径调度应急预案。若干个受灾点灵活选取相应的救援点进行救助,若干受灾点与救援点形成封闭回路。每个闭合回路中的救援点物资种类齐全,但是数量受限。每个救援点有相同型号的车辆若干,但只派一辆车完成某回路中所有受灾点物资的分配任务,任务完成后,无须原地等待,应立即返回所属救援点。为了使救援更加有效组织,必须要求车辆在指定的时间内送达,不能迟于某个时间,否则,救援无效。对受灾点j有一个时间上限lj,对于每一个受灾点j,如果被服务时间迟于li,用惩罚函数来计算应支付的惩罚,如图1所示。

2数学模型

2.1模型假设

1)假设每个救援点要救助的受灾点已知;

2)假设每个受灾点的需求量已知;

3)假设救援点有多个,每个救援点有相同型号的救援车辆若干,每个救援点的物资种类齐全,但数量受限,不同物资可以同车运送;

4)由于现实情况的车辆容量较小,假设救援点为每条路线分配的车辆总容量大于该运输路线上所有受灾点总需求量;

5)每个救援点物资数量受限,因此,从该救援点出发的所有配送路线上的应急物资需求量总和不可超过该救援点物资容量的限制;

6)假设救援车辆从救援点出发完成所属回路所有受灾点物资分配任务后,无须原地等待,立即返回所属救援点。

2.2模型的参数意义与变量

T :救援总时间;

Q :应急救援车辆路径总成本;

i:救援点 (i=1,2,…,m);

j:受灾点 (j=1,2,…,n);

S :救援点与受灾点的集合,S =n∪m ;

V :救援车辆(或路径)集合 (V =1,2,…,v);

Tv :救援车辆(或路径)v的发车时间;

b:单位发车成本;

c:单位距离运输成本;

p :单位时间惩罚成本;

Rgh :节点g到节点h之间的路阻系数;

Qv :车辆v的容量;

tvgh:救援车辆(或路径)v由节点g到节点h的行驶时间;

dvgh:救援车辆(或路径)v由节点g到节点h的行驶距离;

tjv::救援车辆(或路径)v到达节点j的时间;

ljv:时间窗限制,即节点j的上限时间;

Fik :救援点i物资k的储存量;

pivjk:由i救援点通过v回路分配给j受灾点的k物资的供给量;

qjk :受灾点j对k物资的需求量;

Wvgh:某回路v中从节点g到节点h单元路径保持畅通的概率。

2.3模型建立

救援时间最短目标函数

救援成本最少目标函数

约束条件

1)确保每条回路中需求点分配物资总量和不超过车辆的容量Qv,应满足以下约束条件

2)一个应急需求点仅有一辆车服务且仅服务一次,应满足以下约束条件

3)对于进入某一受灾点服务的车辆最后必须离开该受灾点,以保证车辆路线的连续性,应满足以下约束条件

4)因为要保证两个救援点之间不能相互配送货物,应满足以下约束条件

5)路网的连通性通常指救援点与各受灾点连接成的子回路保持畅通的概率,也就是从一点到达另一点的可能性。

假设在整个救援系统中,共有救援点m个,受灾点n个,救援点与受灾点组成若干子回路。某个回路v中各个单元路段保持畅通的概率为wvgh,所以每个子回路的保持通畅的概率为,整个救援系统所有回路保持畅通的概率为所以为了道路连通性的达到预期目标的概率p,应满足以下约束条件

1)由于每个救援点各类物资的储存量受限,所以由每个救援点供给受灾点各类物资总量不大于该救援点各类物资的储存量Fik,应满足以下约束条件

2)对于每个受灾点,救援点对该受灾点各类物资的供应量不大于该受灾点对各物资的qjk,应满足约束条件

pivjk ≤qjk,k∈l,v∈V,i∈ m,vj∈n.(9)

3)0~1整数变量

3算法设计

模拟退火算法的计算步骤:

步骤1:初始化,任选初始解i,判断是否满足条件,若不满足继续给初值判断,若满足则保留。将初始解给定为intchujie[12]={0,1,2,3,0,4,5,6,0,7,8,0},然后通过反复试验给定初始温度T0和终止温度Tf,降温系数r,令迭代指标k =0,Tk=T0 ;

步骤2:随机产生一个邻域解j∈N(i)(N(i)表示i的邻域),即用rand()函数产生两个随机数,对符合条件的进行交换,然后计算目标值增量Δf =f(j)-f(i);

步骤3:若Δf <0,令i=j转第4步;否则产生ξ=U(0,1),若则令i=j;

步骤4:若达到热平衡(内循环次数大于Cn2,在实例中取100)转第5步,否则转第2步;

步骤5:降低Tk,k=k+1,若Tk < Tf,则算法停止,否则转第2步。

4实例分析

以上研究建立了多救援点、多受灾点的应急车辆路径模型,为简化计算,本实例只演算单救援点、多受灾点的应急车辆路径问题。

假设某地区的救灾物资储备中心即救援点需要向8个受灾节点进行救灾物资配送,用节点0表示救援点,节点1,2,3,4,5,6,7,8表示8个受灾点,如图2所示。由于本模型第一目标函数,最短救援时间包括各节点总发车时间和总运行时间(各节点路阻系数与各节点之间运行时间乘积和),所以假设该救援点只采用一种车型,其载重量为8t车,各节点发车时间均为10 min,各节点的路阻系数矩阵、各节点间的时间矩阵及8个受灾点物资需求总量如图2所示。本模型采用第二目标函数,最少救援成本为方便起见在算例中汇总为各节点间的总成本(包括发成成本,运行成本,惩罚成本),每个救援车辆不能超载且必须在规定时间前把物资送到受灾节点,如图2所示。

4.1时间和成本数据的获取

为了尽量模拟真实场景,原则上采用更接近于现实的数据,但由于我国应急管理的水平还不高,建立的模型中很多数据在现实中很难获取,因此,只能采用实验数据来进行模拟。而为了数据尽量合理真实,所获取的时间和成本数据矩阵是通过网络搜索得到,数据如表1、表2、表3所示。

4.2路阻系数的设定

考虑到突发事件下道路状况的不确定性,在查阅相关资料后,将应急救援车辆径路问题中的路阻系数设定为(0,1)间的随机数。

4.3实例结果

模拟退火算法所得结果可定性地将收敛原则归纳为:初始温度T0足够高;降温速度r足够慢;终止温度Tf足够低。所以分别选用三条回路、四条回路做为实验基础,然后对不同参数下所得结果进行多次分析,最终得到一组参数值,使其结果最优。

当为3条回路时,初始温度T0=10000℃,迭代次数Q=200,降温系数r =0.98,而终止温度Tf分别取0℃,2.5℃,5.0℃,7.5℃,10.0℃,12.5℃,15.0℃,17.5℃,20.0℃,22.5℃,25℃,27.5℃时,对每次组合运行10次,由于模拟退火算法运行的结果是近似最优解,所以,每次运行结果不尽相同,每个组合的计算平均值如表4所示。

模拟退火算法中各参数对最优解出现个数的影响情况,如图3所示。

最优解出现个数随迭代次数的增加而显著增加;随初始温度的增加而较为平缓;随终止温度的增加而较为显著下降;随降温系数的增加而显著增加。从图3可以看出迭代次数、降温系数、终止温度的波动对最优解出现个数的影响较大,而初始温度对最优解出现个数影响较小,并且可以看出模拟退火算法求解实例的收敛性与稳定性较好。

模拟退火算法所得结果定性地可将收敛原则归纳为:初始温度足够高;降温速度足够慢;终止温度足够低。不同参数下所得结果进行分析后最终理想参数为Tf=10000,T0=0,r =0.98,Q=200。而当选定这些参数值时,运行结果中的最佳结果是适应度函数,即最短时间为588min,最优解即路径安排为0-5-4-3-0、0-6-8-0、0-1-2-7-0三个回路,此时的成本为15.7万元,程序运行时间为0.390s。实例最优结果如表5所示。

相应的最优路径如图4所示。

5结束语

【多车场车辆路径问题】推荐阅读：

配建停车场07-26