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

摘要： 点对点直达运输是实现交通集散点乘客快速分流的重要方式。然而，各集散点间的随机乘客需求，为运输服务商的车辆调度决策带来了挑战。若服务提供商仅根据当前观察到的乘客需求以最大化即时收益进行决策，则属于短视行为——后续阶段随机乘客需求与车辆资源的不匹配将导致期望收益下降。因此，如何统筹调度车辆，使当前收益与后续阶段期望收益达到最大，成为服务商运营中的关键问题。本文针对带有随机需求的两阶段点对点运输网络的调度决策问题展开研究，首先建立两阶段随机整数规划模型，进而结合模型结构特征，提出了一种具有多项式复杂度TRAC（treerec with arc combination）的算法，用于高效求解第2阶段的期望值函数，数值实验表明，TRAC算法能在保证精确最优解的同时显著提升求解速度，尤其适用于现实中的大规模调度问题。

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