Sustainable vehicle-routing problem with time windows by heterogeneous fleet of vehicles and separated compartments: Application in waste collection problem

Document Type : Research Paper

Authors

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

2 School of Industrial Engineering, College of Engineering, University of Tehran

3 School of Industrial Engineering, Iran University of Science & Technology

4 Interchange, University of British Columbia, Vancouver, Canada

Abstract

The purpose of this study is solving a sustainable vehicle routing problem (VRP) which in this problem special features such as mixed close–open VRP, multi-depot VRP and some others which will be discussed in this section are considered for achieving closer to real life applications. Fleets of vehicle studied in this paper are heterogeneous and for each vehicle separated compartments with different capacity for each type of wastes is took into consideration. Vehicles have different limitation on traveling time, different fixed and variable cost and amount of pollutants that is emitted from them. For achieving a sustainable VRP economic, environment and society aspects should considered simultaneously which in this paper objective functions (1) to (3) respectively are about mentioned purposes; first one minimizes the cost of collecting wastes from customer’s location, second one minimizes the pollutants which are emitted from vehicles while they are collecting wastes and finally third one minimizes violation from time limitations which are exist on each customer’s location. A new mathematical mixed integer programming model is developed for solving this problem and problem is solved by CPLEX solver and augmented ɛ-constraint method. Moreover, AHP technique for making decisions is applied in order to help us to choose the best decision. Finally, sensitivity analysis is done on some important parameters.

Keywords


-Alinezhad, H., Yaghoubi, Ù. S., Hoseini Motlagh, S. M. and Allahyari, S. (2018) "An improved particle swarm optimization for a class of capacitated vehicle routing problems", International Journal of Transportation Engineering, Vol. 5, No. 4, pp. 331-347.
-Alumur, S., and Kara, B. Y. (2007). "A new model for the hazardous waste location-routing problem". Computers and Operations Research, Vol. 34, No.5, pp. 1406-1423.
-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, No. 2, pp. 78-92.
-Azi, N., Gendreau, M. and Potvin, J.-Y. (2010) "An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles", European Journal of Operational Research, Vol. 202, No. 3, pp. 756-763.
-Bae, H. and Moon, I. (2016) "Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles", Applied Mathematical Modelling, Vol. 40, No. 13, pp. 6536-6549.
-Baraki, R. R. and Kianfar, F. (2017) "A fuzzy mathematical model for supplier selection and order allocation considering green vehicle routing problem", International Journal of Logistics Systems and Management, Vol. 27, No. 2, pp. 151-163.
-Braaten, S., Gjønnes, O., Hvattum, L. M. and Tirado, G. (2017) "Heuristics for the robust vehicle routing problem with time windows". Expert Systems with Applications, Vol. 77, pp. 136-147.
-Çimen, M. and Soysal, M. (2017) "Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm", Transportation Research Part D: Transport and Environment, Vol. 54, pp. 82-98.
-Cordeau, J.-F. and Maischberger, M. (2012) "A parallel iterated tabu search heuristic for vehicle routing problems", Computers and Operations Research, Vol. 39, No. 9, pp. 2033-2050.
Dantzig, G. B. and Ramser, J. H. (1959) "The truck dispatching problem", Management Science, Vol. 6, No.1, pp. 80-91.
-Desrochers, M. and Laporte, G. (1991) "Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints", Operations Research Letters, Vol. 10, No.1, pp. 27-36.
-Dominguez, O., Juan, A. A., Barrios, B., Faulin, J. and Agustin, A. (2016) "Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet", Annals of Operations Research, Vol. 236, No. 2, pp. 383-404.
-Erdoğan, S. and Miller-Hooks, E. (2012) "A green vehicle routing problem", Transportation Research Part E: Logistics and Transportation Review, Vol. 48, No. 1, pp. 100-114.
-Errico, F., Desaulniers, G., Gendreau, M., Rei, W. and Rousseau, L.-M. (2016) "A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times", European Journal of Operational Research, Vol. 249, No. 1, pp. 55-66.
-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, Preprint, pp.1-39.
-Felipe, Á., Ortuño, M. T., Righini, G. and Tirado, G. (2014) "A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges", Transportation Research Part E: Logistics and Transportation Review, Vol. 71, pp. 111-128.
-Flood, M. M. (1956) "The traveling-salesman problem", Operations Research, Vol. 4, No.1, pp. 61-75.
-Ghannadpour, S. F. and Zarrabi, A. (2017) "The special application of vehicle routing problem with uncertainty travel times: Locomotive routing problem", International Journal of Transportation Engineereing, Vol. 5, No. 2, pp. 119-136.
-Ghatreh Samani, M. and Hosseini-Motlagh, S.-M. (2017) "A hybrid algorithm for a two-echelon location-routing problem with simultaneous pickup and delivery under fuzzy demand", International Journal of Transportation Engineering, Vol. 5, No. 1, pp. 59-85.
-Haimes, Y. Y., Ladson, L. and Wismer, D. A. (1971) "Bi-criterion formulation of problems of integrated system identification and system optimization", IEEE Transactions on Systems Man and Cybernetics, Vol. 3, pp. 296-298.
-Hernandez, F., Feillet, D., Giroudeau, R. and Naud, O. (2016) "Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows", European Journal of Operational Research, Vol. 249, No. 2, pp. 551-559.
-Hiermann, G., Puchinger, J., Ropke, S. and Hartl, R. F. (2016) "The electric fleet size and mix vehicle routing problem with time windows and recharging stations", European Journal of Operational Research, Vol. 252,  No. 3, pp. 995-1018.
-Issabakhsh, M., Hosseini-Motlagh, S.-M., Pishvaee, M.-S. and Saghafi Nia, M. (2018) "A vehicle routing problem for modeling home healthcare: a case study", International Journal of Transportation Engineering, Vol. 5, No. 3, pp. 211-228.
-Jemai, J., Zekri, M. and Mellouli, K. (2012) "An NSGA-II algorithm for the green vehicle routing problem", Paper presented at the European Conference on Evolutionary Computation in Combinatorial Optimization.
-Kara, I., Laporte, G. and Bektas, T. (2004) "A note on the lifted Miller–Tucker–Zemlin subtour elimination constraints for the capacitated vehicle routing problem", European Journal of Operational Research, Vol. 158, No. 3, pp. 793-795.
-Kim, K. C., Sun, J. U. and Lee, S. W. (2013) "A hierarchical approach to vehicles routing and scheduling with sequential services using the genetic algorithm”, International Journal of Industrial Engineering, Vol. 20, No. 1, pp. 91-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, No. 1, pp. 33-51.
-Koç, Ç. and Karaoglan, I. (2016) "The green vehicle routing problem: A heuristic based exact solution approach",  Applied Soft Computing, Vol. 39, pp.154-164.
-Leggieri, V. and Haouari, M. (2017) "A practical solution approach for the green vehicle routing problem", Transportation Research Part E: Logistics and Transportation Review, Vol. 104, pp. 97-112.
-Li, F., Golden, B. and Wasil, E. (2007) "The open vehicle routing problem: Algorithms, large-scale test problems, and computational results", Computers and Operations Research, Vol. 34, No. 10, pp. 2918-2930.
-Liu, R. and Jiang, Z. (2012) "The close–open mixed vehicle routing problem", European Journal of Operational Research, Vol. 220, No. 2, pp. 349-360.
-Mancini, S. (2016) "A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet: formulation and adaptive large neighborhood search based matheuristic",  Transportation Research Part C: Emerging Technologies, Vol. 70, pp. 100-112.
-Marinakis, Y. and Marinaki, M. (2010) "A hybrid genetic–Particle Swarm Optimization Algorithm for the vehicle routing problem",  Expert Systems with Applications, Vol. 37, No. 2, pp. 1446-1455.
-Mavrotas, G. (2009) "Effective implementation of the ε-constraint method in multi-objective mathematical programming problems", Applied Mathematics and Computation, Vol. 213, No. 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, No. 18, pp. 9652-9669.
-Nadizadeh, A. and Kafash, B. (2017) "Fuzzy capacitated location-routing problem with simultaneous pickup and delivery demands", Transportation Letters, The International Journal of Transportation Research, Vol. 11, Issue 1,  pp. 1-19.
-Nikkhah Qamsari, A., Hosseini Motlagh, S. M., and Jokar, A. (2017) "A two-phase hybrid heuristic method for a multi-depot inventory-routing problem", International Journal of Transportation Engineering, Vol. 4, No. 4, pp. 287-304.
-Pecin, D., Contardo, C., Desaulniers, G. and Uchoa, E. (2017) "New enhancements for the exact solution of the vehicle routing problem with time windows", INFORMS Journal on Computing, Vol. 29, No. 3, pp. 489-502.
-Penna, P. H. V., Afsar, H. M., Prins, C. and Prodhon, C. (2016) "A hybrid iterative local search algorithm for the electric fleet size and mix vehicle routing problem with time windows and recharging stations", IFAC-PapersOnLine, Vol. 49, No. 12, pp. 955-960.
-Rabbani, M., Farrokhi-asl, H. and Rafiei, H. (2016) "A hybrid genetic algorithm for waste collection problem by heterogeneous fleet of vehicles with multiple separated compartments",  Journal of Intelligent and Fuzzy Systems, Vol. 30, No. 3, pp. 1817-1830.
-Repoussis, P. P., Tarantilis, C. D., Bräysy, O. and Ioannou, G. (2010) "A hybrid evolution strategy for the open vehicle routing problem", Computers and Operations Research, Vol. 37, No.3, pp. 443-455.
-Saaty, T. L. (1990) "How to make a decision: the analytic hierarchy process", European Journal of Operational Research, Vol. 48, No. 1, pp. 9-26.
-Shimizu, Y. and Sakaguchi, T. (2014) "A hierarchical hybrid meta-heuristic approach to coping with large practical multi-depot VRP", Industrial Engineering and Management Systems, Vol. 13, No.2, pp. 163-171.
 -Subramanian, A., Uchoa, E. and Ochi, L. S. (2013) "A hybrid algorithm for a class of vehicle routing problems", Computers and Operations Research, Vol. 40, No. 10, pp. 2519-2531.
-Vidal, T., Crainic, T. G., Gendreau, M. and Prins, C. (2014) "Implicit depot assignments and rotations in vehicle routing heuristics", European Journal of Operational Research, Vol. 237, No. 1, pp. 15-28.
-Wang, X., Golden, B., Wasil, E. and Zhang, R. (2016) "The min–max split delivery multi-depot vehicle routing problem with minimum service time requirement", Computers and Operations Research, Vol. 71, pp. 110-126.
-Wy, J., and Kim, B.-I. (2013). "A hybrid metaheuristic approach for the rollon–rolloff vehicle routing problem", Computers and Operations Research, Vol. 40, No. 8, pp. 1947-1952.
-Yakıcı, E. (2017) "A heuristic approach for solving a rich min-max vehicle routing problem with mixed fleet and mixed demand",  Computers and Industrial Engineering, Vol. 109, pp. 288-294.