计算机应用   2017, Vol. 37 Issue (5): 1485-1490,1515  DOI: 10.11772/j.issn.1001-9081.2017.05.1485
0

引用本文 

熊瑞琦, 马昌喜. 多配送中心危险货物配送路径鲁棒优化[J]. 计算机应用, 2017, 37(5): 1485-1490,1515.DOI: 10.11772/j.issn.1001-9081.2017.05.1485.
XIONG Ruiqi, MA Changxi. Robust vehicle route optimization for multi-depot hazardous materials transportation[J]. JOURNAL OF COMPUTER APPLICATIONS, 2017, 37(5): 1485-1490,1515. DOI: 10.11772/j.issn.1001-9081.2017.05.1485.

基金项目

国家自然科学基金资助项目(51408288);陇原青年创新创业人才项目(2016-43)

通信作者

马昌喜, machangxi@mail.lzjtu.cn

作者简介

熊瑞琦 (1992-), 男, 湖北襄阳人, 硕士研究生, 主要研究方向:物流系统优化与仿真;
马昌喜 (1979-), 男, 湖北汉川人, 副教授, 博士, 主要研究方向:交通运输系统优化

文章历史

收稿日期:2016-10-31
修回日期:2016-12-30
多配送中心危险货物配送路径鲁棒优化
熊瑞琦, 马昌喜    
兰州交通大学 交通运输学院, 兰州 730070
摘要: 针对危险货物配送路径对不确定因素敏感度较高的问题,提出了鲁棒性可调的多配送中心危险货物配送路径鲁棒优化方法。首先,以最小化运输风险和最小化运输成本为目标,根据Bertsimas鲁棒离散优化理论,建立鲁棒优化模型;然后,在改进型强度Pareto进化算法(SPEA2)的基础上设计一种三段式编码的多目标遗传算法进行求解,在遗传操作中对不同染色体段分别采用不同的交叉和变异操作,有效避免了种群进化过程中不可行解的产生;最后,以庆阳市西峰区部分路网为例进行实证研究,并将配送方案落实到运输过程的路段中,形成具体的运输路径。研究结果表明:在多配送中心下,运用该鲁棒优化模型及算法,能快速得到具有较好鲁棒性的危险货物配送路径。
关键词: 危险货物    鲁棒优化    多配送中心    改进型强度Pareto进化算法    多目标遗传算法    
Robust vehicle route optimization for multi-depot hazardous materials transportation
XIONG Ruiqi, MA Changxi     
School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou Gansu 730070, China
Abstract: Focused on the issue that the sensitivity of hazardous materials transportation routes to uncertain factors is excessively high, a robust vehicle route optimization method for multi-depot hazardous materials transportation was proposed. Firstly, a robust optimization model was designed under the Bertsimas robust discrete optimization theory with the objective function of minimizing transportation risks and minimizing transportation costs. Secondly, on the basis of Strength Pareto Evolutionary Algorithm 2 (SPEA2), a multi-objective genetic algorithm with three-stage encoding was designed for the model. Then, different crossover and mutation operations were performed on the different segments of chromosomes during genetic manipulation, which effectively avoided the generation of infeasible solutions during population evolution. Finally, part of Qingyang Xifeng district road network was chosen as an empirical research example. Distribution plan was carried out at transportation process to form some specific transportation routes. The results show that better robust hazardous materials transportation routes can be quickly obtained by using the robust model and algorithm under multi-depot situation.
Key words: hazardous materials    robust optimization    multi-depots    Strength Pareto Evolutionary Algorithm 2 (SPEA2)    multiple objectives genetic algorithm    
0 引言

多配送中心车辆配送路径问题 (Multiple Depot Vehicle Routing Problem, MDVRP) 是现代物流系统研究中一项重要的内容,一般可以表述为:由多个物流配送中心,组织多辆运输车辆按照适当的运输方案,对一系列有需求的客户在满足一定的约束条件 (如车辆载重、行驶路线、配送时间等) 下进行配送服务,并且达到一定的目标 (如经济成本最小、时间最短、路段风险最低等)[1]。而危险货物运输作为交通运输的一类重要分支,其运输的安全性十分重要,但在实际中准确获得危险货物运输路段上的信息是十分困难的,大部分信息具有较大的不确定性, 因此,在多配送中心下,寻求对不确定因素不敏感的危险货物配送路径是十分必要的。

现有对多配送中心危险货物配送路径优化问题的研究较少,相关文献资料集中于对危险货物的运输风险进行分析评估以及对配送顺序的优化选择。在国外,Verma[2]通过考虑费用最省、风险最小,构建了一个双目标优化模型,并采用风险费用边界算法对模型进行求解得到优化路径;但该模型中路段的数据均采用的是确定值。Jassbi等[3]以最小化运输里程、最小化受影响的居民数、最小化社会风险、最小化事故概率等制定了危险货物运输多目标优化的框架,虽然该框架考虑到一定的数据不确定性,但不确定数据是由事先假定的概率分布产生的,具有一定的局限性。Wu等[4]将多配送中心车辆路径优化问题简单划分为两个优化问题:配送点的聚类问题和单配送中心车辆路径优化问题,这种处理问题的方法很难得到最优解。在国内, 王云鹏等[5]基于ArcGIS (Arc Geographic Information System) 建立了危险货物运输路径优化模型。麻存瑞等[6]利用一种基于Prufer数编码的改进的遗传算法求解了不确定环境下旅行商问题的鲁棒模型,但并没有对多起点、多终点的问题作进一步研究。

基于以上文献综述,危险货物配送路径优化问题集中于确定环境下,对不确定环境下的研究,其不确定因素往往过多依赖先验知识以及服从概率分布的假定[7],所建立的模型对不确定数据变化的敏感度较高。此外,以往的配送路径优化以需求点的配送顺序作为结果,并没有具体到实际的运输路段中。基于以上考虑,本文采用区间值标定不确定风险值,进而建立不确定风险条件下多配送中心危险货物配送路径鲁棒优化模型,并采用改进的多目标遗传算法对实例进行求解验证以获得鲁棒性较好的配送路径。

1 多配送中心危险货物配送路径鲁棒优化模型

多配送中心危险货物配送路径问题可以概括为:在一定区域内,由多个危险货物配送中心,用多辆危险货物运输车辆,向多个客户需求点进行危险货物配送。

1.1 模型的假设条件

在基于实际配送问题的基础上对模型进行简化,设立以下假设条件:

1) 配送中心危险货物存储量能够实现所有需求点的需求量要求;

2) 任意需求点的危险货物需求量均小于服务该需求点的车辆的标记载重;

3) 运输车辆允许多次经过配送中心,服务对其分配的所有需求点后,危险货物运输车辆行驶最短路径回到各自配送中心;

4) 路段的运输风险不确定,用区间数表达;

5) 配送中心有足够多的危险货物运输车辆;

6) 在一次运输任务中,一辆危险货物运输车辆可服务多个需求点,一个需求点只能由一辆运输车辆服务,车辆可多次经过已被服务的需求点;

7) 一次运输任务中,危险货物运输车辆服务的需求点的需求总量不能超出车辆的标记载重。

1.2 指标体系的建立

采用G=(N, A) 无向连通网络图来描述多配送中心危险货物运输的运输网络,图中所有节点间的属性信息用邻接矩阵表示。

1.2.1 集合定义

P1={p|p=1, 2, …, n′}表示危险货物的需求点集;P0={p′|p′=n′+1, n′+2, …, n′+m}表示危险货物配送中心;P2={p|p=n′+m+1, n′+m+2, …, n}表示危险货物运输网络中除配送中心和需求点外的一般节点;N=P0P1P2表示所有的节点集;W表示危险货物运输网络中路段的集合;Vp′={k|k=1, 2, …,K}表示危险货物运输车辆集,p′∈P0

1.2.2 参数定义

sij表示危险货物运输网络中路段ij的运输距离, (i, j)∈Wf1表示危险货物运输车辆装载危险货物时运输费用系数;f2表示危险货物运输车辆相对空驶距离的运输费用系数;F表示车辆的固定使用费用;M表示完成危险货物运输任务的车辆总数;Qkp′表示车辆k的标记载重,p′∈P0, kVpqi表示需求点p的需求量, pP1rij表示路段ij的运输风险标称值, (i, j)∈Wδij表示路段ij的可变运输风险相对其标称值的偏差值,且δij≥0,(i, j)∈W${\tilde{r}}$ij表示路段ij的可变运输风险,${{\tilde{r}}_{ij}}\in \left[ {{r}_{ij}},{{r}_{ij}}+{{\delta }_{ij}} \right]$,(i, j)∈Wloadijkp′表示危险货物配送中心p车辆k行驶在路段ij上时车上装载的危险货物量,(i, j)∈Wp′∈P0kVp′loadijkp′≥0。

1.2.3 相关的变量定义

相关的变量定义如下:

$IR_{ijk}^{p'}=\left\{ \begin{matrix} 1 & load_{ijk}^{p'}>\text{0} \\ 0 & load_{ijk}^{p'}\text{=0} \\ \end{matrix} \right.$
$x_{ijk}^{p'}=\left\{ \begin{array}{*{35}{l}} 1 & \begin{align} & \text{配送中心}p'\text{的第}k\text{辆车经过路段}ij \\ & \text{且}\left( i,j \right)\in W,p'\in {{P}_{0}},k\in {{V}_{p'}} \\ \end{align} \\ 0 & \text{其他} \\ \end{array} \right.$
$y_{ik}^{p'}=\left\{ \begin{array}{*{35}{l}} 1 & \begin{align} & \text{配送中心}p'\text{的第}k\text{辆车服务需求点}i, \\ & i\in {{P}_{1}},p'\in {{P}_{0}},k\in {{V}_{p'}} \\ \end{align} \\ 0 & \text{其他} \\ \end{array} \right.$
1.3 目标函数

对于多配送中心危险货物配送路径问题,采用区间值的形式来表示配送路径问题中的不确定风险,即${{{\tilde{r}}}_{ij}}$${{\tilde{r}}_{ij}}\in \left[ {{r}_{ij}},{{r}_{ij}}+{{\delta }_{ij}} \right]$,引入参数Γ(Γ∈[0, W]) 和参数TΓ用来控制不确定风险的保守度,Γ的取值反映了决策者的风险偏好信息,T为受不确定性影响风险发生变化的路段集合,|T|为受不确定性影响风险发生变化的路段集合的个数,通过对参数Γ进行不同赋值得到具有不同鲁棒性的配送方案,从而达到对模型鲁棒性的控制。当Γ=0时,忽略了风险偏差的影响,此时路段风险均为定值,模型对不确定风险最为敏感,也就是当配送网络中某一路段的不确定风险发生改变时,之前模型得到的优化解可能发生变化。随着Γ值不断增大,势必会使得模型对不确定风险的敏感程度下降,得到的解的鲁棒性相应加强。当Γ=|T|时,也就是考虑了所有路段不确定风险偏差的影响,此时模型对不确定风险最不敏感,得到的解也最为保守。利用文献[8]中的鲁棒离散优化理论,建立多配送中心危险货物配送路径的Bertsimas鲁棒优化模型如下:

$\begin{align} & \min {{Z}_{1}}=\sum\limits_{p'\in {{P}_{0}}}{\sum\limits_{k\in \{{{V}_{p'}}|p'\in {{P}_{0}}\}}{\sum\limits_{\left( i,j \right)\in W}{{{r}_{ij}}x_{ijk}^{p'}IR_{ijk}^{p'}}}}+ \\ & \text{ }\underset{\left\{ T\left| T\subseteq W,\left| T \right|=\Gamma \right. \right\}}{\mathop{\max }}\,\sum\limits_{p'\in {{P}_{0}}}{\sum\limits_{k\in \{{{V}_{p'}}|p'\in {{P}_{0}}\}}{\sum\limits_{\left( i,j \right)\in W}{{{\delta }_{ij}}x_{ijk}^{p'}}}}IR_{ijk}^{p'} \\ \end{align}$ (1)
$\begin{align} & \min {{Z}_{2}}=\sum\limits_{p'\in {{P}_{0}}}{\sum\limits_{k\in \{{{V}_{p'}}|p'\in {{P}_{0}}\}}{\sum\limits_{\left( i,j \right)\in W}{IR_{ijk}^{p'}{{f}_{1}}{{s}_{ij}}x_{ijk}^{p'}}}}+ \\ & \text{ }\sum\limits_{p'\in {{P}_{0}}}{\sum\limits_{k\in \{{{V}_{p'}}|p'\in {{P}_{0}}\}}{\sum\limits_{\left( i,j \right)\in W}{\left( 1-IR_{ijk}^{p'} \right){{f}_{2}}{{s}_{ij}}x_{ijk}^{p'}}}}+FM \\ \end{align}$ (2)
$\sum\limits_{i\in {{P}_{1}}}{y_{ik}^{p'}{{q}_{i}}}\le Q_{k}^{p'},\forall {{p}^{'}}\in {{P}_{0}},\forall k\in {{V}_{p'}}$ (3)
$\sum\limits_{p'\in {{P}_{0}}}{\sum\limits_{k\in {{V}_{p'}}}{y_{ik}^{p'}=1}},\forall i\in {{P}_{1}}$ (4)
$\sum\limits_{\left( i,j \right)\in W}{x_{_{ijk}}^{p'}}-\sum\limits_{\left( i,j \right)\in W}{x_{_{jik}}^{p'}}=0,\forall i\in \mathsf{N},p'\in {{P}_{0}},k\in {{V}_{p'}}$ (5)

上述模型中,式 (1) 是目标函数,表示最小化危险货物运输风险,其中危险货物运输车辆完成对最后一个需求点的配送服务后,返回其配送中心间路段上的风险不计入式 (1) 中;式 (2) 也为目标函数,表示最小化危险货物运输费用,包括装载危险货物时的运输费用、空车行驶时的运输费用以及车辆的固定使用费用;式 (3) 为载重约束,表示危险货物运输车辆的承载量不得大于该车辆的标记载重;式 (4) 为需求点约束,表明任意需求点只能由一辆危险货物运输车辆服务;式 (5) 为对车辆行驶的路径约束,表示运输车辆配送服务完相应需求点后返回到各自配送中心。

在目标函数式 (1) 中存在max项,因此,式 (1) 不能直接进行求解,还需要对其进行等价转化。利用文献[8]中的鲁棒离散转换规则,将上述模型中目标函数式 (1) 转化为式 (6):

$\begin{align} & \min \left\{ \sum\limits_{p'\in {{P}_{0}}}{\sum\limits_{k\in \left\{ {{V}_{p'}}\left| p'\in {{P}_{0}} \right. \right\}}{\sum\limits_{\left\{ i=1:\left( i,j \right)\in W \right\}}^{\left\{ I:\left( I,j \right)\in W \right\}}{\sum\limits_{\left\{ j=1:\left( i,j \right)\in W \right\}}^{\left\{ J:\left( i,J \right)\in W \right\}}{{{\delta }_{ij}}x_{ijk}^{p'}IR_{ijk}^{p'}}}}}+ \right. \\ & \left. \sum\limits_{p'\in {{P}_{0}}}{\sum\limits_{k\in \left\{ {{V}_{p'}}\left| p'\in {{P}_{0}} \right. \right\}}{\sum\limits_{\left\{ i=1:\left( i,j \right)\in W \right\}}^{\left\{ I:\left( I,j \right)\in W \right\}}{\sum\limits_{\left\{ j=1:\left( i,j \right)\in W \right\}}^{\left\{ J:\left( i,J \right)\in W \right\}}{\left( {{\delta }_{ij}}-{{\delta }_{IJ}} \right)x_{ijk}^{p'}IR_{ijk}^{p'}}}}} \right\}+\mathit{\Gamma }{{\delta }_{IJ}} \\ \end{align}$ (6)

进而风险最优目标值${Z_1} = \mathop {\min }\limits_{\left( {I,J} \right) \in W} {\mkern 1mu} {H^{IJ}}$

2 求解算法

遗传算法与传统的优化方法 (枚举、启发式等) 相比,以生物进化为原型,具有很好的收敛性,在计算精度要求时,计算时间少,稳定性高,是求解多目标优化问题的一个有效算法[9-10]。而上述模型中含有两个目标函数,属于NP难问题,传统的单目标遗传算法无法求解,在针对多目标优化的众多方法中,本文采用强度Pareto遗传算法 (Strength Pareto Evolutionary Algorithm 2, SPEA2) [11]来求解多配送中心危险货物配送鲁棒优化问题。SPEA2算法流程如下:

步骤1 构建内部种群规模Pop与外部附属种群规模Pop′,设定种群最大迭代次数T

步骤2 令t=0,生成初始群体P0,并创建一个空的附属种群P0′。

步骤3 计算内部种群Pt与外部附属种群Pt′中个体的适应值。

步骤4 将PtPt中的所有非支配个体拷贝到新一代Pt+1′中。如果Pt+1′中个体的数量超过了Pop′,则对Pt′中的个体进行种群裁减操作,以减少个体的数量;如果Pt+1′中个体的数量都小于Pop′,则将PtPt′中的优良个体添加到Pt+1′中。

步骤5 检查是否达到最大循环代数 (tT)。若没达到则继续进行步骤6;否则运算终止,并采用文献[12]中基于集合理论的Pareto集选优方法,选出具有代表性的最优成员集,进行输出,获得结果。

步骤6 拷贝Pt+1′生成新的内部种群Pt+1。由预先设定的交叉与变异概率对Pt+1中的个体进行交叉、变异操作,并令t=t+1转步骤3。

其中,在计算内部种群Pt与外部附属种群Pt′中个体的适应值之前,需给种群Pt与种群Pt′中每个个体x赋予强度S(x),表示从属于该个体x的个体数目:

$S(x)=|\{y|y\in Pt+Pt'\wedge x\succ y\}|$ (7)

其中$x\succ y$表示xy的支配关系,进而得到个体x的适应值:

$R(x)=\sum\limits_{y\in {{P}_{t}}+{{P}_{t}}',y\succ x}{S(x)}$ (8)

然而种群Pt与种群Pt′中不仅存在支配个体,也存在非支配个体,因而需计算个体间的距离并按升序排列后引入D(x),表示个体x到其第k个邻近个体间距离的反函数:

$D(x)=1/\sigma _{x}^{k}+2$ (9)

其中$k=\sqrt{|{{P}_{t}}|+|{{P}_{t}}^{'}|}$,最终得到个体适应值为:

$F(x)=R(x)+D(x)$ (10)
2.1 编码和解码

针对多配送中心危险货物配送路径问题,其求解算法需要考虑三个问题:一是各危险货物配送中心选择合适的客户需求点,二是每个配送中心对各客户需求点的配送顺序,三是在对客户需求点进行配送以及返回配送中心的路径选择。因此,本节的遗传算法采用了一种将配送中心、客户需求点以及配送路径相结合的混合编码方式,具体将染色体分成三段。

染色体段1为各危险货物配送中心选择所需服务的客户需求点,其长度为所有客户需求点的数目,基因值为各配送中心的编号;染色体段2表示各客户需求点被配送服务的先后顺序,其长度为所有客户需求点的数目,基因值为各客户需求点的编号;染色体段3表示具体的配送路径,分别由危险货物配送中心-需求点编码,需求点-需求点编码,需求点-危险货物配送中心编码3部分来构成,其长度由配送路径节点数目决定 (若有s个需求点,完成配送任务共派出t辆危险货物运输车辆,则该染色体段3的长度为s+t),基因值为各节点的编号。染色体段1和染色体段2根据危险货物运输车辆装载容量进行贪心选择,染色体段3通过节点间的邻接选择,从而实现关于多配送中心危险货物配送问题求解算法的编码与解码。假设运输网络中有3个危险货物配送中心 (配送中心a,b,c) 参与配送7个需求点 (节点1、2、3、4、5、6,7) 的配送任务,需求点的需求量依次为3 t、4 t、2 t、3 t、5 t、1 t、3 t,车辆载重为10 t,其运输网路图如图 1,产生一条三段式的混合编码染色如下:

图 1 算例运输网络图 Figure 1 Transport network diagram of the example

染色体段1:c-a-a-b-b-c-b

染色体段2:3-1-7-4-6-2-5

染色体段3:7-5-10-a-1-b-11-4-13-2-6-c-9-8-3-12,

    8-6-c-…-5, …, 9-4-10-…-2

由染色体段1可知客户需求点2,3由配送中心a来服务;客户需求点4、5、7由配送中心b来服务;客户需求点1、6由配送中心c来服务。根据染色体段1和染色体段2可知, 配送中心a对需求点2、3的配送顺序为:3→2,进而在满足载重约束的条件下,利用贪心策略将需求点分配给相应的危险货物运输车辆,那么危险货物配送中心a需派出一辆危险货物运输车辆,其配送顺序为:a→3→2→a。同理,配送中心b需派出两辆危险货物运输车辆进行配送,第一辆车的配送顺序为:b→ 7→ 4→b,第二辆车的配送路径为:b→5→b。配送中心c需派出一辆危险货物运输车辆,其配送顺序为:c→1→6→c。

由染色体段3可知,该染色体段共有11组染色体子段,分别表示危险货物配送中心-需求点,需求点-需求点,需求点-危险货物配送中心的配送路径。每个子段共有16个基因,代表路网中所有的节点。通过染色体段1和染色体段2可知,危险货物配送中心a需先对需求点3进行配送。在这里以危险货物配送中心a与需求点3间的配送路径为例详细阐述编码与解码过程。首先产生长度为16, 即:7-5-10-a-1-b-11-4-13-2-6-c-9-8-3-12的初始数列,遍历该数列寻找危险货物配送中心a,找到后将该点从数列中删除,此时数列的长度为15;将危险货物配送中心a作为关键点,根据危险货物运输网络中节点的邻接关系,从数列前端遍历该数列寻找与关键点邻接的节点,找到该节点后,将节点从数列中删除,并将其作为关键点继续根据危险货物运输网络中的邻接关系寻找下一节点,直至找到需求点3。若将某节点作为关键点后,在数列中已经不存在与关键点邻接的节点,而此时尚未寻找到需求点3,则说明解码初始数列无法得到正确的配送路径,是不可行的,此时,应重新产生数列并解码,直到获得两需求点间的配送路径。由以上编码与解码过程可知,配送路径染色体子段的最大长度不能超过16。其他10个子段的编码与解码同理。

图 2 染色体段3的编码与解码示意图 Figure 2 Encoding and decoding of the third segment of chromosome
2.2 遗传算子设计

该遗传算法由锦标赛选择法进行选择操作。针对三段式的编码方式,这里对交叉与变异操作也相应分段进行设计,从而提高算法搜索解的效率,避免不可行解的产生和早熟收敛。

2.2.1 选择算子

采用锦标赛选择法。每次选取几个个体中适应度最高的一个个体遗传到下一代群体中,重复该操作,直到新的种群规模达到原来的种群规模,这样经过选择后的种群能以较高概率保证最优个体被选择,最差个体被淘汰。具体的操作步骤如下:

1) 确定每次选择的个体数量,这里以占种群数量百分比表示。

2) 由种群中的个体随机构成不同分组,在每个组中选择适应度最高的个体遗传到下一代种群中。

3) 重复步骤2),直到子代种群规模达到原有种群规模。

2.2.2 交叉算子

染色体第1段与第2段采用双点交叉完成交叉操作。首先,按一定的概率任意选取两个个体作为父代染色体,并在选定的染色体的第一段任意选取两个基因位作为交叉点;其次,将选取的两个染色体中交叉点之间的部分进行互换,从而形成子代染色体。

针对染色体第3段由危险货物配送中心-需求点染色体子段、需求点-需求点染色体子段、需求点-危险货物配送中心染色体子段构成,本文规定:在染色体第3段中若两子段间的首末位两节点基因值相同,则称它们为等位子段。如图 3,选择带有等位子段的两染色体S1S2作为父代,若满足交叉概率,则交换两染色体中的等位子段V1V2,获得子代染色体S1′、S2′。采用这样的交叉方法,既保证了交叉后产生的子代染色体的多样性,又保证了其可行性,提高了算法的效率。

图 3 等位子段交叉示意图 Figure 3 Schematic diagram of the intersection of allelic segments
2.2.3 变异算子

染色体第1段与第2段由逆转录法完成变异操作。在染色体段中随机确定两个不同基因位,如果满足变异概率,则对这两个基因位间的基因段执行逆转操作。如染色体段4-|3-5-2|,变异后为4-|2-3-5|。

染色体第3段采用等位基因变异法,由于染色体第3段为邻接节点产生的路径染色体具有特殊性,这里规定该染色体段中的等位基因为起始节点与结束节点具有相同基因值的基因。首先确定染色体R上发生变异的两节点k1k2,则这两个节点间 (包含k1k2) 的基因即为变异基因w,如图 4。若满足变异概率,利用染色体段3的编码及解码方法产生相应的等位基因w′去替代原有基因w,从而得到变异后的新染色体R′。为保证后续遗传操作的进行,这里要求变异后的染色体子段实际长度不能超过所允许的最大长度 (危险货物运输网络中节点总量N)。采用该变异方法能有效避免不可行染色体的产生。

图 4 染色体第3段变异示意图 Figure 4 Mutation diagram of the third section of chromosome variation
3 实证研究

选取庆阳市西峰区部分路网展开实例研究,路网中共47个节点,79条路段 (|N|=43, |W|=79),其中节点1,2,…,12为需求点,节点13、14、15为危险货物配送中心,危险货物配送中心将派出运输车辆来配送服务这12个需求点。需求点由该危险货物配送中心发出的标记载重为10 t的车辆来服务,设车辆装载危险货物时运输费用系数为200元/km,空驶时运输费用系数为50元/km,每辆车的固定使用费为400元,各需求点的需求量见表 1。运输网络中路段距离由地图测量产生 (单位:m),路段风险标称值在[10, 99](单位:人) 中随机产生,由于各种原因,得到的风险标称值都存在一定的偏差,这里设定运输风险偏差δij(0≤δij<0.5rij) 为随机产生的实数,结果见图 5(Dxxx为路段距离,Rxx为路段风险标称值)。

表 1 运输任务信息表 Table 1 Transport task information
图 5 庆阳市西峰区部分网络图 Figure 5 Part road network in Qingyang Xifeng district

在Core i3 CPU M380 4 GB内存的计算机配置环境下,以Visual Studio6.0为平台编写代码实现算法求解,设置种群大小100,最大进化代数200,逆转率概率0.1,交叉概率0.6,变异概率0.1,分别设置风险鲁棒控制参数Γ=0、30、60,多次运行程序得到的结果如表 2~5

表 2 Γ=0时所得的Pareto解集 Table 2 Pareto solution set obtained at Γ=0
表 3 Γ=30时所得的Pareto解集 Table 3 Pareto solution set obtained at Γ=30
表 4 Γ=60时所得的Pareto解集 Table 4 Pareto solution set obtained at Γ=60
表 5 Γ取不同值时的Pareto解目标值 Table 5 Pareto solution for different values of Γ

作为对比,采用改进型非劣分类遗传算法 (NSGA2) 对相同算例进行计算。算法参数取值和Pareto最优解集选择策略均与SPEA2算法相同。由表 6可知,与NSGA 2算法相比,在不同Γ值下SPEA2算法所得最终解的两个目标函数均值均较优; 同时, 运算时间较少。结果表明,SPEA2算法不仅能获得较优的满意解,且收敛速度较快。

表 6 SPEA2算法与NSGA 2算法的性能及运算时间比较 Table 6 Comparison of performance and computation time between SPEA2 algorithm and NSGA2 algorithm

表 2~5可知在每个Γ值下,不同Pareto解里危险货物配送中心服务的需求点是相同的,车辆对应服务的需求点也相同,但运输车辆对需求点的配送顺序以及配送路径是不同的,使得每个Pareto解的目标值不同,随着风险目标值的下降,费用目标值呈现逐步上升趋势。

表 6图 6可知,随着风险鲁棒控制参数的增加,最优运输风险值增大,最优运输费用值也增大,理论而言,解的鲁棒性增强在一定程度上会削弱解的最优性。Γ值的大小反映了路段发生变化数据的多少,进而体现出获得的Pareto解对不确定数据的敏感度的高低,具体Γ取值多少,才能达到鲁棒性与最优性之间的平衡,这取决于问题本身以及决策者自身偏好,有待进一步研究。

图 6 Γ取不同值时的Pareto解集曲线 Figure 6 Pareto solution set curves for different values of Γ
4 结语

本文采用鲁棒优化的方法,避免了通过概率分布对不确定运输风险数据进行假定的依赖,只需将不确定数据界定在合理的区间,降低了对基础数据的要求。在求解中,针对问题特点设计了三段式编码方法并依据编码方法设计了相应的解码方法、遗传操作从而有效避免种群进化过程中不可行解的产生。

在综合考虑运输风险与运输费用的基础上,建立了多配送中心危险货物配送路径的多目标鲁棒优化模型,求解模型后获得的危险货物运输配送方案落实到运输过程中的路段,具有较高的安全性、应用性与经济性。同时,通过设置不同的风险鲁棒控制系数可获得不同运输条件下的危险货物运输配送方案。在实际生产生活中,决策者可应用此优化方法,通过路段数据的区间值就可获得鲁棒性较好的危险货物运输配送方案。

参考文献
[1] DESAULNIERS G, LAVIGNE J, SOUMIS F. Multi-depot vehicle scheduling problems with time windows and waiting costs[J]. European Journal of Operational Research, 1998, 111(3): 479-494. doi: 10.1016/S0377-2217(97)00363-9
[2] VERMA M. A cost and expected consequence approach to planning and managing railroad transportation of hazardous materials[J]. Transportation Research Part D:Transport and Environment, 2009, 14(5): 300-305. doi: 10.1016/j.trd.2009.03.002
[3] JASSBI J, MAKVANDI P. Route selection based on soft MODM framework in transportation of hazardous materials[J]. Applied Mathematical Sciences, 2010, 63(4): 3121-3132.
[4] WU T H, LOW C, BAI J W. Heuristicsolutions to multi-depot location routing problems[J]. Computers and Operations Research, 2002, 29(10): 1393-1415. doi: 10.1016/S0305-0548(01)00038-7
[5] 王云鹏, 孙文财, 李世武, 等. 基于ArcGIS的危险货物城市运输路径优化模型[J]. 吉林大学学报 (工学版), 2009, 39(1): 45-49. ( WANG Y P, SUN W C, LI S W, et al. Route optimization model for urban hazardous material transportation based on ArcGIS[J]. Journal of Jilin University (Engineering and Technology Edition), 2009, 39(1): 45-49. )
[6] 麻存瑞, 马昌喜. 不确定旅行商问题的鲁棒模型与算法[J]. 计算机应用, 2014, 34(7): 2090-2092. ( MA C R, MA C X. Robust model and algorithms for uncertain traveling salesman problem[J]. Journal of Computer Applications, 2014, 34(7): 2090-2092. doi: 10.11772/j.issn.1001-9081.2014.07.2090 )
[7] CAPLICE C, MAHMASSANI H S. Aspects of commuting behavior:preferred arrival time, use of information and switching propensity[J]. Transportation Research Part A:Policy & Practice, 1992, 26(5): 409-418.
[8] BERTSIMAS D, SIM M. The price of robustness[J]. Operations Research, 2004, 52(1): 35-53. doi: 10.1287/opre.1030.0065
[9] 阎啸天, 武穆清. 基于GA的网络最短路径多目标优化算法研究[J]. 控制与决策, 2009, 24(7): 1104-1109. ( YAN X T, WU M Q. Research on multi-objective optimization for shortest path algorithm based on GA[J]. Control and Decision, 2009, 24(7): 1104-1109. )
[10] 马昌喜. 应急交通与物流系统优化[M]. 成都: 西南交通大学出版社, 2014 : 55 -58. ( MA C X. Optimization of Emergency Transportation and Logistics System[M]. Chengdu: Southwest Jiaotong University Press, 2014 : 55 -58. )
[11] 郑金华. 多目标进化算法及其应用[M]. 北京: 科学出版社, 2007 : 28 -32. ( ZHENG J H. Multi-objective Evolutionary Algorithm and Application[M]. Beijing: Science Press, 2007 : 28 -32. )
[12] 郭雪斌. 隧道出入口驾驶员瞳孔及视点分布特性实验研究[D]. 上海: 同济大学, 2006. ( GUO X B. Research on characteristic of the driver 's pupil and eye fixation point and its distribution at the tunnel entrance and exit based on experiment[D]. Shanghai:Tongji University, 2006. )