Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Particle Swarm Optimization Algorithm with Path Relinking for the Location Routing Problem

  • Published:
Journal of Mathematical Modelling and Algorithms

Abstract

This paper introduces a new hybrid algorithmic nature inspired approach based on particle swarm optimization, for solving successfully one of the most popular logistics management problems, the location routing problem (LRP). The proposed algorithm for the solution of the location routing problem, the hybrid particle swarm optimization (HybPSO-LRP), combines a particle swarm optimization (PSO) algorithm, the multiple phase neighborhood search – greedy randomized adaptive search procedure (MPNS-GRASP) algorithm, the expanding neighborhood search (ENS) strategy and a path relinking (PR) strategy. The algorithm is tested on a set of benchmark instances. The results of the algorithm are very satisfactory for these instances and for six of them a new best solution has been found.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.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

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. Albareda-Sambola, M., Diaz, J.A., Fernandez, E.: A compact model and tight bounds for a combined location-routing problem. Comput. Oper. Res. 32(3), 407–428 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  2. Averbakh, I., Berman, O.: Routing and location-routing p-delivery men problems on a path. Transp. Sci. 28(2), 162–166 (1994)

    MATH  MathSciNet  Google Scholar 

  3. Barreto, S., Ferreira, C., Paixao, J., Santos, B.S.: Using clustering analysis in a capacitated location-routing problem. Eur. J. Oper. Res. 179(3), 968–977 (2007)

    Article  MATH  Google Scholar 

  4. Bookbinder, J.H., Reece, K.E.: Vehicle routing considerations in distribution system design. Eur. J. Oper. Res. 37, 204–213 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  5. Caballero, R., Gonzalez, M., Guerrero, F.M., Molina, J., Paralera, C.: Solving a multiobjective location routing problem with a metaheuristic based on tabu search. Application to a real case in Andalusia. Eur. J. Oper. Res. 177(3), 1751–1763 (2007)

    MATH  Google Scholar 

  6. Cappanera, P., Gallo, G., Maffioli, F.: Discrete facility location and routing of obnoxious activities. Discrete Appl. Math. 133(1–3), 3–28 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  7. Chan, Y., Baker, S.F.: The multiple depot, multiple traveling salesmen facility-location problem: vehicle range, service frequency, and heuristic implementations. Math. Comput. Model. 41(8–9), 1035-1053 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  8. Chiang, W.C., Russell, R.A.: Integrating purchasing and routing in a propane gas supply chain. Eur J. Oper. Res. 154(3), 710–729 (2004)

    Article  MATH  Google Scholar 

  9. Christofides, N., Eilon, S.: An algorithm for the vehicle dispatching problem. Oper. Res. Q. 20, 309–318 (1969)

    Google Scholar 

  10. Christofides, N., Eilon, S.: Expected distances for distribution problems. Oper. Res. Q. 20, 437–443 (1969)

    Google Scholar 

  11. Daskin, M.: Network and Discrete Location. Models, Algorithms and Applications. Wiley, New York (1995)

    MATH  Google Scholar 

  12. Dondo, R., Cerda, J.: A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. Eur. J. Oper. Res. 176(3), 1478–1507 (2007)

    Article  MATH  Google Scholar 

  13. Franchis, R.L., White, J.H.: Facility Layout and Location. An Analytic Approach, Prentice-Hall, New Jersey (1974)

    Google Scholar 

  14. Franchis, R.L., McGinnis, L.F., White, J.A.: Locational analysis. Eur. J. Oper. Res. 12(3), 220–252 (1983)

    Article  Google Scholar 

  15. Garfinkel, R., Nemhauser, G.: Integer Programming. Wiley, New York (1972)

    MATH  Google Scholar 

  16. Gaskell, T.J.: Bases for vehicle fleet scheduling. Oper. Res. Q. 18, 281–295 (1967)

    Article  Google Scholar 

  17. Ghosh, J.K., Sinha, S.B., Acharya, D.: A generalized reduced gradient based approach to round-trip location problem. In: Jaiswal, N.K. (ed.) Scientific Management of Transport Systems, pp. 209–213. Amsterdam, Holland (1981)

    Google Scholar 

  18. Glover, F., Laguna, M., Marti, R.: Scatter search and path relinking: advances and applications. In: Glover, F., Kochenberger, G.A. (eds.) Handbook of Metaheuristics, pp. 1–36. Kluwer, Boston (2003)

    Chapter  Google Scholar 

  19. Golden B.L., Assad, A.A.: Vehicle Routing: Methods and Studies. North Holland, Amsterdam (1988)

    MATH  Google Scholar 

  20. Hansen, P., Mladenovic, N.: Variable neighborhood search: principles and applications. Eur. J. Oper. Res. 130, 449–467 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  21. Hwang, H.S.: Design of supply-chain logistics system considering service level. Comput. Ind. Eng. 43(1–2), 283–297 (2002)

    Article  Google Scholar 

  22. Jacobsen, S.K., Madsen, O.B.G.: A comparative study of heuristics for two level routing location problem. Eur. J. Oper. Res. 5, 378–387 (1980)

    Article  MATH  Google Scholar 

  23. Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of 1995 IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948 (1995)

  24. Kennedy, J., Eberhart, R.: A discrete binary version of the particle swarm algorithm. In: Proceedings of 1997 IEEE International Conference on Systems, Man, and Cybernetics, vol. 5, pp. 4104–4108 (1997)

  25. Laoutaris, N., Zissimopoulos, V., Stavrakakis, I.: On the optimization of storage capacity allocation for content distribution. Comput. Networks 47(3), 409–428 (2005)

    Article  Google Scholar 

  26. Laporte, G.: Location routing problems. Golden, B.L., et al. (eds.) Vehicle Routing: Methods and Studies, pp. 163–198. North Holland, Amsterdam (1988)

    Google Scholar 

  27. Laporte, G., Dejax, P.J.: Dynamic location-routing problems. J. Oper. Res. Soc. 40(5), 471–482 (1989)

    Article  MATH  Google Scholar 

  28. Laporte, G., Nobert, Y., Arpin, D.: An exact algorithm for solving a capacitated location-routing problem. Ann. Oper. Res. 6, 293–310 (1986)

    Article  Google Scholar 

  29. Laporte, G., Nobert, Y., Pelletier, P.: Hamiltonian location problems. Eur. J. Oper. Res. 12(1), 82–89 (1983)

    Article  MATH  Google Scholar 

  30. Lin, S.: Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44, 2245–2269 (1965)

    MATH  Google Scholar 

  31. Lin, C.K.Y., Chow, C.K., Chen, A.: A location-routing-loading problem for bill delivery services. Comput. Ind. Eng. 43(1–2), 5–25 (2002)

    Article  Google Scholar 

  32. Lin, C.K.Y., Kwok, R.C.W.: Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data. Eur. J. Oper. Res. 175(3), 1833–1849 (2006)

    Article  MATH  Google Scholar 

  33. Liu, S.C., Lee, S.B.: A two-phase heuristic method for the multi-depot location routing problem taking inventory control decisions into consideration. Int. J. Adv. Manuf. Technol. 22(11–12), 941–950 (2003)

    Article  Google Scholar 

  34. Madsen, O.B.G.: Methods for solving combined two level location routing problems of realistic dimension. Eur. J. Oper. Res. 12(3), 295–301 (1983)

    Article  Google Scholar 

  35. Marinakis, Y.: Vehicle routing in distribution problems. Ph.D. thesis, Technical University of Crete, Department of Production Engineering and Management, Chania, Greece (2005)

  36. Marinakis, Y., Migdalas, A., Pardalos, P.M.: Expanding neighborhood grasp for the traveling salesman problem. Comput. Optim. Appl. 32, 231–257 (2004)

    Article  MathSciNet  Google Scholar 

  37. Marinakis, Y., Migdalas, A., Pardalos, P.M.: A hybrid genetic–GRASP algorithm using langrangean relaxation for the traveling salesman problem. J. Comb. Optim. 10, 311–326 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  38. Marinakis, Y., Migdalas, A., Pardalos, P.M.: Multiple phase neighborhood search GRASP based on Lagrangean relaxation and random backtracking Lin–Kernighan for the traveling salesman problem. J. Comb. Optim. 38, 555–580 (2006)

    MathSciNet  Google Scholar 

  39. Marinakis, Y., Marinaki, M., Migdalas, A.: A hybrid Genetic–GRASP–ENS algorithm for the vehicle routing problem. IEEE Trans. Evol. Comput. (2007) (submitted)

  40. Melechovsky, J., Prins, C., Calvo, R.W.: A metaheuristic to solve a location-routing problem with non-linear costs. J. Heuristics 11(5–6), 375–391 (2005)

    Article  MATH  Google Scholar 

  41. Min, H.: Consolidation terminal location-allocation and consolidated routing problems. J. Bus. Logist. 17(2), 235–263 (1996)

    Google Scholar 

  42. Min, H., Jayaraman, V., Srivastava, R.: Combined location-routing problems: a synthesis and future research directions. Eur. J. Oper. Res. 108, 1–15 (1998)

    Article  MATH  Google Scholar 

  43. Nagy, G., Salhi, S.: Nested heuristic methods for the location-routing problem. J. Oper. Res. Soc. 47, 1166–1174 (1996)

    Article  MATH  Google Scholar 

  44. Nagy, G., Salhi, S.: Location-routing: issues, models and methods. Eur. J. Oper. Res. 177, 649–672 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  45. Or, I.: Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. Ph.D. thesis, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL (1976)

  46. Perl, J., Daskin, M.S.: A unified warehouse location-routing methodology. J. Bus. Logist. 5(1), 92–111 (1984)

    Google Scholar 

  47. Perl, J., Daskin, M.S.: A warehouse location routing model. Transp. Res. B 19, 381–396 (1985)

    Article  Google Scholar 

  48. Prins, C., Prodhon, C., Calvo, R.W.: Solving the capacitated location-routing problem by a grasp complemented by a learning process and a path relinking. 4OR 4, 221–238 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  49. Prins, C., Prodhon, C., Calvo, R.W.: A memetic algorithm with population management (MA|PM) for the capacitated location-routing problem. In: Evolutionary Computation Combinatorial Optimization. LNCS, vol. 906, pp. 183–194 (2006)

  50. Resende, M.G.C., Ribeiro, C.C.: Greedy randomized adaptive search procedures. In: Glover, F., Kochenberger, G.A. (eds.) Handbook of Metaheuristics. Kluwer, Boston, pp. 219–249 (1998)

    Google Scholar 

  51. Russell, R., Chiang, W.C., Zepeda, D.: Integrating multi-product production and distribution in newspaper logistics. Comput. Oper. Res. (2007) doi:10.1016/j.cor.2006.09.002

  52. Simchi-Levi, D., Berman, O.: A heuristic algorithm for the traveling salesman location problem on networks. Eur. J. Oper. Res. 36, 478–484 (1988)

    MATH  Google Scholar 

  53. Shi, Y., Eberhart, R.: A modified particle swarm optimizer. In: Proceedings of 1998 IEEE World Congress on Computational Intelligence, pp. 69–73 (1998)

  54. Srivastava, R., Benton, W.C.: The location-routing problem: consideration in physical distribution system design. Comput. Oper. Res. 6, 427–435 (1990)

    Article  Google Scholar 

  55. Stowers, C.L., Palekar, U.S.: Location models with routing considerations for a single obnoxious facility. Transp. Sci. 27(4), 350–362 (1993)

    MATH  Google Scholar 

  56. Toth, P., Vigo, D.: The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications, Siam (2002)

  57. Tuzun, D., Burke, L.I.: A two-phase tabu search approach to the location routing problem. Eur. J. Oper. Res. 116, 87–99 (1999)

    Article  MATH  Google Scholar 

  58. Watson-Gandy, C.T.D., Dohrn, P.J.: Depot location with van salesman – a practical approach. Omega 1, 321–329 (1973)

    Article  Google Scholar 

  59. Wu, T.H., Low, C., Bai, J.W.: Heuristic solutions to multi-depot location-routing problems. Comput. Oper. Res. 29, 1393–1415 (2002)

    Article  MATH  Google Scholar 

  60. Zografos, K.G., Samara, S.: Combined location-routing model for hazardous waste transportation and disposal. Transp. Res. Record 1245, 52–59 (1989)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Production Engineering and Management, Technical University of Crete, 73100, Chania, Greece

    Yannis Marinakis & Magdalene Marinaki

Authors
  1. Yannis Marinakis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Magdalene Marinaki
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yannis Marinakis.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Marinakis, Y., Marinaki, M. A Particle Swarm Optimization Algorithm with Path Relinking for the Location Routing Problem. J Math Model Algor 7, 59–78 (2008). https://doi.org/10.1007/s10852-007-9073-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10852-007-9073-6

Keywords

Mathematics Subject Classifications (2000)

Search

Navigation