IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v166y2015i1d10.1007_s10957-014-0638-z.html
   My bibliography  Save this article

Solution Approaches for the Stochastic Capacitated Traveling Salesmen Location Problem with Recourse

Author

Listed:
  • Luca Bertazzi

    (University of Brescia)

  • Francesca Maggioni

    (University of Bergamo)

Abstract

A facility has to be located in a given area to serve a given number of customers. The position of the customers is not known. The service to the customers is carried out by several traveling salesmen. Each of them has a capacity in terms of the maximum number of customers that can be served in any tour. The aim was to determine the service zone (in a shape of a circle) that minimizes the expected cost of the traveled routes. The center of the circle is the location of the facility. Once the position of the customers is revealed, the customers located outside the service zone are served with a recourse action at a greater unit cost. For this problem, we compare the performance of two different solution approaches. The first is based on a heuristic proposed for the Capacitated Traveling Salesman Problem and the second on the optimal solution of a stochastic second-order cone formulation with an approximate objective function.

Suggested Citation

  • Luca Bertazzi & Francesca Maggioni, 2015. "Solution Approaches for the Stochastic Capacitated Traveling Salesmen Location Problem with Recourse," Journal of Optimization Theory and Applications, Springer, vol. 166(1), pages 321-342, July.
    • Handle: RePEc:spr:joptap:v:166:y:2015:i:1:d:10.1007_s10957-014-0638-z
    DOI: 10.1007/s10957-014-0638-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-014-0638-z
    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/s10957-014-0638-z?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. Klose, Andreas & Drexl, Andreas, 2005. "Facility location models for distribution system design," European Journal of Operational Research, Elsevier, vol. 162(1), pages 4-29, April.
    2. Dimitris J. Bertsimas, 1989. "Traveling Salesman Facility Location Problems," Transportation Science, INFORMS, vol. 23(3), pages 184-191, August.
    3. Melo, M.T. & Nickel, S. & Saldanha-da-Gama, F., 2009. "Facility location and supply chain management - A review," European Journal of Operational Research, Elsevier, vol. 196(2), pages 401-412, July.
    4. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    5. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    6. Santoso, Tjendera & Ahmed, Shabbir & Goetschalckx, Marc & Shapiro, Alexander, 2005. "A stochastic programming approach for supply chain network design under uncertainty," European Journal of Operational Research, Elsevier, vol. 167(1), pages 96-115, November.
    7. Walid Klibi & Francis Lasalle & Alain Martel & Soumia Ichoua, 2010. "The Stochastic Multiperiod Location Transportation Problem," Transportation Science, INFORMS, vol. 44(2), pages 221-237, May.
    8. ReVelle, C. S. & Eiselt, H. A., 2005. "Location analysis: A synthesis and survey," European Journal of Operational Research, Elsevier, vol. 165(1), pages 1-19, August.
    9. F. Maggioni & F. A. Potra & M. I. Bertocchi & E. Allevi, 2009. "Stochastic Second-Order Cone Programming in Mobile Ad Hoc Networks," Journal of Optimization Theory and Applications, Springer, vol. 143(2), pages 309-328, November.
    10. David Simchi-Levi, 1991. "The Capacitated Traveling Salesman Location Problem," Transportation Science, INFORMS, vol. 25(1), pages 9-18, February.
    11. Carlos F. Daganzo, 1984. "The Distance Traveled to Visit N Points with a Maximum of C Stops per Vehicle: An Analytic Model and an Application," Transportation Science, INFORMS, vol. 18(4), pages 331-350, November.
    12. Robert C. Burness & John A. White, 1976. "The Traveling Salesman Location Problem," Transportation Science, INFORMS, vol. 10(4), pages 348-360, November.
    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. Baha Alzalg, 2016. "The Algebraic Structure of the Arbitrary-Order Cone," Journal of Optimization Theory and Applications, Springer, vol. 169(1), pages 32-49, April.
    2. Elgesem, Aurora Smith & Skogen, Eline Sophie & Wang, Xin & Fagerholt, Kjetil, 2018. "A traveling salesman problem with pickups and deliveries and stochastic travel times: An application from chemical shipping," European Journal of Operational Research, Elsevier, vol. 269(3), pages 844-859.

    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. Ben Mohamed, Imen & Klibi, Walid & Sadykov, Ruslan & Şen, Halil & Vanderbeck, François, 2023. "The two-echelon stochastic multi-period capacitated location-routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 645-667.
    2. Klibi, Walid & Martel, Alain & Guitouni, Adel, 2016. "The impact of operations anticipations on the quality of stochastic location-allocation models," Omega, Elsevier, vol. 62(C), pages 19-33.
    3. Walther, Grit & Schatka, Anne & Spengler, Thomas S., 2012. "Design of regional production networks for second generation synthetic bio-fuel – A case study in Northern Germany," European Journal of Operational Research, Elsevier, vol. 218(1), pages 280-292.
    4. Walid Klibi & Francis Lasalle & Alain Martel & Soumia Ichoua, 2010. "The Stochastic Multiperiod Location Transportation Problem," Transportation Science, INFORMS, vol. 44(2), pages 221-237, May.
    5. Kress, Dominik & Pesch, Erwin, 2012. "Sequential competitive location on networks," European Journal of Operational Research, Elsevier, vol. 217(3), pages 483-499.
    6. Mestre, Ana Maria & Oliveira, Mónica Duarte & Barbosa-Póvoa, Ana Paula, 2015. "Location–allocation approaches for hospital network planning under uncertainty," European Journal of Operational Research, Elsevier, vol. 240(3), pages 791-806.
    7. Weijun Xie & Yanfeng Ouyang & Sze Chun Wong, 2016. "Reliable Location-Routing Design Under Probabilistic Facility Disruptions," Transportation Science, INFORMS, vol. 50(3), pages 1128-1138, August.
    8. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    9. Denise D. Tönissen & Joachim J. Arts & Zuo-Jun (Max) Shen, 2019. "Maintenance Location Routing for Rolling Stock Under Line and Fleet Planning Uncertainty," Transportation Science, INFORMS, vol. 53(5), pages 1252-1270, September.
    10. Ansari, Sina & Başdere, Mehmet & Li, Xiaopeng & Ouyang, Yanfeng & Smilowitz, Karen, 2018. "Advancements in continuous approximation models for logistics and transportation systems: 1996–2016," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 229-252.
    11. Schuster Puga, Matías & Minner, Stefan & Tancrez, Jean-Sébastien, 2019. "Two-stage supply chain design with safety stock placement decisions," International Journal of Production Economics, Elsevier, vol. 209(C), pages 183-193.
    12. Menezes, Mozart B.C. & Ruiz-Hernández, Diego & Verter, Vedat, 2016. "A rough-cut approach for evaluating location-routing decisions via approximation algorithms," Transportation Research Part B: Methodological, Elsevier, vol. 87(C), pages 89-106.
    13. Zhang, Ying & Qi, Mingyao & Lin, Wei-Hua & Miao, Lixin, 2015. "A metaheuristic approach to the reliable location routing problem under disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 83(C), pages 90-110.
    14. Manzini, Riccardo, 2012. "A top-down approach and a decision support system for the design and management of logistic networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(6), pages 1185-1204.
    15. Albareda-Sambola, Maria & Fernández, Elena & Nickel, Stefan, 2012. "Multiperiod Location-Routing with Decoupled Time Scales," European Journal of Operational Research, Elsevier, vol. 217(2), pages 248-258.
    16. Melo, M.T. & Nickel, S. & Saldanha-da-Gama, F., 2009. "Facility location and supply chain management - A review," European Journal of Operational Research, Elsevier, vol. 196(2), pages 401-412, July.
    17. Rodolfo Mendoza-Gómez & Roger Z. Ríos-Mercado & Karla B. Valenzuela-Ocaña, 2019. "An Efficient Decision-Making Approach for the Planning of Diagnostic Services in a Segmented Healthcare System," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 18(05), pages 1631-1665, September.
    18. Schuster Puga, Matías & Tancrez, Jean-Sébastien, 2017. "A heuristic algorithm for solving large location–inventory problems with demand uncertainty," European Journal of Operational Research, Elsevier, vol. 259(2), pages 413-423.
    19. Contreras, Ivan & Fernández, Elena & Reinelt, Gerhard, 2012. "Minimizing the maximum travel time in a combined model of facility location and network design," Omega, Elsevier, vol. 40(6), pages 847-860.
    20. Van Engeland, Jens & Beliën, Jeroen & De Boeck, Liesje & De Jaeger, Simon, 2020. "Literature review: Strategic network optimization models in waste reverse supply chains," Omega, Elsevier, vol. 91(C).

    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:joptap:v:166:y:2015:i:1:d:10.1007_s10957-014-0638-z. 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.