Electric Vehicle Assignment Considering Users’ Waiting Time: Comparison
View Latest Version
Please note this is a comparison between Version 2 by Bruce Ren and Version 1 by Jiakai Chen.

A one-way electric-car-sharing system is an environmentally friendly option for urban transportation systems, which can reduce air pollution and traffic congestion with effective vehicle assignment. However, electric vehicle assignment usually faces a dilemma where an insufficient battery level cannot fulfill the requests of users. It greatly affects assignment choices and order fulfillment rates, resulting in the loss of platform profit. In this study, with the assumption that the users agree to wait for a period of time during which electric vehicles can be charged to fulfill trip demands, we proposed a waiting-time policy and introduced users’ utility to measure user retention. 

  • electric vehicle
  • vehicle assignment
  • waiting time
  • bi-level programming

1. Introduction

While people’s living standards and the growth of population keep increasing, people are increasingly demanding comfortable, convenient, fast, and safe travel modes. Private cars have naturally become the first choice, which has also led to a substantial increase in the amount of private cars. According to the statistics provided by URORA [1], the amount of private cars in China has exceeded 200 million. It causes a significant amount of social and environmental issues including traffic congestion, air pollution, higher accident rates, etc. In order to encourage people to choose a more environmentally friendly travel mode, local and regional governments have proposed some measures like license-plate restrictions and increased purchase taxes. However, private car traveling still accounts for most of the travel market share.
Consideration must be taken in both user travel experience and traffic and environmental problems. The car-sharing system (CSS) was originally developed in Switzerland in 1948 and was grown rapidly all over the world during the 1990s [2]. It allows users to pay a rental fee to get the experience of private vehicles rather than to buy a car. The CSS can significantly decrease the amount of vehicles in cities while increasing the vehicle utilization rate, saving land resources and reducing the traffic pressure [3]. Nevertheless, it does not completely solve the above dilemma. The CSS needs many cars to maintain operational stability, and fuel cars not only cost high in maintenance and traveling but also consume gasoline, which will cause environmental pollution. It causes the platform to face a high operating stress, and users need to pay higher rents.
However, the rapid development of electric vehicles (EVs) such as by Tesla brings new ideas to CSS in recent years. EVs not only have low travel costs but also solve problems such as environmental pollution and noise effectively, so CSS has absorbed more EVs for further sustainability. At the same time, countries also regard EVs as a solution to environmental pollution problems. They subsidize EVs, hoping to contribute to sustainable development [4]. Moreover, the concept of the Internet of Things drives the integration between the mobile internet and EVs, so the electric car-sharing system (ECSS) is trending to intellectualization. That is, users can locate themselves and book EVs online in time instead of going offline to book in person. Therefore, we considered the ECSS in our study and proposed a new operation method with a waiting-time policy to improve the performance of the electric vehicle assignment.
The ECSS can be divided into two main modes: the round-trip car-sharing, where vehicles must be retrieved and dropped off at the same station, and the one-way car-sharing, in which vehicles can be picked up at one station and returned at an another one [5]. The outstanding advantages of one-way car-sharing in flexibility make it more attractive to users so that more and more platforms enable this mode. Thus, one-way car-sharing occupies a large proportion of the market. Due to the unique characteristic of EVs, battery constraints must be taken into consideration. Though the technology is developing quickly, trips of EVs are still restricted by its battery capacities [6]. For example, EVs can only be allocated to a trip if the battery is capable of meeting the trip’s needs. When a user reaches a station, his trip cannot be fulfilled if the battery of an EV is not sufficient for the trip even when there are many EVs in the station; then, the user may leave and choose other travel modes.
In our research, the user’s time flexibility was considered to help the platform make the best assignment in the above situation. In the traditional case, users will leave the platform when they find that none of the EVs can meet their needs. However, sometimes, users agree to wait for a period of time due to various reasons. During the waiting time, if there is an EV being charged that meets the requirements of the user’s trip, then the user’s needs can be met, and the order fulfillment rate and the total profit of the platform will improve. From the perspective of the platform, if it proactively provides corresponding subsidies to users who are willing to wait, then users can decide whether to leave the platform based on the subsidies and their actual waiting time.
Based on the above consideration, we proposed a waiting time policy. Under the waiting-time policy, when the platform finds that an EV’s battery is insufficient to meet the need of a user’s trip, it will provide a certain subsidy to the user so that the user can decide whether to wait for a period of time or just go away based on his own utility. Then, the platform makes the optimal EV assignment plan with the recalculated user’s trip demands and the EV’s conditions. We formulated this problem as a bi-level model and developed a new vehicle-assignment policy.
User time flexibility is often mentioned in vehicle-assignment problems, but it rarely involves the relationship between user waiting time and shared EV battery level. This study first considered the influence among the user’s waiting time, the user’s utility, and the EV battery level. A waiting-time policy was proposed for ECSS. In order to verify it, we generated data to illustrate an assignment between EVs and trips with our waiting-time policy. ILOG CPLEX 12.10 was used as the platform in our study, and all numerical experiments were executed on the computer configured with an Intel Core i7-10710U CPU and 16 GB memory. The numerical experiments confirmed the performance superiority of the ECSS with the waiting-time policy.

2. Electric Vehicle Assignment Considering Users’ Waiting Time

For the one-way CSS, the existing studies mainly focused on its model, target, and solution approach. The decision-making problems related to it were mainly divided into strategic, tactical, and operational types. In the ECSS, the platform mainly plays a role in matching user trip needs with the operating EVs in the platform. Users send trip demands to the platform, and the platform assigns these trip demands to viable operating EVs based on certain rules.  Furuhata et al. [7] outlined the main features of different aspects of car-sharing systems and divides the existing systems into some categories based on matching conditions and optimization targets. Decisions related to one-way CSS can be divided into three groups [8]. Strategic decisions include optimizing volumes, locations, and parking spots. Indicative decisions include determining the fleet size and the amount of operators. Operational decisions include assigning vehicles to trip requests and assigning users to vehicles. The content of this section mainly involves the decisions regarding ECSS and corresponding characteristics. Since the waiting-time policy proposed in our study involves user flexibility, the literature associated with the spatial and temporal flexibility is also reviewed.

2.1. Decision Problem

 Su et al. [9] proposed a two-stage multi-period policy to decide which charging station the EV should be assigned to and then recommends the best driving route for each EV taking into account traffic congestion.  Boyacı et al. [10] developed a multi-objective MILP programming considering EV relocation and charging requests in ECSS.  Boyacı et al. [11] presented a discrete simulation model to make operational decisions of vehicle and staff relocation in a CSS and determines the feasibility of vehicle assignment based on available battery levels. Xue et al. [12] developed a comprehensive evaluation framework that shows that vehicle availability and relocation management are the most important factors affecting the performance of ECSS in China. Bruglieri et al. [13] presented the vehicle relocation problem in a station-based one-way ECSS. Movement between stations is performed using bicycles, and then vehicle relocation is performed among stations. The predicted trip requests were considered, and all of them were assumed to be met. Liu et al. [14] proposed a bi-level optimization model that maximizes profit and minimizes operating cost by considering demand-side management for EVs’ distribution and station capacity and location. Liu et al. [15] first determined the optimal physical charging power of the EV fleet and then constructed a decision model to describe whether users accept the scheduling. Based on the optimal scheme of the time-sharing subsidy, the EV fleet size considering users’ subjective decisions was obtained. Ref. [16] addressed the imbalance of vehicles by using a simulation to make prices change dynamically to influence trip demands, while Chow and Yu [17] provided a bidding-based vehicle-sharing model. The fleet-size and trip-pricing problems were combined in [18], taking into account the dynamic changes of trips and the relocation of people and vehicles.

2.2. Optimization Model

In order to solve the problems arising from demand fluctuations and the time-varying state of charge of EVs, Huang et al. [19] presented two decision problems at the strategic and operational levels and proposed a MINLP model to maximize the profit of operators in one-way ECSS. Lu et al. [20] proposed a bi-level nonlinear model to study the pricing and relocation problem. Combinations of different pricing strategies and relocation schemes were analyzed through case studies. Xu et al. [21] used reinforcement learning technology to study the order-scheduling problem, and the goal was to maximize instant rewards and future profit. Lyu et al. [22] studied the multi-period multi-objective online ride-matching problem. They developed an efficient online matching policy to balance the trade-offs among multiple goals. Özkan and Ward [23] proposed a linear-programming-based matching policy that especially accounts for passenger patience, with the goal to maximize the total number of total passengers being served. Hu and Zhou [24] studied the dynamic matching where, if the driver or passenger waits for too long, either of them may leave the platform.
The matching time interval and matching distance are two important factors affecting results in an online matching system. More orders will be fulfilled if the platform extends the matching time interval, but some users may leave the platform if the matching time interval exceeds their patience. Meanwhile, the pick-up distance will be reduced with a shorter match radius, but the matching rate may decrease as well. Bian and Liu [25] considered the individual requirements of users for different inconvenient factors, including waiting times, to determine the optimal matching between passengers and vehicles. Yang et al. [26] proposed to segment the various stages of the online matching process in the ride-sharing market. Abdolmaleki et al. [27] proposed an optimization problem with consistency constraints to synchronize the schedules in the transportation network so that the total waiting time for users’ transferring is minimized.

2.3. User Flexibility

User flexibility was also considered in our one-way ECSS. Correia et al. [28] proposed a model measuring the impact of user flexibility on the vehicle-assignment problem in a one-way CSS. Stiglic et al. [29] replaced the original target point with meeting points where the user can get on and off the vehicle within a certain distance from the original target point. A combination of spatial and temporal flexibility was considered to optimize the vehicle assignment at the same time [30]. A time window was set at the beginning and end of the trip, while locations within a certain radius of the original target point were considered as acceptable. The effect of flexibility on the car-sharing system can be summarized in some parts: increasing the number of matched users, improving vehicle utilization and the number of requests fulfilled, and reducing costs and the fleet size [8].
Taking the key factor that an EV’s trip mileage is limited by battery level, Zhang et al. [31] enabled users to finish longer trips through driving two vehicles in sequence. A new time–space–battery network flow model was proposed to find the best vehicle assignment and relaying decisions so as to achieve higher vehicle utilization.

References

  1. Mobile, A. 2020. Available online: https://www.jiguang.cn/reports/494 (accessed on 27 March 2021).
  2. Illgen, S.; Höck, M. Literature review of the vehicle relocation problem in one-way car sharing networks. Transp. Res. Part B Methodol. 2019, 120, 193–204.
  3. Shaheen, S.A.; Mallery, M.A.; Kingsley, K.J. Personal vehicle sharing services in North America. Res. Transp. Bus. Manag. 2012, 3, 71–81.
  4. Schiavo, F.T.; Calili, R.F.; de Magalhães, C.F.; Fróes, I.C.G. The Meaning of Electric Cars in the Context of Sustainable Transition in Brazil. Sustainability 2021, 13, 11073.
  5. Jorge, D.; Molnar, G.; de Almeida Correia, G.H. Trip pricing of one-way station-based carsharing networks with zone and time of day price variations. Transp. Res. Part B Methodol. 2015, 81, 461–482.
  6. Basso, R.; Kulcsár, B.; Sanchez-Diaz, I. Electric vehicle routing problem with machine learning for energy prediction. Transp. Res. Part B Methodol. 2021, 145, 24–55.
  7. Furuhata, M.; Dessouky, M.; Ordóñez, F.; Brunet, M.E.; Wang, X.; Koenig, S. Ridesharing: The state-of-the-art and future directions. Transp. Res. Part B Methodol. 2013, 57, 28–46.
  8. Boyacı, B.; Zografos, K.G. Investigating the effect of temporal and spatial flexibility on the performance of one-way electric carsharing systems. Transp. Res. Part B Methodol. 2019, 129, 244–272.
  9. Su, S.; Wei, C.; Li, Z.; Xia, D. Two-Stage Multi-Period Coordinated Load Restoration Strategy for Distribution Network Based on Intelligent Route Recommendation of Electric Vehicles. World Electr. Veh. J. 2021, 12, 121.
  10. Boyacı, B.; Zografos, K.G.; Geroliminis, N. An optimization framework for the development of efficient one-way car-sharing systems. Eur. J. Oper. Res. 2015, 240, 718–733.
  11. Boyacı, B.; Zografos, K.G.; Geroliminis, N. An integrated optimization-simulation framework for vehicle and personnel relocations of electric carsharing systems with reservations. Transp. Res. Part B Methodol. 2017, 95, 214–237.
  12. Xue, Y.; Zhang, Y.; Chen, Y. An Evaluation Framework for the Planning of Electric Car-Sharing Systems: A Combination Model of AHP-CBA-VD. Sustainability 2019, 11, 5627.
  13. Bruglieri, M.; Colorni, A.; Luè, A. The Vehicle Relocation Problem for the One-way Electric Vehicle Sharing: An Application to the Milan Case. Procedia-Soc. Behav. Sci. 2014, 111, 18–27.
  14. Liu, W.; Niu, S.; Xu, H.; Li, X. A New Method to Plan the Capacity and Location of Battery Swapping Station for Electric Vehicle Considering Demand Side Management. Sustainability 2016, 8, 557.
  15. Liu, D.; Zhang, T.; Wang, W.; Peng, X.; Liu, M.; Jia, H.; Su, S. Two-Stage Physical Economic Adjustable Capacity Evaluation Model of Electric Vehicles for Peak Shaving and Valley Filling Auxiliary Services. Sustainability 2021, 13, 8153.
  16. Waserhole, A.; Jost, V.; Brauner, N. Pricing techniques for self regulation in Vehicle Sharing Systems. Electron. Notes Discret. Math. 2013, 41, 149–156.
  17. Chow, Y.; Yu, J. Real-time bidding based vehicle sharing. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, 4–8 May 2015; International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS): New York, NY, USA, 2015; Volume 3, pp. 1829–1830.
  18. Xu, M.; Meng, Q.; Liu, Z. Electric vehicle fleet size and trip pricing for one-way carsharing services considering vehicle relocation and personnel assignment. Transp. Res. Part B Methodol. 2018, 111, 60–82.
  19. Huang, K.; An, K.; de Almeida Correia, G.H. Planning station capacity and fleet size of one-way electric carsharing systems with continuous state of charge functions. Eur. J. Oper. Res. 2020, 287, 1075–1091.
  20. Lu, R.; de Almeida Correia, G.H.; Zhao, X.; Liang, X.; Lv, Y. Performance of one-way carsharing systems under combined strategy of pricing and relocations. Transp. B Transp. Dyn. 2021, 9, 134–152.
  21. Xu, Z.; Li, Z.; Guan, Q.; Zhang, D.; Li, Q.; Nan, J.; Liu, C.; Bian, W.; Ye, J. Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach; KDD ’18; Association for Computing Machinery: New York, NY, USA, 2018; pp. 905–913.
  22. Lyu, G.; Cheung, W.C.; Teo, C.; Wang, H. Multi-Objective Online Ride-Matching. SSRN 3356823 2019. Available online: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3356823 (accessed on 27 March 2021).
  23. Özkan, E.; Ward, A.R. Dynamic matching for real-time ride sharing. Stoch. Syst. 2020, 10, 29–70.
  24. Hu, M.; Zhou, Y. Dynamic Type Matching. Manuf. Serv. Oper. Manag. 2021.
  25. Bian, Z.; Liu, X. Mechanism design for first-mile ridesharing based on personalized requirements part I: Theoretical analysis in generalized scenarios. Transp. Res. Part B Methodol. 2019, 120, 147–171.
  26. Yang, H.; Qin, X.; Ke, J.; Ye, J. Optimizing matching time interval and matching radius in on-demand ride-sourcing markets. Transp. Res. Part B Methodol. 2020, 131, 84–105.
  27. Abdolmaleki, M.; Masoud, N.; Yin, Y. Transit timetable synchronization for transfer time minimization. Transp. Res. Part B Methodol. 2020, 131, 143–159.
  28. Correia, G.H.D.A.; Jorge, D.R.; Antunes, D.M. The added value of accounting for users’ flexibility and information on the potential of a station-based one-way car-sharing system: An application in Lisbon, Portugal. J. Intell. Transp. Syst. 2014, 18, 299–308.
  29. Stiglic, M.; Agatz, N.; Savelsbergh, M.; Gradisar, M. The benefits of meeting points in ride-sharing systems. Transp. Res. Part B Methodol. 2015, 82, 36–53.
  30. Tong, L.C.; Zhou, L.; Liu, J.; Zhou, X. Customized bus service design for jointly optimizing passenger-to-vehicle assignment and vehicle routing. Transp. Res. Part C Emerg. Technol. 2017, 85, 451–475.
  31. Zhang, D.; Liu, Y.; He, S. Vehicle assignment and relays for one-way electric car-sharing systems. Transp. Res. Part B Methodol. 2019, 120, 125–146.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/)
Video Production Service
Feedback