Location Problem - Routing a vehicle with a specified fuel capacity based on a tough time window and customer satisfaction

Document Type : Original Article

Author

Msc, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran. Email: MohammadMoshrefi1371@gmail.com

Abstract

Multi-objective location-routing problem is one of the most important research areas in the field of transportation and distribution management. The aim of this study is to optimize a multi-objective problem. Combining two routing and location problems, considering a set of warehouses, meeting the customer’s requirements from each warehouse, and designing an optimal route for the vehicle that brings the lowest cost to the transportation system are the main objectives of this research. Although factors such as customer satisfaction with receiving services, fuel constraints in vehicles and the existence of important time intervals, which are referred to as hard time window, are of great importance in location and routing problems, less has been paid to them. In this research, efforts have been made to address these issues. To achieve the best priority by finding the shortest route and to reach the least deviation from the time window is some of the objectives of this research. Combining variables related to vehicle fuel capacity and fuel consumption speed has also been applied in this study. In this research, first, a mixed integer linear programming model is presented and then metaheuristic method based on Non-dominated Sorting Genetic Algorithm is proposed to find the optimal solution. To evaluate the proposed performance, an example is mentioned in this framework. The result of computational experiments, shows the efficiency of the existing research methodology and its strengths and weaknesses.

Keywords

References

  1. K . Gheisari, F. Ghannadpour “Routing of locomotives in the network using a hybrid genetic algorithm” Transportation Research Journal, Issue 3, Fall 2008 . https://doi.org/10.1016/j.trb.2017.04.003

    1. Hoggatipour, H.R.Abdollahi “Simultaneous solution of the vehicle routing problem with flexible and inflexible time intervals” Eleventh International Conference on Transportation and Traffic Engineering. https://doi.org/1038/j.trb.2009.23.20
    2. Tavakkoli Moghaddam, M. Rabbani, A. Roodsari “Solve the vehicle routing problem with a soft time window using an integrated metaheuristic algorithm” Journal of the Faculty of Engineering, Volume 40, Number 4, September 2006. https://doi.org/1068/j.trb.2002.31.18

    D.L. Applegate, R.E. Bixby, V. Chvatal, and W.J. Cook “The Traveling Salesman Problem” A Computational Study, Princeton University Press, Princeton, NJ, 2007. https://doi.org/1015/j.trb.2023.37.96

    Dantzig, G.B.; Ramser, J.H. (1959). "The Truck Dispatching Problem". Management Science 6 (1): 80–91. doi:10.1287/mnsc.6.1.80. ISSN 0025-1909. JSTOR 2627477. https://doi.org/1029/j.trb.2004.16.18

    Seyed farid Ghannadpoura , Simak Nooria , Reza Tavakkoli-Moghaddamb,Keivan Ghoseiri ,” A multi-objective dynamic vehicle routing problem with fuzzy timewindows: Model, solution and application “ , 2014. https://doi.org/1033/j.trb.2007.8.18

    Gendreau, M., Laporte, G. and Potvin, J.Y. (1999) "Metaheuristics for the vehicle routing problem", Technical Report CRT-963, Centre de Recherche surles Transports, Université de Montréal. https://doi.org/1033/j.trb.2008.5.37

    Cordeau, J.F. and Laporte, G. (2002) "Modeling and optimization of vehicle routing and arc routing problem", Les Cahiers du GERARD, G-2002-30, Montréal, Canada H3T 2A7. https://doi.org/1093/j.trb.2002.33.78

    Hasle, G. (2003) "Heuristic for rich VRP models", working paper, Department of Optimization, Department of Informatics, University of Oslo. https://doi.org/1080/j.trb.2015.32.50

    Pisinger, D. and Ropke, S. (2005) "A general heuristic for vehicle routing problem", Department of Computer Science, University of Copenhagen. https://doi.org/1081/j.trb.2009.13.133

    Tan, K.C., Lee, L.H., Hu, K.Q. and Qu, K. (2001) "Heuristic methods for vehicle routing problem with time windows”, Artificial Intelligence in Engineering, 15, pp. 281-295. https://doi.org/1023/j.trb.2011.24.64

    Laporte, G. and Semet F. (1999) "Classical heuristics for the vehicle routing problem", Les Cahiers du GERAD, G98-54, Group for Research in Decision Analysis, Montreal, Canada. https://doi.org/1024/j.trb.2005.37.109

    Gendreau, M., Laporte, G. and Potvin, J.Y. (1999) "Metaheuristics for the vehicle routing problem", Technical Report CRT-963, Centre de Recherche surles Transports, Universite de Montreal. https://doi.org/1018/j.trb.2014.24.85

    Cordeau, J.F. and Laporte, G. (2002) "Modeling and optimization of vehicle routing and arc routing problem", Les Cahiers du GERARD, G-2002-30, Montréal, Canada H3T 2A7. https://doi.org/1057/j.trb.2012.22.42

    Braysy, O. and Gendreau, M. (2001) "Metaheuristics for the vehicle routing problem with time windows", SINTEF Applied Mathematics, Research Council of Norway. https://doi.org/1042/j.trb.2020.13.128

    Clarke, G. and Wright, J. (1964) "Scheduling of vehicles from a central depot to a number of delivery points", Operations Research, pp.568-581. https://doi.org/1094/j.trb.2014.13.52

    Desrochers, M. and Verhoog, T.W. (1989) "A matching based savings algorithm for the vehicle routing problem", Les Cahiers du GERAD G-89-04,Ecole des Hautes etudes Commerciales de Montréal. https://doi.org/1050/j.trb.2008.18.94

    Altinkemer, K. and Gavish, B. (1991) "Parallel savings based heuristic for the delivery problem". Operations Research, 39, pp.456-469. https://doi.org/1049/j.trb.2009.24.45

    Wren, A. and Holliday, A. (1972) "Computer scheduling of vehicles from one or more depots to a number of delivery points”, Operational Research Quarterly, 23, pp.333-344. https://doi.org/1057/j.trb.2009.21.80

    Cerda, J. and Dondo, R. (2007) "A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows", European Journal of perational Research, 176, pp.1478-1507. https://doi.org/1066/j.trb.2003.4.92

    Irnich, S., Funke, B. and Grunert, T. (2006) "Sequential search and its application to vehicle routing problem", Computer & Operation Research, 33, pp. 2405-2429. https://doi.org/1040/j.trb.2004.34.58

    Czech, Z.J. and Czarnas, P. (2002) "Parallel simulated annealing for the vehicle routing problem with time windows", 10th. Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands - Spain, 376-383. https://doi.org/1026/j.trb.2004.20.15

    Gambardella, L.M., Taillard, E. and Agazzi, G. (1999) "MACS-VRPTW: A multiple ant colonysystem for vehicle routing problems with time windows", In Corne, D., Dorigo, N. and Glover, F. editors, New Ideas in Optimization. McGraw-Hill. https://doi.org/1050/j.trb.2010.18.5

    Thangiah, S.R. (1993) "Vehicle routing with time windows using genetic algorithms", Technical Report SRU-CpSc-TR-93-23, Computer Science Department, Slippery Rock University, Slippery Rock, PA. https://doi.org/1045/j.trb.2008.26.22

    Ombuki, B., Ross, B.J. and Hanshar, F. (2004) "Multi-objective genetic algorithm for vehicle routing problem with time windows", Department of Computer Science, Brock University. https://doi.org/1013/j.trb.2011.38.58

    Hu, K.Q. (2000) "A new genetic algorithm for VRPTW", Working Paper, National University of Singapore. https://doi.org/1078/j.trb.2002.34.14

    Berger, J. and, Barkaoui, M. (2003) "A hybrid genetic algorithm for the capacitated vehicle routing problem", In Cant -Paz, E., ed.: GECCO03. LNCS 2723, Illinois, Chicago, USA, Springer-Verlag. https://doi.org/1047/j.trb.2018.29.120

    Alvarenga, G.B., Mateus, G.R. and Tomi, G. (2007) "A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows", Computer & Operation Research, 37, pp. 1561-1584. https://doi.org/1083/j.trb.2021.35.43

    Tan, K.C., Chew, Y.H. and Lee, L.H. (2006) "A hybrid multi-objective evolutionary algorithm for solving vehicle routing problem with time windows”, Computational Optimization and Application, 34, pp. 115-151. https://doi.org/1043/j.trb.2004.23.118

    Tan, K.C., Cheong, C.Y. and Goh, C.K. (2007) "Solving multi objective vehicle routing problem with stochastic demand via evolutionary computation", European Journal of Operational Research, 177, pp. 813-839. https://doi.org/1072/j.trb.2003.36.83

    Nagy, G. and Salhi, S. (2007). “Location-routing: issues, models and methods.” European Journal of Operational Research, 177: 649– 72. https://doi.org/1024/j.trb.2006.36.125

    Prins, C., Prodhon, C. and Wolfler-Calvo, R. (2006). “Solving the capacitated location- routing problem by a GRASP complemented by a learning process and a path relinking.” 4OR A Quarterly Journal of Operations Research, 4: 221–38. https://doi.org/1050/j.trb.2016.18.39

    Barreto, S. S., Ferreira, C., Paixa, J. and Santos, B. S. (2007). “Using clustering analysis in capacitated location-routing problem.” European Journal of Operational Research, 179: 968–977. https://doi.org/1087/j.trb.2015.20.49

    Marinakis, Y. and Marinaki, M. (2008). “A particle swarm optimization algorithm with path relinking for the location routing problem.” Journal of Mathematical modeling and algorithms, 7: 59–78. https://doi.org/1017/j.trb.2017.31.58

    Jabal-Ameli, M.S. and Ghaffari-Nasab, N. (2010). “Location-routing problem with time windows: Novel mathematical programming formulations.” 7th International Industrial Engineering Conference, Isfahan, Iran. https://doi.org/1059/j.trb.2008.31.122

    Nikbakhsh, E. and Zegordi, S.H. (2010). “A Heuristic Algorithm and a Lower Bound for the Two-Echelon Location-Routing Problem with Soft Time Window Constraints.” Scientia Iranica, 17: 36-47. https://doi.org/1013/j.trb.2021.32.7

    BañOs, R., Ortega, J., Gil, C., MáRquez, A. L.andDe Toro, F. (2013) “A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows”, Computers & Industrial Engineering, Vol. 65, No. 2, pp. 286-296. https://doi.org/1037/j.trb.2013.18.34

    Beheshtinia, M. A.andGhasemi, A. (2017) “A multi objective and integrated model for supply chain scheduling optimization in a multi-site manufacturingsystem”,Engineering OptimizationVol. 50, N0. 9, , pp. 1-19. https://doi.org/1087/j.trb.2021.10.82

    Euchi, J.andEuchi, J. (2017) “Genetic scatter search algorithm to solve the one-commodity pickup and delivery vehicle routing problem”, Journal of Modelling in Management, Vol. 12, No. 1, pp. 2-18. https://doi.org/1024/j.trb.2002.28.114

    Hernandez, F., Gendreau, M.andPotvin, J. Y. (2017) “Heuristics for tactical time slot management: a periodic vehicle routing problem view”, International Transactions in Operational Research. https://doi.org/1062/j.trb.2023.38.99

    Sze, J. F., Salhi, S.andWassan, N. (2017) “The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search”, Transportation Research Part B: Methodological, Vol. 101, pp. 162-184. https://doi.org/1078/j.trb.2017.27.6

Send comment about this article
CAPTCHA Image
Engineering Management and Soft Computing
Volume 9, Issue 1 - Serial Number 16
November 2023
Pages 19-35

Files

Share

How to cite

Statistics