[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Exact and Heuristic Lexicographic Methods for the Fuzzy Traveling Salesman Problem

  • Conference paper
  • First Online:
Hybrid Artificial Intelligent Systems (HAIS 2023)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 14001))

Included in the following conference series:

  • 822 Accesses

Abstract

The traveling salesman problem is notorious not only for its significance in theoretical computer science but also for the vast number of real-world problems it is involved in. In this paper, we propose a branch and bound method and a 2-opt method for solving traveling salesman problems, in situations where pairwise distances, costs, or travel times between cities are not known precisely and are modeled with triangular fuzzy numbers. A lexicographic criterion is used for ranking such fuzzy numbers. This approach is shown to produce intuitively better results than those obtained by using linear ranking functions. Computer codes are provided for reproducibility and practical applications. This research also provides a starting point for the extension to the fuzzy environment of other methods for solving classical (non-fuzzy) traveling salesman problems.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 67.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 84.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Download available from GitHub https://github.com/bpcanedo/ftsp.git.

  2. 2.

    The cost matrix is available at https://github.com/bpcanedo/ftsp.git.

  3. 3.

    Computer codes to replicate these results are available at https://github.com/bpcanedo/ftsp.git.

References

  1. Aćimović, S., Mijušković, V.M., Todorović, I., Spasenić, A.T.: The role and importance of transport within the tourism supply chain. In: Karanovic, G., Polychronidou, P., Karasavvoglou, A., Maskarin Ribaric, H. (eds.) Tourism Management and Sustainable Development. CE, pp. 93–106. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-74632-2_7

    Chapter  Google Scholar 

  2. Balas, E., Toth, P.: Branch and bound methods. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, pp. 361–401. Wiley, Chichester (1985)

    Google Scholar 

  3. Baykasoğlu, A., Subulan, K., Karaslan, F.S.: A new fuzzy linear assignment method for multi-attribute decision making with an application to spare parts inventory classification. Appl. Soft Comput. 42, 1–17 (2016). https://doi.org/10.1016/j.asoc.2016.01.031

    Article  Google Scholar 

  4. Botzheim, J., Földesi, P., Kóczy, L.T.: Solution for fuzzy road transport traveling salesman problem using eugenic bacterial memetic algorithm. In: IFSA/EUSFLAT Conference, pp. 1667–1672 (2009)

    Google Scholar 

  5. Burkard, R.E., Hahn, W., Zimmermann, U.: An algebraic approach to assignment problems. Math. Program. 12, 318–327 (1977). https://doi.org/10.1007/BF01593800

    Article  MathSciNet  Google Scholar 

  6. Changdar, C., Pal, R.K., Mahapatra, G.S.: A genetic ant colony optimization based algorithm for solid multiple travelling salesmen problem in fuzzy rough environment. Soft. Comput. 21(16), 4661–4675 (2016). https://doi.org/10.1007/s00500-016-2075-4

    Article  Google Scholar 

  7. Eren, E., Rıfat Tuzkaya, U.: Safe distance-based vehicle routing problem: medical waste collection case study in COVID-19 pandemic. Comput. Industr. Eng. 157, 107328 (2021). https://doi.org/10.1016/j.cie.2021.107328

    Article  Google Scholar 

  8. Hanss, M.: Applied Fuzzy Arithmetic. Springer, Heidelberg (2005). https://doi.org/10.1007/b138914

  9. Herrera, F., Verdegay, J.: Three models of fuzzy integer linear programming. Eur. J. Oper. Res. 83(3), 581–593 (1995). https://doi.org/10.1016/0377-2217(93)E0338-X

    Article  Google Scholar 

  10. Kuchta, D.: Fuzzy stage dependent travelling salesman problem with networks as nodes. In: Borzemski, L., Grzech, A., Świątek, J., Wilimowska, Z. (eds.) ISAT 2015, Part I. AISC, vol. 429, pp. 89–100. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-28555-9_8

    Chapter  Google Scholar 

  11. Kumar, A., Gupta, A.: Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions. Fuzzy Inf. Eng. 3(1), 3–21 (2011). https://doi.org/10.1007/s12543-011-0062-0

    Article  MathSciNet  Google Scholar 

  12. Păcurar, C.M., Albu, R.G., Păcurar, V.D.: Tourist route optimization in the context of COVID-19 pandemic. Sustainability 13(10), 5492 (2021). https://doi.org/10.3390/su13105492

    Article  Google Scholar 

  13. Pérez-Cañedo, B., Concepción-Morales, E.R.: A lexicographic approach to fuzzy linear assignment problems with different types of fuzzy numbers. Internat. J. Uncertain. Fuzziness Knowl.-Based Syst. 28(03), 421–441 (2020). https://doi.org/10.1142/S0218488520500178

    Article  MathSciNet  Google Scholar 

  14. Pérez-Cañedo, B., Concepción-Morales, E.R.: A method to find the unique optimal fuzzy value of fully fuzzy linear programming problems with inequality constraints having unrestricted L-R fuzzy parameters and decision variables. Expert Syst. Appl. 123, 256–269 (2019). https://doi.org/10.1016/j.eswa.2019.01.041

    Article  Google Scholar 

  15. Pérez-Cañedo, B., Verdegay, J.L., Concepción-Morales, E.R., Rosete, A.: Lexicographic methods for fuzzy linear programming. Mathematics 8(9) (2020). https://doi.org/10.3390/math8091540

  16. Pop, P.C.: The generalized traveling salesman problem (GTSP). In: Generalized Network Design Problems, pp. 60–99. De Gruyter (2012). https://doi.org/10.1515/9783110267686.60

  17. Punnen, A.P.: The traveling salesman problem: applications, formulations and variations. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and Its Variations. Combinatorial Optimization, vol. 12, pp. 1–28. Springer, Boston (2007). https://doi.org/10.1007/0-306-48213-4_1

    Chapter  Google Scholar 

  18. Rego, C., Glover, F.: Local search and metaheuristics. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and Its Variations. Combinatorial Optimization, vol. 12, pp. 309–368. Springer, Boston (2007). https://doi.org/10.1007/0-306-48213-4_8

    Chapter  Google Scholar 

  19. Verdegay, J.L., Brito, J., Cruz, C. (eds.): Computational Intelligence Methodologies Applied to Sustainable Development Goals. Studies in Computational Intelligence, Springer, Cham (2022). https://doi.org/10.1007/978-3-030-97344-5

    Book  Google Scholar 

  20. Zadeh, L.: Fuzzy sets. Inf. Control 8(3), 338–353 (1965). https://doi.org/10.1016/S0019-9958(65)90241-X

    Article  Google Scholar 

Download references

Acknowledgements

The authors acknowledge support from the projects PID2020-112754GB-I00, MCIN/AEI /10.13039/501100011033 and FEDER/Junta de Andalucía-Consejería de Transformación Económica, Industria, Conocimiento y Universidades/Proyecto (B-TIC-640-UGR20).

Author information

Authors and Affiliations

  1. Grupo de Investigación en Modelos de Decisión y Optimización, Departamento de Ciencias de la Computación e Inteligencia Artificial, Universidad de Granada, 18014, Granada, Spain

    Boris Pérez-Cañedo

  2. Department of Mathematics, University of Cienfuegos, 55100, Cienfuegos, Cuba

    Boris Pérez-Cañedo

  3. Departamento de Ciencias de la Computación e Inteligencia Artificial, Universidad de Granada, 18014, Granada, Spain

    Pavel Novoa-Hernández, David A. Pelta & José Luis Verdegay

Authors
  1. Boris Pérez-Cañedo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pavel Novoa-Hernández
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. David A. Pelta
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. José Luis Verdegay
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Boris Pérez-Cañedo .

Editor information

Editors and Affiliations

  1. University of Deusto, Bilbao, Spain

    Pablo García Bringas

  2. University of Leon, León, Spain

    Hilde Pérez García

  3. University of La Rioja, Logroño, La Rioja, Spain

    Francisco Javier Martínez de Pisón

  4. Pablo de Olavide University, Seville, Spain

    Francisco Martínez Álvarez

  5. Pablo de Olavide University, Seville, Spain

    Alicia Troncoso Lora

  6. University of Burgos, Burgos, Spain

    Álvaro Herrero

  7. University of A Coruña, Ferrol - Coruña, Spain

    José Luis Calvo Rolle

  8. University of A Coruña, Ferrol - Coruña, Spain

    Héctor Quintián

  9. University of Salamanca, Salamanca, Spain

    Emilio Corchado

Appendices

A Lexicographic Method for the FLAP

The FLAP can be formulated as the fuzzy integer linear programming problem

$$\begin{aligned} \begin{aligned} \min ~&\sum \limits _{i=1}^n\sum \limits _{j=1}^n\tilde{c}_{ij}\times x_{ij}\\ \text {s.t.}~&\text {constraints}~(2) \;\text {and}\; (3), \end{aligned} \end{aligned}$$
(5)

where the \(x_{ij}\) (\(i,j=1,2,\ldots ,n\)) are binary variables. Definition 1 was used in [13] to transform problem (5) into LLAP (6).

$$\begin{aligned} \begin{aligned} \text {lexmin}~&\sum \limits _{i=1}^n\sum \limits _{j=1}^n c_{ij}x_{ij}\\ \text {s.t.}~&\text {constraints}~(2)\; \text {and}\; (3), \end{aligned} \end{aligned}$$
(6)

where \(c_{ij}=\Big (f_1\left( \tilde{c}_{ij}\right) ,f_2\left( \tilde{c}_{ij}\right) ,f_3\left( \tilde{c}_{ij}\right) \Big )\) (\(i,j=1,2,\ldots ,n\)).

Theorem 2

An optimal solution to LLAP (6) is optimal for FLAP (5).

Proof

See [13].

Burkard et al.’s [5] general algebraic framework can be used to efficiently solve LLAP (6). In their framework, it is assumed that the LAP cost coefficients are elements of a totally ordered commutative semigroup \(\big (H,*,\le \big )\), with internal composition \(*\) and total order relation \(\le \), which fulfills the following properties:

  1. 1.

    \(\forall x,y,z\in H\), \(x\le y\implies x*z\le y*z\) (i.e. \(\le \) is compatible with \(*\)),

  2. 2.

    \(\forall x,y\in H\) with \(x\le y\) \(\exists z\in H\) such that \(x*z = y\).

The authors developed a method, similar to the Hungarian method, to find optimal assignments by using the concept of an admissible transformation, i.e. a transformation that does not alter the relative order of the assignments. The following theorem describes admissible transformations for algebraic assignment problems (see [5]).

Theorem 3

Let \(I,J\subseteq \{1,2,\ldots ,n\}\), \(m=|I|+|J|-n\ge 1\), and \(c=\min \{c_{ij}:i\in I,j\in J\}\). Then the transformation of matrix C into matrix \(\bar{C}\), \(T:C\mapsto \bar{C}\), defined by

$$\begin{aligned} \bar{c}_{ij}*c=c_{ij}\quad i\in I,\,j\in J,\\ \bar{c}_{ij}=c_{ij}*c\quad i\notin I,\,j\notin J,\\ \bar{c}_{ij}=c_{ij}\quad \text {otherwise}, \end{aligned}$$

is admissible with \(z_T=c*c*\cdots *c\), where the expression in the right-hand side contains m factors.

It can be shown that \(\big (\mathbb {R}^{3},+,\le _{\text {lex}}\big )\) is a totally ordered commutative semigroup that meets the properties mentioned above. Consequently, LLAP (6) can be solved with the following method proposed in [5], using \(+\) and \(\le _{\text {lex}}\) in place of \(*\) and \(\le \), respectively.

  • Step 1. Perform row reductions in matrix C, i.e. perform admissible transformations as in Theorem 3 with \(I=\left\{ k\right. \}\), \(J=\left\{ 1,2,\ldots ,n\right. \}\). Start with \(k=1\) and let \(z:=z_T\) be the corresponding index. Continue with \(k=2,\ldots ,n\) and update \(z:=z*z_T\). Afterward, all elements in the transformed matrix are non-negative with respect to z, i.e. \(z\le \bar{c}_{ij}*z\).

  • Step 2. Perform column reductions, i.e. perform admissible transformations with \(I=\left\{ 1,2,\ldots ,n\right. \}\), \(J=\left\{ k\right. \}\), for \(k=1,2,\ldots ,n\). Afterward, every row and column in the transformed cost matrix contains at least one 0-element. All other elements remain non-negative with respect to z.

  • Step 3. Determine a maximum matching in the following bipartite graph \(G = (V; W; E)\), where V contains the row indices of the transformed cost matrix, W the column indices, and \((i,j)\in E\), if and only if \(\bar{c}_{ij}*z=z\).

  • Step 4. If the maximum matching is perfect, then stop: The optimal solution is given by this matching and z is the optimal value of the objective function. Otherwise, go to Step 5.

  • Step 5. Determine a minimum cover of the transformed cost coefficients with a value of 0. This cover produces the new index sets I and J. I contains the indices of the uncovered rows and J contains the indices of the uncovered columns.

  • Step 6. Perform an admissible transformation determined by the new index sets I and J as in Theorem 3, update \(z:=z*z_T\), and go to Step 3.

B Preliminary Experimental Results

Fig. 2.
figure 2

Experimental results.

Full size image

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Pérez-Cañedo, B., Novoa-Hernández, P., Pelta, D.A., Verdegay, J.L. (2023). Exact and Heuristic Lexicographic Methods for the Fuzzy Traveling Salesman Problem. In: García Bringas, P., et al. Hybrid Artificial Intelligent Systems. HAIS 2023. Lecture Notes in Computer Science(), vol 14001. Springer, Cham. https://doi.org/10.1007/978-3-031-40725-3_38

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-40725-3_38

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-40724-6

  • Online ISBN: 978-3-031-40725-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation