Skip to main content
SpringerLink
Log in

Multi-objective Meta-heuristics for the Traveling Salesman Problem with Profits

  • Published:
Journal of Mathematical Modelling and Algorithms

Abstract

We introduce and test a new approach for the bi-objective routing problem known as the traveling salesman problem with profits. This problem deals with the optimization of two conflicting objectives: the minimization of the tour length and the maximization of the collected profits. This problem has been studied in the form of a single objective problem, where either the two objectives have been combined or one of the objectives has been treated as a constraint. The purpose of our study is to find solutions to this problem using the notion of Pareto optimality, i.e. by searching for efficient solutions and constructing an efficient frontier. We have developed an ejection chain local search and combined it with a multi-objective evolutionary algorithm which is used to generate diversified starting solutions in the objective space. We apply our hybrid meta-heuristic to synthetic data sets and demonstrate its effectiveness by comparing our results with a procedure that employs one of the best single-objective approaches.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Awerbuch, B., Azar, Y., Blum, A., Vempala, S.: New approximation guarantees for minimum-weight k-trees and prize-collection salesmen. SIAM J. Comput. 28, 254–262 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  2. Balas, E.: The prize-collecting traveling salesman problem. Networks 19, 621–636 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  3. Boffey, B.: Multiobjective routing problems. Top 3, 167–220 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  4. Deb, K., Pratap, A., Agarwal, S., Meyarvan, T.: A fast and elitist multiobjective genetic algorithm: NSGA II. IEEE Trans. Evolution. Comput. 6, 182–197 (2002)

    Article  Google Scholar 

  5. Dell’Amico, M., Maffioli, F., Värbrand, P.: On prize-collecting tours and the asymmetric travelling salesman problem. Int. Trans. Oper. Res. 2, 297–308 (1995)

    Article  MATH  Google Scholar 

  6. Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multi-objective combinatorial optimization. OR Spektrum 22, 425–460 (2000)

    MATH  MathSciNet  Google Scholar 

  7. Feillet, D., Dejax, P., Gendreau, M.: Traveling salesman problems with profits. Trans. Sci. 39, 188–205 (2005)

    Article  Google Scholar 

  8. Gendreau, M., Hertz, A., Laporte, G.: New insertion and postoptimization procedures for the traveling salesman problem. Oper. Res. 40, 1086–1094 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  9. Gendreau, M., Laporte, G., Semet, F.: A tabu search heuristic for the undirected selective travelling salesman problem. Eur. J. Oper. Res. 106, 539–545 (1998)

    Article  MATH  Google Scholar 

  10. Glover, F.: Heuristics for integer programming using surrogate constraints. Decis. Sci. 8, 156–166 (1977)

    Article  Google Scholar 

  11. Glover, F.: New ejection chain and alternating path methods for the traveling salesman problems. Comput. Sci. Oper. Res. 449–509 (1992)

  12. Glover, F.: Tabu search for nonlinear and parametric optimization (with links to genetic algorithms). Discrete Appl. Math. 49, 231–255 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  13. Glover, F., Laguna, M.: Modern heuristic techniques for combinatorial problems. Chapt. Tabu search, pp. 71–140. Blackwell Scientific Publishing (1993)

  14. Glover, F., Laguna, M.: Tabu Search. Kluwer Academic Press (1997)

  15. Kataoka, S., Morito, S.: An algorithm for the single constraint maximum collection problem. J. Oper. Res. Soc. Jpn. 31, 515–530 (1988)

    MATH  MathSciNet  Google Scholar 

  16. Keller, C.P.: Multiobjective routing through space and time: the MVP and TDVRP problems. Ph.D. thesis, Department of Geography, University of Western Ontario. London, Ontario, Canada (1985)

  17. Keller, C.P., Goodchild, M.: The multiobjective vending problem: a generalization of the traveling salesman problem. Environ. Plann., B. Plann. Des. 15, 447–460 (1988)

    Article  Google Scholar 

  18. Laporte, G., Martello, S.: The selective traveling salesman problem. Discrete Appl. Math. 26, 193–207 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  19. Rego, C.: Relaxed tours and path ejections for the traveling salesman problem. Eur. J. Oper. Res. 106, 522–538 (1998)

    Article  MATH  Google Scholar 

  20. Rosenkrantz, D.J., Stearns, R.E., Lewis II, P.M.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6, 563–581 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  21. Whitley, D., Starkweather, T., Fuquay, D.: Scheduling problems and traveling salesman: the genetic edge recombination operator. In: Schaffer J. (ed.) Proceedings of the Third International Conference on Genetic Algorithms, pp. 133–140 (1989)

  22. Zitzler, E.: Evolutionary algorithm for multiobjective optimization: methods and applications. Ph.D. thesis, Swiss Federal Institute of Technology (ETH). Zurich, Switzerland (1999)

Download references

Author information

Authors and Affiliations

  1. INSA, LAAS-CNRS, Université de Toulouse, 7 Avenue du Colonel Roche, F-31077, Toulouse cedex 4, France

    Nicolas Jozefowiez

  2. Leeds School of Business, University of Colorado at Boulder, CO, USA

    Fred Glover & Manuel Laguna

Authors
  1. Nicolas Jozefowiez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fred Glover
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Manuel Laguna
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nicolas Jozefowiez.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Jozefowiez, N., Glover, F. & Laguna, M. Multi-objective Meta-heuristics for the Traveling Salesman Problem with Profits. J Math Model Algor 7, 177–195 (2008). https://doi.org/10.1007/s10852-008-9080-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10852-008-9080-2

Keywords

Mathematics Subject Classifications (2000)

Search

Navigation