A BI-OBJECTIVE COST MINIMIZATION MODEL FOR THE INSULAR TOUR ROUTE PLANNING PROBLEM
Abstract
This article presents a study on the development of a bi-objective cost problem optimization model in planning tourist routes in the island zone. This problem is a new variant of the tour route plan problem. Bi-objective view of two cost components, namely maritime transportation costs and ground transportation costs. Two models were formulated using a mixed integer linear programming approach. The first model was designed to minimize one of the two cost components separately. The second model was bi-objective cost minimization based on the priority weights of the two costs. It was designed to determine minimum transportation costs based on priority weights. Model testing was carried out through numerical experiments on several cases that often occur in industries in Maluku, Indonesia, especially tourism and goods shipping. Each case has variations in the number of islands and nodes. As a result, the model can demonstrate its adaptability to changes in objectives and parameters. For cases that do not have a single solution, an increase in the network structure on the number of islands and nodes will increase the variety of efficient alternative solutions. The set of efficient solutions also shows an inverse relationship between MTC and GTC. The results also show that MTC minimization cannot be used as a reference for TC minimization in cases with many nodes and islands. Efforts to minimize MTC in the island zone impact reducing total costs but do not mean minimizing total costs. In addition, based on the exponential trend line of computing time, the number of nodes has a more significant influence on computing time compared to the number of islands.
Downloads
References
P. Vansteenwegen, W. Souffriau, G. Vanden Berghe, and D. Van Oudheusden, “Iterated local search for the team orienteering problem with time windows,” Comput. Oper. Res., vol. 36, no. 12, pp. 3281–3290, 2009, doi: 10.1016/j.cor.2009.03.008.
D. Gavalas, C. Konstantopoulos, K. Mastakas, and G. Pantziou, “A survey on algorithmic approaches for solving tourist trip design problems,” J. Heuristics, vol. 20, no. 3, pp. 291–328, 2014, doi: 10.1007/s10732-014-9242-5.
P. Vansteenwegen, W. Souffriau, and D. Van Oudheusden, “The orienteering problem: A survey,” European Journal of Operational Research, vol. 209, no. 1. Elsevier B.V., pp. 1–10, 2011, doi: 10.1016/j.ejor.2010.03.045.
G. Laporte, A. Asef-Vaziri, and C. Sriskandarajah, “Some applications of the generalized travelling salesman problem,” J. Oper. Res. Soc., vol. 47, no. 12, pp. 1461–1467, 1996, doi: 10.1057/jors.1996.190.
G. Laporte and U. Palekar, “Some applications of the clustered travelling salesman problem,” J. Oper. Res. Soc., vol. 53, no. 9, pp. 972–976, 2002, doi: 10.1057/palgrave.jors.2601420.
P. C. Pop, “New integer programming formulations of the generalized travelling salesman problem,” Am. J. Appl. Sci., vol. 4, no. 11, pp. 932–937, 2007, doi: 10.3844/ajassp.2007.932.937.
I. Kara, H. Guden, and O. N. Koc, “New formulations for the generalized traveling salesman problem,” in 6th International Conference on Applied Mathematics, 2012, no. March, pp. 60–65.
B. Bhattacharya, A. ´Custi´c, A. Rafiey, A. Rafiey, and V. Sokol, “Approximation Algorithms for Generalized MST and TSP in Grid Clusters,” in Combinatorial Optimization and Applications, vol. 9486, Z. Lu, D. Kim, W. Wu, W. Li, and D.-Z. Du, Eds. Springer Cham, 2015, pp. 110–125.
M. Y. Khachai and E. D. Neznakhina, “Approximation Schemes for the Generalized,” in Proceedings of the Steklov Institute of Mathematics, 2017, vol. 299, no. 3, pp. 97–105, doi: 10.1134/S0081543817090127.
M. Khachay and K. Neznakhina, “Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters,” Ann. Math. Artif. Intell., vol. 88, pp. 53–69, 2020, doi: 10.1007/s10472-019-09626-w.
D. Karapetyan and G. Gutin, “Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem,” Eur. J. Oper. Res., vol. 219, no. 2, pp. 234–251, 2012, doi: 10.1016/j.ejor.2012.01.011.
S. L. Smith and F. Imeson, “GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem,” Comput. Oper. Res., vol. 87, pp. 1–19, 2017, doi: 10.1016/j.cor.2017.05.010.
K. Helsgaun, “Solving the equality generalized traveling salesman problem using the Lin – Kernighan – Helsgaun Algorithm,” Math. Program. Comput., 2015, doi: 10.1007/s12532-015-0080-8.
Z. Ardalan, S. Karimi, O. Poursabzi, and B. Naderi, “A novel imperialist competitive algorithm for generalized traveling salesman problems,” Appl. Soft Comput. J., vol. 26, pp. 546–555, 2015, doi: 10.1016/j.asoc.2014.08.033.
Z. H. Ahmed, “An exact algorithm for the clustered travelling salesman problem,” Opsearch, vol. 50, no. 2, pp. 215–228, 2013, doi: 10.1007/s12597-012-0107-0.
X. Bao, Z. Liu, W. Yu, and G. Li, “A note on approximation algorithms of the clustered traveling salesman problem,” Inf. Process. Lett., vol. 127, pp. 54–57, 2017, doi: 10.1016/j.ipl.2017.07.003.
M. Mestria, “New Hybrid Heuristic Algorithm for the Clustered Traveling Salesman Problem,” Comput. Ind. Eng., vol. 116, no. February, pp. 1–12, 2018, doi: 10.1016/j.cie.2017.12.018.
S. Edelkamp, M. Pomarlan, and E. Plaku, “Multi-Region Inspection by Combining Clustered Traveling Salesman Tours with Sampling-Based Motion Planning,” IEEE Robot. Autom. Lett., vol. 2, no. 2, pp. 428–435, 2017, doi: 10.1109/LRA.2016.2635107.
Z. H. Ahmed, “The Ordered Clustered Travelling Salesman Problem : A Hybrid Genetic Algorithm,” Sci. World J., vol. 2014, p. 13, 2014, doi: http://dx.doi.org/10.1155/2014/258207.
J. Jiang, X. Yao, E. Yang, J. Mehnen, and H. Yu, “An Improved Adaptive Genetic Algorithm for Mobile Robot Path Planning Analogous to the Ordered Clustered TSP,” in 2020 IEEE Congress on Evolutionary Computation (CEC), 2020, pp. 1–8, doi: 10.1109/cec48606.2020.9185672.
P. Baniasadi, M. Foumani, K. Smith-Miles, and V. Ejov, “A transformation technique for the clustered generalized traveling salesman problem with applications to logistics,” Eur. J. Oper. Res., vol. 285, no. 2, pp. 444–457, 2020, doi: 10.1016/j.ejor.2020.01.053.
P. A. Miranda, C. A. Blazquez, R. Vergara, and S. Weitzler, “A novel methodology for designing a household waste collection system for insular zones,” Transp. Res. Part E, vol. 77, pp. 227–247, 2015, doi: 10.1016/j.tre.2015.02.019.
D. S. A. González, E. Olivares-benitez, and P. A. Miranda, “Insular biobjective routing with environmental considerations for a solid waste collection system in Southern Chile,” Adv. Oper. Res., vol. 2017, no. 2, p. Article number 4093689, 2017, doi: 10.1155/2017/4093689.
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,” Eur. J. Oper. Res., 2018, doi: 10.1016/j.ejor.2018.05.009.
M. Ratli, D. Urošević, A. A. El Cadi, J. Brimberg, N. Mladenović, and R. Todosijević, “An efficient heuristic for a hub location routing problem,” Optim. Lett., vol. 16, no. 1, pp. 281–300, 2020, doi: 10.1007/s11590-020-01675-z.
H. Karimi and M. Setak, “A bi-objective incomplete hub location-routing problem with flow shipment scheduling,” Appl. Math. Model., vol. 57, pp. 406–431, 2018, doi: 10.1016/j.apm.2018.01.012.
K. Danach, S. Gelareh, and N. R. Monemi, “The capacitated single - allocation p - hub location routing problem : a Lagrangian relaxation and a hyper heuristic approach,” EURO J. Transp. Logist., 2019, doi: 10.1007/s13676-019-00141-w.
J. R. Montoya-Torres, J. López Franco, S. Nieto Isaza, H. Felizzola Jiménez, and N. Herazo-Padilla, “A literature review on the vehicle routing problem with multiple depots,” Comput. Ind. Eng., vol. 79, pp. 115–129, 2015, doi: 10.1016/j.cie.2014.10.029.
T. R. P. Ramos, M. I. Gomes, and A. P. B. Póvoa, “Multi-depot vehicle routing problem: a comparative study of alternative formulations,” Int. J. Logist. Res. Appl., vol. 23, no. 2, pp. 103–120, 2020, doi: 10.1080/13675567.2019.1630374.
Y. Wang, Q. Li, X. Guan, M. Xu, Y. Liu, and H. Wang, “Two-echelon collaborative multi-depot multi-period vehicle routing problem,” Expert Syst. Appl., vol. 167, p. 114201, 2021, doi: 10.1016/j.eswa.2020.114201.
L. Zhen, C. Ma, K. Wang, L. Xiao, and W. Zhang, “Multi-depot multi-trip vehicle routing problem with time windows and release dates,” Transp. Res. Part E Logist. Transp. Rev., vol. 135, no. January 2019, p. 101866, 2020, doi: 10.1016/j.tre.2020.101866.
T. Bektaş, L. Gouveia, and D. Santos, “Compact formulations for multi-depot routing problems: Theoretical and computational comparisons,” Comput. Oper. Res., vol. 124, 2020, doi: 10.1016/j.cor.2020.105084.
M. T. Afifudin and D. P. Sahar, “An integer programming approach for single truck routing-and-scheduling problems to islands with time-varying schedules,” J. Ind. Eng. Manag., vol. 5, no. 2, pp. 53–61, Nov. 2020, doi: 10.33536/jiem.v5i2.548.
Copyright (c) 2024 Mohammad Thezar Afifudin, Muspida Muspida, Dian Pratiwi Sahar
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
