陈可嘉 方云飞 骆佳艺

（福州大学经济与管理学院 福州350116）

0 引言

叫车接送运输（dial-a-ride transportation，DART）是指乘客打电话到运营中心告知其接送需求（包括接送起点和终点）后，运营中心的调度员根据乘客预约信息规划路线，并指派车辆接送用户，完成接送任务的面向预约的运输方式[1-2]。这种运输方式作为公共交通运输的1种补充形式，主要是为行动不便的老年人和残疾人设计门到门的接送服务，所使用的车辆配备有轮椅坡道或者轮椅升降机，车内除了正常的座位，还配有担架位、轮椅位，以满足乘客的不同需求，为他们的出行提供便利。随着老年人口比例逐年上升，以及医疗保健服务不断发展，叫车接送运输的需求量日益增长。考虑到运输对象多为特殊群体，为了设计合适的运输路线以避免用户就医延误、实现高质量的服务，过去40年来，叫车接送问题（Dial-a-ride Problem，DARP）已经被研究人员广泛探讨[3]。

DARP是车辆路径问题（vehicle routing problem，VRP）的延伸。然而，DARP不同于VRP及其扩展问题，因为DARP涉及到人而不是货物的运输。DARP满足乘客给定接送起点和终点的接送需求，并且可同时服务多名乘客。因此，DARP关注乘客在特殊要求下出行服务的高水平高质量。一般情况下，DARP旨在最大限度地降低车辆运营成本（主要与车辆行驶成本相关），同时达到乘客可接受的服务水平（主要包括服务时间窗要求、位置资源要求和乘坐时间限制等）。

尽管DARP是1个NP-hard问题，但目前学者对这个问题已经进行了诸多研究，大量的启发式方法被提出并广泛应用于这个问题。……