Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation. (English) Zbl 1110.90015
Summary: This paper considers the routing of vehicles with limited capacity from a central depot to a set of geographically dispersed customers where actual demand is revealed only when the vehicle arrives at the customer. The solution to this vehicle routing problem with stochastic demand (VRPSD) involves the optimization of complete routing schedules with minimum travel distance, driver remuneration, and number of vehicles, subject to a number of constraints such as time windows and vehicle capacity. To solve such a multiobjective and multi-modal combinatorial optimization problem, this paper presents a multiobjective evolutionary algorithm that incorporates two VRPSD-specific heuristics for local exploitation and a route simulation method to evaluate the fitness of solutions. A new way of assessing the quality of solutions to the VRPSD on top of comparing their expected costs is also proposed. It is shown that the algorithm is capable of finding useful tradeoff solutions for the VRPSD and the solutions are robust to the stochastic nature of the problem. The developed algorithm is further validated on a few VRPSD instances adapted from Solomon’s vehicle routing problem with time windows (VRPTW) benchmark problems.
MSC:
| 90B20 | Traffic problems in operations research |
| 90C29 | Multi-objective and goal programming |
| 91B70 | Stochastic models in economics |
References:
| [1] | Bertsimas, D. J.; Chervi, P.; Peterson, M., Computational approaches to stochastic vehicle routing problems, Transportation Science, 29, 4, 342-352 (1995) · Zbl 0853.90037 |
| [2] | Bertsimas, D. J.; Jaillet, P.; Odoni, A. R., A priori optimization, Operations Research, 38, 1019-1033 (1990) · Zbl 0721.90062 |
| [3] | Bianchi, L., Birattari, M., Manfrin, M., Mastrolilli, M., Paquete, L., Rossi-Doria, O., Schiavinotto, T., in press. Hybrid metaheuristics for the vehicle routing problem with stochastic demands. Journal of Mathematical Modelling and Algorithms.; Bianchi, L., Birattari, M., Manfrin, M., Mastrolilli, M., Paquete, L., Rossi-Doria, O., Schiavinotto, T., in press. Hybrid metaheuristics for the vehicle routing problem with stochastic demands. Journal of Mathematical Modelling and Algorithms. · Zbl 1099.90505 |
| [4] | Bianchi, L., Birattari, M., Chiarandini, M., Manfrin, M., Mastrolilli, M., Paquete, L., Rossi-Doria, O., Schiavinotto, T., 2004. Metaheuristics for the vehicle routing problem with stochastic demands. In: Proceedings of the 8th International Conference on Parallel Problem Solving from Nature, Birmingham, UK, Lecture Notes in Computer Science, vol. 3242, pp. 450-460.; Bianchi, L., Birattari, M., Chiarandini, M., Manfrin, M., Mastrolilli, M., Paquete, L., Rossi-Doria, O., Schiavinotto, T., 2004. Metaheuristics for the vehicle routing problem with stochastic demands. In: Proceedings of the 8th International Conference on Parallel Problem Solving from Nature, Birmingham, UK, Lecture Notes in Computer Science, vol. 3242, pp. 450-460. · Zbl 1099.90505 |
| [5] | Charnes, A.; Cooper, W., Deterministic equivalents for optimizing and satisfying under chance constraints, Operations Research, 11, 18-39 (1963) · Zbl 0117.15403 |
| [6] | Charnes, A.; Cooper, W., Chance-constrained programming, Management Science, 6, 73-79 (1959) · Zbl 0995.90600 |
| [7] | Chen, C.H., Wu, S.D., Dai, L., 1997. Algorithm comparison for manufacturing scheduling problems. In: Proceedings of the 36th IEEE Conference on Decision and Control, San Diego, CA, USA, 10-12 December 1997, vol. 2, pp. 1214-1215.; Chen, C.H., Wu, S.D., Dai, L., 1997. Algorithm comparison for manufacturing scheduling problems. In: Proceedings of the 36th IEEE Conference on Decision and Control, San Diego, CA, USA, 10-12 December 1997, vol. 2, pp. 1214-1215. |
| [8] | Dror, M., Modeling vehicle routing with uncertain demands as a stochastic program: Properties of the corresponding solution, European Journal of Operational Research, 64, 3, 432-441 (1993) · Zbl 0776.90017 |
| [9] | Dror, M.; Trudeau, P., Stochastic vehicle routing with modified savings algorithm, European Journal of Operational Research, 23, 2, 228-235 (1986) · Zbl 0577.90058 |
| [10] | Dror, M.; Ball, M. O.; Golden, B. L., Computational comparison of algorithms for inventory routing, Annals of Operations Research, 4, 3-23 (1985) |
| [11] | Fonseca, C.M., 1995. Multiobjective genetic algorithms with application to control engineering problems. Ph.D. Thesis, Department of Automatic Control and Systems Engineering, University of Sheffield, Sheffield, UK.; Fonseca, C.M., 1995. Multiobjective genetic algorithms with application to control engineering problems. Ph.D. Thesis, Department of Automatic Control and Systems Engineering, University of Sheffield, Sheffield, UK. |
| [12] | Gendreau, M.; Laporte, G.; Séguin, R., Stochastic vehicle routing, European Journal of Operational Research, 88, 1, 3-12 (1996) · Zbl 0913.90094 |
| [13] | Gendreau, M.; Laporte, G.; Séguin, R., A tabu search heuristic for the vehicle routing problem with stochastic demands and customers, Operations Research, 44, 3, 469-477 (1996) · Zbl 0864.90043 |
| [14] | Gendreau, M.; Laporte, G.; Séguin, R., An exact algorithm for the vehicle routing problem with stochastic demands and customers, Transportation Science, 29, 143-155 (1995) · Zbl 0860.90051 |
| [15] | Hwang, H. S., An improved model for vehicle routing problem with time constraint based on genetic algorithm, Computers & Industrial Engineering, 42, 2-4, 361-369 (2002) |
| [16] | Jaillet, P.; Odoni, A. R., The probabilistic vehicle routing problem, (Golden, B. L.; Assad, A. A., Vehicle Routing: Methods and Studies (1988), North-Holland: North-Holland Amsterdam) · Zbl 0653.90032 |
| [17] | Jaillet, P., Stochastic routing problems, (Andreatta, G.; Mason, F.; Serafini, P., Stochastics in Combinatorial Optimization (1987), World Scientific: World Scientific New Jersey) · Zbl 0644.90091 |
| [18] | Lambert, V.; Laporte, G.; Louveaux, F. V., Designing collection routes through bank branches, Computers and Operations Research, 20, 783-791 (1993) |
| [19] | Laporte, G.; Louveaux, F. V., Solving stochastic routing problems with the integer L-shaped method, (Crainic, T. G.; Laporte, G., Fleet Management and Logistics (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 159-167 · Zbl 0963.90010 |
| [20] | Laporte, G.; Louveaux, F. V., The integer L-shape method for stochastic integer problems with complete recourse, Operations Research Letters, 13, April, 133-142 (1993) · Zbl 0793.90043 |
| [21] | Larson, R. C., Transportation of sludge to the 106-mile site: An inventory routing algorithm for fleet sizing and logistic system design, Transportation Science, 22, 186-198 (1988) |
| [22] | Lee, L.H., Chew, E.P., 2003. A simulation study on sampling and selecting under fixed computing budget. In: Proceedings of the 2003 Winter Simulation Conference, New Orleans, LA, USA.; Lee, L.H., Chew, E.P., 2003. A simulation study on sampling and selecting under fixed computing budget. In: Proceedings of the 2003 Winter Simulation Conference, New Orleans, LA, USA. |
| [23] | Lee, L. H.; Tan, K. C.; Ou, K.; Chew, Y. H., Vehicle capacity planning system: A case study on vehicle routing problem with time windows, IEEE Transactions on Systems, Man and Cybernetics, Part A, 33, 2, 169-178 (2003) |
| [24] | Potvin, J. Y.; Bengio, S., The vehicle routing problem with time windows—Part II: Genetic search, INFORMS Journal on Computing, 8, 2, 165-172 (1996) · Zbl 0866.90058 |
| [25] | Prins, C., A simple and effective evolutionary algorithm for the vehicle routing problem, Computers and Operations Research, 31, 12, 1985-2002 (2004) · Zbl 1100.90504 |
| [26] | Ross, P., Corne, D., 1994. Applications of genetic algorithms. In: Forgarty, T.C. (Ed.), AISB Quarterly 89, 23-30.; Ross, P., Corne, D., 1994. Applications of genetic algorithms. In: Forgarty, T.C. (Ed.), AISB Quarterly 89, 23-30. |
| [27] | Secomandi, N., A rollout policy for the vehicle routing problem with stochastic demands, Operations Research, 49, 5, 796-802 (2001) · Zbl 1163.90373 |
| [28] | Secomandi, N., Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands, Computers and Operations Research, 27, 11-12, 1201-1225 (2000) · Zbl 0962.90010 |
| [29] | Solomon, M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 35, 2, 254-265 (1987) · Zbl 0625.90047 |
| [30] | Stewart, W. R.; Golden, B. L., Stochastic vehicle routing: A comprehensive approach, European Journal of Operational Research, 14, 4, 371-385 (1983) · Zbl 0519.90031 |
| [31] | Tan, K.C., Lee, T.H., Chew, Y.H., Lee, L.H., 2003a. A hybrid multiobjective evolutionary algorithm for solving truck and trailer vehicle routing problems. In: Proceedings of the 2003 Congress on Evolutionary Computation, Canberra, Australia, 8-12 December, vol. 3, pp. 2134-2141.; Tan, K.C., Lee, T.H., Chew, Y.H., Lee, L.H., 2003a. A hybrid multiobjective evolutionary algorithm for solving truck and trailer vehicle routing problems. In: Proceedings of the 2003 Congress on Evolutionary Computation, Canberra, Australia, 8-12 December, vol. 3, pp. 2134-2141. · Zbl 1111.90021 |
| [32] | Tan, K.C., Lee, T.H., Chew, Y.H., Lee, L.H., 2003b. A multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. In: Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Washington, DC, USA, 5-8 October 2003, vol. 1, pp. 361-366.; Tan, K.C., Lee, T.H., Chew, Y.H., Lee, L.H., 2003b. A multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. In: Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Washington, DC, USA, 5-8 October 2003, vol. 1, pp. 361-366. · Zbl 1111.90022 |
| [33] | Tan, K. C.; Lee, L. H.; Zhu, Q. L.; Ou, K., Heuristic methods for vehicle routing problem with time windows, Artificial Intelligence in Engineering, 15, 3, 281-295 (2001) |
| [34] | Tan, K.C., Lee, T.H., Ou, K., Lee, L.H., 2001b. A messy genetic algorithm for the vehicle routing problem with time window constraints. In: Proceedings of the 2001 Congress on Evolutionary Computation, Seoul, Korea, 27-30 May, vol. 1, pp. 679-686.; Tan, K.C., Lee, T.H., Ou, K., Lee, L.H., 2001b. A messy genetic algorithm for the vehicle routing problem with time window constraints. In: Proceedings of the 2001 Congress on Evolutionary Computation, Seoul, Korea, 27-30 May, vol. 1, pp. 679-686. |
| [35] | Teodorović, D., Lucić, P., 2000. Intelligent vehicle routing system. In: Proceedings of the IEEE International Conference on Intelligent Transportation Systems, Dearborn, MI, USA, 1-3 October 2000, pp. 482-487.; Teodorović, D., Lucić, P., 2000. Intelligent vehicle routing system. In: Proceedings of the IEEE International Conference on Intelligent Transportation Systems, Dearborn, MI, USA, 1-3 October 2000, pp. 482-487. |
| [36] | Teodorović, D.; Pavković, G., The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain, Fuzzy Sets and Systems, 82, 3, 307-317 (1996) |
| [37] | Thangiah, S. R.; Potvin, J. Y.; Sun, T., Heuristic approaches to vehicle routing with backhauls and time windows, Computers and Operations Research, 23, 11, 1043-1057 (1996) · Zbl 0867.90046 |
| [38] | Van Veldhuizen, D., Lamont, G.B., 1998. Multiobjective evolutionary algorithm research: A history and analysis. Technical Report TR-98-03, Department of Electrical and Computer Engineering, Air Force Institute of Technology, Ohio.; Van Veldhuizen, D., Lamont, G.B., 1998. Multiobjective evolutionary algorithm research: A history and analysis. Technical Report TR-98-03, Department of Electrical and Computer Engineering, Air Force Institute of Technology, Ohio. |
| [39] | Yang, W. H.; Mathur, K.; Ballou, R. H., Stochastic vehicle routing problem with restocking, Transportation Science, 34, 99-112 (2000) · Zbl 1014.90020 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
