×

An efficient heuristic algorithm for the alternative-fuel station location problem. (English) Zbl 1431.90087

Summary: We developed an efficient heuristic algorithm for the location of alternative-fuel stations. The algorithm is based on solving the sequence of subproblems restricted on a set of promising station candidates, and fixing a number of the best promising station locations. The set of candidates is initially determined by solving a relaxation model and then modified by exchanging some stations between the promising candidate set and the remaining station set. A number of the best station candidates in the promising candidate set can be fixed to improve computation time. In addition, a parallel computing strategy is integrated into solving simultaneously the set of subproblems to speed up computation time. Experimental results carried out on the benchmark instances show that our algorithm outperforms genetic algorithm and greedy algorithm. As compared with CPLEX solver, our algorithm can obtain all the optimal solutions on the tested instances with less computation time.

MSC:

90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming

Software:

CPLEX
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Albareda-Sambola, M.; Fernandez, E.; Nickel, S., Multiperiod location-routing with decoupled time scales, European Journal of Operational Research, 217, 2, 248-258 (2012) · Zbl 1244.90121
[2] Angelelli, E.; Mansini, R.; Speranza, M., Kernel search: A general heuristic for the multi-dimensional knapsack problem, Computers and Operations Research, 37, 11, 2017-2026 (2010) · Zbl 1188.90207
[3] Angelelli, E.; Mansini, R.; Speranza, M., Kernel search: A new heuristic framework for portfolio selection, Computational Optimization and Applications, 51, 1, 345-361 (2012) · Zbl 1246.91119
[4] Arslan, O.; Yildiz, B.; Karasan, O., Impacts of battery characteristics, driver preferences and road network features on travel costs of a plug-in hybrid electric vehicle (PHEV) for long-distance trips, Energy Policy, 74, 168-178 (2014)
[5] Badri-Koohi, B.; Tavakkoli-Moghaddam, R., Determining optimal number and locations of alternative-fuel stations with a multi-criteria approach, Proceedings of the 8th international industrial engineering conference (2012)
[6] Ballou, R., Dynamic warehouse location analysis, Journal of Marketing Research, 5, 3, 271-276 (1968)
[7] Berman, O., Deterministic flow-demand location problems, Journal of the Operational Research Society, 48, 1, 75-81 (1997) · Zbl 0881.90088
[8] Berman, O.; Hodgson, M.; Krass, D., Flow intercepting models, (Drezner, Z. (1995), Springer: Springer New York), 389-426
[9] Bhatti, S.; Lim, M.; Mak, H., Alternative fuel station location model with demand learning, Annals of Operations Research, 230, 1, 105-127 (2015) · Zbl 1317.90083
[10] Capar, I.; Kuby, M., An efficient formulation of the flow refueling location model for alternative-fuel stations, IIE Transactions, 44, 8, 622-636 (2012)
[11] Capar, I.; Kuby, M.; Leon, V.; Tsai, Y., An arc cover-path-cover formulation and strategic analysis of alternative-fuel station locations, European Journal of Operational Research, 227, 1, 142-151 (2013)
[12] Chung, S.; Kwon, C., Multi-period planning for electric car charging station locations: A case of Korean expressways, European Journal of Operational Research, 242, 2, 677-687 (2015)
[13] Drexl, M.; Schneider, M., A survey of variants and extensions of the location-routing problem, European Journal of Operational Research, 241, 2, 283-308 (2015) · Zbl 1339.90004
[14] European Commission (2013). http://europa.eu/rapid/press-release-MEMO-13-24_en.htm; European Commission (2013). http://europa.eu/rapid/press-release-MEMO-13-24_en.htm
[15] European Commission (2014). http://europa.eu/rapid/press-release-IP-14-1053_en.htm; European Commission (2014). http://europa.eu/rapid/press-release-IP-14-1053_en.htm
[16] Fotheringham, A.; O’Kelly, M., Spatial interaction models: Formulations and applications (1989), Kluwer Academic Publishers
[17] Ghamami, M.; Zockaie, A.; Nie, Y., A general corridor model for designing plug-in electric vehicle charging infrastructure to support intercity travel, Transportation Research Part C: Emerging Technologies, 68, 389-402 (2016)
[18] Guastaroba, G.; Speranza, M., Kernel search: An application to the index tracking problem, European Journal of Operational Research, 217, 1, 54-68 (2012) · Zbl 1244.91109
[19] Guastaroba, G.; Speranza, M., Kernel search for the capacitated facility location problem, Journal of Heuristics, 18, 6, 877-917 (2012)
[20] Guastaroba, G.; Speranza, M., A heuristic for BILP problems: The single source capacitated facility location problem, European Journal of Operational Research, 238, 2, 438-450 (2014) · Zbl 1338.90215
[21] Hodgson, M., The location of public facilities intermediate to the journey to work, European Journal of Operational Research, 6, 2, 199-204 (1981)
[22] Hodgson, M., A flow-capturing location-allocation model, Geographical Analysis, 22, 3, 270-279 (1990)
[23] Hodgson, M.; Berman, O., A billboard location model, Geographical and Environmental Modeling, 1, 1, 25-45 (1997)
[24] Hodgson, M.; Rosing, K., A network location-allocation model trading off flow capturing and p-median objectives, Annals of Operations Research, 40, 1, 247-260 (1992) · Zbl 0781.90061
[25] Hodgson, M.; Rosing, K.; Zhang, J., Locating vehicle inspection stations to protect a transportation network, Geographical Analysis, 28, 4, 299-314 (1996)
[26] Hosseini, M.; MirHassani, S., Refueling-station location problem under uncertainty, Transportation Research Part E, 84, 101-116 (2015)
[27] Huang, Y.; Li, S.; Qian, Z., Optimal deployment of alternative fueling stations on transportation networks considering deviation paths, Networks and Spatial Economics, 15, 1, 183-204 (2015) · Zbl 1339.90081
[28] Jung, J.; Chow, J.; Jayakrishnan, R.; Park, J., Stochastic dynamic itinerary interception refueling location problem with queue delay for electric taxi charging stations, Transportation Science Part C, 40, 123-142 (2014)
[29] Kang, J.; Recker, W., Strategic hydrogen refueling station locations with scheduling and routing considerations of individual vehicles, Transportation Science, 49, 4, 767-783 (2015)
[30] Kelley, S.; Kuby, M., On the way or around the corner? Observed refueling choices of alternative-fuel drivers in Southern California, Journal of Transport Geography, 33, 258-267 (2013)
[31] Kim, J.; Kuby, M., The deviation-flow refueling location model for optimizing a network of refueling stations, International Journal of Hydrogen Energy, 37, 6, 5406-5420 (2012)
[32] Kim, J.; Kuby, M., A network transformation heuristic approach for the deviation flow refueling location model, Computers and Operations Research, 40, 4, 1122-1131 (2013)
[33] Kuby, M.; Capar, I.; Kim, J., Efficient and equitable transnational infrastructure planning for natural gas trucking in the european union, European Journal of Operational Research, 257, 3, 979-991 (2017) · Zbl 1394.90096
[34] Kuby, M.; Lim, S., The flow-refueling location problem for alternative-fuel vehicles, Socio-Economic Planning Sciences, 39, 2, 125-145 (2005)
[35] Kuby, M.; Lines, L.; Schultz, R.; Xie, Z.; Kim, J.; Lim, S., Optimization of hydrogen stations in Florida using the flow-refueling location model, International Journal of Hydrogen Energy, 34, 15, 6045-6064 (2009)
[36] Lim, S.; Kuby, M., Heuristic algorithms for siting alternative-fuel stations using the flow-refueling location model, European Journal of Operational Research, 204, 1, 51-61 (2010) · Zbl 1178.90291
[37] Miralinaghi, M.; Keskin, B.; Lou, Y.; Roshandeh, A., Capacitated refueling station location problem with traffic deviations over multiple time periods, Networks and Spatial Economics, 17, 1, 129-151 (2017) · Zbl 1364.90193
[38] MirHassani, S.; Ebrazi, R., A flexible reformulation of the refueling station location problem, Transportation Science, 47, 4, 617-628 (2013)
[39] Nagy, G.; Salhi, S., Location-routing: Issues, models and methods, European Journal of Operational Research, 177, 2, 649-672 (2007) · Zbl 1109.90056
[40] Nambiar, J.; Gelders, L.; Van Wassenhove, L., Plant location and vehicle routing in the Malaysian rubber smallholder sector: A case study, European Journal of Operational Research, 38, 1, 14-26 (1989)
[41] Nie, Y.; Ghamami, M., A corridor-centric approach to planning electric vehicle charging infrastructure, Transportation Research Part B, 57, 172-190 (2013)
[42] Prodhon, C.; Prins, C., A survey of recent research on location-routing problems, European Journal of Operational Research, 238, 1, 1-17 (2014) · Zbl 1338.90223
[43] Rosenhead, J.; Elton, M.; Gupta, S., Robustness and optimality as criteria for strategic decisions, Journal of the Operational Research Society, 23, 4, 413-431 (1972)
[44] Salhi, S.; Nagy, G., Consistency and robustness in location-routing, Studies in Locational Analysis, 13, 3-19 (1999) · Zbl 0981.90043
[45] Singh, S.; Sharma, R., Two level modified simulated annealing based approach for solving facility layout problem, International Journal of Production Research, 46, 13, 3563-3582 (2008) · Zbl 1141.90473
[46] Tran, T.; Ng, K., Two-level water flow algorithm for vehicle routing problems, Proceedings of the 5th Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), Arizona, US (2011)
[47] Upchurch, C.; Kuby, M.; Lim, S., A model for location of capacitated alternative-fuel stations, Geographical Analysis, 41, 1, 85-106 (2009)
[48] Wang, Y.; Lin, C., Locating road-vehicle refueling stations, Transportation Research E, 45, 5, 821-829 (2009)
[49] Wang, Y.; Wang, C., Locating passenger vehicle refueling stations, Transportation Research E, 46, 5, 791-801 (2010)
[50] Wen, M.; Laporte, G.; Madsen, O.; Norrelund, A.; Olsen, A., Locating replenishment stations for electric vehicles: application to Danish traffic data, Journal of the Operational Research Society, 65, 10, 1555-1561 (2014)
[51] Yang, J.; Sun, H., Battery swap station location-routing problem with capacitated electric vehicles, Computers and Operations Research, 55, 217-232 (2015) · Zbl 1348.90145
[52] Yildiz, B.; Arslan, O.; Karasan, O., A branch and price approach for routing and refueling station location model, European Journal of Operational Research, 248, 3, 815-826 (2016) · Zbl 1346.90525
[53] Zockaie, A.; Aashtiani, H.; Ghamami, M.; Nie, Y., Solving detour-based fuel stations location problems, Computer-Aided Civil and Infrastructure Engineering, 31, 2, 132-144 (2016)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.