Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/145432
Title: ONLINE VEHICLE ROUTING UNDER STOCHASTIC DEMANDS USING APPROXIMATE DYNAMIC PROGRAMMING
Authors: LOUIS EDOUARD DOUGE
Keywords: Online Vehicle Routing, Reinforcement Learning, Stochastic Demands, Approximate Dynamic Programming, Policy Approximation, Simulation
Issue Date: 6-Feb-2018
Citation: LOUIS EDOUARD DOUGE (2018-02-06). ONLINE VEHICLE ROUTING UNDER STOCHASTIC DEMANDS USING APPROXIMATE DYNAMIC PROGRAMMING. ScholarBank@NUS Repository.
Abstract: This thesis studies an instance of a Dynamic Vehicle Routing Problem (DVRP) under Stochastic Demands, drawn from a real-world situation. Specifically, a single courier must accomplish two kinds of tasks: deliveries that are known from the beginning of operations, and pickups that appear after the beginning of operations, at random times. The objective is to maximize the rewards obtained from serving both types of customers, during a limited period of time. Our contribution lies in the use of historical couriers’ decisions to learn a base heuristic. The Reinforcement Learning framework is then used to make the base heuristic explore new scenarios through simulations. The best trajectories from this exploration process allow the generation of new data to further train the base policy. The enhanced policy thus obtained is finally used in the real world, in combination with the simulator to estimate the downstream value of available actions. The most rewarding one is finally chosen. We show that under some conditions, our approach allows the serving of on average 4.4% more customers than the Nearest-Neighbor policy.
URI: http://scholarbank.nus.edu.sg/handle/10635/145432
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
DougeL.pdf3.17 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

261
checked on Jun 26, 2020

Download(s)

153
checked on Jun 26, 2020

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.