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 - The split-demand one-commodity pickup-and-delivery travelling salesman problem
AU - Salazar-Gonzalez, Juan-Jose
AU - Santos-Hernandez, Beatriz
PY - 2015/5
Y1 - 2015/5
N2 - This paper introduces a new vehicle routing problem transferring one commodity between customers with a capacitated vehicle that can visit a customer more than once, although a maximum number of visits must be respected. It generalizes the capacitated vehicle routing problem with split demands and some other variants recently addressed in the literature. We model the problem with a single commodity flow formulation and design a branch-and-cut approach to solve it. We make use of Benders Decomposition to project out the flow variables from the formulation. Inequalities to strengthen the linear programming relaxation are also presented and separated within the approach. Extensive computational results illustrate the performance of the approach on benchmark instances from the literature. (C) 2015 Elsevier Ltd. All rights reserved.
AB - This paper introduces a new vehicle routing problem transferring one commodity between customers with a capacitated vehicle that can visit a customer more than once, although a maximum number of visits must be respected. It generalizes the capacitated vehicle routing problem with split demands and some other variants recently addressed in the literature. We model the problem with a single commodity flow formulation and design a branch-and-cut approach to solve it. We make use of Benders Decomposition to project out the flow variables from the formulation. Inequalities to strengthen the linear programming relaxation are also presented and separated within the approach. Extensive computational results illustrate the performance of the approach on benchmark instances from the literature. (C) 2015 Elsevier Ltd. All rights reserved.
KW - Vehicle routing problem
KW - Branch and cut
KW - Split demand
KW - VEHICLE-ROUTING PROBLEM
KW - WORST-CASE ANALYSIS
KW - REBALANCING PROBLEM
KW - ALGORITHMS
KW - INEQUALITIES
KW - LOADS
U2 - 10.1016/j.trb.2015.02.014
DO - 10.1016/j.trb.2015.02.014
M3 - Journal article
VL - 75
SP - 58
EP - 73
JO - Transportation Research Part B: Methodological
JF - Transportation Research Part B: Methodological
SN - 0191-2615
ER -