A Study To The Stochastic Vehicle Routing Problem With Approximate Dynamic Programming Approach

With the economic development, logistics is becoming more and more important insociety. Everyday activities, such as companies’ sourcing activities, delivery of milk andnewspaper to households, post and express delivery services, collection of garbage, etc.,connect our life closely to logistics. On the other hand, logistics often encounter uncer-tainties, such as whether changes, road congestions, stochastic customer demand and/orservice time, etc., which bring great challenges to the logistics planning and operationsmanagement.This research studies the single vehicle routing problem with stochastic customerdemand and models the problem as a stochastic dynamic program. The vehicle routingproblem is an NP-hard combinatorial optimization problem, and the computational timeof the classical backward dynamic programming method grows exponentially with theproblem size. Stochastic vehicle routing problems face the curses of dimensionality in thestate, decision, and outcome spaces. To overcome this difculty, we resort to approximatedynamic programming, which is an emerging research area. Very few research have beenfound in literature on its applications in stochastic vehicle routing problems.We frst study and compare diferent routing policies by numerical experiments. Theresults show that, allowing early replenishment can efectively reduce the expected cost(measured by expected total distance). When few commodity remains in the vehicleand the location of vehicle is close to the depot, it is preferable to return to the depotand replenish before serving the remaining customers. We also observe that dynamiconline rerouting based on the updated customer demand information can also reduce theexpected cost signifcantly, as compared to the ofine planning. However, the solutiontime for the dynamic routing problem grows exponentially with the problem size.We adopt the approximate dynamic programming method, more specifcally, thevalue function approximation (VFA) method with lookup-table representation, and studythe key algorithmic issues via numerical experiments. We also implement the Rollout al-gorithm based on the literature, and compare them with the exact algorithm on (standard)test instances in the literature. Our numerical results show that, comparing to Rolloutalgorithm, VFA explores many more routing options and therefore obtains better solu-tions for small to moderate problem sizes. However, when the problem size grows, VFA requires much more computational time in approximating and updating the exponentiallygrowing state and decision spaces. We try to reduce the size of the lookup-table, andobtain a certain level of improvement. More research are expected to extend this line ofresearch.