This work presents a steady-state genetic algorithm enhanced by a complete trie-based solution archive for solving the generalized vehicle routing problem with stochastic demands using a preventive restocking strategy. As the necessary dynamic programming algorithm for the solution evaluation is very time consuming, considered candidate solutions are stored in the solution archive. It acts as complete memory of the search history, avoids reevaluations of duplicate solution candidates, and is able to efficiently transform them into guaranteed new ones. This increases the diversity of the population and reduces the risk of premature convergence. Similar to a branch-and-bound algorithm, the tree structure of the solution archive is further exploited to compute lower bounds on the nodes to cut off parts of the solution space that evidently do not contain good solutions. Since in each iteration a not yet considered solution candidate is generated and completeness can be efficiently checked, the overall method is in principle an exact enumeration algorithm, which leads to guaranteed optimal solutions for smaller instances. Computational results of this algorithm show the superiority over the so far state-of-the-art metaheuristic and also prove its effectiveness on the nongeneralized version of this problem.

The aim of this work is to schedule the charging of electric vehicles (EVs) at a single charging station such that the temporal availability of each EV as well as the maximum available power at the station are considered. The total costs for charging the vehicles should be minimized w.r.t. time-dependent electricity costs. A particular challenge investigated in this work is that the maximum power at which a vehicle can be charged is dependent on the current state of charge (SOC) of the vehicle. Such a consideration is particularly relevant in the case of fast charging. Considering this aspect for a discretized time horizon is not trivial, as the maximum charging power of an EV may also change in between time steps. To deal with this issue, we instead consider the energy by which an EV can be charged within a time step. For this purpose, we show how to derive the maximum charging energy in an exact as well as an approximate way. Moreover, we propose two methods for solving the scheduling problem. The first is a cutting plane method utilizing a convex hull of the, in general, nonconcave SOC–power curves. The second method is based on a piecewise linearization of the SOC–energy curve and is effectively solved by branch-and-cut. The proposed approaches are evaluated on benchmark instances, which are partly based on real-world data. To deal with EVs arriving at different times as well as charging costs changing over time, a model-based predictive control strategy is usually applied in such cases. Hence, we also experimentally evaluate the performance of our approaches for such a strategy. The results show that optimally solving problems with general piecewise linear maximum power functions requires high computation times. However, problems with concave, piecewise linear maximum charging power functions can efficiently be dealt with by means of linear programming. Approximating an EV’s maximum charging power with a concave function may result in practically infeasible solutions, due to vehicles potentially not reaching their specified target SOC. However, our results show that this error is negligible in practice.