You are here : English versionNewsNews

LIFAT Defense - Nicholas D. KULLMAN


on the May 4, 2020

Lundi 4 mai 2020 
Salle Lovelace - PolytechTours - 
64 Av Portalis TOURS

Nicholas D. KULLMAN - Titre : Dynamic Decision Making Under Uncertainty in Vehicle Routing and Logistics

BILLAUT Jean-Charles Professeur, Université de Tours, France
MENDOZA Jorge E. Professeur Visiteur, HEC Montréal, Canada

Abstract : Abstract :
This thesis details three problems and two software tools related to dynamic decision making
under uncertainty in vehicle routing and logistics, with an emphasis on the challenges
encountered when adopting electric vehicles. We first 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, we design routing policies that anticipate
station queue dynamics. We 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 us to establish dual bounds,
providing a measure of goodness for our routing policies. In computational experiments
using real instances from industry, we show the value of our policies to be within five
percent of the value of an optimal policy in the majority of instances and within eleven
percent on average. Further, we demonstrate that our policies significantly outperform
the industry-standard routing strategy in which vehicle recharging generally occurs at a
central depot. Our proposed methods for this problem stand to reduce the operating costs
associated with electric vehicles, facilitating the transition from internal-combustion engine
We then consider the problem of an operator controlling a fleet of electric vehicles for
use in a ridehailing service. The operator, seeking to maximize revenue, must assign vehicles
to requests as they arise and recharge and reposition vehicles in anticipation of future
requests. To solve this problem, we employ deep reinforcement learning, developing policies
whose decision making uses Q-value approximations learned by deep neural networks.
We compare these policies against a common taxi dispatching heuristic and against dual
bounds on the value of an optimal policy, including the value of an optimal policy with
perfect information which we establish using a Benders-based decomposition. We assess
performance on instances derived from real data for the island of Manhattan in New
York City. We find that, across instances of varying size, our best policy trained with
deep reinforcement learning outperforms the taxi dispatching heuristic. We also provide
evidence that this policy may be effectively scaled and deployed on larger instances without
We then present a new general approach to modeling research problems as Atari-like
videogames to make them amenable to recent solution methods from the deep reinforcement
learning community. The approach is flexible, applicable to a wide range of problems. Here,
we demonstrate its application on the well-studied vehicle routing problem with stochastic
service requests. Our preliminary results on this problem, though not transformative, show
signs of success and suggest that Atari-fication may be a useful modeling approach for
researchers studying problems involving sequential decision making under uncertainty.
We then introduce frvcpy, the first of our two proposed software tools. In the routing
of electric vehicles, one of the most challenging tasks is determining how to make good
charging decisions for an electric vehicle traveling a given route. This is known as the
fixed route vehicle charging problem. An exact and efficient algorithm for this task exists,
but its implementation is sufficiently complex to deter researchers from adopting it. Our
proposed tool, frvcpy, is an open-source Python package implementing this algorithm. Our
aim with the package is to make it easier for researchers to solve electric vehicle routing
problems, facilitating the development of optimization tools that may ultimately enable
the mass adoption of electric vehicles.
Finally, we introduce the second software tool, Mapper. Mapper is a simple web-based
visualizer of problem instances and solutions for vehicle routing problems. It is designed to
accompany the suite of tools already available to users of the vehicle routing community’s
website, The Vehicle Routing Problem Repository.

Keywords : dynamic routing, uncertainty, optimization, Markov decision process, logistics, electric