29 September 2021 in IEEE Transactions on Intelligent Transportation Systems
We consider an increasingly popular demand-response scenario where a home user schedules the flexible electric vehicle (EV) charging load in response to real-time electricity prices. The objective is to minimize the total charging cost with user dissatisfaction taken into account. We focus on the online setting where neither accurate prediction nor distribution of future real-time prices is available to the user when making irrevocable charging decisions in each time slot. The emphasis on considering user dissatisfaction and achieving optimal competitive ratio differentiates our work from existing ones and makes our study uniquely challenging. Our key contribution is two simple online algorithms with the optimal competitive ratio among all deterministic algorithms. The optimal competitive ratio is upper-bounded by $\min \left \{{ \sqrt {\alpha /p_{\min }},p_{\max }/p_{\min }}\right \} $ and the bound is asymptotically tight with respect to $\alpha $ , where $p_{\max }$ and $p_{\min }$ are the upper and lower bounds of real-time prices and $\alpha \geq p_{\min }$ captures the consideration of user dissatisfaction. The bounds with respect to small and large values of $\alpha $ suggest the fundamental difference of the problems with and without considering user dissatisfaction. We also extend the algorithms to take minimum charging requirement and short-term prediction into account. Simulation results based on real-world traces corroborate our theoretical findings and show that the empirical performance of our algorithms can be substantially better than the theoretical worst-case guarantees. Our algorithms also achieve notable performance gains under diverse settings as compared to conceivable alternatives.
29 October 2025 in Nature Communications
Electrifying heavy-duty trucks is crucial for decarbonizing transportation, but maximizing their potential requires minimizing the carbon footprint of timely deliveries. This complex optimization task involves strategic path, speed, and charging planning, which traditional methods struggle to optimize at scale. We present a stage-expanded graph formulation that reduces complexity and reveals a useful problem structure. Our formulation naturally decomposes the problem into more tractable subproblems, allowing efficient coordination between routing and charging decisions, and maintains a manageable graph size. We exploit these structural insights to design an efficient algorithm with performance guarantees. Simulations using real-world data over the U.S. highway system demonstrate that our method complements the 36% carbon reduction from electrification with an additional 25% decrease, totaling a 61% reduction. Moreover, our carbon-optimized strategy, applicable to various truck types, can achieve comparable carbon reductions 9 years sooner than zero-emission truck adoption alone. This approach accelerates transportation decarbonization, offering a powerful tool in the fight against climate change.
8 July 2025 in IEEE Transactions on Networking
We consider the scenario where an energy harvesting source sends its updates to a receiver. The source optimizes its energy allocation over a decision period to maximize a sum of time-varying functions of the age of information (AoI), representing the value of providing timely information. In a practical online setting, we need to make irrevocable energy allocation decisions at each time while the time-varying functions and the energy arrivals are only revealed sequentially. The problem is then challenging as 1) we are facing uncertain energy harvesting arrivals and time-varying functions, and 2) the energy allocation decisions and the energy harvesting process are coupled due to the capacity-limited battery. In this paper, we develop an optimal online algorithm $\textsf {CR-RePursuit}$ and show it achieves $(\ln \theta +1)$ -competitiveness, where $\theta $ is a parameter representing the level of uncertainty of the time-varying functions. It is the optimal competitive ratio among all deterministic and randomized online algorithms. We also introduce an adaptive variant of the algorithm, +, that further exploits the revealed information to obtain significantly improved empirical performance. We conduct simulations based on real-world traces and compare our algorithms with conceivable alternatives. The results show that our algorithms achieve 15% performance improvement as compared to the state-of-the-art baseline.
2 July 2025 in IEEE Transactions on Intelligent Transportation Systems
We consider the problem of exploring travel demand statistics to optimize ride-sharing routing, which is to determine a route to transport multiple customers with similar itineraries and schedules in a cost-effective and timely manner. This problem is important for unleashing the economic and societal benefits of ride-sharing. Meanwhile, it is challenging due to the need to (i) meet the travel delay requirements of customers and (ii) make online decisions without knowing the exact travel demands beforehand. We present a general framework for exploring the new design space enabled by the demand-aware approach. We show that demand-aware ride-sharing routing is fundamentally a two-stage stochastic optimization problem. While the problem is combinatorial in nature and challenging, we exploit the two-stage structure to design an optimal solution that maximizes the expected reward of the route with polynomial time complexity, which makes it amenable to practical implementation. Our approach can be applied to optimize a variety of objectives in a ride-sharing trip, including revenue, driver’s profit, and total travel time reduction compared to serving customers individually. We carry out extensive simulations based on real-world travel demand traces in Manhattan. Simulation results show that applying our demand-aware solution increases the revenue by 26% against conceivable alternatives. As compared to the case without ride-sharing, our ride-sharing solution increases the driver’s profit per slot by 12% and decreases the total vehicle travel time (an indicator of greenhouse gas emission) by 16%.