需求响应式公交中考虑即时订单的线路重调度优化  

Optimization of Route Rescheduling Considering Realtime Orders in Demandresponsive Transit

作　　者：赫雪婷 镇璐[1] HE Xue-ting;ZHEN Lu(School of Management,Shanghai University,Shanghai 200444,China)

机构地区：[1]上海大学管理学院,上海200444

出　　处：《中国管理科学》2023年第3期113-123,共11页Chinese Journal of Management Science

基　　金：国家自然科学基金资助重点项目(71831008);国家杰出青年科学基金资助项目(72025103)。

摘　　要：为了同时满足需求响应式公交中预约订单和即时订单两种用户需求,设计了一个公交线路的重新调度优化模型。该模型确保在满足预约订单出行需求的基础上,对公交行驶线路进行调度优化,以响应即时订单的需求,实现系统利润最大化的目标。根据模型的特殊结构,运用列生成算法求解,并设计了双向标签算法以加速子问题的求解效率。基于一个以上海市为背景的实际案例,验证了模型的可行性与有效性,大量的数值实验进一步验证了算法的高效性。结果表明:本文提出的模型与设计的算法可在较短时间内响应即时订单需求,并且可显著提高公交系统的收益。To satisfy the existing demand for convenient and ontime travel,a new kind of public transportation service systemdemandresponsive bus system—is rapidly developing in China.In a demandresponsive transit system,regular travel routes are developed from longterm experience.Customers can reserve travel services in the system according to the information of regular travel routes.Meanwhile,some customers have realtime travel requirements.Under the premise of meeting the demand of scheduled orders,how the routine travel routes are rescheduled to better respond to the customers’realtime orders is the key issue in this paper.To solve the mentioned problem,a mixed integer programming model with the objective of maximizing the system revenue is proposed.The proposed model reschedules regular travel routes while satisfying the pick-up and drop-off stops,time windows and vehicle capacity constraints for scheduled orders,and makes decisions on whether real-time orders are served,the pick-up and drop-off stops for real-time orders,the routes joined by real-time orders,and new driving routes for the buses.Based on the special structure of the model,the column generation algorithm is used to solve the problem.To further improve the solving efficiency,a tailored bi-directional labelling algorithm is proposed to solve subproblem.Subsequently,a real case is designed in the context of Shanghai.The results show that the proposed model can effectively improve the system's revenue,and the tailored algorithm can quickly respond to the real-timeorders.Further,extensive numerical experiments are designed to validate the proposed model and tailored algorithm's effectiveness.

关 键 词：需求响应式公交 路径优化 列生成算法 双向标签算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]