Large neighborhood search for the double traveling salesman problem with multiple stacks Page: 3 of 16
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to UNT Digital Library by the UNT Libraries Government Documents Department.
Extracted Text
The following text was automatically extracted from the image on this page using optical character recognition software:
The DTSPMS was introduced in [13] to model a real-life short-haul/long haul
combined pickup and delivery applications. Goods are picked up in one local area
and delivered "en mass" to a long-haul operation (e.g., a freight train) where,
due to labor, time, union rules, and fragility, the goods cannot be re-packed and
must be shipped as is. Upon reaching the long-haul destination, the goods are
delivered in reverse order in which they were packed. Once again, due to labor
and time-intensive costs, the vehicle may only deliver goods that are not blocked
by other goods.
The difficulty in the DTSPMS lies in the side-constraints and the stack as-
signment variables, which complicate the neighborhoods and invalidates many
of the traditional VRP moves [14]. Indeed, the stack in which a pickup cus-
tomer is placed severely restricts the order in which a delivery customer may
be served. The pickup and delivery constraints are more standard and arise in
many applications such as dial-a-ride problems, airline scheduling, bus routing,
tractor-trailer problems, helicopter support of offshore oil field platforms, and
logistics and maintenance support [12], many of which may exhibit the types of
constraints described in the DTSPMS. Because of these side constraints, the DT-
SPMS is an appealing application to evaluate and compare various approaches
and methodologies. Indeed, industrial vehicle routing problems are rarely pure
and often feature complex side-constraints, which make it increasingly important
to compare existing algorithms on such complex applications.
This paper proposes a Large Neighborhood Search (LNS) algorithm for the
DTSPMS, since the constraint-based nature of LNS makes it a natural candi-
date to gracefully accommodate the problem-specific structure of the DTSPMS.
Experimental results on difficult DTSPMS problems demonstrate the effective-
ness of the algorithm. On the benchmarks provided by [13], our LNS algorithm
matches or improves the best-known solutions in 65% of the instances, improv-
ing the best-known solution by more than 5% in one case. Moreover, the LNS
algorithm is always within 2% of the best-known solution, indicating that the
LNS algorithm is also robust.
The rest of this paper is organized as follows. Section 2 specifies the DTSPMS
and describes the notations. Section 3 gives an overview of the overall algorithm.
Section 4 presents the experimental results. Section 5 discusses related work and
Section 6 concludes the paper.
2 Problem Formulation
This section defines the double traveling salesman problem with multiple stacks
(DTSPMS) and various concepts used in the paper.
Customers The problem is defined in terms of n customers who are represented
by the numbers 0,... , n -1 and four depots represented by de, di, d2, ds. The set
{0, 1,... ,n - 1, do, di, d2, ds} represents all the sites considered in the problem.
We use Customers to represent the set of customers and Sites to represent the set
of sites (The distinction between customers and sites simplifies the formalization
Upcoming Pages
Here’s what’s next.
Search Inside
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Bent, Russell W & Van Hentenryck, Pascal. Large neighborhood search for the double traveling salesman problem with multiple stacks, article, January 1, 2009; [New Mexico]. (https://digital.library.unt.edu/ark:/67531/metadc926656/m1/3/?rotate=270: accessed April 24, 2024), University of North Texas Libraries, UNT Digital Library, https://digital.library.unt.edu; crediting UNT Libraries Government Documents Department.