Home > Research > Publications & Outputs > An exact method for the double TSP with multipl...

Research

Links

Text available via DOI:

Keywords

View graph of relations

An exact method for the double TSP with multiple stacks

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

An exact method for the double TSP with multiple stacks. / Lusby, Richard M.; Larsen, Jesper; Ehrgott, Matthias et al.
In: International Transactions in Operational Research, Vol. 17, No. 5, 01.09.2010, p. 637-652.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Lusby, RM, Larsen, J, Ehrgott, M & Ryan, D 2010, 'An exact method for the double TSP with multiple stacks', International Transactions in Operational Research, vol. 17, no. 5, pp. 637-652. https://doi.org/10.1111/j.1475-3995.2009.00748.x

APA

Lusby, R. M., Larsen, J., Ehrgott, M., & Ryan, D. (2010). An exact method for the double TSP with multiple stacks. International Transactions in Operational Research, 17(5), 637-652. https://doi.org/10.1111/j.1475-3995.2009.00748.x

Vancouver

Lusby RM, Larsen J, Ehrgott M, Ryan D. An exact method for the double TSP with multiple stacks. International Transactions in Operational Research. 2010 Sept 1;17(5):637-652. doi: 10.1111/j.1475-3995.2009.00748.x

Author

Lusby, Richard M. ; Larsen, Jesper ; Ehrgott, Matthias et al. / An exact method for the double TSP with multiple stacks. In: International Transactions in Operational Research. 2010 ; Vol. 17, No. 5. pp. 637-652.

Bibtex

@article{8963750af3e0425d90f13f483eb699fd,
title = "An exact method for the double TSP with multiple stacks",
abstract = "The double travelling salesman problem (TSP) with multiple stacks (DTSPMS) is a pickup and delivery problem in which all pickups must be completed before any deliveries can be made. The problem originates from a real-life application where a 40-foot container (configured as 11 rows of three columns) is used to transport 33 pallets from a set of pickup customers to a set of delivery customers. The pickups and deliveries are performed in two separate trips, where each trip starts and ends at a depot and visits a number of customers. The aim of the problem is to produce a packing plan for the pallets that minimizes the total transportation cost given that the container cannot be repacked at any stage. In this paper we present an exact solution method based on matching k-best tours to each of the separate pickup and delivery TSPs. The approach is shown to outperform the only known previous exact method for this problem in that solutions can be obtained faster and previously unsolved instances containing as many as 18 customers can now be solved to optimality.",
keywords = "exact method, k-best solution , packing , routing , TSP",
author = "Lusby, {Richard M.} and Jesper Larsen and Matthias Ehrgott and David Ryan",
year = "2010",
month = sep,
day = "1",
doi = "10.1111/j.1475-3995.2009.00748.x",
language = "English",
volume = "17",
pages = "637--652",
journal = "International Transactions in Operational Research",
issn = "0969-6016",
publisher = "Blackwell Publishing",
number = "5",

}

RIS

TY - JOUR

T1 - An exact method for the double TSP with multiple stacks

AU - Lusby, Richard M.

AU - Larsen, Jesper

AU - Ehrgott, Matthias

AU - Ryan, David

PY - 2010/9/1

Y1 - 2010/9/1

N2 - The double travelling salesman problem (TSP) with multiple stacks (DTSPMS) is a pickup and delivery problem in which all pickups must be completed before any deliveries can be made. The problem originates from a real-life application where a 40-foot container (configured as 11 rows of three columns) is used to transport 33 pallets from a set of pickup customers to a set of delivery customers. The pickups and deliveries are performed in two separate trips, where each trip starts and ends at a depot and visits a number of customers. The aim of the problem is to produce a packing plan for the pallets that minimizes the total transportation cost given that the container cannot be repacked at any stage. In this paper we present an exact solution method based on matching k-best tours to each of the separate pickup and delivery TSPs. The approach is shown to outperform the only known previous exact method for this problem in that solutions can be obtained faster and previously unsolved instances containing as many as 18 customers can now be solved to optimality.

AB - The double travelling salesman problem (TSP) with multiple stacks (DTSPMS) is a pickup and delivery problem in which all pickups must be completed before any deliveries can be made. The problem originates from a real-life application where a 40-foot container (configured as 11 rows of three columns) is used to transport 33 pallets from a set of pickup customers to a set of delivery customers. The pickups and deliveries are performed in two separate trips, where each trip starts and ends at a depot and visits a number of customers. The aim of the problem is to produce a packing plan for the pallets that minimizes the total transportation cost given that the container cannot be repacked at any stage. In this paper we present an exact solution method based on matching k-best tours to each of the separate pickup and delivery TSPs. The approach is shown to outperform the only known previous exact method for this problem in that solutions can be obtained faster and previously unsolved instances containing as many as 18 customers can now be solved to optimality.

KW - exact method

KW - k-best solution

KW - packing

KW - routing

KW - TSP

U2 - 10.1111/j.1475-3995.2009.00748.x

DO - 10.1111/j.1475-3995.2009.00748.x

M3 - Journal article

VL - 17

SP - 637

EP - 652

JO - International Transactions in Operational Research

JF - International Transactions in Operational Research

SN - 0969-6016

IS - 5

ER -