Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Heuristic algorithm for the Split-Demand One-Commodity Pickup-and-Delivery Travelling Salesman Problem
AU - Hernández-Pérez, Hipólito
AU - Salazar-González, Juan José
AU - Santos-Hernández, Beatriz
PY - 2018/9/1
Y1 - 2018/9/1
N2 - This article addresses the problem of designing routes of minimum cost for a capacitated vehicle moving a commodity between a set of customers, allowing two characteristics uncommon in the pickup-and-delivery literature. One characteristic is that a customer may be visited several times. The other characteristic is that a customer may be used as intermediate location to temporarily collect and deliver product. The article describes a matheuristic algorithm that iteratively applies a constructive procedure and a refinement procedure. The constructive procedure represents each customer by a set of nodes each one associated with a potential visit|, decomposes each customer demand into partial demands associated with its nodes, and solves a one-commodity pickup-and-delivery Travelling Salesman Problem with a variable neighbourhood search. The refinement procedure is a branch-and-cut algorithm to optimize some pieces of a given solution. Exhaustive computational results on benchmark instances demonstrate the good performance of the algorithm when solving instances with up to 500 customers.
AB - This article addresses the problem of designing routes of minimum cost for a capacitated vehicle moving a commodity between a set of customers, allowing two characteristics uncommon in the pickup-and-delivery literature. One characteristic is that a customer may be visited several times. The other characteristic is that a customer may be used as intermediate location to temporarily collect and deliver product. The article describes a matheuristic algorithm that iteratively applies a constructive procedure and a refinement procedure. The constructive procedure represents each customer by a set of nodes each one associated with a potential visit|, decomposes each customer demand into partial demands associated with its nodes, and solves a one-commodity pickup-and-delivery Travelling Salesman Problem with a variable neighbourhood search. The refinement procedure is a branch-and-cut algorithm to optimize some pieces of a given solution. Exhaustive computational results on benchmark instances demonstrate the good performance of the algorithm when solving instances with up to 500 customers.
KW - Heuristics
KW - Split demand
KW - Travelling salesman
KW - Vehicle routing problem
U2 - 10.1016/j.cor.2018.04.016
DO - 10.1016/j.cor.2018.04.016
M3 - Journal article
AN - SCOPUS:85046450686
VL - 97
SP - 1
EP - 17
JO - Computers and Operations Research
JF - Computers and Operations Research
SN - 0305-0548
ER -