IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v72y2014icp144-158.html
   My bibliography  Save this article

Heuristic approaches for the flow-based set covering problem with deviation paths

Author

Listed:
  • Li, Shengyin
  • Huang, Yongxi

Abstract

A multipath refueling location model is developed to take into account the effects of vehicle range and multiple deviation paths. It is formulated as a mixed integer linear program, which is intrinsically difficult to solve with increase in the number of deviation paths and network size. This study is focused on developing heuristic approximation solutions, specifically the greedy-adding and greedy-adding with extension algorithms. These algorithms are shown to be efficient and effective to solve the model for the Sioux Falls network. The heuristics are also applied to locate electric vehicle charging stations in the state of South Carolina.

Suggested Citation

  • Li, Shengyin & Huang, Yongxi, 2014. "Heuristic approaches for the flow-based set covering problem with deviation paths," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 144-158.
    • Handle: RePEc:eee:transe:v:72:y:2014:i:c:p:144-158
    DOI: 10.1016/j.tre.2014.10.013
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554514001860
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2014.10.013?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. John Hodgson, M. & Rosing, K. E. & Leontien, A. & Storrier, G., 1996. "Applying the flow-capturing location-allocation model to an authentic network: Edmonton, Canada," European Journal of Operational Research, Elsevier, vol. 90(3), pages 427-443, May.
    2. Wang, Ying-Wei & Wang, Chuan-Ren, 2010. "Locating passenger vehicle refueling stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(5), pages 791-801, September.
    3. 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.
    4. Lan, Guanghui & DePuy, Gail W. & Whitehouse, Gary E., 2007. "An effective and simple heuristic for the set covering problem," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1387-1403, February.
    5. Jin Y. Yen, 1971. "Finding the K Shortest Loopless Paths in a Network," Management Science, INFORMS, vol. 17(11), pages 712-716, July.
    6. Oded Berman & Dimitris Bertsimas & Richard C. Larson, 1995. "Locating Discretionary Service Facilities, II: Maximizing Market Size, Minimizing Inconvenience," Operations Research, INFORMS, vol. 43(4), pages 623-632, August.
    7. Wang, Ying-Wei & Lin, Chuah-Chih, 2013. "Locating multiple types of recharging stations for battery-powered electric vehicle transport," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 58(C), pages 76-87.
    8. Weiping Zeng & Ignacio Castillo & M. Hodgson, 2010. "A Generalized Model for Locating Facilities on a Network with Flow-Based Demand," Networks and Spatial Economics, Springer, vol. 10(4), pages 579-611, December.
    9. 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.
    10. V. Chvatal, 1979. "A Greedy Heuristic for the Set-Covering Problem," Mathematics of Operations Research, INFORMS, vol. 4(3), pages 233-235, August.
    11. Wang, Ying-Wei & Lin, Chuah-Chih, 2009. "Locating road-vehicle refueling stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(5), pages 821-829, September.
    12. M Haouari & J S Chaouachi, 2002. "A probabilistic greedy search algorithm for combinatorial optimisation with application to the set covering problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(7), pages 792-799, July.
    13. Haddadi, Salim, 1997. "Simple Lagrangian heuristic for the set covering problem," European Journal of Operational Research, Elsevier, vol. 97(1), pages 200-204, February.
    14. Alberto Caprara & Matteo Fischetti & Paolo Toth, 1999. "A Heuristic Method for the Set Covering Problem," Operations Research, INFORMS, vol. 47(5), pages 730-743, October.
    15. Oded Berman & Richard C. Larson & Nikoletta Fouska, 1992. "Optimal Location of Discretionary Service Facilities," Transportation Science, INFORMS, vol. 26(3), pages 201-211, August.
    16. 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.
    17. Alberto Caprara & Paolo Toth & Matteo Fischetti, 2000. "Algorithms for the Set Covering Problem," Annals of Operations Research, Springer, vol. 98(1), pages 353-371, December.
    18. Marshall L. Fisher & Pradeep Kedia, 1990. "Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics," Management Science, INFORMS, vol. 36(6), pages 674-688, June.
    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. Yang, Woosuk, 2018. "A user-choice model for locating congested fast charging stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 110(C), pages 189-213.
    2. Xie, Fei & Lin, Zhenhong, 2021. "Integrated U.S. nationwide corridor charging infrastructure planning for mass electrification of inter-city trips," Applied Energy, Elsevier, vol. 298(C).
    3. Arslan, Okan & Yıldız, Barış & Karaşan, Oya Ekin, 2015. "Minimum cost path problem for Plug-in Hybrid Electric Vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 80(C), pages 123-141.
    4. Guo, Fang & Yang, Jun & Lu, Jianyi, 2018. "The battery charging station location problem: Impact of users’ range anxiety and distance convenience," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 1-18.
    5. Pichamon Keawthong & Veera Muangsin & Chupun Gowanit, 2022. "Location Selection of Charging Stations for Electric Taxis: A Bangkok Case," Sustainability, MDPI, vol. 14(17), pages 1-23, September.
    6. Scheiper, Barbara & Schiffer, Maximilian & Walther, Grit, 2019. "The flow refueling location problem with load flow control," Omega, Elsevier, vol. 83(C), pages 50-69.
    7. Anjos, Miguel F. & Gendron, Bernard & Joyce-Moniz, Martim, 2020. "Increasing electric vehicle adoption through the optimal deployment of fast-charging stations for local and long-distance travel," European Journal of Operational Research, Elsevier, vol. 285(1), pages 263-278.
    8. Xie, Fei & Liu, Changzheng & Li, Shengyin & Lin, Zhenhong & Huang, Yongxi, 2018. "Long-term strategic planning of inter-city fast charging infrastructure for battery electric vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 261-276.
    9. 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.
    10. Arslan, Okan & Karaşan, Oya Ekin, 2016. "A Benders decomposition approach for the charging station location problem with plug-in hybrid electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 670-695.
    11. Hosseini, Meysam & MirHassani, S.A., 2015. "Refueling-station location problem under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 84(C), pages 101-116.
    12. Wang, Yusheng & Huang, Yongxi & Xu, Jiuping & Barclay, Nicole, 2017. "Optimal recharging scheduling for urban electric buses: A case study in Davis," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 100(C), pages 115-132.
    13. Göpfert, Paul & Bock, Stefan, 2019. "A Branch&Cut approach to recharging and refueling infrastructure planning," European Journal of Operational Research, Elsevier, vol. 279(3), pages 808-823.
    14. Kuby, Michael & Capar, Ismail & Kim, Jong-Geun, 2017. "Efficient and equitable transnational infrastructure planning for natural gas trucking in the European Union," European Journal of Operational Research, Elsevier, vol. 257(3), pages 979-991.
    15. Tran, Cong Quoc & Keyvan-Ekbatani, Mehdi & Ngoduy, Dong & Watling, David, 2021. "Stochasticity and environmental cost inclusion for electric vehicles fast-charging facility deployment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(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. 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.
    2. 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.
    3. Capar, Ismail & Kuby, Michael & Leon, V. Jorge & Tsai, Yu-Jiun, 2013. "An arc cover–path-cover formulation and strategic analysis of alternative-fuel station locations," European Journal of Operational Research, Elsevier, vol. 227(1), pages 142-151.
    4. Zhang, Anpeng & Kang, Jee Eun & Kwon, Changhyun, 2017. "Incorporating demand dynamics in multi-period capacitated fast-charging location planning for electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 5-29.
    5. Marković, Nikola & Ryzhov, Ilya O. & Schonfeld, Paul, 2017. "Evasive flow capture: A multi-period stochastic facility location problem with independent demand," European Journal of Operational Research, Elsevier, vol. 257(2), pages 687-703.
    6. Chung, Sung Hoon & Kwon, Changhyun, 2015. "Multi-period planning for electric car charging station locations: A case of Korean Expressways," European Journal of Operational Research, Elsevier, vol. 242(2), pages 677-687.
    7. Anjos, Miguel F. & Gendron, Bernard & Joyce-Moniz, Martim, 2020. "Increasing electric vehicle adoption through the optimal deployment of fast-charging stations for local and long-distance travel," European Journal of Operational Research, Elsevier, vol. 285(1), pages 263-278.
    8. Hosseini, Meysam & MirHassani, S.A., 2015. "Refueling-station location problem under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 84(C), pages 101-116.
    9. Scheiper, Barbara & Schiffer, Maximilian & Walther, Grit, 2019. "The flow refueling location problem with load flow control," Omega, Elsevier, vol. 83(C), pages 50-69.
    10. Schiffer, Maximilian & Walther, Grit, 2017. "The electric location routing problem with time windows and partial recharging," European Journal of Operational Research, Elsevier, vol. 260(3), pages 995-1013.
    11. Joonho Ko & Tae-Hyoung Tommy Gim & Randall Guensler, 2017. "Locating refuelling stations for alternative fuel vehicles: a review on models and applications," Transport Reviews, Taylor & Francis Journals, vol. 37(5), pages 551-570, September.
    12. Patrick Jochem & Carsten Brendel & Melanie Reuter-Oppermann & Wolf Fichtner & Stefan Nickel, 2016. "Optimizing the allocation of fast charging infrastructure along the German autobahn," Journal of Business Economics, Springer, vol. 86(5), pages 513-535, July.
    13. Yang, Woosuk, 2018. "A user-choice model for locating congested fast charging stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 110(C), pages 189-213.
    14. Okan Arslan & Oya Ekin Karaşan & Ridha Mahjoub & Hande Yaman, 2019. "A Branch-and-Cut Algorithm for the Alternative Fuel Refueling Station Location Problem with Routing," Transportation Science, INFORMS, vol. 53(4), pages 1107-1125, July.
    15. Arslan, Okan & Karaşan, Oya Ekin, 2016. "A Benders decomposition approach for the charging station location problem with plug-in hybrid electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 670-695.
    16. Sun, Zhuo & Gao, Wei & Li, Bin & Wang, Longlong, 2020. "Locating charging stations for electric vehicles," Transport Policy, Elsevier, vol. 98(C), pages 48-54.
    17. Wang, Ying-Wei & Lin, Chuah-Chih, 2013. "Locating multiple types of recharging stations for battery-powered electric vehicle transport," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 58(C), pages 76-87.
    18. Farzaneh Ferdowsi & Hamid Reza Maleki & Sanaz Rivaz, 2020. "Air refueling tanker allocation based on a multi-objective zero-one integer programming model," Operational Research, Springer, vol. 20(4), pages 1913-1938, December.
    19. 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.
    20. Lin, Cheng-Chang & Lin, Chuan-Chih, 2018. "The p-center flow-refueling facility location problem," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 124-142.

    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:transe:v:72:y:2014:i:c:p:144-158. 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/600244/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.