Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/147524
Title: Peak-hour vehicle routing for first-mile transportation : problem formulation and algorithms
Authors: Jiang, Guiyuan
Lam, Siew-Kei
Ning, Fangxin
He, Peilan
Xie, Jidong
Keywords: Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence
Issue Date: 2020
Source: Jiang, G., Lam, S., Ning, F., He, P. & Xie, J. (2020). Peak-hour vehicle routing for first-mile transportation : problem formulation and algorithms. IEEE Transactions On Intelligent Transportation Systems, 21(8), 3308-3321. https://dx.doi.org/10.1109/TITS.2019.2926065
Journal: IEEE Transactions on Intelligent Transportation Systems 
Abstract: The first-mile transportation provides a transit service using ridesharing-based vehicles, e.g., feeder buses, for passengers to travel from their homes, workplaces, or public institutions to the nearest public transportation depots (rapid-transit metro or appropriated bus stations) which are located beyond comfortable walking distance. This paper studies the vehicle routing problem (VRP) for the first-mile transportation, which aims at finding the optimal travel routes for a vehicle fleet to deliver passengers from their doorstep to the depots, where the passengers can continue their journeys using fixed-route buses or trains. We focus on the Peak-Hour VRP (PHVRP) for a limited vehicle fleet capacity to serve a large volume of travel requests, with the aim of maximizing the number of served passengers. The PHVRP generalizes the VRP with time window by considering multiple alternative depots for each travel request, such that a request is satisfied if the passenger is taken to one of his/her nearest depots. We formally formulate the PHVRP with constraints on vehicle capacity, pickup time windows, and quality of service regarding riding time, where a novel trip-based constraint model is used. We proposed an ant-colony optimization algorithm for the PHVRP, which is initialized with pheromone information that jointly considers the temporal-spatial distance as well as depot similarity among different travel requests. We introduced a novel scheme (called trip-by-trip scheme) to construct the travel routes by repeatedly forming a single trip for the vehicle with earliest end time until no vehicle can accept any more trips. In constructing a single trip, the algorithm intelligently decides whether or not to end the trip instead of taking more passengers. The effectiveness of the proposed methods is evaluated by comparing with optimal solutions on small size instances and with heuristic solutions on large-size instances, using road network in Singapore and synthetic travel requests that are generated based on real bus travel demands.
URI: https://hdl.handle.net/10356/147524
ISSN: 1524-9050
DOI: 10.1109/TITS.2019.2926065
Rights: © 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: https://doi.org/10.1109/TITS.2019.2926065
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
2019jiang.pdf4.65 MBAdobe PDFView/Open

SCOPUSTM   
Citations 50

6
Updated on Nov 26, 2022

Web of ScienceTM
Citations 20

5
Updated on Nov 27, 2022

Page view(s)

132
Updated on Dec 1, 2022

Download(s) 50

70
Updated on Dec 1, 2022

Google ScholarTM

Check

Altmetric


Plumx

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