Abstract:

This paper addresses the least-time itinerary planning problem for the urban public-transport travelers, especially those with deadlines imposed at their destinations. A risk- pooling- based robust model is used to solve the problem. Headway and travel time of each bus are uncertain, which are given in intervals in this paper. Based on the risk pooling concept, the set of combined uncertain travel times and headways are designated. This set could be adjusted flexibly by a parameter, which represents the conservativeness of each traveler. Subsequently, a robust model for the problem is proposed, as well as an exact polynomial time algorithm. Through an example and the associated simulation, the paper demonstrates that the solution of this model (compared with the solution of the deterministic model) is less likely to break the deadline. It is also concluded that an itinerary is more inclined to be a robust optimal solution with less transfer times or by more reliable bus lines.

Key words: urban traffic, itinerary planning, robust optimization, bus traveler, risk pooling

摘要：

本文面向城市中需要在给定期限内到达终点的出行者，针对最短耗时公交换 乘问题，利用基于风险分担的鲁棒优化方法进行了建模和求解.公交行车时间和发车间隔 时间是不确定的，本文将其建模为区间数，并基于风险分担的思想给出了这些不确定参 数的集合描述，该集合可以通过一个代表出行者保守程度的参数进行灵活调整，在此基 础上提出了城市公交换乘最短耗时鲁棒优化模型，给出了多项式时间精确算法.通过对一 个算例的求解和仿真实验，展示了该模型求解结果（相对于确定性模型的求解结果）具有 更小的迟到概率；并通过分析讨论，总结出换乘更少，运行更稳定的换乘方案更倾向于成 为鲁棒最优换乘方案.

关键词: 城市交通, 换乘路径优化, 鲁棒优化, 公交出行者, 风险分担