时变交通拥挤和需求随机的移动设施运营优化  

Optimization of mobile facility operations under time-varying traffic congestion and stochastic demand

作　　者：龚华天 杨晓光[1,2] GONG Huatian;YANG Xiaoguang(Urban Mobility Institute,Tongji University,Shanghai 201804,China;School of Traffic and Transportation Engineering,Tongji University,Shanghai 201804,China)

机构地区：[1]同济大学,城市交通研究院,上海201804 [2]同济大学,交通运输工程学院,上海201804

出　　处：《交通运输工程与信息学报》2024年第2期147-162,共16页Journal of Transportation Engineering and Information

基　　金：国家自然科学基金项目(52072264);广西科技重大专项项目(2023AA14006);郑州市重大科技创新专项子课题项目(2021KJZX0060-9)。

摘　　要：为了优化移动设施(Mobile Facility,MF)的运营,在充分考虑时变交通状况和用户需求随机性的基础上,构建了一个两阶段随机规划模型,以期为决策者提供有力的工具。在第一阶段,模型针对MF的数量、时刻表和路径进行决策;第二阶段则聚焦于用户需求的分配和未满足服务量的确定。在求解此模型的过程中,本研究结合了时间依赖最短路径算法与L-shaped算法。在解决MF的移动路径和用户到达服务点的时间依赖最短路径问题时,将时变路段行驶速度离散化为分段函数,使得路段行驶时间成为连续分段线性函数,并且满足网络先进先出的原则,从而可以修改现有最短路径算法高效求解时间依赖最短路径。在L-shaped算法中,视一阶段模型为主问题,二阶段模型为子问题。首先通过求解主问题获得一阶段的决策变量,然后利用这些变量求解子问题,为主问题生成最优割。通过主、子问题的迭代交互,实现了对模型全局最优解的收敛,同时,通过加入有效不等式,使得算法能够快速收敛。在上海市嘉定区COVID-19核酸检测服务的MF实例中,对所提出的模型和算法进行了实证研究。结果表明:多割L-shaped算法结合有效不等式显著提升求解效率;同时,随着用户需求分布情况数量的增加,完美信息期望值和随机解价值均显著增加,这强调了在决策过程中获取准确信息和考虑时变交通状况与需求随机性的重要性。A two-stage stochastic planning model is developed to optimize the operation of Mobile Facility(MF).The model considers the stochastic nature of both time-varying traffic conditions and user demands,providing a powerful tool for decision-makers.In the first stage,the model decides the number of MFs,schedules,and routes.The second stage focuses on the allocation of user demands and determines the unsatisfied service volume.To solve this model efficiently,this study combines time-dependent shortest-path algorithms with an L-shaped algorithm.To solve the time-dependent shortest-path problems for the movement paths of MFs and user arrivals at service points,the vary-ing speeds on the road links are discretized into piecewise functions.This makes the travel time a continuous linear function that satisfies the first-in-first-out network property,thereby enabling the modification of existing shortest-path algorithms for solving the time-dependent shortest-path problems.In the L-shaped algorithm,the first-stage model is treated as the master problem,whereas the second-stage model serves as a subproblem.The algorithm first solves the master problem to obtain the first-stage decision variables,which are then used to solve the subproblem to generate optimal cuts for the master problem.Through iterative interactions between the master problem and subproblem,convergence to the global optimal solution of the model is achieved.In addition,the algorithm converges rapidly by incorporating valid inequalities.The proposed model and algorithm are empirically studied using the case of MF instances in the COVID-19 nucleic acid testing service in Jiading District,Shanghai.The results indicate that the multi-cut L-shaped algorithm combined with valid inequalities significantly improves the solution efficiency.Furthermore,as the scenarios of the user demand distribution increase,both the expected value of perfect information and the value of stochastic solutions significantly increase.These results underscore the importance of obtaining

关 键 词：城市交通 移动设施 时变交通拥挤 需求随机 随机模型 时间依赖最短路径 L-shaped算法 有效不等式 

分 类 号：U491[交通运输工程—交通运输规划与管理]