Abstract:

For solving contradictions between service quality and service efficiency, this paper proposes a method designing demand-responsive service by mixed-type vehicles. Firstly, a k-means-based algorithm is used to cluster requests which scatters in spatiotemporal space, into service units. Then the assigning and routing of vehicles is viewed as a pickup and delivery problem with time windows; a model whose objective are minimizing total running distance and count of vehicles is made by Dantzig-Wolfe decomposition. In order to have an exact and efficient solution for problem, a distributed column generation algorithm based on MapReduce framework is proposed, with an approach avoiding infeasibility of solution caused by linear relaxation. Finally, taking Beijing as the background of a case, the feasibility and accuracy of our study is proved.

Key words: urban traffic, pickup and delivery problem with time windows, MapReduce framework, demandresponsive service, distributed column generation

摘要：

针对现存需求响应公交服务中服务质量与服务效率的矛盾，本文提出一种使用混合车型的需求响应服务定制方法.首先采用基于k-means的算法，获得具有时空特性的服务单元.在此基础上，将载运车辆的分配与路径规划问题，视为一个带时间窗的取送问题，通过Dantzig-Wolfe分解，以最小化走行距离和使用车辆数为目标，构建需求响应公交服务定制等价分解模型.在MapReduce框架下，设计了分布式列生成算法，提出了解的可行性保障机制.最后，求解以北京市为背景的案例，验证了模型和方法的可行性和正确性.

关键词: 城市交通, 带时间窗的取送模型, MapReduce框架, 需求响应公交服务定制, 分布式列生成算法