Gilbert Laporte, Ola Jabali, and e-VRO’s Aurélien Froger and Jorge E. Mendoza just published a new paper on the electric vehicle routing problem with nonlinear charging function (E-VRP-NL). The problem was introduced a couple of years ago (by e-VRO’s researchers) to account for the more realistic nonlinear relationship between the time spent charging and the amount of energy charged. In this new paper Froger et al. propose two new formulations for the E-VRP-NL. They first develop an arc-based tracking of the time and the state of charge which, according to their experiments, outperforms the classical node-based tracking of these values. To avoid replicating the charging stations nodes, as done for both node and arc based formulations, they also introduce a path-based model. They develop an algorithm to generate a tractable number of these paths. This path-based model outperforms the classical models. They also propose a new model, a heuristic, and an exact labeling algorithm for the problem of finding the optimal charging decisions for a given route. Extensive computational results show that charging decisions considerably impact the quality of the E-VRP-NL solutions. Indeed, they improve 23 out of 120 best known E-VRP-NL solutions by solely revising the charging decisions. You can access the paper here.
Çağrı Koç, Ola Jabali, Gilbert Laporte, and e-VRO’s Jorge E. Mendoza just published a paper on the electric vehicle routing problem with shared charging stations in ITOR. The E‐VRP‐SCS extends the electric vehicle routing problem with nonlinear charging function (E‐VRP‐NL) by considering several companies that jointly invest in charging stations (CSs). The objective is to minimize the sum of the fixed opening cost of CSs and the drivers cost. The problem consists of deciding the location and technology of the CSs and building the routes for each company. In the article they solve the problem by means of a multistart heuristic that performs an adaptive large neighborhood search coupled with the solution of mixed integer linear programs. The algorithm embeds a number of advanced efficient procedures tailored to handle specific components of the E‐VRP‐SCS. The paper reports on extensive computational experiments on benchmark instances. They assess the competitiveness of the heuristic on the E‐VRP‐NL and derive 38 new best known solutions. You can access the article here. This is the first official outcome of our productive collaboration with the Canada Research Chair in Distribution Management!
e-VRO’s N. Kullman, J. Goodson, and J.E. Mendoza just released a manuscript titled “Dynamic Electric Vehicle Routing: Heuristics and Dual Bounds”. In their paper, they introduce the electric vehicle routing problem with public-private recharging strategy in which vehicles may recharge en-route at public charging infrastructure as well as at a privately-owned depot. To hedge against uncertain demand at public charging stations, they design routing policies that anticipate station queue dynamics. They leverage a decomposition to identify good routing policies, including the optimal static policy and fixed-route-based rollout policies that dynamically respond to observed queues. The decomposition also enables them to establish dual bounds, providing a measure of goodness for their routing policies. In computational experiments, they show the value of their policies to be within 4.7 percent of the value of an optimal policy in most instances. Further, they demonstrate that their policies significantly outperform the industry-standard routing strategy in which vehicle recharging generally occurs at a central depot. More broadly, they offer examples for how operations research tools classically employed in static and deterministic routing can be adapted for dynamic and stochastic routing problems. The manuscript, available here, is the first paper of N. Kullman‘s dissertation. Congratulations Nick.
e-VRO’s Juan G. Villegas, Christelle Guéret, Jorge E. Mendoza, and Alejandro Montoya just published a technical report on the technician routing and scheduling problem with conventional and electric vehicles. This is the result of joint work between e-VRO and the research and development department of EDF in Saclay (Paris). The report describes a routing problem faced by the utility and proposes a parallel matheuristic to solve it. You can access the paper here.
We forgot to tell you! e-VRO’s Aurélien Froger and Jorge E. Mendoza released two technical reports on the E-VRP with nonlinear charging function (E-VRP-NL) and the E-VRP-NL with capacitated charging stations. These two reports present the first results of e-VRO’s collaboration with the Canada research chair on distribution management held by Professor Gilbert Laporte at HEC Montéal. The first report introduces new mixed integer linear programming (MILP) models for the E-VRP-NL and three new methods for the fixed route vehicle recharging problem (download the report here). The second report extends the E-VRP-NL to consider charging station capacity (i.e., number of available chargers). The report presents two MILP formulations and introduces a route-first, assemble-second matheuristic for the problem. The latter uses a novel solution framework based on Benders decomposition that can be quite useful in other VRP variants (download the report here). Journal-paper versions of these two reports are coming soon, in the meantime enjoy the reports!
A new version of Alejandro Montoya’s et al. paper on the electric vehicle routing problem with nonlinear charging function is available here.