IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v48y2014i3p442-457.html
   My bibliography  Save this article

The Team Orienteering Arc Routing Problem

Author

Listed:
  • Claudia Archetti

    (Dipartimento Metodi Quantitativi, Universitá di Brescia, 25122 Brescia, Province of Brescia, Italy)

  • M. Grazia Speranza

    (Dipartimento Metodi Quantitativi, Universitá di Brescia, 25122 Brescia, Province of Brescia, Italy)

  • Ángel Corberán

    (Departamento de Estadística e Investigación Operativa, Universidad de Valencia, 46010 Valencia, Spain)

  • José M. Sanchis

    (Departamento de Matemática Aplicada, Universidad Politécnica de Valencia, 46022 Valencia, Spain)

  • Isaac Plana

    (Departamento Matemáticas para la Economía y la Empresa, Universidad de Valencia, 46010 Valencia, Spain)

Abstract

The team orienteering arc routing problem (TOARP) is the extension to the arc routing setting of the team orienteering problem. In the TOARP, in addition to a possible set of regular customers that have to be serviced, another set of potential customers is available. Each customer is associated with an arc of a directed graph. Each potential customer has a profit that is collected when it is serviced, that is, when the associated arc is traversed. A fleet of vehicles with a given maximum traveling time is available. The profit from a customer can be collected by one vehicle at most. The objective is to identify the customers that maximize the total profit collected while satisfying the given time limit for each vehicle.In this paper we propose a formulation for this problem and study a relaxation of its associated polyhedron. We present some families of valid and facet-inducing inequalities that we use in the implementation of a branch-and-cut algorithm for the resolution of the problem. Computational experiments are run on a large set of benchmark instances.

Suggested Citation

  • Claudia Archetti & M. Grazia Speranza & Ángel Corberán & José M. Sanchis & Isaac Plana, 2014. "The Team Orienteering Arc Routing Problem," Transportation Science, INFORMS, vol. 48(3), pages 442-457, August.
    • Handle: RePEc:inm:ortrsc:v:48:y:2014:i:3:p:442-457
    DOI: 10.1287/trsc.2013.0484
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.2013.0484
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2013.0484?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
    ---><---

    References listed on IDEAS

    as
    1. Malandraki, Chryssi & Daskin, Mark S., 1993. "The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 65(2), pages 218-234, March.
    2. Alain Hertz & Gilbert Laporte & Pierrette Nanchen Hugo, 1999. "Improvement Procedures for the Undirected Rural Postman Problem," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 53-62, February.
    3. Aráoz, Julián & Fernández, Elena & Meza, Oscar, 2009. "Solving the Prize-collecting Rural Postman Problem," European Journal of Operational Research, Elsevier, vol. 196(3), pages 886-896, August.
    4. Vansteenwegen, Pieter & Souffriau, Wouter & Oudheusden, Dirk Van, 2011. "The orienteering problem: A survey," European Journal of Operational Research, Elsevier, vol. 209(1), pages 1-10, February.
    5. Ángel Corberán & Elena Fernández & Carles Franquesa & José María Sanchis, 2011. "The Windy Clustered Prize-Collecting Arc-Routing Problem," Transportation Science, INFORMS, vol. 45(3), pages 317-334, August.
    6. Julián Aráoz & Elena Fernández & Carles Franquesa, 2009. "The Clustered Prize-Collecting Arc Routing Problem," Transportation Science, INFORMS, vol. 43(3), pages 287-300, August.
    7. Letchford, Adam N., 1997. "New inequalities for the General Routing Problem," European Journal of Operational Research, Elsevier, vol. 96(2), pages 317-322, January.
    8. Pearn, W. L. & Wang, K. H., 2003. "On the Maximum Benefit Chinese Postman Problem," Omega, Elsevier, vol. 31(4), pages 269-273, August.
    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. Ávila, Thais & Corberán, Ángel & Plana, Isaac & Sanchis, José M., 2016. "A branch-and-cut algorithm for the profitable windy rural postman problem," European Journal of Operational Research, Elsevier, vol. 249(3), pages 1092-1101.
    2. Archetti, Claudia & Bertazzi, Luca & Laganà, Demetrio & Vocaturo, Francesca, 2017. "The Undirected Capacitated General Routing Problem with Profits," European Journal of Operational Research, Elsevier, vol. 257(3), pages 822-833.
    3. Ferreira, Reinaldo & Móra, Vasco & Mourão, Maria Cândida & Moz, Margarida & Pinto, Leonor S. & Ribeiro, João, 2022. "Arc Routing for Parking Enforcement Officers: Exact and heuristic solutions," European Journal of Operational Research, Elsevier, vol. 299(1), pages 283-301.
    4. Mostafa Khorramizadeh & Roghayeh Javvi, 2024. "A branch-and-cut algorithm for the windy profitable location rural postman problem," Annals of Operations Research, Springer, vol. 341(2), pages 993-1022, October.
    5. Oruc, Buse Eylul & Kara, Bahar Yetis, 2018. "Post-disaster assessment routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 116(C), pages 76-102.
    6. Kobeaga, Gorka & Rojas-Delgado, Jairo & Merino, María & Lozano, Jose A., 2024. "A revisited branch-and-cut algorithm for large-scale orienteering problems," European Journal of Operational Research, Elsevier, vol. 313(1), pages 44-68.
    7. Li, Yuan & Chen, Haoxun & Prins, Christian, 2016. "Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests," European Journal of Operational Research, Elsevier, vol. 252(1), pages 27-38.
    8. Archetti, Claudia & Corberán, Ángel & Plana, Isaac & Sanchis, José Maria & Speranza, M. Grazia, 2015. "A matheuristic for the Team Orienteering Arc Routing Problem," European Journal of Operational Research, Elsevier, vol. 245(2), pages 392-401.
    9. Riera-Ledesma, Jorge & Salazar-González, Juan José, 2017. "Solving the Team Orienteering Arc Routing Problem with a column generation approach," European Journal of Operational Research, Elsevier, vol. 262(1), pages 14-27.
    10. Gunawan, Aldy & Lau, Hoong Chuin & Vansteenwegen, Pieter, 2016. "Orienteering Problem: A survey of recent variants, solution approaches and applications," European Journal of Operational Research, Elsevier, vol. 255(2), pages 315-332.
    11. Xia, Jun & Wang, Kai & Wang, Shuaian, 2019. "Drone scheduling to monitor vessels in emission control areas," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 174-196.
    12. Zhang, Guowei & Jia, Ning & Zhu, Ning & Adulyasak, Yossiri & Ma, Shoufeng, 2023. "Robust drone selective routing in humanitarian transportation network assessment," European Journal of Operational Research, Elsevier, vol. 305(1), pages 400-428.

    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. Enrique Benavent & Ángel Corberán & Luís Gouveia & Maria Mourão & Leonor Pinto, 2015. "Profitable mixed capacitated arc routing and related problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(1), pages 244-274, April.
    2. Ávila, Thais & Corberán, Ángel & Plana, Isaac & Sanchis, José M., 2016. "A branch-and-cut algorithm for the profitable windy rural postman problem," European Journal of Operational Research, Elsevier, vol. 249(3), pages 1092-1101.
    3. Colombi, Marco & Corberán, Ángel & Mansini, Renata & Plana, Isaac & Sanchis, José M., 2017. "The directed profitable rural postman problem with incompatibility constraints," European Journal of Operational Research, Elsevier, vol. 261(2), pages 549-562.
    4. Elena Fernández & Jessica Rodríguez-Pereira, 2017. "Multi-depot rural postman problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(2), pages 340-372, July.
    5. Archetti, Claudia & Bertazzi, Luca & Laganà, Demetrio & Vocaturo, Francesca, 2017. "The Undirected Capacitated General Routing Problem with Profits," European Journal of Operational Research, Elsevier, vol. 257(3), pages 822-833.
    6. 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.
    7. Colombi, Marco & Mansini, Renata, 2014. "New results for the Directed Profitable Rural Postman Problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 760-773.
    8. Ángel Corberán & Elena Fernández & Carles Franquesa & José María Sanchis, 2011. "The Windy Clustered Prize-Collecting Arc-Routing Problem," Transportation Science, INFORMS, vol. 45(3), pages 317-334, August.
    9. Rodríguez-Pereira, Jessica & Fernández, Elena & Laporte, Gilbert & Benavent, Enrique & Martínez-Sykora, Antonio, 2019. "The Steiner Traveling Salesman Problem and its extensions," European Journal of Operational Research, Elsevier, vol. 278(2), pages 615-628.
    10. Summerfield, Nichalin S. & Dror, Moshe & Cohen, Morris A., 2015. "City streets parking enforcement inspection decisions: The Chinese postman’s perspective," European Journal of Operational Research, Elsevier, vol. 242(1), pages 149-160.
    11. Elena Fernández & Gilbert Laporte & Jessica Rodríguez-Pereira, 2018. "A Branch-and-Cut Algorithm for the Multidepot Rural Postman Problem," Transportation Science, INFORMS, vol. 52(2), pages 353-369, March.
    12. Arbib, Claudio & Servilio, Mara & Archetti, Claudia & Speranza, M. Grazia, 2014. "The directed profitable location Rural Postman Problem," European Journal of Operational Research, Elsevier, vol. 236(3), pages 811-819.
    13. Archetti, Claudia & Corberán, Ángel & Plana, Isaac & Sanchis, José Maria & Speranza, M. Grazia, 2015. "A matheuristic for the Team Orienteering Arc Routing Problem," European Journal of Operational Research, Elsevier, vol. 245(2), pages 392-401.
    14. 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.
    15. Jessica Rodríguez-Pereira & Gilbert Laporte, 2022. "The target visitation arc routing problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 60-76, April.
    16. Orlis, Christos & Laganá, Demetrio & Dullaert, Wout & Vigo, Daniele, 2020. "Distribution with Quality of Service Considerations: The Capacitated Routing Problem with Profits and Service Level Requirements," Omega, Elsevier, vol. 93(C).
    17. Elena Fernández & Oscar Meza & Robert Garfinkel & Maruja Ortega, 2003. "On the Undirected Rural Postman Problem: Tight Bounds Based on a New Formulation," Operations Research, INFORMS, vol. 51(2), pages 281-291, April.
    18. Riera-Ledesma, Jorge & Salazar-González, Juan José, 2017. "Solving the Team Orienteering Arc Routing Problem with a column generation approach," European Journal of Operational Research, Elsevier, vol. 262(1), pages 14-27.
    19. Dang, Duc-Cuong & Guibadj, Rym Nesrine & Moukrim, Aziz, 2013. "An effective PSO-inspired algorithm for the team orienteering problem," European Journal of Operational Research, Elsevier, vol. 229(2), pages 332-344.
    20. Fernández, Elena & Roca-Riu, Mireia & Speranza, M. Grazia, 2018. "The Shared Customer Collaboration Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 265(3), pages 1078-1093.

    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:inm:ortrsc:v:48:y:2014:i:3:p:442-457. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.