A Heuristic Approach for Fixed-Route Vehicle Charging with Nonlinear Time-Dependent Charging Function

Abstract

This paper investigates the Fixed-Route Vehicle Charging Problem based on Time (FRVCP-T), considering the nonlinear characteristics of electric vehicle (EV) charging functions. A new linearization method using secant lines is introduced to convert the nonlinear charging curve into a Mixed-Integer Linear Programming (MILP) model with significantly fewer variables. To solve large-scale instances efficiently, we propose a heuristic algorithm—Dynamic Iterative Partial Optimization with Tabu Search (DIPOTS). Computational experiments on various datasets demonstrate that DIPOTS achieves high-quality solutions with average deviation below 0.6%, while reducing computational time by over 95% compared to commercial solver on large instances.