.png){kind=icon}
.png){kind=icon}
Return
Optimizing Cross-Line Dispatching for Minimum Electric Bus Fleet
.png){kind=icon}
PRE
AI
DOI：10.1109/TMC.2021.3119421.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Recent years have witnessed the increasing popularity of electric buses (e-buses) around the globe due to their environment friendly nature. However, various factors, such as the prohibitive purchasing costs and the scarcity of large-scale charging facilities, hinder the wider adoption of e-buses. Thus, to effectively cut the cost of building and maintaining urban e-bus systems, we optimize the dispatching strategy for urban e-bus systems to satisfy public transportation demands with the minimum e-bus fleet. Specifically, we propose to systematically exploit at city-scale cross-line dispatching, a smart dispatching strategy allowing one bus to serve multiple bus lines when necessary. Technically, we construct a novel and generalizable graph-theoretic model for urban e-bus systems integrating e-buses non-negligible charging time, the spatio-temporal constraints of bus trips, and various other real-world factors. We prove that it is NP-hard, and has no $(2-\epsilon)$(2-e)-approximation algorithm. Next, we propose a polynomial-time algorithm solving the problem with a guaranteed approximation ratio. Furthermore, we conduct extensive experiments on a large-scale real-world bus dataset from Shenzhen, China, which validate the effectiveness of our algorithms. As shown by our experimental results, to serve 300 bus lines, our dispatching strategy needs 38.2% less e-buses than the one currently used in practice.
Keywords:
Dispatching
Task analysis
Urban areas
Approximation algorithms
Costs
Schedules
Public transportation
Cross-line dispatching
electric bus
minimum fleet
combinatorial optimization
Journal
IF:
9.2
Papers:
5.6K
Citations:
1.8W
View more organizations