Home > Research > Publications & Outputs > The split-demand one-commodity pickup-and-deliv...
View graph of relations

The split-demand one-commodity pickup-and-delivery travelling salesman problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

The split-demand one-commodity pickup-and-delivery travelling salesman problem. / Salazar-Gonzalez, Juan-Jose; Santos-Hernandez, Beatriz.
In: Transportation Research Part B: Methodological, Vol. 75, 05.2015, p. 58-73.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

Salazar-Gonzalez, J-J & Santos-Hernandez, B 2015, 'The split-demand one-commodity pickup-and-delivery travelling salesman problem', Transportation Research Part B: Methodological, vol. 75, pp. 58-73. https://doi.org/10.1016/j.trb.2015.02.014

APA

Vancouver

Salazar-Gonzalez JJ, Santos-Hernandez B. The split-demand one-commodity pickup-and-delivery travelling salesman problem. Transportation Research Part B: Methodological. 2015 May;75:58-73. Epub 2015 Mar 19. doi: 10.1016/j.trb.2015.02.014

Author

Salazar-Gonzalez, Juan-Jose ; Santos-Hernandez, Beatriz. / The split-demand one-commodity pickup-and-delivery travelling salesman problem. In: Transportation Research Part B: Methodological. 2015 ; Vol. 75. pp. 58-73.

Bibtex

@article{721857f298fb4e91a97f349e59836faf,
title = "The split-demand one-commodity pickup-and-delivery travelling salesman problem",
abstract = "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.",
keywords = "Vehicle routing problem, Branch and cut, Split demand, VEHICLE-ROUTING PROBLEM, WORST-CASE ANALYSIS, REBALANCING PROBLEM, ALGORITHMS, INEQUALITIES, LOADS",
author = "Juan-Jose Salazar-Gonzalez and Beatriz Santos-Hernandez",
year = "2015",
month = may,
doi = "10.1016/j.trb.2015.02.014",
language = "English",
volume = "75",
pages = "58--73",
journal = "Transportation Research Part B: Methodological",
issn = "0191-2615",
publisher = "PERGAMON-ELSEVIER SCIENCE LTD",

}

RIS

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 -