A New Heuristic Algorithm for Multi Vehicle Routing Problem with AND/OR-Type Precedence Constraints and Hard Time Windows
DOI:
https://doi.org/10.31181/oresta300622015bKeywords:
Multi Vehicle Routing Problem, AND/OR precedence constraints, Hard Time Windows, Branch and Search AlgorithmAbstract
In this paper the classic known Multi Vehicle Routing Problem (VRP) is studied where classically several vehicles are set in a central depot, depending on the allocation strategy, each vehicle starts traveling to visit a set of nodes one after another to provide a service of gathering or delivering commodities with the aim of minimizing total traveling distances and costs. In the current paper, this classic problem is extended by new approach of AND/OR precedence constraints (PC) which have not been considered so far in the related literature. Traditionally, PC have been considered in VRPs as the 'AND' type, where the immediate successor of a node cannot be visited until its predecessor nodes have reached their end of services. However by additional OR-type precedence constraints, there are some interconnected nodes through the concept of OR, therein no mandatory need to visit all predecessors of a successor node is acquired before it can be met, and only finishing a part of them can let to that particular node to get visited. This fact is widely observed in pickup and routing and distribution real cases where requisites for some specific products can be fulfilled via various potential suppliers. Implementation of this type of PC graph in VRP is considered as the first introduction and application in the category of this problem. So, initially, the problem is mathematically formulated, then, due to problem’s NP-hard complexity and allocation-routing characteristics, a decomposition-based technique is utilized to solve the problem. The procedure is based on recently enhanced Benders’ decomposition approach named as Branch and Search Algorithm, partitioning the original main problem into allocation and routing parts. Unlike the previous version of Benders algorithm, logic based, this newly promoted method acts in a way that at the allocation level, it generates partition of nodes with feasible solutions in lower routing level. The routing part itself has been enhanced by heuristics to cover AND/OR PC graphs. Furthermore, the efficiency of the proposed solution procedure is tested and verified by running on several generated problems in different sizes and in the larger scale it is implemented on the real case of a distribution company in Iran.
Downloads
References
Alvarez, A., & Munari, P. (2017). An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen. Computers & Operations Research, 83, 1-12. https://doi.org/10.1016/j.cor.2017.02.001
Anggodo, Y. P., Ariyani, A. K., Ardi, M. K., & Mahmudy, W. F. (2017). Optimization of multi-trip vehicle routing problem with time windows using genetic algorithm. Journal of Environmental Engineering and Sustainable Technology, 3(2), 92-97. https://doi.org/10.21776/ub.jeest.2017.003.02.4
Ariyani, A. K., Mahmudy, W. F., & 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), 8(6). http://doi.org/10.11591/ijece.v8i6.pp4713-4723
Azi, N., Gendreau, M., & 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, 202(3), 756-763. https://doi.org/10.1016/j.ejor.2009.06.034
Bae, H., & Moon, I. (2016). Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles. Applied Mathematical Modelling, 40(13-14), 6536-6549. https://doi.org/10.1016/j.apm.2016.01.059
Cetin S., Gencer C. (2010). Vehicle routing problems with hard time windows and simultaneous pickup and delivery: a mathematical model. J. Fac. Eng. Arch. Gazi Univ. 25(3): 579–585]. https://doi.org/10.4236/jss.2015.33008
Chen, C. P. (1989, November). Precedence knowledge acquisition for generating robot assembly sequences. In Conference Proceedings., IEEE International Conference on Systems, Man and Cybernetics (pp.71-76).IEEE. https://doi.org/10.1109/icsmc.1989.71255
Chen, C. P. (1990, January). Planning optimal precedence-constraint robot assembly sequences problem with neural computation. In Applications of Artificial Intelligence VIII (Vol. 1293, pp. 320-331). International Society for Optics and Photonics. https://doi.org/10.1117/12.21080
Chen, C. P. (1990, June). Neural computation for planning AND/OR precedence-constraint robot assembly sequences. In 1990 IJCNN International Joint Conference on Neural Networks (pp. 127-142). IEEE. https://doi.org/10.1109/ijcnn.1990.137557
Chiang, T. C., & Hsu, W. H. (2014). A knowledge-based evolutionary algorithm for the multi objective vehicle routing problem with time windows. Computers & Operations Research, 45, 25-37. https://doi.org/10.1016/j.cor.2013.11.014
Chunyu, R., & Xiaobo, W. (2010, October). Research on multi-vehicle and multi-depot vehicle routing problem with time windows for electronic commerce. In 2010 international conference on artificial intelligence and computational intelligence (Vol. 1, pp. 552-555). IEEE. https://doi.org/10.1109/aici.2010.121
Coelho, V. N., Grasas, A., Ramalhinho, H., Coelho, I. M., Souza, M. J., & Cruz, R. C. (2016). An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints. European Journal of Operational Research, 250(2), 367-376. https://doi.org/10.1016/j.ejor.2015.09.047
Cömert, S. E., YAZGAN, H. R., Sertvuran, I., & ŞENGÜL, H. (2017). A new approach for solution of vehicle routing problem with hard time window: an application in a supermarket chain. Sādhanā, 42(12), 2067-2080. https://doi.org/10.1007/s12046-017-0754-1
Dabia, S., Ropke, S., Van Woensel, T., & De Kok, T. (2013). Branch and price for the time-dependent vehicle routing problem with time windows. Transportation science, 47(3), 380-396. https://doi.org/10.1287/trsc.1120.0445
De Fazio, T., & Whitney, D. (1987). Simplified generation of all mechanical assembly sequences. IEEE Journal on Robotics and Automation, 3(6), 640-658. https://doi.org/10.1109/jra.1987.1087132
Dong, W., Zhou, K., Qi, H., He, C., & Zhang, J. (2018). A tissue P system based evolutionary algorithm for multi-objective VRPTW. Swarm and evolutionary computation, 39, 310-322. https://doi.org/10.1016/j.swevo.2017.11.001
Errico, F., Desaulniers, G., Gendreau, M., Rei, W., & Rousseau, L. M. (2018). The vehicle routing problem with hard time windows and stochastic service times. EURO Journal on Transportation and Logistics, 7(3), 223-251. https://doi.org/10.1007/s13676-016-0101-4
Ghoseiri, K., & Ghannadpour, S. F. (2010). Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm. Applied Soft Computing, 10(4), 1096-1107. https://doi.org/10.1016/j.asoc.2010.04.001
Gillies, D. W., & Liu, J. S. (1990, December). Scheduling tasks with and/or precedence constraints. In Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing 1990 (pp. 394-401). IEEE. https://doi.org/10.1109/spdp.1990.143572
Gillies, D. W., & Liu, J. W. S. (1995). Scheduling tasks with AND/OR precedence constraints. SIAM Journal on Computing, 24(4), 797-810. https://doi.org/10.1137/s0097539791218664
Goel, R., & Maini, R. (2021). Improved multi-ant-colony algorithm for solving multi-objective vehicle routing problems. Scientia Iranica, 28(6), 3412-3428. https://doi.org/10.24200/sci.2019.51899.2414
Golden, B., Assad, A., Levy, L., & Gheysens, F. (1984). The fleet size and mix vehicle routing problem. Computers & Operations Research, 11(1), 49-66. https://doi.org/10.1016/0305-0548(84)90007-8
Golden, Bruce L., Subramanian Raghavan, Edward A. Wasil, eds (2008). The vehicle routing problem: latest advances and new challenges. Vol. 43. Springer Science & Business Media. https://doi.org/10.1007/978-0-387-77778-8
Gordon, V., Potapneva, E., & Werner, F. (1997). Single machine scheduling with deadlines, release and due dates. Optimization, 42(3), 219-244. https://doi.org/10.1080/02331939708844360
Hernandez, F., Feillet, D., Giroudeau, R., & Naud, O. (2014). A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration. 4or, 12(3), 235-259. https://doi.org/10.1007/s10288-013-0238-z
Hernandez, F., Feillet, D., Giroudeau, R., & 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, 249(2), 551-559. https://doi.org/10.1016/j.ejor.2015.08.040
Hu, C., Lu, J., Liu, X., & Zhang, G. (2018). Robust vehicle routing problem with hard time windows under demand and travel time uncertainty. Computers & Operations Research, 94, 139-153. https://doi.org/10.1016/j.cor.2018.02.006
Jiang, J., Ng, K. M., Poh, K. L., & Teo, K. M. (2014). Vehicle routing problem with a heterogeneous fleet and time windows. Expert Systems with Applications, 41(8), 3748-3760. https://doi.org/10.1016/j.eswa.2013.11.029
Koç, Ç., Bektaş, T., Jabali, O., & Laporte, G. (2015). A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows. Computers & Operations Research, 64, 11-27. https://doi.org/10.1016/j.cor.2015.05.004
Kumar, S. N. & Panneerselvam, R. (2015). A time-dependent vehicle routing problem with time windows for e-commerce supplier site pickups using genetic algorithm. Intelligent Information Management, 7, 181-194. https://doi.org/10.4236/iim.2015.74015
Li & Lim (2008) benchmark web page www.sintef.no/projectweb/top/pdptw/li-lim-benchmark.
Le Bouthillier, A., & Crainic, T. G. (2005). A cooperative parallel meta-heuristic for the vehicle routing problem with time windows. Computers & Operations Research, 32(7), 1685-1708. https://doi.org/10.1016/j.cor.2003.11.023
Lee, S., Moon, I., Bae, H., & Kim, J. (2012). Flexible job-shop scheduling problems with ‘AND’/‘OR’precedence constraints. International Journal of Production Research, 50(7), 1979-2001. https://doi.org/10.1080/00207543.2011.561375
Mingozzi, A., Roberti, R., & Toth, P. (2013). An exact algorithm for the multitrip vehicle routing problem. INFORMS Journal on Computing, 25(2), 193-207. https://doi.org/10.1287/ijoc.1110.0495
Miranda, D. M., & Conceição, S. V. (2016). The vehicle routing problem with hard time windows and stochastic travel and service time. Expert Systems with Applications, 64, 104-116. https://doi.org/10.1016/j.eswa.2016.07.022
Möhring R.H., Skutella M., Stork F. (2004). Forcing relations for AND/OR precedence constraints. SIAM Journal on computing. http://dx.doi.org/10.14279/depositonce-14708
Möhring, R. H., Skutella, M., & Stork, F. (2004). Scheduling with AND/OR precedence constraints. SIAM Journal on Computing, 33(2), 393-415. https://doi.org/10.1137/s009753970037727x
Nazif H. and Lee L. S. (2010). Optimized crossover genetic algorithm for vehicle routing problem with time windows. American Journal of Applied Sciences, 7(1), 95-101. https://doi.org/10.3844/ajassp.2010.95.101
Parragh, S. N., & Cordeau, J. F. (2017). Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows. Computers & Operations Research, 83, 28-44. https://doi.org/10.1016/j.cor.2017.01.020
Pierre, D. M., & Zakaria, N. (2017). Stochastic partially optimized cyclic shift crossover for multi-objective genetic algorithms for the vehicle routing problem with time-windows. Applied Soft Computing, 52, 863-876. https://doi.org/10.1016/j.asoc.2016.09.039
Qi, X., Yu, G., & Bard, J. F. (2002). Single machine scheduling with assignable due dates. Discrete Applied Mathematics, 122(1-3), 211-233. https://doi.org/10.1016/s0166-218x(01)00316-x
Toth, P., & Vigo, D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problem,Discrete Applied Mathematics, 123( 1–3), 487-512 . https://doi.org/10.1016/S0166-218X(01)00351-1
Wang, Y., Ma, X., Xu, M., Liu, Y., & Wang, Y. (2015). Two-echelon logistics distribution region partitioning problem based on a hybrid particle swarm optimization–genetic algorithm. Expert Systems with Applications, 42(12), 5019-5031. https://doi.org/10.1016/j.eswa.2015.02.058
Zhang, D., Cai, S., Ye, F., Si, Y. W., & Nguyen, T. T. (2017). A hybrid algorithm for a vehicle routing problem with realistic constraints. Information Sciences, 394, 167-182. https://doi.org/10.1016/j.ins.2017.02.028
