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 | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
DougeL.pdf | 3.17 MB | Adobe PDF | OPEN | None | View/Download |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.