关键词: 点对点运输网络, 随机需求, 调度决策, 随机规划, 算法

Abstract: Point-to-point direct transportation is one of the key approaches for efficiently dispersing passengers at transportation hubs. However, the stochastic passenger demand between these hubs poses significant challenges to vehicle dispatching decisions for transportation service providers. If providers make decisions solely based on the observed demand in the current stage to maximize immediate revenue, such an approach can be short-sighted. This is because mismatches between vehicle supply and uncertain future demand in the subsequent stage may lead to a decline in expected overall revenue. Therefore, the core operational challenge lies in how to schedule vehicles to maximize the combined profit of the current stage and the expected profit in the next stage. This paper investigates the vehicle dispatching problem in a two-stage point-to-point transportation network under stochastic demand. First, it develops a two-stage stochastic integer programming model to formulate the problem. Then, leveraging the structural characteristics of the model, it proposes a polynomial-time TRAC (treerec with arc combination) algorithm to efficiently solve the expected value function in the second stage. Numerical experiments demonstrate that the TRAC algorithm can obtain exact optimal solutions with high computational efficiency, making it particularly suitable for large-scale real-world applications.

Key words: point-to-point transportation networks, stochastic demand, dispatching decision, stochastic programming, algorithm