1. Optimizing Cross-Line Dispatching for Minimum Electric Bus Fleet
- Author
-
Lu Su, Chonghuan Wang, Xinbing Wang, Guiyun Fan, Haiming Jin, Fan Zhang, and Yiwen Song
- Subjects
Operations research ,Exploit ,Computer Networks and Communications ,Computer science ,business.industry ,media_common.quotation_subject ,Approximation algorithm ,Construct (python library) ,Purchasing ,Scarcity ,Public transport ,Combinatorial optimization ,TRIPS architecture ,Electrical and Electronic Engineering ,business ,Software ,media_common - Abstract
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)$ -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.
- Published
- 2023
- Full Text
- View/download PDF