Solution Algorithm for Vehicle Routing Problem with Stochastic Demand

Masahiro Komatsu; Ryota Omori; Tetsuya Sato; Takayuki Shiina

doi:10.52731/ijskm.v7.i1.710

Masahiro Komatsu Waseda University
Ryota Omori Waseda University
Tetsuya Sato Waseda University
Takayuki Shiina Waseda University

DOI: https://doi.org/10.52731/ijskm.v7.i1.710

Keywords: vehicle routing problem, VRP, subtour elimination constraint, stochastic programming, stochastic demand

Abstract

The vehicle routing problem (VRP) determines a delivery route that minimizes the delivery cost. In this study, we consider the stochastic VRP with uncertainty and consider the variation in customer demand, which may cause a shortage of products during delivery. In this case, delivery vehicles have to return to the depot and replenish the products. We consider a model that minimizes the sum of the additional cost caused by the shortage and the normal delivery cost.

In previous studies, the decomposition method using the L-shaped method was used. In this study, we improve the decomposition method to make it more efficient. In addition, we have improved the direct method of calculating the additional cost without the decomposition method by considering subtour elimination constraints. We have shown that the direct method is superior in terms of time-saving.

References

Toth, P., Vigo, D.: Vehicle Routing Problems, Methods, and Applications. Second Edition,

Society for Industrial and Applied Mathematics (2014)

Omori, R., Shiina, T.: New Formulation for the Vehicle Routing Problem with Stochastic

Demands, 9th International Congress on Advanced Applied Informatics (IIAI-AAI),

–728 (2020)

Laporte, G., Louveaux, F., Hamme, L.: An integer L-shaped algorithm for the capacitated

vehicle routing problem with stochastic demands, Operations Research, 50,

–423 (2002)

Giacco, G.L., D’Ariano, A., Pacciarelli, D.: Rolling stock rostering optimization under

maintenance constraints, Journal of Intelligent Transportation Systems, 18(1), 95–105 (2014)

Laporte, G., Louveaux, F., Mercure, H.: The vehicle routing problem with stochastic travel times, Transportation Science, 26, 161–170 (1992)

Roberti, R., Toth, T.: Models and algorithms for the asymmetric traveling salesman problem: an experimental comparison, EURO Journal on Transportation and Logistics, 1, 113–133 (2012)

Laporte, G., Louveaux, F.: The integer L-shaped method for stochastic integer programs with complete resource, Operations Research Letters, 13, 133–142 (1993)

Gavish, B., Graves, S.C.: The traveling salesman problem and related problems,Working Paper OR-078-78, Operations Research Center, MIT, Cambridge, MA(1978)

Miller, C.E., Tucker, A.W., Zemlin, R.A.: Integer programming formulations and travelling salesman problems, Journal of the ACM, 7, 326–329 (1960)

Shiina, T.: Stochastic Programming, Asakura Publishing (2015) (in Japanese)