Vehicle routing for customized on-demand bus services
- 21 March 2023
- journal article
- research article
- Published by Taylor & Francis in IISE Transactions
- Vol. 55 (12) , 1277-1294
Abstract
This study investigates a variant of the vehicle routing problem (VRP) for customized on-demand bus service platforms. In this problem, the platform plans customized bus routes upon receiving a batch of orders released by passengers and informs the passengers of the planned pick-up and drop-off locations. The related decision process takes into account some passenger-side time window-related requirements, walking limits, the availability and capacities of various types of buses. A mixed-integer linear programming model of this new VRP variant with floating targets (passengers) is formulated. To solve the model efficiently, a solution method is developed that combines the branch-and-bound and column generation algorithms and includes embedded acceleration techniques such as the multi-labeling algorithm. Experiments based on real data from Dalian, China are conducted to validate the effectiveness of the proposed model and efficiency of the algorithm; the small-scale experimental results demonstrate our algorithm can obtain optimal results in majority of instances. Additionally, sensitivity analysis is conducted and model extensions are investigated to provide customized bus service platform operators with potentially useful managerial insights; for example, a platform need not establish as many candidate stops as possible, a wide range of walking distance may not bring early arrival at destinations for customers, more mini-buses should be deployed than large buses in our real-world case. Moreover, the rolling horizon based context and zoning strategies are also investigated by extending our proposed methodology.Keywords
Funding Information
- National Natural Science Foundation of China (72025103, 71831008, 72071173, 71871043)
This publication has 30 references indexed in Scilit:
- Key determinants and heterogeneous frailties in passenger loyalty toward customized buses: An empirical investigation of the subscription termination hazard of usersTransportation Research Part C: Emerging Technologies, 2020
- A two-phase optimization model for the demand-responsive customized bus network designTransportation Research Part C: Emerging Technologies, 2020
- Optimal zone sizes and headways for flexible-route bus servicesTransportation Research Part B: Methodological, 2019
- An integrated car-and-ride sharing system for mobilizing heterogeneous travelers with application in underserved communitiesIISE Transactions, 2019
- CB-Planner: A bus line planning framework for customized bus systemsTransportation Research Part C: Emerging Technologies, 2019
- The Vehicle Routing Problem with Floating Targets: Formulation and Solution ApproachesINFORMS Journal on Computing, 2018
- Customized bus service design for jointly optimizing passenger-to-vehicle assignment and vehicle routingTransportation Research Part C: Emerging Technologies, 2017
- Optimization for dynamic ride-sharing: A reviewEuropean Journal of Operational Research, 2012
- Pedestrians' Normal Walking Speed and Speed When Crossing a StreetTransportation Research Record: Journal of the Transportation Research Board, 2007
- Decomposition Principle for Linear ProgramsOperations Research, 1960