New paper on the E-VRP-NL

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.


New paper on the electric vehicle routing problem with shared charging stations

Ç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!




Dynamic Electric Vehicle Routing: Heuristics and Dual Bounds

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.

New paper on the TRSP-CEV

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.

Pascal Van Hentenryck @ Polytech Tours

Pr. Pascal Van Hentenryck will visit Polytech Tours from June 16 to 22. He will give an invited talk at the Matheuristics Workshop organized by the operations research, scheduling, and transportation team and work with e-VRO’s Nick Kullman, Aurélien Froger, Laura Echeverri, and Jorge E. Mendoza on topics related to the project. We are delighted Pr. Han Hentenryck accepted our invitation and are looking forward to his visit.


The 2018 ODYSSEUS conference starts Sunday in Cagliari (Italy). e-VRO will contribute three tacks to the high-level scientific program. Nick Kullman will present his research on dynamic routing for electric vehicles. His talk is scheduled Wednesday morning (9a.m.) in the Green Room. Aurélien Froger will discuss his impressive results on the electric vehicle routing problem with non-linear charging function (E-VRP-NL) and will present the latest version of his approach for the E-VRP-NL with capacitated charging stations. Jorge E. Mendoza will present the final results of our collaboration with EDF-R&D on the technician routing and scheduling problem with conventional and electric vehicles. The two last talk are scheduled on Wednesday Morning (9a.m. and in the White Room. If you are attending the conference, do not miss these talks! You can download the book of extended abstracts here.

S. Pelletier @ Polytech Tours

Samuel Pelletier (HEC – Montréal) will visit Polytech Tours from 12/02/2018 to 20/02/2018. Samuel is a senior-year Ph.D. student at HEC – Montréal, working under the supervision of Professors Gilbert Laporte and Ola Jabali. During his visit, Samuel and e-VRO members will have the opportunity to discuss the state of the research on the field of electric vehicle routing and explore avenues for collaboration. Taking advantage of his visit, e-VRO has organised a research seminar on February 14 (find details here). If you happen to be around Tours that day, do not miss his talk. Welcome Samuel!

Technical reports on the E-VRP-NL and E-VRP-NL-C

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!

e-VRO @ ROADEF 2018

e-VRO’s Jorge E. Mendoza and our friends Jakob Puchinger and Ammar Oularama are putting together a special session on E-VRPs for ROADEF 2018. The conference will be held in Lorient (Brittany, France) on Fev. 21-23. You can find more information about the special session here. Submissions are in the form of 2-page extended abstract. You can submit your contribution to the session here.