查看文章

Dial-a-ride problems aim to design the least-costly door-to-door vehicle routes for transporting individual users, subject to several service constraints like time windows, service and route durations, and ride-time. In some cases, providers cannot meet the demand and may outsource some requests. In this paper, we introduce, model, and solve the dial-a-ride problem with private fleet and common carrier (DARP-PFCC) that makes it possible to transfer the demand unmet by the provider to mobility-on-demand services and taxis. All outsourced vehicles are assumed to be available at any instant of the day and have unlimited capacity, enabling to satisfy all user requests, particularly during peak times. We implement a branch-and-cut (B&C) algorithm based on an exact method from the literature to solve the DARP-PFCC, and we develop a near parameter-free parallel metaheuristic to handle large instances. Our …