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

被引：45
作者：
Li, Shengyin [1 ]
Huang, Yongxi [1 ]
机构：
[1] Clemson Univ, Glenn Dept Civil Engn, Clemson, SC 29634 USA
来源：
TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW | 2014年 / 72卷
关键词：
Heuristic method; Greedy-adding; Alternative fueling stations; Deviation paths; Mixed integer programming; OPTIMAL LOCATION; NETWORK; OPTIMIZATION; STATIONS; MODEL; ALGORITHMS; SIZE;
D O I：
10.1016/j.tre.2014.10.013
中图分类号：
F [经济];
学科分类号：
02 ;
摘要：
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. (C) 2014 Elsevier Ltd. All rights reserved.
引用
收藏
页码：144 / 158
页数：15
相关论文
共 44 条
[1]  
BALAS E, 1980, MATH PROGRAM STUD, V12, P37, DOI 10.1007/BFb0120886
[2]  
BEASLEY JE, 1990, NAV RES LOG, V37, P151, DOI 10.1002/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO
[3]  
2-2
[4]   OPTIMAL LOCATION OF DISCRETIONARY SERVICE FACILITIES [J].
BERMAN, O ;
LARSON, RC ;
FOUSKA, N .
TRANSPORTATION SCIENCE, 1992, 26 (03) :201-211
[5]   LOCATING DISCRETIONARY SERVICE FACILITIES .2. MAXIMIZING MARKET-SIZE, MINIMIZING INCONVENIENCE [J].
BERMAN, O ;
BERTSIMAS, D ;
LARSON, RC .
OPERATIONS RESEARCH, 1995, 43 (04) :623-632
[6]   A population-based iterated greedy algorithm for the minimum weight vertex cover problem [J].
Bouamama, Salim ;
Blum, Christian ;
Boukerram, Abdellah .
APPLIED SOFT COMPUTING, 2012, 12 (06) :1632-1639
[7]   Algorithms for the set covering problem [J].
Caprara, A ;
Toth, P ;
Fischetti, M .
ANNALS OF OPERATIONS RESEARCH, 2000, 98 (1-4) :353-371
[8]   A heuristic method for the set covering problem [J].
Caprara, A ;
Fischetti, M ;
Toth, P .
OPERATIONS RESEARCH, 1999, 47 (05) :730-743
[9]  
Chvatal V., 1979, Mathematics of Operations Research, V4, P233, DOI 10.1287/moor.4.3.233
[10]  
Daskin M.S., 1995, NETWORK DISCRETE LOC
12345