IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v65y2018i1p78-85.html
   My bibliography  Save this article

Simple paths with exact and forbidden lengths

Author

Listed:
  • Alexandre Dolgui
  • Mikhail Y. Kovalyov
  • Alain Quilliot

Abstract

We study new decision and optimization problems of finding a simple path between two given vertices in an arc weighted directed multigraph such that the path length is equal to a given number or it does not fall into the given forbidden intervals (gaps). A fairly complete computational complexity classification is provided and exact and approximation algorithms are suggested.

Suggested Citation

  • Alexandre Dolgui & Mikhail Y. Kovalyov & Alain Quilliot, 2018. "Simple paths with exact and forbidden lengths," Naval Research Logistics (NRL), John Wiley & Sons, vol. 65(1), pages 78-85, February.
    • Handle: RePEc:wly:navres:v:65:y:2018:i:1:p:78-85
    DOI: 10.1002/nav.21783
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.21783
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.21783?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. Peter Brucker & Mikhail Kovalyov & Yakov Shafransky & Frank Werner, 1998. "Batch scheduling with deadlines on parallel machines," Annals of Operations Research, Springer, vol. 83(0), pages 23-40, October.
    2. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation Science, INFORMS, vol. 39(1), pages 104-118, February.
    3. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    4. Arthur Warburton, 1987. "Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems," Operations Research, INFORMS, vol. 35(1), pages 70-79, February.
    5. Refael Hassin, 1992. "Approximation Schemes for the Restricted Shortest Path Problem," Mathematics of Operations Research, INFORMS, vol. 17(1), pages 36-42, February.
    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. Soriano, Adria & Vidal, Thibaut & Gansterer, Margaretha & Doerner, Karl, 2020. "The vehicle routing problem with arrival time diversification on a multigraph," European Journal of Operational Research, Elsevier, vol. 286(2), pages 564-575.

    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. Asbach, Lasse & Dorndorf, Ulrich & Pesch, Erwin, 2009. "Analysis, modeling and solution of the concrete delivery problem," European Journal of Operational Research, Elsevier, vol. 193(3), pages 820-835, March.
    2. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    3. Gerhard Hiermann & Matthias Prandtstetter & Andrea Rendl & Jakob Puchinger & Günther Raidl, 2015. "Metaheuristics for solving a multimodal home-healthcare scheduling problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 23(1), pages 89-113, March.
    4. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    5. Ullrich, Christian A., 2013. "Integrated machine scheduling and vehicle routing with time windows," European Journal of Operational Research, Elsevier, vol. 227(1), pages 152-165.
    6. Qi, Mingyao & Lin, Wei-Hua & Li, Nan & Miao, Lixin, 2012. "A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 248-257.
    7. Zhiping Zuo & Yanhui Li & Jing Fu & Jianlin Wu, 2019. "Human Resource Scheduling Model and Algorithm with Time Windows and Multi-Skill Constraints," Mathematics, MDPI, vol. 7(7), pages 1-18, July.
    8. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    9. Ulrike Ritzinger & Jakob Puchinger & Richard Hartl, 2016. "Dynamic programming based metaheuristics for the dial-a-ride problem," Annals of Operations Research, Springer, vol. 236(2), pages 341-358, January.
    10. John E. Fontecha & Oscar O. Guaje & Daniel Duque & Raha Akhavan-Tabatabaei & Juan P. Rodríguez & Andrés L. Medaglia, 2020. "Combined maintenance and routing optimization for large-scale sewage cleaning," Annals of Operations Research, Springer, vol. 286(1), pages 441-474, March.
    11. Subramanyam, Anirudh & Wang, Akang & Gounaris, Chrysanthos E., 2018. "A scenario decomposition algorithm for strategic time window assignment vehicle routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 296-317.
    12. Mohammad Torkjazi & Nathan Huynh, 2019. "Effectiveness of Dynamic Insertion Scheduling Strategy for Demand-Responsive Paratransit Vehicles Using Agent-Based Simulation," Sustainability, MDPI, vol. 11(19), pages 1-12, September.
    13. Julia Rieck & Jürgen Zimmermann, 2010. "A new mixed integer linear model for a rich vehicle routing problem with docking constraints," Annals of Operations Research, Springer, vol. 181(1), pages 337-358, December.
    14. Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2021. "A large neighborhood search approach to the vehicle routing problem with delivery options," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 103-132.
    15. Randeep Bhatia & Sudipto Guha & Samir Khuller & Yoram J. Sussmann, 1998. "Facility Location with Dynamic Distance Functions," Journal of Combinatorial Optimization, Springer, vol. 2(3), pages 199-217, September.
    16. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    17. Ehmke, Jan Fabian & Campbell, Ann Melissa, 2014. "Customer acceptance mechanisms for home deliveries in metropolitan areas," European Journal of Operational Research, Elsevier, vol. 233(1), pages 193-207.
    18. Koch, Sebastian & Klein, Robert, 2020. "Route-based approximate dynamic programming for dynamic pricing in attended home delivery," European Journal of Operational Research, Elsevier, vol. 287(2), pages 633-652.
    19. Taş, D. & Gendreau, M. & Dellaert, N. & van Woensel, T. & de Kok, A.G., 2014. "Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach," European Journal of Operational Research, Elsevier, vol. 236(3), pages 789-799.
    20. Zajac, Sandra & Huber, Sandra, 2021. "Objectives and methods in multi-objective routing problems: a survey and classification scheme," European Journal of Operational Research, Elsevier, vol. 290(1), pages 1-25.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:65:y:2018:i:1:p:78-85. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.