A Multi-depot Vehicle Routing Problem with Time Windows and Load Balancing: A Real World Application

Document Type : Research Paper

Authors

1 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

2 School of Industrial Engineering, Iran University of Science & Technology, Tehran, Iran

Abstract

This paper presents a mixed integer non-linear programming (MINLP) model for a bi-
objective and multi-depot vehicle routing problem with time windows. The main goals of the
paper are minimization of total cost and equitable distribution of commodities between
vehicles. Two types of vehicle including delivery and installation vehicles are utilized in the
network regarding customers’ needs. Satisfying all demands of the customers is not
obligatory and unmet demands are permitted which leads to extra cost. A presented model is applied for real life case study in different provinces of Iran. To tackle the small-size
problems, the augmented e-constraint method is utilized by linearization of the model.
Because of the NP-hard nature of the problem, as the size of the problem increases, so does the complexity. As such, we develop multi-objective simulated annealing (MOSA meta-heuristic) algorithm for large scale problems. Then, several numerical experiments and sensitivity analyses are conducted to validate the presented model and the solution method, which indicate the efficiency of our proposed approach.

Keywords

References

Afshar-Nadjafi, B., and Afshar-Nadjafi, A. (2017). A constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet. Journal of king saud university-Engineering sciences, Vol. 29(1), pp. 29-34.
Ariyani, A. K., Mahmudy, W. F., and Anggodo, Y. P. (2018). Hybrid Genetic Algorithms and Simulated Annealing for Multi-trip Vehicle Routing Problem with Time Windows. International Journal of Electrical & Computer Engineering (2088-8708), Vol.8, pp. 4713-4723.
Azadeh, A., and Farrokhi-Asl, H. (2019). The close–open mixed multi depot vehicle routing problem considering internal and external fleet of vehicles. Transportation Letters, Vol. 11(2), pp. 78-92.
Babaee Tirkolaee, E., Abbasian, P., Soltani, M., and Ghaffarian, S. A. (2019). Developing an applied algorithm for multi-trip vehicle routing problem with time windows in urban waste collection: A case study. Waste Management & Research, Vol. 37(1_suppl), pp. 4-13.
Bae, H., and Moon, I. (2016). Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles. Applied Mathematical Modelling, Vol.40(13-14), pp. 6536-6549.
Bianchessi, N., Drexl, M., and Irnich, S. (2019). The split delivery vehicle routing problem with time windows and customer inconvenience constraints. Transportation Science, Vol.53(4), pp. 1067-1084.
Chen, J., and Shi, J. (2019). A multi-compartment vehicle routing problem with time windows for urban distribution–A comparison study on particle swarm optimization algorithms. Computers & Industrial Engineering, Vol.133, pp. 95-106.
Desaulniers, G., Errico, F., Irnich, S., and Schneider, M. (2016). Exact algorithms for electric vehicle-routing problems with time windows. Operations Research, Vol.64(6), pp. 1388-1405.
Dharmapriya, U., Siyambalapitiya, S., and Kulatunga, A. (2010, January). Artificial intelligence computational techniques to optimize a multi objective oriented distribution operations. In Proceedings of the 2010 International Conference on Industrial Engineering and Operations Management Dhaka, Bangladesh.
Farrokhi-Asl, H., Makui, A., Ghousi, R., and Rabbani, M. (2019). Designing a sustainable integrated forward/reverse logistics network. Journal of Modelling in Management, Vol.14(4), pp. 896-921.
Farrokhi-Asl, H., Makui, A., Jabbarzadeh, A., and Barzinpour, F. (2018). Solving a multi-objective sustainable waste collection problem considering a new collection network. Operational Research, Vol. 20, pp. 1-39.
Farrokhi-Asl, H., Tavakkoli-Moghaddam, R., Asgarian, B., and Sangari, E. (2017). Metaheuristics for a bi-objective location-routing-problem in waste collection management. Journal of Industrial and Production Engineering, Vol.34(4), pp. 239-252.
Ghannadpour, S. F., Noori, S., Tavakkoli-Moghaddam, R., and Ghoseiri, K. (2014). A multi-objective dynamic vehicle routing problem with fuzzy time windows: Model, solution and application. Applied Soft Computing, Vol.14, pp. 504-527.
Ghomi, S. F., and Asgarian, B. (2019). Development of metaheuristics to solve a transportation inventory location routing problem considering lost sale for perishable goods. Journal of Modelling in Management, Vol. 14(1), pp. 175-198.
Ghoseiri, K., and Ghannadpour, S. F. (2010). A hybrid genetic algorithm for multi-depot homogenous locomotive assignment with time windows. Applied Soft Computing, Vol. 10(1), pp. 53-65.
Guezouli, L., and Abdelhamid, S. (2017). A new multi-criteria solving procedure for multi-depot FSM-VRP with time window. International Journal of Applied Industrial Engineering (IJAIE), Vol. 4(1), pp. 1-18.
Kaboudani, Y., Ghodsypour, S. H., Kia, H., & Shahmardan, A. (2018). Vehicle routing and scheduling in cross docks with forward and reverse logistics. Operational Research, Vol. 20, pp. 1-34.
Kachitvichyanukul, V., Sombuntham, P., and Kunnapapdeelert, S. (2015). Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via PSO. Computers & Industrial Engineering, Vol. 89, pp. 125-136.
Khalili‐Damghani, K., Abtahi, A. R., and Tavana, M. (2014). A decision support system for solving multi‐objective redundancy allocation problems. Quality and Reliability Engineering International, Vol. 30(8), pp. 1249-1262.
Kim, K. C., Sun, J. U., and Lee, S. W. (2013). A HIERARCHICAL APPROACH TO VEHICLE ROUTING AND SCHEDULING WITH SEQUENTIAL SERVICES USING THE GENETIC ALGORITHM. International Journal of Industrial Engineering, Vol. 20, pp. 99-113.
Koç, Ç., Bektaş, T., Jabali, O., and Laporte, G. (2016). The fleet size and mix location-routing problem with time windows: Formulations and a heuristic algorithm. European Journal of Operational Research, Vol. 248(1), pp. 33-51.
Kritikos, M. N., and Ioannou, G. (2010). The balanced cargo vehicle routing problem with time windows. International Journal of Production Economics, Vol. 123(1), pp. 42-51.
Lahyani, R., Coelho, L. C., and Renaud, J. (2018). Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem. Or Spectrum, 40(1), 125-157.
Lee, T. R., and Ueng, J. H. (1999). A study of vehicle routing problems with load‐balancing. International Journal of Physical Distribution & Logistics Management, Vol. 29(10), pp. 646-657.
Majidi, S., Hosseini-Motlagh, S. M., Yaghoubi, S., and Jokar, A. (2017). Fuzzy green vehicle routing problem with simultaneous pickup–delivery and time windows. RAIRO-Operations Research, Vol. 51(4), pp. 1151-1176.
Mavrotas, G. (2009). Effective implementation of the ε-constraint method in multi-objective mathematical programming problems. Applied mathematics and computation, Vol. 213(2), pp. 455-465.
Mavrotas, G., and Florios, K. (2013). An improved version of the augmented ε-constraint method (AUGMECON2) for finding the exact pareto set in multi-objective integer programming problems. Applied Mathematics and Computation, Vol. 219(18), pp. 9652-9669.
Molina, J. C., Salmeron, J. L., and Eguia, I. (2020). An ACS-based Memetic algorithm for the Heterogeneous Vehicle Routing Problem with time windows. Expert Systems with Applications, Vol. 157, pp. 113379.
Rabbani, M., Mokhtarzadeh, M., and Farrokhi-Asl, H. (2018). A New Mathematical Model for Designing a Municipal Solid Waste System Considering Environmentally Issues. International Journal of Supply and Operations Management, Vol. 5(3), pp. 234-255.
Rabbani, M., Ramezankhani, M. J., Farrokhi-Asl, H., and Farshbaf-Geranmayeh, A. (2015). Vehicle routing with time windows and customer selection for perishable goods. International Journal of Supply and Operations Management, Vol. 2(2), pp. 700-719.
Capacitated Windy Rural Postman Problem with several vehicles: A hybrid multi-objective simulated annealing algorithm
Rabbouch, B., Saâdaoui, F., and Mraihi, R. (2020). Empirical-type simulated annealing for solving the capacitated vehicle routing problem. Journal of Experimental & Theoretical Artificial Intelligence, Vol. 32(3), pp. 437-452.
Tirkolaee, E. B., Hadian, S., Weber, G. W., and Mahdavi, I. (2020). A robust green traffic‐based routing problem for perishable products distribution. Computational Intelligence, Vol. 36(1), pp. 80-101.
Wang, G., and Bian, W. (2016, July). Vehicle routing problem with simultaneous delivery and pick-up under different weights. In 2016 International Conference on Logistics, Informatics and Service Sciences (LISS) (pp. 1-4). IEEE.
Xiao, Y., Zuo, X., Kaku, I., Zhou, S., and Pan, X. (2019). Development of energy consumption optimization model for the electric vehicle routing problem with time windows. Journal of Cleaner Production, Vol. 225, pp. 647-663.
Yoon, K. P., and Hwang, C. L. (1995). Multiple attribute decision making: an introduction (Vol. 104). Sage publications.
International Journal of Supply and Operations Management
Volume 8, Issue 3
August 2021
Pages 347-369

Files

Share

How to cite

Statistics