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

An exact algorithm for designing optimal districts in the collection of waste electric and electronic equipment through an improved reformulation

Author

Listed:
  • Ríos-Mercado, Roger Z.
  • Bard, Jonathan F.

Abstract

In this paper, a maximum dispersion districting problem is considered that arises in the collection of waste electric and electronic equipment. For a given geographic region, the problem is to partition a set of collection or basic units such that each district in the region is assigned to a different company in a way that maximizes a dispersion function subject to a set of planning requirements. Starting with the traditional mixed-integer programming model, a covering-type model is proposed that is shown to be much more effective. In addition, a new upper bound for the maximum dispersion partitioning problem – a relaxation of the problem studied – is developed. Next, an exact algorithm based on the reformulated model is presented along with the newly derived upper bound. The algorithm intelligently exploits properties of the problem in a manner that allows for a large number of binary variables to be fixed and eliminated in a pre-processing step.

Suggested Citation

  • Ríos-Mercado, Roger Z. & Bard, Jonathan F., 2019. "An exact algorithm for designing optimal districts in the collection of waste electric and electronic equipment through an improved reformulation," European Journal of Operational Research, Elsevier, vol. 276(1), pages 259-271.
    • Handle: RePEc:eee:ejores:v:276:y:2019:i:1:p:259-271
    DOI: 10.1016/j.ejor.2018.12.030
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718311032
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.12.030?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. Juan Carlos Duque & Raúl Ramos & Jordi Suriñach, 2007. "Supervised Regionalization Methods: A Survey," International Regional Science Review, , vol. 30(3), pages 195-220, July.
    2. Federica Ricca & Andrea Scozzari & Bruno Simeone, 2013. "Political Districting: from classical models to recent approaches," Annals of Operations Research, Springer, vol. 204(1), pages 271-299, April.
    3. Z P Fan & Y Chen & J Ma & S Zeng, 2011. "A hybrid genetic algorithmic approach to the maximally diverse grouping problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(1), pages 92-99, January.
    4. J Mar-Ortiz & B Adenso-Diaz & J L González-Velarde, 2011. "Design of a recovery network for WEEE collection: the case of Galicia, Spain," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(8), pages 1471-1484, August.
    5. Martí, Rafael & Gallego, Micael & Duarte, Abraham, 2010. "A branch and bound algorithm for the maximum diversity problem," European Journal of Operational Research, Elsevier, vol. 200(1), pages 36-44, January.
    6. Fernández, Elena & Kalcsics, Jörg & Nickel, Stefan, 2013. "The maximum dispersion problem," Omega, Elsevier, vol. 41(4), pages 721-730.
    7. Sourour Elloumi & Martine Labbé & Yves Pochet, 2004. "A New Formulation and Resolution Method for the p-Center Problem," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 84-94, February.
    8. Z P Fan & Y Chen & J Ma & S Zeng, 2011. "Erratum: A hybrid genetic algorithmic approach to the maximally diverse grouping problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1423-1430, July.
    9. M Gallego & M Laguna & R Martí & A Duarte, 2013. "Tabu search with strategic oscillation for the maximally diverse grouping problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(5), pages 724-734, May.
    10. Andris A. Zoltners & Prabhakant Sinha, 2005. "The 2004 ISMS Practice Prize Winner—Sales Territory Design: Thirty Years of Modeling and Implementation," Marketing Science, INFORMS, vol. 24(3), pages 313-331, September.
    11. Hammond, David & Beullens, Patrick, 2007. "Closed-loop supply chain network equilibrium under legislation," European Journal of Operational Research, Elsevier, vol. 183(2), pages 895-908, December.
    12. S C Lee & L H Shih, 2012. "A novel heuristic approach to determine compromise management for end-of-life electronic products," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 63(5), pages 606-619, May.
    13. E Fernández & J Kalcsics & S Nickel & R Z Ríos-Mercado, 2010. "A novel maximum dispersion territory design model arising in the implementation of the WEEE-directive," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(3), pages 503-514, March.
    14. Erkut, Erhan, 1990. "The discrete p-dispersion problem," European Journal of Operational Research, Elsevier, vol. 46(1), pages 48-60, May.
    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. Diglio, Antonio & Peiró, Juanjo & Piccolo, Carmela & Saldanha-da-Gama, Francisco, 2023. "Approximation schemes for districting problems with probabilistic constraints," European Journal of Operational Research, Elsevier, vol. 307(1), pages 233-248.
    2. Shi, Jianmai & Chen, Wenyi & Verter, Vedat, 2023. "The joint impact of environmental awareness and system infrastructure on e-waste collection," European Journal of Operational Research, Elsevier, vol. 310(2), pages 760-772.
    3. Sergey Kovalev & Isabelle Chalamon & Fabio J. Petani, 2023. "Maximizing single attribute diversity in group selection," Annals of Operations Research, Springer, vol. 320(1), pages 535-540, January.
    4. Bruno, Giuseppe & Diglio, Antonio & Passaro, Renato & Piccolo, Carmela & Quinto, Ivana, 2021. "Measuring spatial access to the recovery networks for WEEE: An in-depth analysis of the Italian case," International Journal of Production Economics, Elsevier, vol. 240(C).
    5. Sandoval, M. Gabriela & Álvarez-Miranda, Eduardo & Pereira, Jordi & Ríos-Mercado, Roger Z. & Díaz, Juan A., 2022. "A novel districting design approach for on-time last-mile delivery: An application on an express postal company," Omega, Elsevier, vol. 113(C).
    6. Gliesch, Alex & Ritt, Marcus, 2021. "A hybrid heuristic for the maximum dispersion problem," European Journal of Operational Research, Elsevier, vol. 288(3), pages 721-735.

    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. Arne Schulz, 2022. "A new mixed-integer programming formulation for the maximally diverse grouping problem with attribute values," Annals of Operations Research, Springer, vol. 318(1), pages 501-530, November.
    2. Fernández, Elena & Kalcsics, Jörg & Nickel, Stefan, 2013. "The maximum dispersion problem," Omega, Elsevier, vol. 41(4), pages 721-730.
    3. Sandoval, M. Gabriela & Álvarez-Miranda, Eduardo & Pereira, Jordi & Ríos-Mercado, Roger Z. & Díaz, Juan A., 2022. "A novel districting design approach for on-time last-mile delivery: An application on an express postal company," Omega, Elsevier, vol. 113(C).
    4. Arne Schulz, 2024. "Efficient neighborhood evaluation for the maximally diverse grouping problem," Annals of Operations Research, Springer, vol. 341(2), pages 1247-1265, October.
    5. Yang, Xiao & Cai, Zonghui & Jin, Ting & Tang, Zheng & Gao, Shangce, 2022. "A three-phase search approach with dynamic population size for solving the maximally diverse grouping problem," European Journal of Operational Research, Elsevier, vol. 302(3), pages 925-953.
    6. Anna Martínez-Gavara & Vicente Campos & Micael Gallego & Manuel Laguna & Rafael Martí, 2015. "Tabu search and GRASP for the capacitated clustering problem," Computational Optimization and Applications, Springer, vol. 62(2), pages 589-607, November.
    7. Sebastián Moreno & Jordi Pereira & Wilfredo Yushimito, 2020. "A hybrid K-means and integer programming method for commercial territory design: a case study in meat distribution," Annals of Operations Research, Springer, vol. 286(1), pages 87-117, March.
    8. Seizinger, Markus & Brunner, Jens O., 2023. "Optimized planning of nursing curricula in dual vocational schools focusing on the German health care system," European Journal of Operational Research, Elsevier, vol. 304(3), pages 1223-1241.
    9. Johnes, Jill, 2015. "Operational Research in education," European Journal of Operational Research, Elsevier, vol. 243(3), pages 683-696.
    10. Gliesch, Alex & Ritt, Marcus, 2021. "A hybrid heuristic for the maximum dispersion problem," European Journal of Operational Research, Elsevier, vol. 288(3), pages 721-735.
    11. Verónica Arredondo & Miguel Martínez-Panero & Teresa Peña & Federica Ricca, 2021. "Mathematical political districting taking care of minority groups," Annals of Operations Research, Springer, vol. 305(1), pages 375-402, October.
    12. Djordje Dugošija & Aleksandar Savić & Zoran Maksimović, 2020. "A new integer linear programming formulation for the problem of political districting," Annals of Operations Research, Springer, vol. 288(1), pages 247-263, May.
    13. Nicolas Dupin & Frank Nielsen & El-Ghazali Talbi, 2021. "Unified Polynomial Dynamic Programming Algorithms for P-Center Variants in a 2D Pareto Front," Mathematics, MDPI, vol. 9(4), pages 1-30, February.
    14. Martí, Rafael & Martínez-Gavara, Anna & Pérez-Peló, Sergio & Sánchez-Oro, Jesús, 2022. "A review on discrete diversity and dispersion maximization from an OR perspective," European Journal of Operational Research, Elsevier, vol. 299(3), pages 795-813.
    15. Lei, Ting L. & Church, Richard L., 2015. "On the unified dispersion problem: Efficient formulations and exact algorithms," European Journal of Operational Research, Elsevier, vol. 241(3), pages 622-630.
    16. Nickel, Stefan & Velten, Sebastian, 2017. "Optimization problems with flexible objectives: A general modeling approach and applications," European Journal of Operational Research, Elsevier, vol. 258(1), pages 79-88.
    17. Aringhieri, Roberto & Cordone, Roberto & Grosso, Andrea, 2015. "Construction and improvement algorithms for dispersion problems," European Journal of Operational Research, Elsevier, vol. 242(1), pages 21-33.
    18. Yao, Ming-Jong & Lin, Jen-Yen & Lin, Yu-Liang & Fang, Shu-Cherng, 2020. "An integrated algorithm for solving multi-customer joint replenishment problem with districting consideration," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 138(C).
    19. Anna Martínez-Gavara & Vicente Campos & Manuel Laguna & Rafael Martí, 2017. "Heuristic solution approaches for the maximum minsum dispersion problem," Journal of Global Optimization, Springer, vol. 67(3), pages 671-686, March.
    20. Sayah, David & Irnich, Stefan, 2017. "A new compact formulation for the discrete p-dispersion problem," European Journal of Operational Research, Elsevier, vol. 256(1), pages 62-67.

    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:276:y:2019:i:1:p:259-271. 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.