A genetic algorithm improvement by tour constraint violation penalty discount for maritime cargo delivery
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2023.2.08Keywords:
maritime cargo delivery, tour length, genetic algorithm, tour constraint violation penalty, penalty discountAbstract
The problem of minimizing the cost of maritime cargo delivery is considered. The cost is equivalent to the sum of the tour lengths of feeders used for the delivery. The problem is formulated as a multiple traveling salesman problem. In order to find its solution as the shortest route of the tours of feeders, a genetic algorithm is used where we present two inequalities constraining the tour length of every feeder to lie between the shortest and longest lengths. Apart from the constant tour constraint violation penalty in the genetic algorithm, we suggest a changeable penalty as an exponential function of the algorithm iteration, where we maintain the possibility of the penalty rate to be either increasing or decreasing, whose steepness is controlled by a positive parameter. Our tests show that the changeable penalty algorithm may return shorter routes, although the constant penalty algorithms cannot be neglected. As the longest possible tour of the feeder is shortened, the changeable penalty becomes more useful owing to a penalty discount required either at the beginning or at the end of the algorithm run to improve the selectivity of the best feeder tours. In optimizing maritime cargo delivery, we propose to run the genetic algorithm by the low and constant penalties along with the increasing and decreasing penalties. The solution is the minimal value of the four route lengths. In addition, we recommend that four algorithm versions be initialized by four different pseudorandom number generator states. The expected gain is a few percent, by which the route length is shortened, but it substantially reduces expenses for maritime cargo delivery.
References
T.R. Walker et al., “Chapter 27 — Environmental Effects of Marine Transportation,” in World Seas: an Environmental Evaluation. Cambridge, Massachusetts, USA: Academic Press, 2019, pp. 505–530. Available: https://doi.org/10.1016/B978-0-12-805052-1.00030-9
W. Li, R. Pundt, and E. Miller-Hooks, “An updatable and comprehensive global cargo maritime network and strategic seaborne cargo routing model for global containerized and bulk vessel flow estimation,” Maritime Transport Research, vol. 2, 100038, 2021. Available: https://doi.org/10.1016/j.martra.2021.100038
C. Archetti, L. Peirano, and M. G. Speranza, “Optimization in multimodal freight transportation problems: A Survey,” European Journal of Operational Research, vol. 299, iss. 1, pp. 1–20, 2022. Available: https://doi.org/10.1016/j.ejor.2021.07.031
X. Wu, J. Lu, S. Wu, and X. Zhou, “Synchronizing time-dependent transportation services: Reformulation and solution algorithm using quadratic assignment problem,” Transportation Research Part B: Methodological, vol. 152, pp. 140–179, 2021. Available: https://doi.org/10.1016/j.trb.2021.08.008
P.A. Miranda, C.A. Blazquez, C. Obreque, J. Maturana-Ross, and G. Gutierrez-Jarpa, “The bi-objective insular traveling salesman problem with maritime and ground transportation costs,” European Journal of Operational Research, vol. 271, iss. 3, pp. 1014–1036, 2018. Available: https://doi.org/10.1016/j.ejor.2018.05.009
D.-Z. Du and P.M. Pardalos, Handbook of Combinatorial Optimization. New York, NY, USA: Springer, 1998, 2406 p. Available: https://doi.org/10.1007/978-1-4613-0303-9
A. Hertz and M. Widmer, “Guidelines for the use of meta-heuristics in combinatorial optimization,” European Journal of Operational Research, vol. 151, iss. 2, pp. 247–252, 2003. Available: https://doi.org/10.1016/S0377-2217(02)00823-8
A. Colorni, M. Dorigo, F. Maffioli, V. Maniezzo, G. Righini, and M. Trubian, “Heuristics from nature for hard combinatorial optimization problems,” International Transactions in Operational Research, vol. 3, iss. 1, pp. 1–21, 1996. Available: https://doi.org/10.1016/0969-6016(96)00004-4
L.D. Chambers, The Practical Handbook of Genetic Algorithms. Chapman and Hall/CRC, 2000, 544 p.
R. L. Haupt and S.E. Haupt, Practical Genetic Algorithms. John Wiley & Sons, 2003, 253 p. Available: https://doi.org/10.1002/0471671746
C. Thornton, F. Hutter, H.H. Hoos, and K. Leyton-Brown, “Auto-WEKA: Combined selection and hyperparameter optimization of classification algorithms,” in KDD’13: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 847–855, 2013.
V.V. Romanuke, “Optimal training parameters and hidden layer neurons number of two-layer perceptron for generalized scaled objects classification problem,” Information Technology and Management Science, vol. 18, pp. 42–48, 2015. doi: 10.1515/itms-2015-0007
E. Merhej, S. Schockaert, and M. De Cock, “Repairing inconsistent answer set programs using rules of thumb: A gene regulatory networks case study,” International Journal of Approximate Reasoning, vol. 83, pp. 243–264, 2017. Available: https://doi.org/10.1016/j.ijar.2017.01.012
A. Santini, A. Viana, X. Klimentova, and J.P. Pedroso, “The probabilistic travelling salesman problem with crowdsourcing,” Computers & Operations Research, vol. 142, 105722, 2022. Available: https://doi.org/10.1016/j.cor.2022.105722
A. Király and J. Abonyi, “Redesign of the supply of mobile mechanics based on a novel genetic optimization algorithm using Google Maps API,” Engineering Applications Of Artificial Intelligence, vol. 38, pp. 122–130, 2015. Available: https://doi.org/10.1016/j.engappai.2014.10.015
L. Kota and K. Jarmai, “Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary programming,” Applied Mathematical Modelling, vol. 39, iss. 12, pp. 3410–3433, 2015. Available: https://doi.org/10.1016/j.apm.2014.11.043
V. V. Romanuke, “Job order input for efficient exact minimization of total tardiness in tight-tardy progressive single machine scheduling with idling-free preemptions,” Scientific Papers of O. S. Popov Odessa National Academy of Telecommunications, no. 1, pp. 19–36, 2020. Available: https://doi.org/10.33243/2518-7139-2020-1-1-19-36
