Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/148610
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. https://dx.doi.org/10.1016/j.ins.2021.04.054
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.
URI: https://hdl.handle.net/10356/148610
ISSN: 0020-0255
DOI: 10.1016/j.ins.2021.04.054
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: embargo_20230930
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
Passenger-centric vehicle routing for first-mile transportation considering request uncertainty.pdf
  Until 2023-09-30
1.11 MBAdobe PDFUnder embargo until Sep 30, 2023

Page view(s)

143
Updated on Jul 1, 2022

Google ScholarTM

Check

Altmetric


Plumx

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