拉格朗日松弛启发式算法求解时空网络下的弧路径问题

为减少车辆调度成本,优化车辆运输路径,在时空网络中研究路段作业车辆的弧路径问题;考虑道路出行的时变性,利用车辆运行的时间、空间特征,构建时间-空间网络,建立弧路径问题的时空网络流模型;设计了拉格朗日松弛启发式算法,引入拉格朗日乘子松弛耦合约束,构建拉格朗日松弛问题;进一步通过拉格朗日分解,把松弛问题分解为单车最短路问题;用次梯度算法更新乘子,求解拉格朗日对偶问题,并更新原问题最优解的下界;使用启发式算法获得可行解,并更新原问题最优解的上界;用六结点运输网络和Sioux-Falls网络下的算例对算法进行实证分析。计算结果表明:六结点运输网络中6个算例的上下界间隙值等于0或接近0,Sioux-Falls网络中算例2的间隙值为0.02%,其余5个算例的间隙值等于0,均可以得到质量较高的近似最优解;在最复杂的算例(15辆车,70个任务)中,算法在可接受的时间内也得到了间隙值为0的解,找出了最优的车辆路径;随着迭代次数的增加,拉格朗日乘子会逐步收敛到固定值;当车辆容量从50增加到100时,最优解从52下降到42,说明在任务数和车辆数一定时,适当增加车容量可以降低运营成本。可见,与商业求解器相比,拉格朗日松弛启发式算法的间隙值更小,求解质量更高,可以更有效地求解弧路径问题。      

观测路径出行时间下随机网络交通需求估计

道路网络起讫点（OD）需求是城市决策长期交通规划和短期交通管理中的基础参数,准确的交通需求更是实施交通拥堵控制、限行限速、路径诱导等措施的先决条件。综合运用观测的轨迹已知和未知路径出行时间,建立随机网络交通需求估计双层规划模型。上层广义最小二乘模型最小化历史交通需求与待估交通需求、观测路径出行时间与待估路径出行时间之间的偏差,约束为交通需求、路段流量、路段出行时间与路径出行时间之间的传播关系,通过高斯混合模型（GMM）对其中轨迹未知的观测出行时间依概率聚类。下层为随机网络交通出行均衡模型,分别运用出行时间预算和随机用户均衡处理路网不确定性和出行者感知误差。上、下层之间通过交通需求和OD-路段关联比例进行信息传递。设计迭代算法框架求解双层规划模型,迭代算法包含求解上层模型的最速下降法、求解下层模型的相继平均算法和求解GMM模型的最大期望（EM）算法。通过算例表明轨迹未知的路径出行信息的加入在提升需求估计精度的同时也增大了估计值的方差;设计的迭代算法能够稳定收敛到10^-5的精度;GMM软聚类方法估计的交通需求显著优于硬聚类方法估计的需求值;交通需求值对观测路径出行时间的扰动更加敏感。研究考虑出行者风险态度,通过轨迹信息的重新构建揭示城市交通需求演化规律。     

考虑潜在需求的区域共享泊位滚动时域分配研究

为研究城市道路网络交通状况和停车潜在需求对区域共享泊位选择的影响，本文通过分析历史停车数据得到当日潜在停车需求，以区域共享停车场和道路网络为研究对象，构建考虑潜在需求的区域多停车场泊位动态预约与分配整数线性规划模型。模型以平台收益和用户成本两者综合收益最高为目标，在分配开始前，处理提前预约停车用户数据时考虑潜在停车需求，提前拒绝一部分周转率较差和车位利用率较低的停车预约用户，在开始分配阶段，同时考虑提前预约用户和临时预约用户，根据实时路网交通流状况进行车位滚动时域分配。通过模型评价和算例分析发现，当停车需求较大时，在实时分配预约停车用户过程中考虑潜在需求能够提高后续泊位分配收益。相比单一停车场的共享泊位分配研究，考虑潜在需求并根据路网交通状况和停车用户信息进行区域共享泊位滚动时域动态分配会使停车场收益平均提高10%，停车位利用率和拒绝率分别提高20%和降低8.5%。在考虑潜在需求的情况下，拒绝的停车用户数量和停车时长均显著影响系统收益。模型可为共享停车平台在局部存在多共享停车场和多目的地时的停车分配与管理决策提供理论参考。