A Scenario-Based Robust Optimization Model for a Periodic Vehicle Routing Problem with Time Windows under Uncertainty by Using a Differential Evolution Algorithm

Document Type : Research Paper

Authors

Department of Industrial Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran

Abstract

This paper provides a model for evaluating the efficiency of a periodic vehicle routing problem (PVRP) to get the short routes with maximum sale by providing suitable services to customers before delivering the goods by other competitor distributors. In the goods distribution with short lifetime that customers need a special device for keeping them, the arriving time to customers influence on the sales amount, in which classical VRPs are unable to calculate this kind of assumptions. According to real world applications, the arriving time of the competitors is uncertain because of customer demands, traffic, weather conditions, and the like. A scenario approach is employed to handle the uncertainty of the arriving time of rivals. The purpose of this paper is to solve this problem by optimizing the sale of products to customers before delivering the products to other competitor distributors in an uncertain condition by robust optimization. To evaluate the presented model, a number of test problems are solved by two strategies of a differential evolution (DE) algorithm. Results are compared with those obtained by the CPLEX method in GAMS in small and medium sizes. To evaluate the proposed algorithm for solving large-scale problems, some solutions are implemented, and the results are compared in term of their accuracy. The computational results represent the capability of the proposed DE strategies in solving large-scale problems in a reasonable time.

Keywords

Main Subjects

References

  1. 1.   Kos, C., and Karaoglan, I. (2016). “The green vehicle routing problem: A heuristic based exact solution approach”, Applied Soft Computing, Vol. 39, No.1. PP. 154–164.

    2.   Archetti, C., Savelsbergh, M. and Speranza, M. (2016). “Vehicle Routing Problem with Occasional Drivers”, European Journal of Operational Research, Vol. 254, No.2, PP. 472–480.

    3.   Noruzi, N., Sadegh-Amalnick, M. and Alinaghian, M. (2015). “Evaluating of the particle swarm optimization in a periodic vehicle routing problem”, Measurement, Vol.62, No.2, PP. 162-169.

    1. Leung, S.C.H. et al. (2007). “A robust optimization model for multi-site production planning problem in an uncertain environment”, European Journal of Operational Research, Vol. 181, No.5, PP. 224-238.
    2. Kohl, N., and Madsen, O.B.G. (1997). “An optimization algorithm for the vehicle routing problem with time windows based on lagrangian relaxation”, Jornal of Operation Research, Vol.45, No.3, PP. 395-406.
    3. Coene, S., Arnout, A., and Spieksma, F. (2010). “On a periodic vehicle routing problem”, Journal of Operation Research, Vol. 61, No.12, PP. 1719–1728.
    4. Hemmelmayr, V. et al. (2011). “A heuristic solution method for node routing based solid waste collection problems”, Journal of Heuristics, Vol.19, No.2, PP. 129-156.
    5. Baptista, S., Oliveira, R.C. and Zúquete, E. (2002). “A period vehicle routing case study”, European Journal Operation Research, Vol.139, No.2, PP. 220-229.
    6. Tavakkoli-Moghaddam, R. et al. (2011). “New mathematical model for a competitive vehicle routing problem with time windows solved by simulated annealing”, Journal of Manufacturing Systems, Vol.30, No.2, PP. 83-92.
    7. Norouzi, N. et al. (2012). “A New Multi-objective Competitive Open Vehicle Routing Problem Solved by Particle Swarm Optimization”, Journal of Manufacturing Systems, Vol. 12, No.4, PP. 609-633.
    8. Erera, A., L, Morales, J. C, and Savelsbergh, M. (2010). “The vehicle routing problem with stochastic demand and duration constraints”, Journal of Transportation Science, Vol. 44, No.4, PP. 474–49.
    9. Novoa, C. and Storer, R. (2009). “An approximate dynamic programming approach for the vehicle routing problem with stochastic demands”, ‌European Journal of Operational Research, Vol. 196, No.2, PP. 509–515.
    10. Goodson, J. C., Ohlmann, J. W, and Thomas, B. (2012). “Cyclic -order neighborhoods with application to the vehicle routing problem with stochastic demand”, European Journal of Operational Research, Vol. 2172, No.2, PP. 312–323.
    11. List, B. F., Wood, B, and Nozick, L. K. (2003). “Robust optimization for fleet planning under uncertainty”, Transportation Research Part E: Logistics and Transportation Review, Vol. 39, No.3, PP. 209– 227.
    12. Soyster, A. (1973). “Convex programming with set-inclusive constraints and applications to inexact linear programming”, Journal of Operation Research, Vol. 21, No.5, PP. 1154– 1157.
    13. Mulvey J. M., Vanderbei, R. J, and Zenios, S. A. (1995). “Robust optimization of large-scale systems”, Journal of Operation Research, Vol. 43, No.2, PP. 264–281.
    14. Bahri, O., Ben Amor, N, and Talbi, EG. (2016). “Robust Routes for the Fuzzy Multi-objective Vehicle Routing Problem”, 8th IFAC Conference on Manufacturing Modeling, Management and Control, Vol.49, No.12, PP. 769-774.
    15. Ben-Tal, A. and Nemirovski, A. (1998). “Robust convex optimization”, Mathematic Operation Research, Vol. 23, No.4,   PP. 769–805.
    16. Ben-Tal, A. and Nemirovski, A. (2000). “Robust solutions of linear programming problems contaminated with uncertain data” Mathematic Programming, Vol. 88, No.3, PP. 411–424.
    17. El-Ghaoui, L., Oustry, F, and Lebret, H. (1998). “Robust solutions to uncertain semi definite programs”, SIAM Journal on Optimization, Vol. 9, No.1, PP. 33–52.
    18. Sungur, I., Ordonez, F, and Dessouky, M. (2008). “A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty.” IIE Transactions, Vol. 40, PP. 509–523.
    19. Gounaris, C. E., Wiseman, W, and Floudas, C. A. (2013). “The robust capacitated vehicle routing problem under demand uncertainty.” Journal of Operations Research, Vol. 61, No.3, PP. 677–693.
    20. Lee, C., Lee, K, and Park, S. (2012). “Robust vehicle routing problem with deadlines and travel time /demand uncertainty”, Journal of the Operational Research Society, Vol. 63, No.9, PP. 1294–1306.
    21. Lenstra, J.K. and Rinnooy Kan, A.H.G. (1981). “Complexity of vehicle and scheduling problem", Networks, Vol.11, No.2, PP. 221-227.
    22. Coene, S., Arnout, A, and Spieksma, F. (2010). “On a periodic vehicle routing problem”, Journal of Operation Research society, Vol.61, No.12, PP. 1719-1728.
    23. Alegre, J., Laguna, M, and Pacheco, J. (2007). “Optimizing the periodic pickup of raw materials for a manufacturer of auto parts”, European Journal Operation. Research, Vol.179, No.3, PP. 739746.
    24. Alinaghian, M., et al. (2012). “A new competitive approach on multi-objective periodic vehicle routing problem”, International Journal Applied Operation Research. Vol.1, No.3, PP. 33-41.
    25. Angelelli, E and Speranza, M.G. (2002). “The periodic vehicle routing problem with intermediate facilities”, European Journal of Operation Research, Vol.137, No.2, PP. 233-247.
    26. Das, S, and Suganthan, PN. (2011). “Differential evolution: a survey of the state-of-the-art”, transaction on Evolutionary Computation, Vol.15. No.2, PP.4-31
    27. Kunnapapdeelert, S, and Kachitvichyanukul, V. (2013). “Differential evolution algorithm for generalized multi depot vehicle routing problem with pickup and delivery requests”, In: Lin YK., Tsao YC., Lin SW. (Eds) Proceedings of the Institute of Industrial Engineers Asian Conference 2013. Springer, Singapore.
    28.  Kunnapapdeelert, S, and Kachitvichyanukul, V. (2015). “Modified DE Algorithms for Solving Multi-depot Vehicle Routing Problem with Multiple Pickup and Delivery Requests”, Toward Sustainable Operations of Supply Chain and Logistics Systems, Eco Production.
    29. Pan, F, and Nagi, R. (2010). “Robust supply chain design under uncertain demand in agile manufacturing”, Computers and Operations Research, Vol. 37, No.4, PP.668-683.
    30. Yu, C.S and Li H.L. (2000). “A robust optimization model for stochastic logistic problems”, International Journal of Production Economics, Vol.64, No.1, PP. 385-397.
    31. Leung, S.C.H, and Chan S.S.W. (2009). “A Goal Programming Model for Aggregate Production Planning with Resource Utilization Constraint”, Computers and Industrial Engineering, Vol.56, No.3, PP. 1053-1064.
    32. Storn, R, and Price. K. (1997). “Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces.” Journal of Global Optimization, Vol.11, No.4, PP. 359-431.
    33. Price, K.V., Storn, R.M, and Lampinen, J.A. (2005). “Differential Evolution: A Practical Approach to Global Optimization”, Natural Computing Series, Springer.
    34. Qin, A.K, and Suganthan. P.N. (2005). “Self-Adaptive Differential Evolution Algorithm for Numerical Optimization”, In Proceedings of the IEEE Congress on Evolutionary Computation, Vol. 2, No.3, PP.1785–1791.
    35. L´ opez Cruz, I.L. et al. (2005). “Efficient Differential Evolution algorithms for multimodal optimal control problems‌”, Applied Soft Computing, Vol.3, No.2, PP. 97-122.
    36. Cordeau, J.F., Gendreau, M, and Laporte, G. (1997). “A tabu search heuristic for periodic and multi-depot vehicle routing problems”, Networks Vol 30. No.2, PP.105-119.
Advances in Industrial Engineering
Volume 52, Issue 1
April 2018
Pages 73-86

Files

Share

How to cite

Statistics