Vehicle assignment and relays for one-way electric car-sharing systems. (February 2019)

• Record Type: Journal Article
• Authors: Zhang, Dong; Liu, Yang; He, Shuangchi
• Is Part Of: Transportation research. Volume 120(2019)
• Page Start: 125
• Page End: 146
• Publication Date: 2019-02
• Subjects: One-way electric car-sharing systems -- Space–time–battery network flow model -- Optimal vehicle assignment -- Vehicle relay; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2018.12.004
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: We optimize vehicle assignment and relays to circumvent battery constraints and to improve utilization in electric car-sharing systems. We propose a novel space-time-battery network flow model that is computationally amiable. We develop a novel diving heuristic guided by LP relaxations and propose perturbed models that are computationally tractable. Our approach can consistently obtain satisfactory solutions in much shorter time than using the CPLEX solver. Numerical results show that the optimal assignment and relay decision may achieve a comparable vehicle utilization rate as in a non-electric car-sharing system. Abstract: One-way electric car-sharing systems are expected to be an integral part of future transportation systems, playing an important role in reducing traffic congestion and carbon emissions. Owing to limited battery capacities and the lengthy charging process, an electric car-sharing system may not achieve the high vehicle utilization that a non-electric car-sharing system can achieve. We investigate two approaches to vehicle management, in order to circumvent battery constraints and to improve vehicle utilization rates in one-way electric car-sharing systems. In the first approach, we optimize vehicle assignment decisions, and in the second approach, we further allow vehicle relays, enabling users to complete longer trips by sequentially taking two vehicles. We propose a novel space–time–battery network flow model to determine optimal assignment and relay decisions. With an extra dimension for tracking each vehicle's battery level, the proposed model is a single-commodity network flow model that is computationally amiable. To meet the requirement of quick responses, we propose an efficient algorithm that exploits an innovative diving heuristic to solve the resulting integer program. Numerical results show that when vehicle assignment and relays are optimized in an electric car-sharing system, we may achieve a comparable vehicle utilization rate as in a non-electric car-sharing system. In particular, optimizing vehicle assignment is essential when most trips are short trips, and vehicle relays are critical when users demand more long trips.