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

Heuristic methods for the sectoring arc routing problem

Author

Listed:
  • Mourão, Maria Cândida
  • Nunes, Ana Catarina
  • Prins, Christian

Abstract

The sectoring arc routing problem (SARP) is introduced to model activities associated with the streets of large urban areas, like municipal waste collection. The aim is to partition the street network into a given number of sectors and to build a set of vehicle trips in each sector, to minimize the total duration of the trips. Two two-phase heuristics and one best insertion method are proposed. In the two-phase methods, phase 1 constructs the sectors using two possible heuristics, while phase 2 solves a mixed capacitated arc routing problem (MCARP) to compute the trips in each sector. The best insertion method determines sectors and trips simultaneously. In addition to solution cost, some evaluation criteria such as imbalance, diameter and dispersion measures are used to compare algorithms. Numerical results on large instances with up to 401 nodes and 1056 links (arcs or edges) are reported and analysed.

Suggested Citation

  • Mourão, Maria Cândida & Nunes, Ana Catarina & Prins, Christian, 2009. "Heuristic methods for the sectoring arc routing problem," European Journal of Operational Research, Elsevier, vol. 196(3), pages 856-868, August.
    • Handle: RePEc:eee:ejores:v:196:y:2009:i:3:p:856-868
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00383-4
    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. H. A. Eiselt & Michel Gendreau & Gilbert Laporte, 1995. "Arc Routing Problems, Part II: The Rural Postman Problem," Operations Research, INFORMS, vol. 43(3), pages 399-414, June.
    2. Bodin, Lawrence & Levy, Laurence, 1991. "The arc partitioning problem," European Journal of Operational Research, Elsevier, vol. 53(3), pages 393-401, August.
    3. Bozkaya, Burcin & Erkut, Erhan & Laporte, Gilbert, 2003. "A tabu search heuristic and adaptive memory procedure for political districting," European Journal of Operational Research, Elsevier, vol. 144(1), pages 12-26, January.
    4. Sidney W. Hess & Stuart A. Samuels, 1971. "Experiences with a Sales Districting Model: Criteria and Implementation," Management Science, INFORMS, vol. 18(4-Part-II), pages 41-54, December.
    5. Andreas Drexl & Knut Haase, 1999. "Fast Approximation Methods for Sales Force Deployment," Management Science, INFORMS, vol. 45(10), pages 1307-1323, October.
    6. H. A. Eiselt & Michel Gendreau & Gilbert Laporte, 1995. "Arc Routing Problems, Part I: The Chinese Postman Problem," Operations Research, INFORMS, vol. 43(2), pages 231-242, April.
    7. Andris A. Zoltners & Prabhakant Sinha, 1983. "Sales Territory Alignment: A Review and Model," Management Science, INFORMS, vol. 29(11), pages 1237-1256, November.
    8. Labelle, A. & Langevin, A. & Campbell, J. F., 2002. "Sector design for snow removal and disposal in urban areas," Socio-Economic Planning Sciences, Elsevier, vol. 36(3), pages 183-202, September.
    9. L Muyldermans & D Cattrysse & D Van Oudheusden, 2003. "District design for arc-routing applications," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(11), pages 1209-1221, November.
    10. S. W. Hess & J. B. Weaver & H. J. Siegfeldt & J. N. Whelan & P. A. Zitlau, 1965. "Nonpartisan Political Redistricting by Computer," Operations Research, INFORMS, vol. 13(6), pages 998-1006, December.
    11. Ulusoy, Gunduz, 1985. "The fleet size and mix problem for capacitated arc routing," European Journal of Operational Research, Elsevier, vol. 22(3), pages 329-337, December.
    12. Philippe Lacomme & Christian Prins & Wahiba Ramdane-Cherif, 2004. "Competitive Memetic Algorithms for Arc Routing Problems," Annals of Operations Research, Springer, vol. 131(1), pages 159-185, October.
    13. Julie Wunderlich & Martin Collette & Laurence Levy & Lawrence Bodin, 1992. "Scheduling Meter Readers for Southern California Gas Company," Interfaces, INFORMS, vol. 22(3), pages 22-30, June.
    14. Mourao, Maria Candida & Amado, Ligia, 2005. "Heuristic method for a mixed capacitated arc routing problem: A refuse collection application," European Journal of Operational Research, Elsevier, vol. 160(1), pages 139-153, January.
    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. Kasaei, Maziar & Salman, F. Sibel, 2016. "Arc routing problems to restore connectivity of a road network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 177-206.
    2. T R P Ramos & R C Oliveira, 2011. "Delimitation of service areas in reverse logistics networks with multiple depots," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1198-1210, July.
    3. Ouyang, Zhiyuan & Leung, Eric Ka Ho & Huang, George Q., 2022. "Community logistics for dynamic vehicle dispatching: The effects of community departure “time” and “space”," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    4. 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.
    5. Fung, Richard Y.K. & Liu, Ran & Jiang, Zhibin, 2013. "A memetic algorithm for the open capacitated arc routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 53-67.
    6. Constantino, Miguel & Gouveia, Luís & Mourão, Maria Cândida & Nunes, Ana Catarina, 2015. "The mixed capacitated arc routing problem with non-overlapping routes," European Journal of Operational Research, Elsevier, vol. 244(2), pages 445-456.
    7. Alexander Butsch & Jörg Kalcsics & Gilbert Laporte, 2014. "Districting for Arc Routing," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 809-824, November.
    8. Geroliminis, Nikolas & Kepaptsoglou, Konstantinos & Karlaftis, Matthew G., 2011. "A hybrid hypercube - Genetic algorithm approach for deploying many emergency response mobile units in an urban network," European Journal of Operational Research, Elsevier, vol. 210(2), pages 287-300, April.
    9. Gopalan, Ram, 2014. "The Aircraft Maintenance Base Location Problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 634-642.
    10. Lu Chen & Boxiao Chen & Quoc Trung Bui & Minh Hoàng Hà, 2017. "Designing service sectors for daily maintenance operations in a road network," International Journal of Production Research, Taylor & Francis Journals, vol. 55(8), pages 2251-2265, April.
    11. Ouyang, Zhiyuan & Leung, Eric K.H. & Huang, George Q., 2023. "Community logistics and dynamic community partitioning: A new approach for solving e-commerce last mile delivery," European Journal of Operational Research, Elsevier, vol. 307(1), pages 140-156.
    12. Antonio Diglio & Stefan Nickel & Francisco Saldanha-da-Gama, 2020. "Towards a stochastic programming modeling framework for districting," Annals of Operations Research, Springer, vol. 292(1), pages 249-285, September.
    13. Jens Van Engeland & Jeroen Beliën, 2021. "Tactical waste collection: column generation and mixed integer programming based heuristics," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(1), pages 89-126, March.
    14. Cortinhal, Maria João & Mourão, Maria Cândida & Nunes, Ana Catarina, 2016. "Local search heuristics for sectoring routing in a household waste collection context," European Journal of Operational Research, Elsevier, vol. 255(1), pages 68-79.

    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. Alexander Butsch & Jörg Kalcsics & Gilbert Laporte, 2014. "Districting for Arc Routing," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 809-824, November.
    2. Rui Fragoso & Conceição Rego & Vladimir Bushenkov, 2016. "Clustering of Territorial Areas: A Multi-Criteria Districting Problem," Journal of Quantitative Economics, Springer;The Indian Econometric Society (TIES), vol. 14(2), pages 179-198, December.
    3. Hyun Kim & Yongwan Chun & Kamyoung Kim, 2015. "Delimitation of Functional Regions Using a p-Regions Problem Approach," International Regional Science Review, , vol. 38(3), pages 235-263, July.
    4. 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.
    5. Fernando Tavares-Pereira & José Figueira & Vincent Mousseau & Bernard Roy, 2007. "Multiple criteria districting problems," Annals of Operations Research, Springer, vol. 154(1), pages 69-92, October.
    6. Johannes Habel & Sascha Alavi & Nicolas Heinitz, 2023. "A theory of predictive sales analytics adoption," AMS Review, Springer;Academy of Marketing Science, vol. 13(1), pages 34-54, June.
    7. Jesica Armas & Peter Keenan & Angel A. Juan & Seán McGarraghy, 2019. "Solving large-scale time capacitated arc routing problems: from real-time heuristics to metaheuristics," Annals of Operations Research, Springer, vol. 273(1), pages 135-162, February.
    8. F Caro & T Shirabe & M Guignard & A Weintraub, 2004. "School redistricting: embedding GIS tools with integer programming," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(8), pages 836-849, August.
    9. 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.
    10. Fung, Richard Y.K. & Liu, Ran & Jiang, Zhibin, 2013. "A memetic algorithm for the open capacitated arc routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 53-67.
    11. Muyldermans, L. & Cattrysse, D. & Van Oudheusden, D. & Lotan, T., 2002. "Districting for salt spreading operations," European Journal of Operational Research, Elsevier, vol. 139(3), pages 521-532, June.
    12. Cortinhal, Maria João & Mourão, Maria Cândida & Nunes, Ana Catarina, 2016. "Local search heuristics for sectoring routing in a household waste collection context," European Journal of Operational Research, Elsevier, vol. 255(1), pages 68-79.
    13. Gilbert Laporte & Roberto Musmanno & Francesca Vocaturo, 2010. "An Adaptive Large Neighbourhood Search Heuristic for the Capacitated Arc-Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 44(1), pages 125-135, February.
    14. Han, Jialin & Hu, Yaoguang & Mao, Mingsong & Wan, Shuping, 2020. "A multi-objective districting problem applied to agricultural machinery maintenance service network," European Journal of Operational Research, Elsevier, vol. 287(3), pages 1120-1130.
    15. Maria da Conceição Rego & Rui Fragoso & Vladimir Bushenkov, 2014. "Clustering of Territorial Areas: A Multi-Criteria Districting Problem," ERSA conference papers ersa14p218, European Regional Science Association.
    16. Brian Lunday & Hanif Sherali & Kevin Lunday, 2012. "The coastal seaspace patrol sector design and allocation problem," Computational Management Science, Springer, vol. 9(4), pages 483-514, November.
    17. Mourao, Maria Candida & Amado, Ligia, 2005. "Heuristic method for a mixed capacitated arc routing problem: A refuse collection application," European Journal of Operational Research, Elsevier, vol. 160(1), pages 139-153, January.
    18. Ríos-Mercado, Roger Z. & López-Pérez, J. Fabián, 2013. "Commercial territory design planning with realignment and disjoint assignment requirements," Omega, Elsevier, vol. 41(3), pages 525-535.
    19. Constantino, Miguel & Gouveia, Luís & Mourão, Maria Cândida & Nunes, Ana Catarina, 2015. "The mixed capacitated arc routing problem with non-overlapping routes," European Journal of Operational Research, Elsevier, vol. 244(2), pages 445-456.
    20. Ram Gopalan & Steven O. Kimbrough & Frederic H. Murphy & Nicholas Quintus, 2013. "The Philadelphia Districting Contest: Designing Territories for City Council Based Upon the 2010 Census," Interfaces, INFORMS, vol. 43(5), pages 477-489, October.

    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:196:y:2009:i:3:p:856-868. 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.