Please use this identifier to cite or link to this item:
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.
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.
ISSN: 1524-9050
DOI: 10.1109/TITS.2019.2926065
Schools: School of Computer Science and Engineering 
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:
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
2019jiang.pdf4.65 MBAdobe PDFThumbnail

Citations 20

Updated on Jun 20, 2024

Web of ScienceTM
Citations 20

Updated on Oct 31, 2023

Page view(s)

Updated on Jun 24, 2024

Download(s) 50

Updated on Jun 24, 2024

Google ScholarTM




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