详情

原文传递不确定旅行时间环境下带时间限制的路径优化模型与算法

论文题名：	不确定旅行时间环境下带时间限制的路径优化模型与算法
关键词：	路径优化;车辆旅行时间;不确定环境;公交换乘;机场接送;旅行商问题
摘要：	路径优化问题是运筹学与管理科学领域一类经典的问题。典型的路径优化问题包括最短路问题、旅行商问题、车辆路径问题等。在交通与物流、计算机网络、通信等应用领域中，很多现实问题都可归结为路径优化问题，因此对路径优化问题的研究不仅具有重要的学术价值，而且具有广泛的应用价值。　　随着世界经济社会水平的高速发展，人类的生活节奏越来越快，时间也变得越来越宝贵。因此，尤其在以人为运送对象的交通与物流系统中，人的行为因素给路径优化问题带来了新的挑战。在此背景下，研究带时间限制的路径优化问题变得更加重要和急迫，研究成果可以帮助出行者尽量在时间限制内到达终点等等。　　在现实世界中，车辆旅行时间是不确定的。在路径规划阶段忽略不确定性可能会导致所谓的最优路径在实施阶段却违背预先设定的时间限制，如不确定性导致公交出行时间超出时间预算，导致将顾客送达机场的时刻严重早于或晚于时间窗，等等。而考虑不确定性又会使原本就难以求解的带时间限制的路径优化问题新增一个维度的复杂性，从而带来了建模和求解方面的挑战。　　本文针对路径优化问题，以尽量满足时间限制为目标，考虑车辆旅行时间的不确定性，提出了一个研究框架，并将其应用于公交换乘问题，旅行商问题，和机场接送服务问题中。本文的研究内容主要包括以下五个方面: 　　(1)提出了一个针对不确定旅行时间环境下带时间限制的路径优化问题的研究框架。本框架从构建可行路径集合、描述旅行时间不确定性、选择决策准则、设计高效算法四个方面展开，每个方面给予不同的选项，从而可以解释大部分相关研究的思路，同时催生了一些新的研究机会。根据旅行时间分布完全可知、部分统计信息可知、只知道上下界的情况，分别采用随机规划、分布鲁棒优化、鲁棒优化的方法论进行建模和求解。特别地，就测度“满足时间限制”的决策准则而言，经典的“准时到达概率”计算速度慢且无法刻画迟到时长，因此本文提出了一类新的决策准则，即最大化风险抵御指数（鲁棒优化中的保守系数、效用函数中的风险厌恶参数、Markowitz均值-方差函数中的方差项权重等等），同时保证该指数水平下对应的出行时间确定性等价能满足时间限制。这类准则除了具有良好的管理学性质外，最大的优点是计算速度快，因此可用于解决现实大规模问题。　　(2)面向城市中公交出行者，考虑车辆旅行时间的不确定性，针对带时间预算的公交换乘问题，利用鲁棒优化方法进行建模与求解，以帮助出行者尽量在最后期限前到达终点。车辆旅行时间由一个不确定集描述，鲁棒优化模型在保证能准时到达的前提下最大化不确定集的体积，也就最大化了能准时到达的场景数。通过对偶理论，推导并提出一种精确算法。假设出行者对于每条公交线最多使用一次，则可构造一个基于行程的公交网络模型，并提出一个标签设定算法和一个Floyd-A加速算法对该问题进行高效求解。通过与最大化准时到达概率的随机规划模型的对比实验，发现鲁棒优化模型所求得的路径旅行时间具有较小的迟到时长和较小的方差。通过在沈阳公交网络中的计算测试，表明平均换乘查询时间在一秒以内，验证了Floyd-A算法可用于解决现实大规模问题。　　(3)针对上述带时间预算的公交换乘问题，考虑旅行时间分布可知的情形，利用随机规划方法进行建模和求解。通过期望效用理论刻画出行者的风险厌恶行为，并在保证旅行时间的确定性等价满足时间预算约束的前提下最大化风险厌恶水平，也就最大化了换乘路径抵御风险的能力。理论证明该决策准则能同时考虑迟到概率和迟到时长。由于旅行时间分布完全相关的情况下该问题NP难，所以研究了分布独立和公交线内旅行时间相关两种多项式时间可解的情况。将原问题分解为两阶段问题，则求解原问题可等价为求解一系列不带时间预算的公交换乘问题。通过数值实验发现该方法的计算表现“介于”最大化准时到达概率模型和最小化期望迟到时长模型之间。通过在沈阳公交网络中的计算测试，表明平均换乘查询时间在一秒以内，验证了该算法对于解决现实大规模问题的实用性。　　(4)针对经典的带时间窗的旅行商问题，考虑车辆旅行时间的不确定性，提出了一个称为基本风险指数的决策准则，用以评估路径晚于时间窗到达访问点的风险，该指标函数具有凸性等优良理论特性，既考虑了迟到概率，又考虑了迟到时长。在车辆旅行时间的分布完全可知和仅均值和协方差可知的情况下，分别采用基于采样平均近似的随机规划和分布鲁棒优化方法进行建模和求解。为了提高计算速度，提出了一种Benders分解结合切平面的方法进行求解。计算实验说明:基于基本风险指数的模型就准时达到概率而言，在样本数量少的情况下，竟然优于基于采样平均近似的最大化准时到达概率模型。在样本数量大的情况下，最大化准时到达概率模型已很难在可接受的时间内进行求解，而提出的Benders分解方法可以求解样本数量很大的实例。　　(5)针对城市中的机场接送服务问题，以最小费用为目标，决策接送购票顾客到机场的车辆路径和时间安排，使得顾客以一定概率在时间窗内送达机场。建立了机会约束随机规划和分布鲁棒优化模型，在旅行时间服从独立正态分布或仅知均值和协方差的情况下推导出机会约束的等价解析形式;在其服从一般分布的情况下通过采样平均近似法来处理。设计了两阶段算法，除采样平均近似外，该算法为精确算法，第一阶段生成可行路径，第二阶段通过集合划分确定最优车辆路径。并提出了二分法求解在给定费用预算的情况下最大化时间窗内送达机场概率的问题。通过与目前的确定性模型的对比实验，验证了所提出的模型能减小迟到概率和迟到时长。
作者：	章宇
专业：	系统工程
导师：	唐加福
授予学位：	博士
授予学位单位：	东北大学
学位年度：	2017