IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v210y2011i2p204-212.html
   My bibliography  Save this article

A hybrid evolutionary algorithm for the periodic location-routing problem

Author

Listed:
  • Prodhon, Caroline

Abstract

The well-known vehicle routing problem (VRP) has been studied in depth over the last decades. Nowadays, generalizations of VRP have been developed for tactical or strategic decision levels of companies but not both. The tactical extension or periodic VRP (PVRP) plans a set of trips over a multiperiod horizon, subject to frequency constraints. The strategic extension is motivated by interdependent depot location and routing decisions in most distribution systems. Low-quality solutions are obtained if depots are located first, regardless of the future routes. In the location-routing problem (LRP), location and routing decisions are tackled simultaneously. Here for the first time, except for some conference papers, the goal is to combine the PVRP and LRP into an even more realistic problem covering all decision levels: the periodic LRP or PLRP. A hybrid evolutionary algorithm is proposed to solve large size instances of the PLRP. First, an individual representing an assignment of customers to combinations of visit days is randomly generated. The evolution operates through an Evolutionary Local Search (ELS) on visit day assignments. The algorithm is hybridized with a heuristic based on the Randomized Extended Clarke and Wright Algorithm (RECWA) to create feasible solutions and stops when a given number of iterations is reached. The method is evaluated over three sets of instances, and solutions are compared to the literature on particular cases such as one-day horizon (LRP) or one depot (PVRP). This metaheuristic outperforms the previous methods for the PLRP.

Suggested Citation

  • Prodhon, Caroline, 2011. "A hybrid evolutionary algorithm for the periodic location-routing problem," European Journal of Operational Research, Elsevier, vol. 210(2), pages 204-212, April.
    • Handle: RePEc:eee:ejores:v:210:y:2011:i:2:p:204-212
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00619-3
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. K.S. Al‐Sultan & M.A. Al‐Fawzan, 1999. "A tabu search approach to the uncapacitated facility location problem," Annals of Operations Research, Springer, vol. 86(0), pages 91-103, January.
    2. Lacomme, Philippe & Prins, Christian & Ramdane-Cherif, Wahiba, 2005. "Evolutionary algorithms for periodic arc routing problems," European Journal of Operational Research, Elsevier, vol. 165(2), pages 535-553, September.
    3. Salhi, Said & Rand, Graham K., 1989. "The effect of ignoring routes when locating depots," European Journal of Operational Research, Elsevier, vol. 39(2), pages 150-156, March.
    4. Gilbert Laporte & Yves Nobert & Serge Taillefer, 1988. "Solving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems," Transportation Science, INFORMS, vol. 22(3), pages 161-172, August.
    5. ,, 2002. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 18(1), pages 193-194, February.
    6. Mina, Hokey & Jayaraman, Vaidyanathan & Srivastava, Rajesh, 1998. "Combined location-routing problems: A synthesis and future research directions," European Journal of Operational Research, Elsevier, vol. 108(1), pages 1-15, July.
    7. S. Lin & B. W. Kernighan, 1973. "An Effective Heuristic Algorithm for the Traveling-Salesman Problem," Operations Research, INFORMS, vol. 21(2), pages 498-516, April.
    8. Chu, Feng & Labadi, Nacima & Prins, Christian, 2006. "A Scatter Search for the periodic capacitated arc routing problem," European Journal of Operational Research, Elsevier, vol. 169(2), pages 586-605, March.
    9. Laporte, Gilbert & Louveaux, Francois & Mercure, Helene, 1989. "Models and exact solutions for a class of stochastic location-routing problems," European Journal of Operational Research, Elsevier, vol. 39(1), pages 71-78, March.
    10. ,, 2002. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 18(2), pages 541-545, April.
    11. Christian Prins & Caroline Prodhon & Angel Ruiz & Patrick Soriano & Roberto Wolfler Calvo, 2007. "Solving the Capacitated Location-Routing Problem by a Cooperative Lagrangean Relaxation-Granular Tabu Search Heuristic," Transportation Science, INFORMS, vol. 41(4), pages 470-483, November.
    12. ,, 2002. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 18(4), pages 1007-1017, August.
    13. Hemmelmayr, Vera C. & Doerner, Karl F. & Hartl, Richard F., 2009. "A variable neighborhood search heuristic for periodic routing problems," European Journal of Operational Research, Elsevier, vol. 195(3), pages 791-802, June.
    14. ,, 2002. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 18(6), pages 1461-1465, December.
    15. ,, 2002. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 18(5), pages 1273-1289, October.
    16. ,, 2002. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 18(3), pages 819-821, June.
    17. Tuzun, Dilek & Burke, Laura I., 1999. "A two-phase tabu search approach to the location routing problem," European Journal of Operational Research, Elsevier, vol. 116(1), pages 87-99, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Albareda-Sambola, Maria & Fernández, Elena & Nickel, Stefan, 2012. "Multiperiod Location-Routing with Decoupled Time Scales," European Journal of Operational Research, Elsevier, vol. 217(2), pages 248-258.
    2. Rieck, Julia & Ehrenberg, Carsten & Zimmermann, Jürgen, 2014. "Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery," European Journal of Operational Research, Elsevier, vol. 236(3), pages 863-878.
    3. Guerrero, W.J. & Prodhon, C. & Velasco, N. & Amaya, C.A., 2013. "Hybrid heuristic for the inventory location-routing problem with deterministic demand," International Journal of Production Economics, Elsevier, vol. 146(1), pages 359-370.
    4. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    5. Moshref-Javadi, Mohammad & Lee, Seokcheon, 2016. "The Latency Location-Routing Problem," European Journal of Operational Research, Elsevier, vol. 255(2), pages 604-619.
    6. Hashemi Doulabi, Seyed Hossein & Seifi, Abbas, 2013. "Lower and upper bounds for location-arc routing problems with vehicle capacity constraints," European Journal of Operational Research, Elsevier, vol. 224(1), pages 189-208.
    7. Nadizadeh, Ali & Hosseini Nasab, Hasan, 2014. "Solving the dynamic capacitated location-routing problem with fuzzy demands by hybrid heuristic algorithm," European Journal of Operational Research, Elsevier, vol. 238(2), pages 458-470.
    8. Jaller, Miguel & Pahwa, Anmol, 2023. "Coping with the Rise of E-commerce Generated Home Deliveries through Innovative Last-mile Technologies and Strategies," Institute of Transportation Studies, Working Paper Series qt5t76x0kh, Institute of Transportation Studies, UC Davis.
    9. Alvarez, Jose A. Lopez & Buijs, Paul & Deluster, Rogier & Coelho, Leandro C. & Ursavas, Evrim, 2020. "Strategic and operational decision-making in expanding supply chains for LNG as a fuel," Omega, Elsevier, vol. 97(C).
    10. Gläser, Sina & Stücken, Mareike, 2021. "Introduction of an underground waste container system–model and solution approaches," European Journal of Operational Research, Elsevier, vol. 295(2), pages 675-689.
    11. Zare Mehrjerdi, Yahia & Nadizadeh, Ali, 2013. "Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands," European Journal of Operational Research, Elsevier, vol. 229(1), pages 75-84.
    12. Prodhon, Caroline & Prins, Christian, 2014. "A survey of recent research on location-routing problems," European Journal of Operational Research, Elsevier, vol. 238(1), pages 1-17.
    13. Qian Zhu & Yongqing Li & Zhen Zhang, 2023. "Swarm Robots Search for Multiple Targets Based on Historical Optimal Weighting Grey Wolf Optimization," Mathematics, MDPI, vol. 11(12), pages 1-19, June.
    14. Hemmelmayr, Vera C., 2015. "Sequential and parallel large neighborhood search algorithms for the periodic location routing problem," European Journal of Operational Research, Elsevier, vol. 243(1), pages 52-60.
    15. Olmez, Omer Berk & Gultekin, Ceren & Balcik, Burcu & Ekici, Ali & Özener, Okan Örsan, 2022. "A variable neighborhood search based matheuristic for a waste cooking oil collection network design problem," European Journal of Operational Research, Elsevier, vol. 302(1), pages 187-202.
    16. Sinem Kınay Savaşer & Bahar Yetis Kara, 2022. "Mobile healthcare services in rural areas: an application with periodic location routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(3), pages 875-910, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ting, Ching-Jung & Chen, Chia-Ho, 2013. "A multiple ant colony optimization algorithm for the capacitated location routing problem," International Journal of Production Economics, Elsevier, vol. 141(1), pages 34-44.
    2. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    3. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    4. Drexl, M. & Schneider, M., 2014. "A Survey of the Standard Location-Routing Problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65940, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    5. Michael Schneider & Michael Drexl, 2017. "A survey of the standard location-routing problem," Annals of Operations Research, Springer, vol. 259(1), pages 389-414, December.
    6. Christian Prins & Caroline Prodhon & Angel Ruiz & Patrick Soriano & Roberto Wolfler Calvo, 2007. "Solving the Capacitated Location-Routing Problem by a Cooperative Lagrangean Relaxation-Granular Tabu Search Heuristic," Transportation Science, INFORMS, vol. 41(4), pages 470-483, November.
    7. Karaoglan, Ismail & Altiparmak, Fulya & Kara, Imdat & Dengiz, Berna, 2011. "A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery," European Journal of Operational Research, Elsevier, vol. 211(2), pages 318-332, June.
    8. Mahdi Bashiri & Zeinab Rasoulinejad & Ehsan Fallahzade, 2016. "A new approach on auxiliary vehicle assignment in capacitated location routing problem," International Journal of Systems Science, Taylor & Francis Journals, vol. 47(4), pages 886-902, March.
    9. Lin, C.K.Y. & Kwok, R.C.W., 2006. "Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1833-1849, December.
    10. Roberto Baldacci & Aristide Mingozzi & Roberto Wolfler Calvo, 2011. "An Exact Method for the Capacitated Location-Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1284-1296, October.
    11. Karaoglan, Ismail & Altiparmak, Fulya & Kara, Imdat & Dengiz, Berna, 2012. "The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach," Omega, Elsevier, vol. 40(4), pages 465-477.
    12. Wasner, Michael & Zapfel, Gunther, 2004. "An integrated multi-depot hub-location vehicle routing model for network planning of parcel service," International Journal of Production Economics, Elsevier, vol. 90(3), pages 403-419, August.
    13. Rieck, Julia & Ehrenberg, Carsten & Zimmermann, Jürgen, 2014. "Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery," European Journal of Operational Research, Elsevier, vol. 236(3), pages 863-878.
    14. Weijun Xie & Yanfeng Ouyang & Sze Chun Wong, 2016. "Reliable Location-Routing Design Under Probabilistic Facility Disruptions," Transportation Science, INFORMS, vol. 50(3), pages 1128-1138, August.
    15. Sahar Validi & Arijit Bhattacharya & P. J. Byrne, 2020. "Sustainable distribution system design: a two-phase DoE-guided meta-heuristic solution approach for a three-echelon bi-objective AHP-integrated location-routing model," Annals of Operations Research, Springer, vol. 290(1), pages 191-222, July.
    16. Aksen, Deniz & Altinkemer, Kemal, 2008. "A location-routing problem for the conversion to the "click-and-mortar" retailing: The static case," European Journal of Operational Research, Elsevier, vol. 186(2), pages 554-575, April.
    17. Stenger, Andreas & Schneider, Michael & Schwind, Michael & Vigo, Daniele, 2012. "Location routing for small package shippers with subcontracting options," International Journal of Production Economics, Elsevier, vol. 140(2), pages 702-712.
    18. Nasrin Asgari & Mohsen Rajabi & Masoumeh Jamshidi & Maryam Khatami & Reza Zanjirani Farahani, 2017. "A memetic algorithm for a multi-objective obnoxious waste location-routing problem: a case study," Annals of Operations Research, Springer, vol. 250(2), pages 279-308, March.
    19. Zhang, Ying & Qi, Mingyao & Lin, Wei-Hua & Miao, Lixin, 2015. "A metaheuristic approach to the reliable location routing problem under disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 83(C), pages 90-110.
    20. Hunkar Toyoglu & Oya Karasan & Bahar Kara, 2012. "A New Formulation Approach for Location-Routing Problems," Networks and Spatial Economics, Springer, vol. 12(4), pages 635-659, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:210:y:2011:i:2:p:204-212. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.