Please use this identifier to cite or link to this item:
Title: Passenger-centric vehicle routing for first-mile transportation considering request uncertainty
Authors: Ning, Fangxin
Jiang, Guiyuan
Lam, Siew-Kei
Ou, Changhai
He, Peilan
Sun, Yidan
Keywords: Engineering::Computer science and engineering
Issue Date: 2021
Source: Ning, F., Jiang, G., Lam, S., Ou, C., He, P. & Sun, Y. (2021). Passenger-centric vehicle routing for first-mile transportation considering request uncertainty. Information Sciences, 570, 241-261.
Journal: Information Sciences 
Abstract: First-mile transportation provides convenient transit service for passengers to travel from their homes, workplaces, or public institutions to a public transit station that is located beyond comfortable walking distance. This paper studies the Passenger-Centric Vehicle Routing for First-Mile Transportation (PCVR-FMT) problem to plan optimal vehicle routes that provide a high quality of service (QoS) to enhance passenger experience. We consider a practical scenario with 1) deterministic requests, consisting of travel requests that are known in advance (e.g., submitted by passengers through a mobile application), and 2) uncertain requests (e.g., new travel requests generated during service operation). We formally formulate the PCVR-FMT problem to maximize the QoS in terms of the passenger waiting and riding time (for both deterministic and uncertain requests) while jointly considering the traditional constraints on the pickup time window as well as vehicle capacity. We developed an Ant-Colony Optimization algorithm based on a novel Dynamic Request Driven scheme for vehicle route construction, denoted as DRD-ACO, to efficiently solve PCVR-FMT. DRD-ACO relies on a novel request-location graph that models both deterministic and uncertain requests, which enable the ants to share information across different generations via pheromone for dealing with uncertain requests. A dynamic seat reservation mechanism is devised to determine a suitable number of reserved seats to deal with uncertain requests. A time window expansion mechanism is developed to selectively expand passengers’ pickup time window if the number of vehicles is insufficient. The effectiveness of the proposed methods is evaluated using Singapore’s road network and synthetic travel requests generated from real bus travel demands. Some of the travel requests are treated as uncertain requests. The results show that on relatively small size instances, our methods obtain solutions that are close to the optimal ones computed by CPLEX, with deviations ranging from only 2.55% to 8.79%. In comparison to other baselines, our methods achieve better results in the objective function, ratio of served uncertain passengers, as well as the expansion in waiting time due to request uncertainty, for both small-scale and large-scale problem instances.
ISSN: 0020-0255
DOI: 10.1016/j.ins.2021.04.054
Schools: School of Computer Science and Engineering 
Rights: © 2021 Elsevier Inc. All rights reserved. This paper was published in Information Sciences and is made available with permission of Elsevier Inc.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Citations 20

Updated on Nov 24, 2023

Web of ScienceTM
Citations 20

Updated on Oct 30, 2023

Page view(s)

Updated on Dec 7, 2023


Updated on Dec 7, 2023

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.