A multi-objective memetic algorithm for risk minimizing vehicle routing problem and scheduling problem

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Iran University of Science and Technology, Iran, 16846-13114

2 School of Mathematical Science, University Sains Malaysia, 11800 Penang, Malaysia

Abstract

In this paper, a new approach to risk minimizing vehicle routing and scheduling problem is presented. Forwarding agents or companies have two main concerns for the collection of high-risk commodities like cash or valuable commodities between the central depot and the customers: one; because of the high value of the commodities transported, the risk of ambush and robbery are very high. Two; the cost of a security guard that protects the vehicle is high. Therefore, the goals of these companies are to deliver and collect commodities with maximum security and minimum risk. Hence, in this paper, a multi-objective vehicle routing problem with time windows (VRPTW) is proposed to minimize risk and transportation costs. Finally, a memetic algorithm is designed to optimize the proposed model. The proposed algorithm is evaluated and compared with the non-dominated genetic algorithm (NSGAII) using Solomon VRPTW test sets. The results demonstrate that the presented approach is effective for valuables routing problem.

Keywords

References

-Androutsopoulos, Konstantinos N. and Zografos, Konstantinos G. (2012) "A bi-objective time-dependent vehicle routing and scheduling problem for hazardous materials distribution", EURO Journal on Transportation and Logistics, Vol. 1, No.1-2, pp. 157-183.
-Bederina, Hiba and Hifi, Mhand (2018) "A hybrid multi-objective evolutionary optimization approach for the robust vehicle routing problem", Applied Soft Comutng, Vol. 71, pp. 980-993.
-Beheshtinia, Mohammad Ali and Ghazivakili, Niloofar (2018) "Reference group genetic algorithm for flexible job shop scheduling problem with multiple objective functions", Jurnal of Industrial and Systems Engineering, Vol  11, No. 4, pp. 153-169.
-Beheshtinia, Mohammad Ali, Ahmadi, Bahar and Fathi, Masood (2019) "A Genetic Algorithm with Multiple Populations to Reduce Fuel Consumption in Supply Chain", International Journal of Transportation Engineering. Under publication,  doi: 10.22119/IJTE.2019.134126.1410
-Beheshtinia, Mohammad Ali, Ghasemi, Amir and Farokhnia, Moein (2018) "Supply chain scheduling and routing in multi-site manufacturing system (case study: a drug manufacturing company)", Journal of Modelling in Management, Vol.  13, No. 1, pp. 27-49.
-Beheshtinia, Mohammad Ali and Ghasemi, Amir (2018) "A multi-objective and integrated model for supply chain scheduling optimization in a multi-site manufacturing system", Engineering Optimization, Vol.  50, No. 9, pp. 1415-1433.
-Borumand, Ali and Beheshtinia,  Mohammad Ali (2018) "A developed genetic algorithm for solving the multi-objective supply chain scheduling problem",  Kybernetes, Vol. 47, No. 7, pp. 1401-1419.
-Bozkaya, Burcin F., Salman, Sibel and Telciler, Kaan (2017) "An adaptive and diversified vehicle routing approach to reducing the security risk of cash‐in‐transit operations", Networks, Vol. 69, No. 3, pp. 256-269.
-Bula, Gustavo Alfredo, Gonzalez, Fabio Augusto, Prodhon, Caroline, Afsar, H. Murat and Velasco, Nubia Milena (2016) "Mixed Integer Linear Programming Model for Vehicle Routing Problem for Hazardous Materials Transportation" IFAC-PapersOnLine, Vol. 49, No. 12, pp. 538-543.
-Bula, Gustavo Alfredo, Afsar, H. Murat, Gonzalez, Fabio Augusto, Prodhon, Caroline and Velasco, Nubia Milena (2019) "Bi-objective vehicle routing problem for hazardous materials transportation", Journal of Cleaner Production, Vol.  206, pp. 976-986.
-Bula, Gustavo Alfredo, Prodhon, Caroline, Gonzalez, Fabio Augusto, Afsar, H. Murat and Velasco, Nubia Milena (2017) "Variable neighborhood search to solve the vehicle routing problem for hazardous materials transportation", Journal of Hazardous Materials, Vol. 324, pp. 472-480.
-Chen, Yujie, Cowling, Peter, Polack, Fiona, Remde, Stephen and Mourdjis, Philip (2017) "Dynamic optimisation of preventative and corrective maintenance schedules for a large scale urban drainage system", European Journal of Operational Research, Vol. 257, No. 2, pp. 494-510.
-Constantino, Miguel M., Mourão, Cândida and Pinto, Leonor S. (2017) "Dissimilar arc routing problems", Networks, Vol.  70, No. 3, pp. 233-245.
-Deb, Kalyanmoy, Pratap, Amrit and Agarwal, Sameer (2002) "A fast and elitist multiobjective genetic algorithm: NSGA-II",  IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, pp. 182-197.
-Du, Jiaoman, Li, Xiang, Yu, Lean, Dan, Ralescu and Zhou, Jiandong (2017) "Multi-depot vehicle routing problem for hazardous materials transportation: A fuzzy bilevel programming", Information Sciences, Vol. 399, pp. 201-218.
-Fallah-tafti, Alireza, Vahdatzad Mohammad Ali and Sadeghieh, Ahmad (2019) "A comprehensive mathematical model for a location-routing-inventory problem under uncertain demand: a numerical illustration in cash-in-transit sector", International Journal of Engineering, Vol.  32, No. 11, pp. 1634-1642.
-Ghannadpour, Seyed Farid and Zandiyeh, Fatemeh (2019) "A Game Theory Based Vehicle Routing Problem with Risk Minimizing of Valuable Commodity Transportation", (Original paper in Persian) Quarterly Journal of Transportation Engineering, Vol.  11, No. 1, pp. 71-98.
-Ghoseiri, Keivan and Ghannadpour, Seyed Farid (2010) "Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm", Applied Soft Computing, Vol. 10 No.4, pp. 1096-1107.
-Hoogeboom, Maaike and Dullaert, Wout  (2019) "Vehicle routing with arrival time diversification", European Journal of Operational Research, Vol. 275, No. 1, pp. 93-107.
-Hu, Hao, Guo, Sini, Ma, Hongguang, Li, Jian and Li, Xiang (2017) "A Credibilistic Mixed Integer Programming Model for Time-Dependent Hazardous Materials Vehicle Routing Problem", Journal of Uncertain Systems, Vol. 11, No. 3, pp. 163-175.
-Michallet, Julien, Prins, Christian, Amodeo, Lionel, Yalaoui, Farouk and Vitry, Grégoire (2014) "Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services", Computers & Operations Research, Vol. 41, pp. 196-207.
-Moscato, Pablo (1999) "Memetic algorithms: A short introduction", New ideas in optimization, McGraw-Hill Ltd., UK.
-Najian, Mohammad Hossein and Beheshtinia, Mohammad Ali (2019) "Supply Chain Scheduling Using a Transportation System Composed of Vehicle Routing Problem and Cross-Docking Approaches",  International Journal of Transportation Engineering, Vol. 7, No. 1, pp. 1-19.
-Ngueveu, Sandra Ulrich, Prins, Christian and Calvo, Roberto Wolfler (2009) "A hybrid tabu search for the m-peripatetic vehicle routing problem", Matheuristics, Springer, pp. 253-266.
-Ngueveu, Sandra Ulrich, Prins, Christian and Calvo, Roberto Wolfler (2010) "Lower and upper bounds for the m-peripatetic vehicle routing problem", 4OR, Vol. 8, No. 4, pp. 387-406.
-Ngueveu, Sandra Ulrich, Prins, Christian and Calvo, Roberto Wolfler (2013) "New lower bounds and exact method for the m-PVRP", Transportation Science, Vol. 47, No. 1, pp. 38-52.
-Pradhananga, Rojee, Taniguchi, Eiichi, Yamada, Tadashi and Qureshi, Ali Gul (2014) "Bi-objective decision support system for routing and scheduling of hazardous materials", Socio-Economic Planning Sciences, Vol. 48, No. 2, pp. 135-148.
-Rabbani, Masoud, Heidari, Razieh, Farrokhi-Asl, Hamed and Rahimi, Navid (2018) "Using metaheuristic algorithms to solve a multi-objective industrial hazardous waste location-routing problem considering incompatible waste types", Journal of Cleaner Production, Vol. 170, pp. 227-241.
-Rabbani, Masoud, Heidari, Razieh and Yazdanparast, Reza (2019) "A stochastic multi-period industrial hazardous waste location-routing problem: Integrating NSGA-II and Monte Carlo simulation", European Journal of Operational Research, Vol. 272, No. 3, pp. 945-961.
-Radojičić, Nina, Djenić, Aleksandar and Marić, Miroslav (2018) "Fuzzy GRASP with path relinking for the Risk-constrained Cash-in-Transit Vehicle Routing Problem", Applied Soft Computing, Vol. 72, pp. 486-497.
-Radojičić, Nina, Marić, Miroslav and Takači, Aleksandar (2018) "A new fuzzy version of the risk-constrained Cash-in-Transit Vehicle Routing Problem", Information Technology and Control, Vol  47, No. 2, pp. 321-337.
-Rudolph, Günter and Agapie, Alexandru (2000) "Convergence properties of some multi-objective evolutionary algorithms", Proceedings of the 2000 Congress on Evolutionary Computation, CEC00 (Cat. No. 00TH8512), IEEE.
-Solomon, Marius M. and Desrosiers, Jacques (1988) "Survey paper—time window constrained routing and scheduling problems", Transportation Science, Vol.  22, No. 1, pp. 1-13.
-Taguchi, G. and Wu, Y. (1979). Introduction to off-line quality control, Central Japan Quality Control Association.
Taheri, Seyed Mohammad Reza and Beheshtinia, Mohammad Ali (2019) "A genetic algorithm developed for a supply chain scheduling problem", Iranian Journal of Management Studies, Vol. 12, No. 2, pp. 107-132.
-Talarico, Luca, Sörensen, Kenneth and  Springael, Johan (2015) "A biobjective decision model to increase security and reduce travel costs in the cash‐in‐transit sector" International Transactions in Operational Research, Vol. 24, No. 1-2, pp. 59-76.
-Talarico, Luca, Sörensen, Kenneth and  Springael, Johan (2015) "The k-dissimilar vehicle routing problem", European Journal of Operational Research, Vol. 244 No. 1, pp. 129-140.
-Talarico, Luca, Sörensen, Kenneth and  Springael, Johan (2015) "Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem", European Journal of Operational Research, Vol. 244, No. 2, pp. 457-470.
-Talarico, Luca, Springael, Johan, Sörensen, Kenneth and. Talarico, Fabio (2017) "A large neighbourhood metaheuristic for the risk-constrained cash-in-transit vehicle routing problem", Computers & Operations Research, Vol. 78, pp. 547-556.
-Tan, Kay Chen, Lee, Loo Hay, Zhu, Q. L. and Ou, Ke (2001) "Heuristic methods for vehicle routing problem with time windows", Artificial Intelligence in Engineering, Vol. 15, No. 3, pp. 281-295.
-Xu, Guoxun, Li, Yanfeng, Szeto, W. Y. and Li, Jun (2019) "A cash transportation vehicle routing problem with combinations of different cash denominations", International Transactions in Operational Research, Vol. 26, No. 9, pp. 2179-2198.
-Yan, Shangyao, Wang, Sin-Siang and Chang, Yu-Hsuan (2014) "Cash transportation vehicle routing and scheduling under stochastic travel times", Engineering Optimization ,Vol. 46, No. 3, pp. 289-307.
-Yan, Shangyao, Wang, Sin-Siang and Wu,  Ming-Wei (2012) "A model with a solution algorithm for the cash transportation vehicle routing and scheduling problem", Computers & Industrial Engineering, Vol. 63, No. 2, pp.464-473.
-Yuan, Wenyan, Wang, Jian, Li, Jian, Yan, Bailu and Wu, Jun (2018) "Two-stage heuristic algorithm for a new model of hazardous material multi-depot vehicle routing problem", UK Workshop on Computational Intelligence, Springer.
 
 

Files

Share

How to cite

Statistics