IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v157y2008i1p153-16710.1007-s10479-007-0252-7.html
   My bibliography  Save this article

A multi-stop routing problem

Author

Listed:
  • Jose Gonzalez-Velarde
  • Salvador Garcia-Lumbreras
  • Alberto Garcia-Diaz

Abstract

The problem of determining the sequence of stops and the amount of load to carry in each segment route, named the Multi-Stop Routing Problem (MSRP) is addressed. A 0/1 mixed integer linear program and formulation refinements which facilitate the solution process are presented. Since the constraint set of the MSRP includes 0/1 mixed rows, valid inequalities for this type of regions are presented. Then these results are applied to the constraint set of the routing problem, presenting additional valid inequalities. In addition, polynomial separation algorithms associated with the valid inequalities are given, computational results are also included. Copyright Springer Science+Business Media, LLC 2008

Suggested Citation

  • Jose Gonzalez-Velarde & Salvador Garcia-Lumbreras & Alberto Garcia-Diaz, 2008. "A multi-stop routing problem," Annals of Operations Research, Springer, vol. 157(1), pages 153-167, January.
    • Handle: RePEc:spr:annopr:v:157:y:2008:i:1:p:153-167:10.1007/s10479-007-0252-7
    DOI: 10.1007/s10479-007-0252-7
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-007-0252-7
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-007-0252-7?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. Robert Richardson, 1976. "An Optimization Approach to Routing Aircraft," Transportation Science, INFORMS, vol. 10(1), pages 52-71, February.
    2. Merrill M. Flood, 1956. "The Traveling-Salesman Problem," Operations Research, INFORMS, vol. 4(1), pages 61-75, February.
    3. J Pacheco & R Martí, 2006. "Tabu search for a multi-objective routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(1), pages 29-37, January.
    4. Keng Hoo Chuah & Jon C. Yingling, 2005. "Routing for a Just-in-Time Supply Pickup and Delivery System," Transportation Science, INFORMS, vol. 39(3), pages 328-339, August.
    5. Kai Gutenschwager & Christian Niklaus & Stefan Voß, 2004. "Dispatching of an Electric Monorail System: Applying Metaheuristics to an Online Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 38(4), pages 434-446, November.
    6. A Corberán & E Fernández & M Laguna & R Martí, 2002. "Heuristic solutions to the problem of routing school buses with multiple objectives," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(4), pages 427-435, April.
    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. Nicolas Jozefowiez & Gilbert Laporte & Frédéric Semet, 2012. "A Generic Branch-and-Cut Algorithm for Multiobjective Optimization Problems: Application to the Multilabel Traveling Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 554-564, November.
    2. Ellegood, William A. & Campbell, James F. & North, Jeremy, 2015. "Continuous approximation models for mixed load school bus routing," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 182-198.
    3. Joaquín Pacheco & Rafael Caballero & Manuel Laguna & Julián Molina, 2013. "Bi-Objective Bus Routing: An Application to School Buses in Rural Areas," Transportation Science, INFORMS, vol. 47(3), pages 397-411, August.
    4. Wang, Zhongxiang & Haghani, Ali, 2020. "Column generation-based stochastic school bell time and bus scheduling optimization," European Journal of Operational Research, Elsevier, vol. 286(3), pages 1087-1102.
    5. C Alabas-Uslu, 2008. "A self-tuning heuristic for a multi-objective vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(7), pages 988-996, July.
    6. Fátima M. Souza Lima & Davi S. D. Pereira & Samuel V. Conceição & Ricardo S. Camargo, 2017. "A multi-objective capacitated rural school bus routing problem with heterogeneous fleet and mixed loads," 4OR, Springer, vol. 15(4), pages 359-386, December.
    7. Huasheng Liu & Yuqi Zhao & Jin Li & Yu Li & Xiaowen Li & Sha Yang, 2022. "A Two-Phase, Joint-Commuting Model for Primary and Secondary Schools Considering Parking Sharing," IJERPH, MDPI, vol. 19(11), pages 1-25, May.
    8. Ellegood, William A. & Solomon, Stanislaus & North, Jeremy & Campbell, James F., 2020. "School bus routing problem: Contemporary trends and research directions," Omega, Elsevier, vol. 95(C).
    9. Shafahi, Ali & Wang, Zhongxiang & Haghani, Ali, 2018. "SpeedRoute: Fast, efficient solutions for school bus routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 473-493.
    10. P. Matl & R. F. Hartl & T. Vidal, 2018. "Workload Equity in Vehicle Routing Problems: A Survey and Analysis," Transportation Science, INFORMS, vol. 52(2), pages 239-260, March.
    11. Gutierrez, Genaro J. & Kouvelis, Panagiotis & Kurawarwala, Abbas A., 1996. "A robustness approach to uncapacitated network design problems," European Journal of Operational Research, Elsevier, vol. 94(2), pages 362-376, October.
    12. Neves-Moreira, Fábio & Almada-Lobo, Bernardo & Guimarães, Luís & Amorim, Pedro, 2022. "The multi-product inventory-routing problem with pickups and deliveries: Mitigating fluctuating demand via rolling horizon heuristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    13. 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.
    14. Marti, Rafael, 2006. "Scatter Search--Wellsprings and Challenges," European Journal of Operational Research, Elsevier, vol. 169(2), pages 351-358, March.
    15. Timo Gschwind & Stefan Irnich & Simon Emde & Christian Tilk, 2018. "Branch-Cut-and-Price for the Scheduling Deliveries with Time Windows in a Direct Shipping Network," Working Papers 1805, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    16. Fügenschuh, Armin, 2009. "Solving a school bus scheduling problem with integer programming," European Journal of Operational Research, Elsevier, vol. 193(3), pages 867-884, March.
    17. Shaza Hanif & Shahab Ud Din & Ning Gui & Tom Holvoet, 2023. "Multiagent Coordination and Teamwork: A Case Study for Large-Scale Dynamic Ready-Mixed Concrete Delivery Problem," Mathematics, MDPI, vol. 11(19), pages 1-25, September.
    18. Meyer, Anne & Amberg, Boris, 2018. "Transport concept selection considering supplier milk runs – An integrated model and a case study from the automotive industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 113(C), pages 147-169.
    19. Herer, Yale T., 1999. "Submodularity and the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 114(3), pages 489-508, May.
    20. Hernan Caceres & Rajan Batta & Qing He, 2017. "School Bus Routing with Stochastic Demand and Duration Constraints," Transportation Science, INFORMS, vol. 51(4), pages 1349-1364, November.

    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:annopr:v:157:y:2008:i:1:p:153-167:10.1007/s10479-007-0252-7. 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.