Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem. / Hernandez-Perez, Hipolito; Rodriguez-Martin, Inmaculada; Salazar-Gonzalez, Juan-Jose.
In: European Journal of Operational Research, Vol. 251, No. 1, 16.05.2016, p. 44-52.Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem
AU - Hernandez-Perez, Hipolito
AU - Rodriguez-Martin, Inmaculada
AU - Salazar-Gonzalez, Juan-Jose
PY - 2016/5/16
Y1 - 2016/5/16
N2 - We address in this article the multi-commodity pickup-and-delivery traveling salesman problem, which is a routing problem for a capacitated vehicle that has to serve a set of customers that provide or require certain amounts of m different products. Each customer must be visited exactly once by the vehicle, and it is assumed that a unit of a product collected from a customer can be supplied to any other customer that requires that product. Each product is allowed to have several sources and several destinations. The objective is to minimize the total travel distance. We propose a hybrid three-stage heuristic approach that combines a procedure to generate initial solutions with several local search operators and shaking procedures, one of, them based on solving an integer programming model. Extensive computational experiments on randomly generated instances with up to 400 locations and 5 products show the effectiveness of the approach. (C) 2015 Elsevier B.V. All rights reserved.
AB - We address in this article the multi-commodity pickup-and-delivery traveling salesman problem, which is a routing problem for a capacitated vehicle that has to serve a set of customers that provide or require certain amounts of m different products. Each customer must be visited exactly once by the vehicle, and it is assumed that a unit of a product collected from a customer can be supplied to any other customer that requires that product. Each product is allowed to have several sources and several destinations. The objective is to minimize the total travel distance. We propose a hybrid three-stage heuristic approach that combines a procedure to generate initial solutions with several local search operators and shaking procedures, one of, them based on solving an integer programming model. Extensive computational experiments on randomly generated instances with up to 400 locations and 5 products show the effectiveness of the approach. (C) 2015 Elsevier B.V. All rights reserved.
KW - Pickup-and-delivery
KW - Hybrid approach
KW - Traveling salesman
KW - Local search
KW - VARIABLE NEIGHBORHOOD SEARCH
KW - ROUTING PROBLEM
KW - CUT ALGORITHM
KW - SINGLE
U2 - 10.1016/j.ejor.2015.10.053
DO - 10.1016/j.ejor.2015.10.053
M3 - Journal article
VL - 251
SP - 44
EP - 52
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 1
ER -