A New Heuristic Algorithm for Multi Vehicle Routing Problem with AND/OR-Type Precedence Constraints and Hard Time Windows

  • Unes Bahalke Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran
  • Nima Hamta Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran
  • Amir Reza Shojaeifard Department of Statistical Sciences, School of Economics and Management, Università di Bologna, Italy
  • Maryam Alimoradi Baumann Bildung und Qualifizierung GMBH, Daten­analyse und Prozess­analyse, Berlin, Germany
  • Samira Rabiee Department of Industrial Engineering, University of Eyvanekey, Eyvanekey, Iran
Keywords: Multi Vehicle Routing Problem, AND/OR precedence constraints, Hard Time Windows, Branch and Search Algorithm

Abstract

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

Download data is not yet available.

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

Published
2022-06-30
How to Cite
Bahalke, U., Hamta, N., Shojaeifard, A. R., Alimoradi, M., & Rabiee, S. (2022). A New Heuristic Algorithm for Multi Vehicle Routing Problem with AND/OR-Type Precedence Constraints and Hard Time Windows. Operational Research in Engineering Sciences: Theory and Applications. https://doi.org/10.31181/oresta300622015b
Section
Articles