Passenger-centric vehicle routing for first-mile transportation considering request uncertainty
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 Transpo...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/148610 |
| _version_ | 1826113764714348544 |
|---|---|
| author | Ning, Fangxin Jiang, Guiyuan Lam, Siew-Kei Ou, Changhai He, Peilan Sun, Yidan |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Ning, Fangxin Jiang, Guiyuan Lam, Siew-Kei Ou, Changhai He, Peilan Sun, Yidan |
| author_sort | Ning, Fangxin |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T03:28:34Z |
| format | Journal Article |
| id | ntu-10356/148610 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:28:34Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | ntu-10356/1486102021-12-04T07:53:37Z Passenger-centric vehicle routing for first-mile transportation considering request uncertainty Ning, Fangxin Jiang, Guiyuan Lam, Siew-Kei Ou, Changhai He, Peilan Sun, Yidan School of Computer Science and Engineering Engineering::Computer science and engineering First-Mile Transportation Passenger-Centric Request Uncertainty Hybrid Demand Vehicle Routing 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. Accepted version 2021-05-27T01:50:35Z 2021-05-27T01:50:35Z 2021 Journal Article 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 0020-0255 https://hdl.handle.net/10356/148610 10.1016/j.ins.2021.04.054 570 241 261 en Information Sciences © 2021 Elsevier Inc. All rights reserved. This paper was published in Information Sciences and is made available with permission of Elsevier Inc. application/pdf |
| spellingShingle | Engineering::Computer science and engineering First-Mile Transportation Passenger-Centric Request Uncertainty Hybrid Demand Vehicle Routing Ning, Fangxin Jiang, Guiyuan Lam, Siew-Kei Ou, Changhai He, Peilan Sun, Yidan Passenger-centric vehicle routing for first-mile transportation considering request uncertainty |
| title | Passenger-centric vehicle routing for first-mile transportation considering request uncertainty |
| title_full | Passenger-centric vehicle routing for first-mile transportation considering request uncertainty |
| title_fullStr | Passenger-centric vehicle routing for first-mile transportation considering request uncertainty |
| title_full_unstemmed | Passenger-centric vehicle routing for first-mile transportation considering request uncertainty |
| title_short | Passenger-centric vehicle routing for first-mile transportation considering request uncertainty |
| title_sort | passenger centric vehicle routing for first mile transportation considering request uncertainty |
| topic | Engineering::Computer science and engineering First-Mile Transportation Passenger-Centric Request Uncertainty Hybrid Demand Vehicle Routing |
| url | https://hdl.handle.net/10356/148610 |
| work_keys_str_mv | AT ningfangxin passengercentricvehicleroutingforfirstmiletransportationconsideringrequestuncertainty AT jiangguiyuan passengercentricvehicleroutingforfirstmiletransportationconsideringrequestuncertainty AT lamsiewkei passengercentricvehicleroutingforfirstmiletransportationconsideringrequestuncertainty AT ouchanghai passengercentricvehicleroutingforfirstmiletransportationconsideringrequestuncertainty AT hepeilan passengercentricvehicleroutingforfirstmiletransportationconsideringrequestuncertainty AT sunyidan passengercentricvehicleroutingforfirstmiletransportationconsideringrequestuncertainty |