IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v36y1988i3p478-484.html
   My bibliography  Save this article

A Heuristic Algorithm for the Traveling Salesman Location Problem on Networks

Author

Listed:
  • David Simchi-Levi

    (Columbia University, New York, New York)

  • Oded Berman

    (University of Massachusetts, Boston, Massachusetts)

Abstract

In this paper, we present a heuristic for the traveling salesman location problem on a network. Each day the salesman (e.g., a repair vehicle) must visit all the calls that are registered in a service list. Each call is generated with a given probability and the service list contains at most n calls. The heuristic requires O ( n 3 ) time to find the location that “minimizes” the expected distance traveled. A worst case analysis of the heuristic indicates that it will produce a solution which is at most 50% worse than the optimal solution. The paper also contains several asymptotic results for the problem in the plane.

Suggested Citation

  • David Simchi-Levi & Oded Berman, 1988. "A Heuristic Algorithm for the Traveling Salesman Location Problem on Networks," Operations Research, INFORMS, vol. 36(3), pages 478-484, June.
    • Handle: RePEc:inm:oropre:v:36:y:1988:i:3:p:478-484
    DOI: 10.1287/opre.36.3.478
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.36.3.478
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.36.3.478?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
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. S. A. MirHassani & R. Ebrazi, 2013. "A Flexible Reformulation of the Refueling Station Location Problem," Transportation Science, INFORMS, vol. 47(4), pages 617-628, November.
    2. Lee, Chungmok & Han, Jinil, 2017. "Benders-and-Price approach for electric vehicle charging station location problem under probabilistic travel range," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 130-152.
    3. Mahmutoğulları, Özlem & Yaman, Hande, 2023. "Robust alternative fuel refueling station location problem with routing under decision-dependent flow uncertainty," European Journal of Operational Research, Elsevier, vol. 306(1), pages 173-188.
    4. Yıldız, Barış & Arslan, Okan & Karaşan, Oya Ekin, 2016. "A branch and price approach for routing and refueling station location model," European Journal of Operational Research, Elsevier, vol. 248(3), pages 815-826.
    5. Igor Averbakh & Wei Yu, 2020. "Multi-depot traveling salesmen location problems on networks with special structure," Annals of Operations Research, Springer, vol. 286(1), pages 635-648, March.
    6. Van Can Nguyen & Chi-Tai Wang & Ying-Jiun Hsieh, 2021. "Electrification of Highway Transportation with Solar and Wind Energy," Sustainability, MDPI, vol. 13(10), pages 1-28, May.
    7. Ramesh Bollapragada & Uday S. Rao & Junying Wu, 2023. "Hub location–allocation for combined fixed-wireless and wireline broadband access networks," DECISION: Official Journal of the Indian Institute of Management Calcutta, Springer;Indian Institute of Management Calcutta, vol. 50(1), pages 115-128, March.
    8. Guozhong Liu & Li Kang & Zeyu Luan & Jing Qiu & Fenglei Zheng, 2019. "Charging Station and Power Network Planning for Integrated Electric Vehicles (EVs)," Energies, MDPI, vol. 12(13), pages 1-22, July.
    9. Drexl, Andreas & Klose, Andreas, 2001. "Facility location models for distribution system design," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 546, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    10. Kuby, Michael & Lim, Seow, 2005. "The flow-refueling location problem for alternative-fuel vehicles," Socio-Economic Planning Sciences, Elsevier, vol. 39(2), pages 125-145, June.
    11. Sun, Siyang & Yang, Qiang & Ma, Jin & Ferré, Adrià Junyent & Yan, Wenjun, 2020. "Hierarchical planning of PEV charging facilities and DGs under transportation-power network couplings," Renewable Energy, Elsevier, vol. 150(C), pages 356-369.
    12. Kınay, Ömer Burak & Gzara, Fatma & Alumur, Sibel A., 2021. "Full cover charging station location problem with routing," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 1-22.
    13. Yang, Jun & Guo, Fang & Zhang, Min, 2017. "Optimal planning of swapping/charging station network with customer satisfaction," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 103(C), pages 174-197.
    14. Yongxi Huang & Shengyin Li & Zhen Qian, 2015. "Optimal Deployment of Alternative Fueling Stations on Transportation Networks Considering Deviation Paths," Networks and Spatial Economics, Springer, vol. 15(1), pages 183-204, March.
    15. Lim, Seow & Kuby, Michael, 2010. "Heuristic algorithms for siting alternative-fuel stations using the Flow-Refueling Location Model," European Journal of Operational Research, Elsevier, vol. 204(1), pages 51-61, July.
    16. Davood Shishebori & Lawrence Snyder & Mohammad Jabalameli, 2014. "A Reliable Budget-Constrained FL/ND Problem with Unreliable Facilities," Networks and Spatial Economics, Springer, vol. 14(3), pages 549-580, December.
    17. Joseph Y. J. Chow & Hamid R. Sayarshad, 2016. "Reference Policies for Non-myopic Sequential Network Design and Timing Problems," Networks and Spatial Economics, Springer, vol. 16(4), pages 1183-1209, December.
    18. Michael Kuby & Seow Lim, 2007. "Location of Alternative-Fuel Stations Using the Flow-Refueling Location Model and Dispersion of Candidate Sites on Arcs," Networks and Spatial Economics, Springer, vol. 7(2), pages 129-152, June.
    19. Hunkar Toyoglu & Oya Ekin Karasan & Bahar Yetis Kara, 2011. "Distribution network design on the battlefield," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(3), pages 188-209, April.
    20. 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.
    21. Mina, Hokey & Jayaraman, Vaidyanathan & Srivastava, Rajesh, 1998. "Combined location-routing problems: A synthesis and future research directions," European Journal of Operational Research, Elsevier, vol. 108(1), pages 1-15, July.
    22. Sayarshad, Hamid R. & Du, Xinpi & Gao, H. Oliver, 2020. "Dynamic post-disaster debris clearance problem with re-positioning of clearance equipment items under partially observable information," Transportation Research Part B: Methodological, Elsevier, vol. 138(C), pages 352-372.
    23. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    24. Luyun Wang & Bo Zhou, 2023. "Optimal Planning of Electric Vehicle Fast-Charging Stations Considering Uncertain Charging Demands via Dantzig–Wolfe Decomposition," Sustainability, MDPI, vol. 15(8), pages 1-23, April.
    25. Cuiyu Kong & Raka Jovanovic & Islam Safak Bayram & Michael Devetsikiotis, 2017. "A Hierarchical Optimization Model for a Network of Electric Vehicle Charging Stations," Energies, MDPI, vol. 10(5), pages 1-20, May.

    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:inm:oropre:v:36:y:1988:i:3:p:478-484. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.