Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery |
| |
| Affiliation: | 1. College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, China;2. School of Computer Science, University of Birmingham, B15 2TT, UK;3. Department of Biomedical Engineering, Shenzhen University, Shenzhen 518060, China;1. Department of Management Science, Otto-von-Guericke-University Magdeburg, 39106 Magdeburg, Germany;2. Department of Quantitative Methods, University of Brescia, 25122 Brescia, Italy;1. Instituto de Computação, Universidade Federal Fluminense, Rua Passo da Pátria, 156 - São Domingos, Niterói RJ 24210-240, Brazil;2. Departamento de Engenharia Industrial, Pontifícia Universidade Católica do Rio de Janeiro, Rua Marquês de São Vicente, 225 - Gávea, Rio de Janeiro RJ 22451-900, Brazil;3. Dpt. de Informática, Pontifícia Universidade Católica do Rio de Janeiro Rua Marquês de São Vicente, 225 - Gávea, Rio de Janeiro RJ 22451-900, Brazil;4. Departamento de Computação, Universidade Federal de Ouro Preto, Campus Universitário, Morro do Cruzeiro, Ouro Preto - MG 35400-000, Brazil;5. Department of Business Administration, Universität Wien, Oskar-Morgenstern-Platz 1, Vienna A-1090, Austria |
| |
| Abstract: | 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. |
| |
| Keywords: | Location routing problem Simultaneous pickup and delivery Metaheuristics Multi-start simulated annealing |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
