IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v17y2009i2d10.1007_s10878-007-9109-x.html
   My bibliography  Save this article

An extension of the relaxation algorithm for solving a special case of capacitated arc routing problems

Author

Listed:
  • Saman Eskandarzadeh

    (University of Tehran)

  • Reza Tavakkoli-Moghaddam

    (University of Tehran)

  • Amir Azaron

    (Dalhousie University)

Abstract

In this paper, we propose an exact method for solving a special integer program associated with the classical capacitated arc routing problems (CARPs) called split demand arc routing problems (SDARP). This method is developed in the context of monotropic programming theory and bases a promising foundation for developing specialized algorithms in order to solve general integer programming problems. In particular, the proposed algorithm generalizes the relaxation algorithm developed by Tseng and Bertsekas (Math. Oper. Res. 12(4):569–596, 1987) for solving linear programming problems. This method can also be viewed as an alternative for the subgradient method for solving Lagrangian relaxed problems. Computational experiments show its high potential in terms of efficiency and goodness of solutions on standard test problems.

Suggested Citation

  • Saman Eskandarzadeh & Reza Tavakkoli-Moghaddam & Amir Azaron, 2009. "An extension of the relaxation algorithm for solving a special case of capacitated arc routing problems," Journal of Combinatorial Optimization, Springer, vol. 17(2), pages 214-234, February.
    • Handle: RePEc:spr:jcomop:v:17:y:2009:i:2:d:10.1007_s10878-007-9109-x
    DOI: 10.1007/s10878-007-9109-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-007-9109-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-007-9109-x?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. Gerard Sierksma & Gert Tijssen, 1998. "Routing helicopters for crew exchanges on off-shore locations," Annals of Operations Research, Springer, vol. 76(0), pages 261-286, January.
    2. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    3. Jin, Mingzhou & Liu, Kai & Bowden, Royce O., 2007. "A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem," International Journal of Production Economics, Elsevier, vol. 105(1), pages 228-242, January.
    4. Moshe Dror & Pierre Trudeau, 1989. "Savings by Split Delivery Routing," Transportation Science, INFORMS, vol. 23(2), pages 141-145, May.
    5. J. M. Belenguer & M. C. Martinez & E. Mota, 2000. "A Lower Bound for the Split Delivery Vehicle Routing Problem," Operations Research, INFORMS, vol. 48(5), pages 801-810, October.
    6. Moshe Dror & Pierre Trudeau, 1990. "Split delivery routing," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(3), pages 383-402, June.
    7. Paul Tseng & Dimitri P. Bertsekas, 1987. "Relaxation Methods for Linear Programs," Mathematics of Operations Research, INFORMS, vol. 12(4), pages 569-596, November.
    8. 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.
    Full references (including those not matched with items on IDEAS)

    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. Leonardo Berbotto & Sergio García & Francisco Nogales, 2014. "A Randomized Granular Tabu Search heuristic for the split delivery vehicle routing problem," Annals of Operations Research, Springer, vol. 222(1), pages 153-173, November.
    2. Guy Desaulniers, 2010. "Branch-and-Price-and-Cut for the Split-Delivery Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 58(1), pages 179-192, February.
    3. Jianli Shi & Jin Zhang & Kun Wang & Xin Fang, 2018. "Particle Swarm Optimization for Split Delivery Vehicle Routing Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(02), pages 1-42, April.
    4. Salani, Matteo & Vacca, Ilaria, 2011. "Branch and price for the vehicle routing problem with discrete split deliveries and time windows," European Journal of Operational Research, Elsevier, vol. 213(3), pages 470-477, September.
    5. Gizem Ozbaygin & Oya Karasan & Hande Yaman, 2018. "New exact solution approaches for the split delivery vehicle routing problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 85-115, March.
    6. C. Archetti & M. Bouchard & G. Desaulniers, 2011. "Enhanced Branch and Price and Cut for Vehicle Routing with Split Deliveries and Time Windows," Transportation Science, INFORMS, vol. 45(3), pages 285-298, August.
    7. Lin, Yen-Hung & Batta, Rajan & Rogerson, Peter A. & Blatt, Alan & Flanigan, Marie, 2011. "A logistics model for emergency supply of critical items in the aftermath of a disaster," Socio-Economic Planning Sciences, Elsevier, vol. 45(4), pages 132-145, December.
    8. Yugang Yu & Chengbin Chu & Haoxun Chen & Feng Chu, 2012. "Large scale stochastic inventory routing problems with split delivery and service level constraints," Annals of Operations Research, Springer, vol. 197(1), pages 135-158, August.
    9. C. Archetti & M. G. Speranza & A. Hertz, 2006. "A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem," Transportation Science, INFORMS, vol. 40(1), pages 64-73, February.
    10. Bortfeldt, Andreas & Yi, Junmin, 2020. "The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 282(2), pages 545-558.
    11. Yu, Mingzhu & Jin, Xin & Zhang, Zizhen & Qin, Hu & Lai, Qidong, 2019. "The split-delivery mixed capacitated arc-routing problem: Applications and a forest-based tabu search approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 132(C), pages 141-162.
    12. Nicola Bianchessi & Stefan Irnich, 2019. "Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 53(2), pages 442-462, March.
    13. Jin, Mingzhou & Liu, Kai & Bowden, Royce O., 2007. "A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem," International Journal of Production Economics, Elsevier, vol. 105(1), pages 228-242, January.
    14. Hertz, Alain & Uldry, Marc & Widmer, Marino, 2012. "Integer linear programming models for a cement delivery problem," European Journal of Operational Research, Elsevier, vol. 222(3), pages 623-631.
    15. Jeffrey W. Ohlmann & Michael J. Fry & Barrett W. Thomas, 2008. "Route Design for Lean Production Systems," Transportation Science, INFORMS, vol. 42(3), pages 352-370, August.
    16. Frank Hennig & Bjørn Nygreen & Marco E. Lübbecke, 2012. "Nested column generation applied to the crude oil tanker routing and scheduling problem with split pickup and split delivery," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(3‐4), pages 298-310, April.
    17. Claudia Archetti & Martin W. P. Savelsbergh & M. Grazia Speranza, 2006. "Worst-Case Analysis for Split Delivery Vehicle Routing Problems," Transportation Science, INFORMS, vol. 40(2), pages 226-234, May.
    18. Berbotto, Leonardo & García, Sergio & Nogales, Francisco J., 2011. "A vehicle routing model with split delivery and stop nodes," DES - Working Papers. Statistics and Econometrics. WS ws110906, Universidad Carlos III de Madrid. Departamento de Estadística.
    19. Han, Anthony Fu-Wha & Chu, Yu-Ching, 2016. "A multi-start heuristic approach for the split-delivery vehicle routing problem with minimum delivery amounts," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 11-31.
    20. Claudia Archetti & M. Grazia Speranza & Martin W. P. Savelsbergh, 2008. "An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem," Transportation Science, INFORMS, vol. 42(1), pages 22-31, February.

    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:spr:jcomop:v:17:y:2009:i:2:d:10.1007_s10878-007-9109-x. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.