Document Type : Research Paper
Authors
School of Industrial Engineering, Iran University of Science and Technology
Abstract
Most studies on decision making issue have supposed the problem in deterministic environment, and because uncertainty makes the decisions taken suboptimal, so in this paper we propose a credibility based fuzzy model for the Vehicle Routing Problem with Simultaneous Delivery and Pickup and Time Windows (VRPSDPTW). The dispatching cost of vehicles and customers’ time windows are supposed to be trapezoidal fuzzy numbers. We also proposed a hybrid meta-heuristic algorithm called Improved Particle Swarm Optimization (IPSO) for solving the problem. The proposed algorithm is the combination of Particle Swarm Optimization (PSO) and some removal and insertion techniques which helps to improve the searching ability and maintain diversity of solutions. Finally, to demonstrate the applicability of the proposed model in the real world we studied the distribution of dairy products among customers by a distribution company in Fars province. The computational results show that distributors can use this method to reduce operating costs of the company.
Keywords
1.Dantzig, G.B. and J.H. Ramser, The truck dispatching problem. Management science, 1959. 6(1): p. 80-91.
2.Erbao, C. and L. Mingyong, A hybrid differential evolution algorithm to vehicle routing problem with fuzzy demands. Journal of computational and applied mathematics, 2009. 231(1): p. 302-310.
3.Pishvaee, M., S. Torabi, and J. Razmi, Credibility-based fuzzy mathematical programming model for green logistics design under uncertainty. Computers & Industrial Engineering, 2012. 62(2): p. 624-632.
4.Bertsimas, D.J., A vehicle routing problem with stochastic demand. Operations Research, 1992. 40(3): p. 574-585.
5.Dror, M., G. Laporte, and P. Trudeau, Vehicle routing with stochastic demands: Properties and solution frameworks. Transportation science, 1989. 23(3): p. 166-176.
6.Gendreau, M., G. Laporte, and R. Séguin, Stochastic vehicle routing. European Journal of Operational Research, 1996. 88(1): p. 3-12.
7.Liu, B. and K. Lai. Stochastic programming models for vehicle routing problems. in Focus on computational neurobiology. 2004. Nova Science Publishers, Inc.
8.Teodorović, D. and G. Pavković, The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain. Fuzzy sets and systems, 1996. 82(3): p. 307-317.
9.El-Sayed, M., N. Afia, and A. El-Kharbotly, A stochastic model for forward–reverse logistics network design under risk. Computers & Industrial Engineering, 2010. 58(3): p. 423-431.
10.Pishvaee, M.S., F. Jolai, and J. Razmi, A stochastic optimization model for integrated forward/reverse logistics network design. Journal of Manufacturing Systems, 2009. 28(4): p. 107-114.
11.Schütz, P., A. Tomasgard, and S. Ahmed, Supply chain design under uncertainty using sample average approximation and dual decomposition. European Journal of Operational Research, 2009. 199(2): p. 409-419.
12.Pishvaee, M.S., M. Rabbani, and S.A. Torabi, A robust optimization approach to closed-loop supply chain network design under uncertainty. Applied Mathematical Modelling, 2011. 35(2): p. 637-649.
13.Pishvaee, M. and S. Torabi, A possibilistic programming approach for closed-loop supply chain network design under uncertainty. Fuzzy sets and systems, 2010. 161(20): p. 2668-2683.
14.Qin, Z. and X. Ji, Logistics network design for product recovery in fuzzy environment. European Journal of Operational Research, 2010. 202(2): p. 479-490.
15.Cheng, R., M. Gen, and T. Tozawa, Vehicle routing problem with fuzzy due-time using genetic algorithms. 日本ファジィ学会誌, 1995. 7(5): p. 1050-1061.
16.Lai, K., B. Liu, and J. Peng, Vehicle routing problem with fuzzy travel times and its genetic algorithm. 2003, Technical Report.
17.He, Y. and J. Xu, A class of random fuzzy programming model and its application to vehicle routing problem. World Journal of Modelling and simulation, 2005. 1(1): p. 3-11.
18.Zheng, Y. and B. Liu, Fuzzy vehicle routing model with credibility measure and its hybrid intelligent algorithm. Applied mathematics and computation, 2006. 176(2): p. 673-683.
19.Van Woensel, T., et al., Vehicle routing with dynamic travel times: A queueing approach. European Journal of Operational Research, 2008. 186(3): p. 990-1007.
20.Tang, J., et al., Vehicle routing problem with fuzzy time windows. Fuzzy Sets and Systems, 2009. 160(5): p. 683-695.
21.Brito, J., J.A. Moreno, and J.L. Verdegay. Fuzzy Optimization in Vehicle Routing Problems. in IFSA/EUSFLAT Conf. 2009.
22.Cao, E. and M. Lai, The open vehicle routing problem with fuzzy demands. Expert Systems with Applications, 2010. 37(3): p. 2405-2411.
23.Gupta, R., B. Singh, and D. Pandey, Fuzzy vehicle routing problem with uncertainty in service time. International Journal of Contemporary Mathematical Sciences, 2010. 5(11): p. 497-507.
24.Xu, J., F. Yan, and S. Li, Vehicle routing optimization with soft time windows in a fuzzy random environment. Transportation Research Part E: Logistics and Transportation Review, 2011. 47(6): p. 1075-1091.
25.Kuo, R., F.E. Zulvia, and K. Suryadi, Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand–A case study on garbage collection system. Applied Mathematics and Computation, 2012. 219(5): p. 2574-2588.
26.Duygu, T., et al., Vehicle routing problem with stochastic travel times including soft time windows and service costs. Computers & Operations Research, 2013. 40: p. 214-224.
27.Ghaffari-Nasab, N., S.G. Ahari, and M. Ghazanfari, A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands. Scientia Iranica, 2013. 20(3): p. 919-930.
28.Zare Mehrjerdi, Y. and A. Nadizadeh, Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands. European Journal of Operational Research, 2013. 229(1): p. 75-84.
29.Nadizadeh, A. and H. Hosseini Nasab, Solving the dynamic capacitated location-routing problem with fuzzy demands by hybrid heuristic algorithm. European Journal of Operational Research, 2014. 238(2): p. 458-470.
30.Dinc Yalcın, G. and N. Erginel, Fuzzy multi-objective programming algorithm for vehicle routing problems with backhauls. Expert Systems with Applications, 2015. 42(13): p. 5632-5644.
31.Kuo, R.J., B.S. Wibowo, and F.E. Zulvia, Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time. Applied Mathematical Modelling, 2016. 40(23): p. 9990-10001.
32.Bahri, O., N.B. Amor, and E.-G. Talbi, Robust Routes for the Fuzzy Multi-objective Vehicle Routing Problem. IFAC-PapersOnLine, 2016. 49(12): p. 769-774.
33.Majidi, S., et al., Fuzzy green vehicle routing problem with simultaneous pickup – delivery and time windows. RAIRO-Oper. Res., 2017. 51(4): p. 1151-1176.
34.Shi, Y., T. Boudouh, and O. Grunder, A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand. Expert Systems with Applications, 2017. 72: p. 160-176.
35.Zadeh, L.A., Fuzzy sets. Information and control, 1965. 8(3): p. 338-353.
36.Kaufmann, A., Introduction to the Theory of Fuzzy Subsets. 1975, New York: Academic Press.
37.Negoita, C., L. Zadeh, and H. Zimmermann, Fuzzy sets as a basis for a theory of possibility. Fuzzy sets and systems, 1978. 1: p. 3-28.
38.Liu, B., Uncertain Theory: An Introduction to its Axiomatic Foundations. 2004, Berlin: Springer.
39.Liu, B. and Y.K. Liu, Expected value of fuzzy variable and fuzzy expected value models. IEEE Transactions on fuzzy systems, 2002. 10(4): p. 445-450.
40.Liu, B. and K. Iwamura, Chance constraint programming with fuzzy parameters. Fuzzy Sets and Systems, 1998. 94: p. 227-237.
41.Liu, B., Dependent chance programming with fuzzy decisions. IEEE Transactions and Fuzzy Systems, 1999. 7(354-360).
42.Karaoglan, I., et al., The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 2012. 40: p. 465-477.
43.Chen, C.-Y. and F. Ye. Particle swarm optimization algorithm and its application to clustering analysis. in Networking, Sensing and Control, 2004 IEEE International Conference on. 2004. IEEE.
44.Hamed, A., et al., An improved particle swarm optimization for a class of capacitated vehicle routing problems. International Journal of Transportation Engineering, 2017. 5(4): p. 331-347.
45.Shi, Y. and R.C. Eberhart, A modified particle swarm optimizer. Proceedings of the Congress Evoluationary Computer, 1998: p. 69–73.
46.Lichtblau, T., Discrete optimization using mathematica, in World Multi Conference on Systemics and Informatics, N. Callaos, et al., Editors. 2002, International Institute of Informatics and Systemics. p. 169-174.
47.Wang, H., et al., Diversity enhanced particle swarm optimization with neighborhood search. Information Sciences, 2013. 223: p. 119-135.
48.Cho, P., et al., An assessment of consecutively presenting orthokeratology patients in a Hong Kong based private practice. Clinical and Experimental Optometry, 2003. 86(5): p. 331-338.
49.Planeta, D.S., Priority Queue Based on Multilevel Prefix Tree. arXiv preprint arXiv:0708.2936, 2007.
2.Erbao, C. and L. Mingyong, A hybrid differential evolution algorithm to vehicle routing problem with fuzzy demands. Journal of computational and applied mathematics, 2009. 231(1): p. 302-310.
3.Pishvaee, M., S. Torabi, and J. Razmi, Credibility-based fuzzy mathematical programming model for green logistics design under uncertainty. Computers & Industrial Engineering, 2012. 62(2): p. 624-632.
4.Bertsimas, D.J., A vehicle routing problem with stochastic demand. Operations Research, 1992. 40(3): p. 574-585.
5.Dror, M., G. Laporte, and P. Trudeau, Vehicle routing with stochastic demands: Properties and solution frameworks. Transportation science, 1989. 23(3): p. 166-176.
6.Gendreau, M., G. Laporte, and R. Séguin, Stochastic vehicle routing. European Journal of Operational Research, 1996. 88(1): p. 3-12.
7.Liu, B. and K. Lai. Stochastic programming models for vehicle routing problems. in Focus on computational neurobiology. 2004. Nova Science Publishers, Inc.
8.Teodorović, D. and G. Pavković, The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain. Fuzzy sets and systems, 1996. 82(3): p. 307-317.
9.El-Sayed, M., N. Afia, and A. El-Kharbotly, A stochastic model for forward–reverse logistics network design under risk. Computers & Industrial Engineering, 2010. 58(3): p. 423-431.
10.Pishvaee, M.S., F. Jolai, and J. Razmi, A stochastic optimization model for integrated forward/reverse logistics network design. Journal of Manufacturing Systems, 2009. 28(4): p. 107-114.
11.Schütz, P., A. Tomasgard, and S. Ahmed, Supply chain design under uncertainty using sample average approximation and dual decomposition. European Journal of Operational Research, 2009. 199(2): p. 409-419.
12.Pishvaee, M.S., M. Rabbani, and S.A. Torabi, A robust optimization approach to closed-loop supply chain network design under uncertainty. Applied Mathematical Modelling, 2011. 35(2): p. 637-649.
13.Pishvaee, M. and S. Torabi, A possibilistic programming approach for closed-loop supply chain network design under uncertainty. Fuzzy sets and systems, 2010. 161(20): p. 2668-2683.
14.Qin, Z. and X. Ji, Logistics network design for product recovery in fuzzy environment. European Journal of Operational Research, 2010. 202(2): p. 479-490.
15.Cheng, R., M. Gen, and T. Tozawa, Vehicle routing problem with fuzzy due-time using genetic algorithms. 日本ファジィ学会誌, 1995. 7(5): p. 1050-1061.
16.Lai, K., B. Liu, and J. Peng, Vehicle routing problem with fuzzy travel times and its genetic algorithm. 2003, Technical Report.
17.He, Y. and J. Xu, A class of random fuzzy programming model and its application to vehicle routing problem. World Journal of Modelling and simulation, 2005. 1(1): p. 3-11.
18.Zheng, Y. and B. Liu, Fuzzy vehicle routing model with credibility measure and its hybrid intelligent algorithm. Applied mathematics and computation, 2006. 176(2): p. 673-683.
19.Van Woensel, T., et al., Vehicle routing with dynamic travel times: A queueing approach. European Journal of Operational Research, 2008. 186(3): p. 990-1007.
20.Tang, J., et al., Vehicle routing problem with fuzzy time windows. Fuzzy Sets and Systems, 2009. 160(5): p. 683-695.
21.Brito, J., J.A. Moreno, and J.L. Verdegay. Fuzzy Optimization in Vehicle Routing Problems. in IFSA/EUSFLAT Conf. 2009.
22.Cao, E. and M. Lai, The open vehicle routing problem with fuzzy demands. Expert Systems with Applications, 2010. 37(3): p. 2405-2411.
23.Gupta, R., B. Singh, and D. Pandey, Fuzzy vehicle routing problem with uncertainty in service time. International Journal of Contemporary Mathematical Sciences, 2010. 5(11): p. 497-507.
24.Xu, J., F. Yan, and S. Li, Vehicle routing optimization with soft time windows in a fuzzy random environment. Transportation Research Part E: Logistics and Transportation Review, 2011. 47(6): p. 1075-1091.
25.Kuo, R., F.E. Zulvia, and K. Suryadi, Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand–A case study on garbage collection system. Applied Mathematics and Computation, 2012. 219(5): p. 2574-2588.
26.Duygu, T., et al., Vehicle routing problem with stochastic travel times including soft time windows and service costs. Computers & Operations Research, 2013. 40: p. 214-224.
27.Ghaffari-Nasab, N., S.G. Ahari, and M. Ghazanfari, A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands. Scientia Iranica, 2013. 20(3): p. 919-930.
28.Zare Mehrjerdi, Y. and A. Nadizadeh, Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands. European Journal of Operational Research, 2013. 229(1): p. 75-84.
29.Nadizadeh, A. and H. Hosseini Nasab, Solving the dynamic capacitated location-routing problem with fuzzy demands by hybrid heuristic algorithm. European Journal of Operational Research, 2014. 238(2): p. 458-470.
30.Dinc Yalcın, G. and N. Erginel, Fuzzy multi-objective programming algorithm for vehicle routing problems with backhauls. Expert Systems with Applications, 2015. 42(13): p. 5632-5644.
31.Kuo, R.J., B.S. Wibowo, and F.E. Zulvia, Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time. Applied Mathematical Modelling, 2016. 40(23): p. 9990-10001.
32.Bahri, O., N.B. Amor, and E.-G. Talbi, Robust Routes for the Fuzzy Multi-objective Vehicle Routing Problem. IFAC-PapersOnLine, 2016. 49(12): p. 769-774.
33.Majidi, S., et al., Fuzzy green vehicle routing problem with simultaneous pickup – delivery and time windows. RAIRO-Oper. Res., 2017. 51(4): p. 1151-1176.
34.Shi, Y., T. Boudouh, and O. Grunder, A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand. Expert Systems with Applications, 2017. 72: p. 160-176.
35.Zadeh, L.A., Fuzzy sets. Information and control, 1965. 8(3): p. 338-353.
36.Kaufmann, A., Introduction to the Theory of Fuzzy Subsets. 1975, New York: Academic Press.
37.Negoita, C., L. Zadeh, and H. Zimmermann, Fuzzy sets as a basis for a theory of possibility. Fuzzy sets and systems, 1978. 1: p. 3-28.
38.Liu, B., Uncertain Theory: An Introduction to its Axiomatic Foundations. 2004, Berlin: Springer.
39.Liu, B. and Y.K. Liu, Expected value of fuzzy variable and fuzzy expected value models. IEEE Transactions on fuzzy systems, 2002. 10(4): p. 445-450.
40.Liu, B. and K. Iwamura, Chance constraint programming with fuzzy parameters. Fuzzy Sets and Systems, 1998. 94: p. 227-237.
41.Liu, B., Dependent chance programming with fuzzy decisions. IEEE Transactions and Fuzzy Systems, 1999. 7(354-360).
42.Karaoglan, I., et al., The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 2012. 40: p. 465-477.
43.Chen, C.-Y. and F. Ye. Particle swarm optimization algorithm and its application to clustering analysis. in Networking, Sensing and Control, 2004 IEEE International Conference on. 2004. IEEE.
44.Hamed, A., et al., An improved particle swarm optimization for a class of capacitated vehicle routing problems. International Journal of Transportation Engineering, 2017. 5(4): p. 331-347.
45.Shi, Y. and R.C. Eberhart, A modified particle swarm optimizer. Proceedings of the Congress Evoluationary Computer, 1998: p. 69–73.
46.Lichtblau, T., Discrete optimization using mathematica, in World Multi Conference on Systemics and Informatics, N. Callaos, et al., Editors. 2002, International Institute of Informatics and Systemics. p. 169-174.
47.Wang, H., et al., Diversity enhanced particle swarm optimization with neighborhood search. Information Sciences, 2013. 223: p. 119-135.
48.Cho, P., et al., An assessment of consecutively presenting orthokeratology patients in a Hong Kong based private practice. Clinical and Experimental Optometry, 2003. 86(5): p. 331-338.
49.Planeta, D.S., Priority Queue Based on Multilevel Prefix Tree. arXiv preprint arXiv:0708.2936, 2007.
)