IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v66y2017ipap79-90.html
   My bibliography  Save this article

Models and column generation approach for the resource-constrained minimum cost path problem with relays

Author

Listed:
  • Li, Xiangyong
  • Lin, Shaochong
  • Tian, Peng
  • Aneja, Y.P.

Abstract

In this paper, we introduce the resource-constrained minimum cost path problem with relays (RMCPR), which deals with multiple-resource constraint on the path with relays. The RMCPR consists of finding a path from a source to a destination, and locating relays on some nodes of the path, such that the total cost of setting arcs and relays is minimized, and for each resource, the total consumption between the source and the first relay, any two consecutive relays, and the last relay and the destination do not exceed a predefined upper bound of resource consumption. The RMCPR is a single-commodity resource-constrained network design problem with relays.

Suggested Citation

  • Li, Xiangyong & Lin, Shaochong & Tian, Peng & Aneja, Y.P., 2017. "Models and column generation approach for the resource-constrained minimum cost path problem with relays," Omega, Elsevier, vol. 66(PA), pages 79-90.
    • Handle: RePEc:eee:jomega:v:66:y:2017:i:pa:p:79-90
    DOI: 10.1016/j.omega.2016.01.012
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S030504831600013X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2016.01.012?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. Gianpaolo Ghiani & Gilbert Laporte & Frédéric Semet, 2006. "The Black and White Traveling Salesman Problem," Operations Research, INFORMS, vol. 54(2), pages 366-378, April.
    2. Vanderbeck, F. & Wolsey, L. A., 1996. "An exact algorithm for IP column generation," LIDAM Reprints CORE 1242, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Li, Xiangyong & Aneja, Y.P. & Huo, Jiazhen, 2012. "Using branch-and-price approach to solve the directed network design problem with relays," Omega, Elsevier, vol. 40(5), pages 672-679.
    4. Formaneck, Steven D. & Cozzarin, Brian P., 2013. "Technology adoption and training practices as a constrained shortest path problem," Omega, Elsevier, vol. 41(2), pages 459-472.
    5. Cabral, Edgar Alberto & Erkut, Erhan & Laporte, Gilbert & Patterson, Raymond A., 2007. "The network design problem with relays," European Journal of Operational Research, Elsevier, vol. 180(2), pages 834-844, July.
    6. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    7. Mirela Stojković & François Soumis & Jacques Desrosiers, 1998. "The Operational Airline Crew Scheduling Problem," Transportation Science, INFORMS, vol. 32(3), pages 232-245, August.
    8. Michel Gamache & François Soumis & Gérald Marquis & Jacques Desrosiers, 1999. "A Column Generation Approach for Large-Scale Aircrew Rostering Problems," Operations Research, INFORMS, vol. 47(2), pages 247-263, April.
    9. Santos, Luis & Coutinho-Rodrigues, João & Current, John R., 2007. "An improved solution algorithm for the constrained shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 41(7), pages 756-771, August.
    10. Ulrich Derigs & Stefan Friederichs & Simon Schäfer, 2009. "A New Approach for Air Cargo Network Planning," Transportation Science, INFORMS, vol. 43(3), pages 370-380, August.
    11. Halit Üster & Panitan Kewcharoenwong, 2011. "Strategic Design and Analysis of a Relay Network in Truckload Transportation," Transportation Science, INFORMS, vol. 45(4), pages 505-523, November.
    12. Zhu, Xiaoyan & Wilhelm, Wilbert E., 2007. "Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context," European Journal of Operational Research, Elsevier, vol. 183(2), pages 564-577, December.
    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. Zhang, Yue & Feng, Qiang & Fan, Dongming & Ren, Yi & Sun, Bo & Yang, Dezhen & Wang, Zili, 2023. "Optimization of maritime support network with relays under uncertainty: A novel matheuristics method," Reliability Engineering and System Safety, Elsevier, vol. 232(C).
    2. Blanco, Víctor & González, Gabriel & Hinojosa, Yolanda & Ponce, Diego & Pozo, Miguel A. & Puerto, Justo, 2022. "Network flow based approaches for the pipelines routing problem in naval design," Omega, Elsevier, vol. 111(C).
    3. Li, Xiangyong & Ding, Yi & Pan, Kai & Jiang, Dapei & Aneja, Y.P., 2020. "Single-path service network design problem with resource constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    4. Kewcharoenwong, Panitan & Li, Qiaofeng & Üster, Halit, 2023. "Lagrangean relaxation algorithms for fixed-charge capacitated relay network design," Omega, Elsevier, vol. 121(C).

    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. Yiyong Xiao & Abdullah Konak, 2017. "A variable neighborhood search for the network design problem with relays," Journal of Heuristics, Springer, vol. 23(2), pages 137-164, June.
    2. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    3. Barış Yıldız & Oya Ekin Karaşan, 2017. "Regenerator Location Problem in Flexible Optical Networks," Operations Research, INFORMS, vol. 65(3), pages 595-620, June.
    4. Wang, Li & Yang, Lixing & Gao, Ziyou, 2016. "The constrained shortest path problem with stochastic correlated link travel times," European Journal of Operational Research, Elsevier, vol. 255(1), pages 43-57.
    5. Kewcharoenwong, Panitan & Li, Qiaofeng & Üster, Halit, 2023. "Lagrangean relaxation algorithms for fixed-charge capacitated relay network design," Omega, Elsevier, vol. 121(C).
    6. Markus Leitner & Ivana Ljubić & Martin Riedler & Mario Ruthmair, 2019. "Exact Approaches for Network Design Problems with Relays," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 171-192, February.
    7. Maenhout, Broos & Vanhoucke, Mario, 2010. "A hybrid scatter search heuristic for personalized crew rostering in the airline industry," European Journal of Operational Research, Elsevier, vol. 206(1), pages 155-167, October.
    8. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    9. Fei, Hongying & Meskens, Nadine & Combes, Catherine & Chu, Chengbin, 2009. "The endoscopy scheduling problem: A case study with two specialised operating rooms," International Journal of Production Economics, Elsevier, vol. 120(2), pages 452-462, August.
    10. Konak, Abdullah, 2012. "Network design problem with relays: A genetic algorithm with a path-based crossover and a set covering formulation," European Journal of Operational Research, Elsevier, vol. 218(3), pages 829-837.
    11. Syam Menon & Rakesh Gupta, 2008. "Optimal Broadcast Scheduling in Packet Radio Networks via Branch and Price," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 391-399, August.
    12. Beraudy, Sébastien & Absi, Nabil & Dauzère-Pérès, Stéphane, 2022. "Timed route approaches for large multi-product multi-step capacitated production planning problems," European Journal of Operational Research, Elsevier, vol. 300(2), pages 602-614.
    13. Andrew Allman & Qi Zhang, 2021. "Branch-and-price for a class of nonconvex mixed-integer nonlinear programs," Journal of Global Optimization, Springer, vol. 81(4), pages 861-880, December.
    14. Xue, Li & Luo, Zhixing & Lim, Andrew, 2016. "Exact approaches for the pickup and delivery problem with loading cost," Omega, Elsevier, vol. 59(PB), pages 131-145.
    15. Cynthia Barnhart & Christopher A. Hane & Pamela H. Vance, 2000. "Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems," Operations Research, INFORMS, vol. 48(2), pages 318-326, April.
    16. Ioachim, Irina & Desrosiers, Jacques & Soumis, Francois & Belanger, Nicolas, 1999. "Fleet assignment and routing with schedule synchronization constraints," European Journal of Operational Research, Elsevier, vol. 119(1), pages 75-90, November.
    17. Hu, Qian & Zhu, Wenbin & Qin, Hu & Lim, Andrew, 2017. "A branch-and-price algorithm for the two-dimensional vector packing problem with piecewise linear cost function," European Journal of Operational Research, Elsevier, vol. 260(1), pages 70-80.
    18. Degraeve, Z. & Jans, R.F., 2003. "A New Dantzig-Wolfe Reformulation And Branch-And-Price Algorithm For The Capacitated Lot Sizing Problem With Set Up Times," ERIM Report Series Research in Management ERS-2003-010-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    19. Vedat Bayram & Hande Yaman, 2018. "Shelter Location and Evacuation Route Assignment Under Uncertainty: A Benders Decomposition Approach," Transportation Science, INFORMS, vol. 52(2), pages 416-436, March.
    20. Louis-Philippe Bigras & Michel Gamache & Gilles Savard, 2008. "Time-Indexed Formulations and the Total Weighted Tardiness Problem," INFORMS Journal on Computing, INFORMS, vol. 20(1), pages 133-142, 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:eee:jomega:v:66:y:2017:i:pa:p:79-90. 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/wps/find/journaldescription.cws_home/375/description#description .

    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.