基于萨维奇准则的鲁棒最短路模型研究

方威

（长沙理工大学，湖南　长沙　410004）

基于萨维奇准则的鲁棒最短路模型研究

方威

（长沙理工大学，湖南长沙410004）

需求的不确定性及通行能力等方面的因素导致路段阻抗的不确定性。为了研究区间阻抗下的最短路问题，同时考虑到决策的风险性，文中基于萨维奇准则即最小最大后悔值准则构建最短路模型，并通过算例对该模型进行验证，结果表明基于最小最大后悔值准则的最短路模型具有良好的鲁棒性。

公路交通；萨维奇准则；鲁棒最短路；区间阻抗

最短路问题是交通网络中交通分配的关键所在。如果交通网络是确定的，则走行时间是确定数，最短路的求解将非常简便，可运用传统的最短路算法如Dijkstra算法和Floyd算法进行求解。然而，实际交通网络中走行时间是一个不确定数，这与需求的不确定性及路网走行的不确定性有关。如果忽略这些不确定性，后果将难以想象。因此，寻找一条抗风险能力强的鲁棒最短路具有很强的实际意义。

1951年，统计学家Leonard Jim-mie Savage提出萨维奇准则，又称最小最大后悔值准则。作为管理学的重要准则之一，它主要描述的是决策者在一无所知的自然状态下，为了避免更大的机会损失而采取的一种方法。2011年，邱若臻运用该准则构建了一个物流供应链鲁棒模型，降低了需求不确定性对系统及其成员运作绩效的影响。2014年，张玲运用该准则建立了应急救灾网络优化模型，解决了应对自然灾害临时应急配送中心选择和应急救灾物资配置问题；余璇在最小最大后悔值理论的基础上建立了需求不确定下的轴辐式班轮航线网络优化模型，有效提升了轮船班线的稳定性及公司的利益。

在不确定性需求下交通分配研究方面，主要研究有模糊需求、随机需求及区间需求三方面。基于模糊需求条件，周南金运用模糊可信性理论对交通用户平衡分配进行研究，提出了模糊有效路径的概念，并给出了模糊最短路的求解算法；刘洋运用模糊集理论构建了出行生成量的模糊回归预测模型，并通过算例说明了模型的有效性。基于随机需求条件，卞长志等基于随机需求建立了离散型交通网络设计模型并设计了相应算法，提高了预测的可靠性； Zhang C.等基于随机需求与供给，以走行时间为变量、期望残差最小为目标函数，建立了鲁棒用户平衡分配模型。基于区间需求条件，Xie Binglei等研究了在区间阻抗下的平衡交通分配，建立了基于区间数的变量不等式模型，并设置了相应算法求解；左丹建立了基于区间数的用户平衡分配模型，给出了基于MSA的改进算法并用MATLAB编程计算；全维杰建立了区间不确定需求下的OD反推模型，并运用区间节点法求区间阻抗下的最短路，最后采用区间遗传算法进行求解。

1　最短路模型描述

最短路问题实际上是一个网络图问题。先定义一个有向网络图G=（V，A），其中V代表点集，A代表弧集，起点为r∈V，终点为s∈V。在网络图中，最短路都是从有效路径集中挑选出来的。

黄海军等考虑到实际交通网络中那些流量非常小的路径不会影响最后的交通分配，重新定义了有效路径。秦鸣等介绍了3种有效路径的定义方法并作了比较，对于确定阻抗下的有效路径搜寻具有一定实际意义，但对于区间阻抗下的有效路径的确定无能为力。在此研究中，阻抗是不确定的，是一个区间数，而且各路段阻抗相差不大，路径数又有限，为了计算简便，将所有路径视为有效路径。

O.E.Karasan等对区间阻抗下的网络作了如下描述：任意弧段阻抗在任何情况下是已知的，但不确定，即根据以上定义与描述，区间阻抗下的最短路问题可转化成以下minimax问题：

式中：Rij为路段的阻抗，是一个区间值；若弧（i，j）不在从r到s的路径上，xij取零，否则取1；Ys为从起点r到终点s的最短路。

在上述模型中，Ys表示从起点r到终点s的最短路，是一个变量，会随着x取值的变化而变化，当网络上所有xij取值后，可得到xij=1的唯一路径，不在此路径上的路段阻抗取最小值，由此可得到该路径诱导下产生的从r到s的最短路Ys。模型的约束条件的含义可参照传统最短路模型的约束条件。

2　算法

根据上文的定义和描述及最小最大后悔值准则，设计最短路计算步骤如下：

（1）输入全面的路网参数、出行需求点对矩阵S及总出行需求点对数N，令i=1。

（2）计算出行点对Si之间的有效路径，将各路径的区间走行时间按顺序组成矩阵M，同时令N =N-1。

（3）令n=n-2（n为当前出行点对之间的总有效路径数量），取Mk与Mj，按照最小最大后悔准则选择两者中最小的最大后悔路径，并令k取其位置顺序。

（4）按照最小最大后悔准则进行选择，对于M1与M2，取两者中最小的最大后悔路径，令j=3。

（5）如果n=1，输出Si之间的最小最大后悔路径Mj，i=i+1，转到下一步；如果n>1，则j=j +1，返回第4步。

（6）如果N=0，转到下一步；如果n>0，返回第2步。

（7）结束并输出结果。

3　算例分析

如图1所示，某路网包含12条单向路段及9个节点，其中区间阻抗值均为零流情况下的数据，起点r为节点1，终点s为节点9。

运用上文提出的方法，计算各情景下各节点到终点的最大后悔值。表1为起点至终点的各路径区间阻抗及最大后悔值计算结果。

图1　路网示意图

表1　各路径最小最大后悔值

由表1可知：各路径的最小最大后悔值为10，即起点到终点的鲁棒最短路为1—2—5—8—9。

4　结语

该文考虑到需求的不确定性及路网的不确定性，引入最小最大后悔值准则解决不确定性的问题，并基于最小最大后悔值准则构建了最短路模型。由于考虑不够深入，还存在以下不足之处，有待进一步深入研究：1）网络较复杂时，特别是路段阻抗不确定的情况下，如何来定义有效路径，让后面的计算更加简便。2）文中最小最大后悔值恰好是唯一的，当最小最大后悔值不唯一时，如何进一步进行比较，确定是否存在唯一最短路。3）如何将这里的最短路研究应用到不确定性交通分配问题中。

［1］施泰.萨维奇［J].统计与预测，2002（6）.

［2］邱若臻，黄小原.基于最小最大后悔值准则的供应链鲁棒协调模型［J].系统管理学报，2011，20（3）.

［3］张玲，陈涛，黄钧.基于最小最大后悔值的应急救灾网络构建鲁棒优化模型与算法［J].中国管理科学，2014， 22（7）.

［4］余璇.基于最小最大后悔值的轴辐式班轮航线网络优化研究［D].大连：大连海事大学，2014.

［5］周南金.基于可信性的模糊用户平衡交通分配［D].长沙：长沙理工大学，2012.

［6］刘洋.基于模糊出行需求的交通分布与分配组合模型研究［D].哈尔滨：哈尔滨工业大学，2013.

［7］卞长志，陆化普，张洁.基于随机需求的离散交通网络设计［J].公路工程，2009，34（5）.

［8］Zhang C，Chen X，Sumalee A.Robust wardrop′s user equilibrium assignment under stochastic demand and supply：expected residual minimization approach［J].Transportation Research Part B：Methodological，2011， 45（3）.

［9］Xie Binglei，An Shi，Zhao Zebin.Traffic assignment model and algorithm based on interval-valued impedance［A].International Conference on Transportation Engineering［C].2007.

［10］左丹.区间不确定需求下的交通用户平衡分配方法［D].长沙：长沙理工大学，2010.

［11］全维杰.区间不确定需求下的OD反推模型与算法研究［D].长沙：长沙理工大学，2013.

［12］李志纯，黄海军.随机交通分配中有效路径的确定方法［J].交通运输系统工程与信息，2003，3（1）.

［13］秦鸣，姜培.基于有效路径的多路径交通流分配［J].交通标准化，2010（4）.

［14］O E Karasan，M C Pinar，H Yaman.The robust shortest path problem with interval data［R].Bilkent University，2001.

U491.1

A

1671-2668（2016）01-0031-02

2015-08-30