TY - JOUR
T1 - Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery
AU - Yu, Vincent F.
AU - Lin, Shih Wei
PY - 2014/11
Y1 - 2014/11
N2 - The location routing problem with simultaneous pickup and delivery (LRPSPD) is a new variant of the location routing problem (LRP). The objective of LRPSPD is to minimize the total cost of a distribution system including vehicle traveling cost, depot opening cost, and vehicle fixed cost by locating the depots and determining the vehicle routes to simultaneously satisfy the pickup and the delivery demands of each customer. LRPSPD is NP-hard since its special case, LRP, is NP-hard. Thus, this study proposes a multi-start simulated annealing (MSA) algorithm for solving LRPSPD which incorporates multi-start hill climbing strategy into simulated annealing framework. The MSA algorithm is tested on 360 benchmark instances to verify its performance. Results indicate that the multi-start strategy can significantly enhance the performance of traditional single-start simulated annealing algorithm. Our MSA algorithm is very effective in solving LRPSPD compared to existing solution approaches. It obtained 206 best solutions out of the 360 benchmark instances, including 126 new best solutions.
AB - The location routing problem with simultaneous pickup and delivery (LRPSPD) is a new variant of the location routing problem (LRP). The objective of LRPSPD is to minimize the total cost of a distribution system including vehicle traveling cost, depot opening cost, and vehicle fixed cost by locating the depots and determining the vehicle routes to simultaneously satisfy the pickup and the delivery demands of each customer. LRPSPD is NP-hard since its special case, LRP, is NP-hard. Thus, this study proposes a multi-start simulated annealing (MSA) algorithm for solving LRPSPD which incorporates multi-start hill climbing strategy into simulated annealing framework. The MSA algorithm is tested on 360 benchmark instances to verify its performance. Results indicate that the multi-start strategy can significantly enhance the performance of traditional single-start simulated annealing algorithm. Our MSA algorithm is very effective in solving LRPSPD compared to existing solution approaches. It obtained 206 best solutions out of the 360 benchmark instances, including 126 new best solutions.
KW - Location routing problem
KW - Metaheuristics
KW - Multi-start simulated annealing
KW - Simultaneous pickup and delivery
UR - http://www.scopus.com/inward/record.url?scp=84905385028&partnerID=8YFLogxK
U2 - 10.1016/j.asoc.2014.06.024
DO - 10.1016/j.asoc.2014.06.024
M3 - 文章
AN - SCOPUS:84905385028
SN - 1568-4946
VL - 24
SP - 284
EP - 290
JO - Applied Soft Computing Journal
JF - Applied Soft Computing Journal
ER -