带换乘与步行服务的电话约车问题

《EURO Journal on Transportation and Logistics》：The Dial-A-Ride Problem with transfers and walking

　　

本研究提出带换乘与步行服务的电话约车问题（Dial-A-Ride Problem with Transfers and Walking，DARPTW），该问题是经典电话约车问题（Dial-A-Ride Problem，DARP）的推广，其中乘客行程可包含多次换乘与步行段。优化目标为最小化双准则函数，包括车辆总行驶时间与所有用户总行程时间。引入换乘与步行可提升运营灵活性，实现负载均衡、缩小服务区域并利用步行捷径避免不必要车辆绕行，但同时也显著增加问题复杂度，因DARPTW推广了本已NP难（NP-hard）的DARP。为应对该挑战，研究人员提出一种自适应大邻域搜索（Adaptive Large Neighborhood Search，ALNS）框架，集成可行性检查与调度启发式。可行性检查准确且计算高效，调度器高效性使该方法支持迭代或近实时路由。基于特拉维夫Bubble-Dan真实运营数据的计算实验表明，ALNS在各规模算例上持续产出高质量可行解，而精确方法迅速不可解。针对换乘策略的聚焦分析显示，在步行灵活性受限或车辆容量受限等约束条件下，换乘对提升可行性与路由效率最为有利。

研究背景方面，持续城市化使高密度人口下公共交通需求聚合潜力增大，但传统公交因时间长、频次低、接驳步行距离不合理而吸引力不足。电话约车（DARP）原为行动不便者提供点对点响应式出行，现代网约车（ride-pooling）通过手机应用支持预约与近实时请求。DARP作为取送货问题（Pickup and Delivery Problem，PDP）的推广是NP难问题，需在容量、车场、时间窗与最大乘车时长约束下优化运营成本与服务质效。既有文献分别研究过单次换乘的DARPT（Dial-A-Ride Problem with Transfers）与仅端点步行的检查点DARP，但换乘与步行在统一框架内联合优化及其交互影响尚属空白。鉴于现代网约车面向普通人群，可在不损害门到门体验前提下利用多次换乘与途中步行提升效率，故研究人员开展DARPTW研究。

主要关键技术方法上，研究人员构建了四下标混合整数线性规划（four-index MILP）模型；设计了四步启发式处理含多次换乘与车辆交换交织连接的可行调度；在ALNS框架中引入请求间相似性度量并改造插入启发式以显式纳入换乘与步行；基于特拉维夫Bubble-Dan真实运营数据生成新基准算例集。此外，调度子问题通过专用可行性检查与高效调度器求解，支撑迭代与近实时决策。

研究结果部分，引言指出DARP变体研究脉络及换乘与步行单独研究的局限，明确DARPTW将多次换乘与任意阶段步行（含换乘点间步行）统一建模，目标为车辆总行驶时间加用户总行程时间（含步行、等待、车内及拼车绕行时间），并对最大步行时间与最大换乘次数设限。第2节问题定义与建模在完全有向图G=(V,A)上给出车辆集合?={1,…,m}、起点车场??={o₁,…,o_m}与终点车场?={f₁,…,f_m}，异质车辆容量Q_k，用户请求集合?={1,…,n}含上车点??、下车点??、群体规模q_r、时间窗[e_r,l_r]与最大行程时间J_r，以四下标变量表述路径与换乘节点指派，目标最小化Σ车辆行驶时间+Σ用户行程时间，约束涵盖容量、时间窗、最大换乘数、最大步行时间、车辆起讫车场。第3节调度子问题给出给定车辆序列下判定乘客行程可行并分配步行/换乘/等待时间的四步启发式，确保时间窗与行程上限不被破坏。第4节ALNS框架扩展请求相似度（融合起讫点、时间窗、换乘容忍度）并修正插入代价估算，使销毁与修复算子能评估含步行 shortcut 与多段换乘的路线增量收益。第5节计算实验基于Bubble-Dan数据，实例规模渐增，对比ALNS与精确法：精确法在小型实例即不可解，ALNS在各类规模保持可行与稳定收敛；换乘策略分析显示当步行上限收紧或车辆容量下降时，允许换乘显著提升接受率与降低车辆里程，而步行宽松时换乘边际收益减弱。第6节结论讨论指出DARPTW较DARP/DARPT更贴近网约车实际，多次换乘分解行程可改善负载均衡、缩小单车服务区，步行可补路网有向约束下的捷径；限制条件（最大步行时长、最大换乘次数）保障用户体验不劣化。研究贡献为四方面：定义DARPTW并建MILP、四步调度启发式、ALNS扩展、Bubble-Dan基准集。该文发表于《EURO Journal on Transportation and Logistics》。

讨论与结论翻译总结：研究人员认为，尽管DARP文献曾孤立考察换乘或步行，DARPTW首次在统一模型中允许乘客多次换乘且在行程任意阶段（含换乘站之间）步行，利用路网有向性未覆盖的步行捷径降低绕行。双准则目标以用户总行程时间表征服务质量、车辆总行驶时间表征运营成本。实验证实ALNS较精确法更适合近实时运营，且换乘在资源受限情境（有限步行、有限容量）下效益最大。未来方向可包括动态请求流入、与固定线路公交协同及用户异质性偏好建模，但原文仅列示方向未展开。全文所有结论均根植于上述MILP表述、四步调度与ALNS计算证据，未对未实验假设做推断。