European Journal of Operational Research 171 (2006) 750–775

www.elsevier.com/locate/ejor

A unified heuristic for a large class of Vehicle

Routing Problems with Backhauls
Stefan Ropke *, David Pisinger
DIKU––Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen Ø, Denmark

Abstract

The Vehicle Routing Problem with Backhauls is a generalization of the ordinary capacitated vehicle routing problem
where goods are delivered from the depot to the linehaul customers, and additional goods are brought back to the depot
from the backhaul customers. Numerous ways of modeling the backhaul constraints have been proposed in the liter-
ature, each imposing different restrictions on the handling of backhaul customers. A survey of these models is presented,
and a unified model is developed that is capable of handling most variants of the problem from the literature. The uni-
fied model can be seen as a Rich Pickup and Delivery Problem with Time Windows, which can be solved through an
improved version of the large neighborhood search heuristic proposed by Ropke and Pisinger [An adaptive large neigh-
borhood search heuristic for the pickup and delivery problem with time windows, Technical Report, DIKU, University
of Copenhagen, 2004]. The results obtained in this way are comparable to or improve on similar results found by state
of the art heuristics for the various variants of the problem. The heuristic has been tested on 338 problems from the
literature and it has improved the best known solution for 227 of these. An additional benefit of the unified modeling
and solution method is that it allows the dispatcher to mix various variants of the Vehicle Routing Problem with Back-
hauls for the individual customers or vehicles.

2004 Elsevier B.V. All rights reserved.

Keywords: Metaheuristics; Vehicle routing problems; Large neighborhood search

1. Introduction

In the classical Capacitated Vehicle Routing

Problem (CVRP) we have to deliver goods from
*
a depot to a set of customers, using a set of iden-
Corresponding author. Tel.: +45 35 32 14 52; fax: +45 35
32 14 01.
tical vehicles. Each customer demands a certain
E-mail addresses: sropke@diku.dk (S. Ropke), pisinger@ quantity of goods and the vehicles have a limited
diku.dk (D. Pisinger). capacity. Our task is to construct routes starting

0377-2217/$ - see front matter
2004 Elsevier B.V. All rights reserved.
doi:10.1016/j.ejor.2004.09.004
 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775 751

and ending at the depot that minimize the total sibility of the model, by also allowing pickup and
travel distance and that obey the capacity of the delivery requests, precedence constraints, etc. This
vehicles. allows us to formulate the six most common vari-
The problems that need to be solved in real-life ants of vehicle routing problems with backhauls
situations are usually much more complicated. within the framework, and to find high-quality
One complication that arises in practice is that heuristic solutions that are comparable to or im-
goods not only need to be brought from the depot prove on similar results for specialized algorithms.
to the customers, but also must be picked up at a The underlying problem of all of the problems
number of customers and brought back to the we consider is the Pickup and Delivery Problem
depot. A simple way of handling such problems with Time Windows (PDPTW), which we will de-
is to solve two independent CVRPs. One for the scribe in Section 2. A survey of the six most com-
delivery (linehaul) customers and one for the pick- mon variants of vehicle routing problems with
up (backhaul) customers, such that some vehicles backhauls––and additional, less frequently used
would be designated to linehaul customers and models––is given in Section 3. The subsequent sec-
others to backhaul customers. This approach is tions present the heuristic algorithm proposed in
not likely to create high-quality solutions this paper, which is outlined in Fig. 1. Some of
though––it seems more profitable to serve both the problem types we wish to solve are illustrated
pickup and delivery customers using the same at the top of the figure. To solve an instance of
vehicles. The Vehicle Routing Problem with Back- one of these problem types, we transform it to
hauls (VRPB) models problems with both pickup an instance of the Rich Pickup and Delivery Prob-
and delivery customers in the same route. lem with Time Windows, as illustrated by the
Applications of VRPB can be found in the dis- arrows from the top row to the next row. Trans-
tribution of groceries. Groceries are delivered to formations are discussed in Section 4. The
supermarkets and grocery stores from a central PDPTW instance is solved by a heuristic which
distribution center and groceries are picked up at will be presented in Section 5; this produces a
production sites and brought to the distribution PDPTW solution that finally is interpreted as a
center. Another application is the handling of solution to the original problem. This solution
returnable bottles, where full bottles are brought framework has been tested on 338 benchmarks
to customers and empty bottles are brought back problems proposed in the literature. The results
to breweries to be recycled. Such applications are of this computational test are reported in Section
likely to become more common in the future due 6. The paper is finally concluded in Section 7.
to the increased awareness of environmental is-
sues. It is important to develop fast and robust
algorithms for real-life transportation problems, 2. The Pickup and Delivery Problem with Time
which are able to handle various side constraints Windows (PDPTW)
that appear in practice.
The general trend in the transportation sector is Before starting to discuss the various variants of
that transportation companies are merging to lar- the VRPB we introduce the Rich Pickup and Delivery
ger units which can provide a large number of Problem with Time Windows (Rich PDPTW). All
delivery services. In order to get the most possible considered variants of the VRPB can be seen as
benefit from the vehicle fleet, it can be attractive to extensions of the PDPTW. IP models of the PDPTW
service conceptually different transportation tasks can be found in Desaulniers et al. [8] and Sigurd et al.
by the same fleet, thus models are needed that [35], for our purpose we will only give a verbal
can handle all additional constraints associated description of our problem which differs slightly
with a transportation task. Cordeau et al. [6] for from the problems in the afore-mentioned papers.
example provide a unified approach for several In the Rich PDPTW we have n requests and m
Vehicle Routing Problems with Time Windows. vehicles. A request i 2 {1, . . . , n} consists of pick-
The present paper considerably extends the expres- ing up a quantity li of goods at one location and
752 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775

Fig. 1. Solution framework: as described in Section 3 the algorithm accepts as input variants of the Vehicle Routing Problem with
Backhauls, including: VRPB, MVRPB, MDMVRPB, VRPBTW, MVRPBTW and VRPSDP. All of the problems are transformed to a
Rich Pickup and Delivery Problem with Time Windows, which is solved heuristically through a Large Neighborhood Search
algorithm. The last step of the algorithm transforms the obtained solution back to the original problem. The framework is not limited
to backhaul models, but can be used to solve other types of vehicle routing problems, such as the vehicle routing problem with time
windows or the capacitated vehicle routing problem.

delivering it to another location. With each request Sigurd et al. [35] for various applications of prece-
is associated a pickup time window, a delivery time dence constraints).
window, and two service times spi and sdi indicating Each request i can only be served by a vehicle
how long the pickup and delivery operations take k 2 Fi, where Fi is the set of feasible vehicles corre-
to perform. A vehicle is allowed to arrive at a loca- sponding to request i. Each vehicle k 2 {1, . . . , m}
tion before the start of the time window, in which has an associated capacity Ck, a start time bk and
case it will have to wait before starting the corre- end time ek, and an associated start terminal Bk
sponding operation. A vehicle may never arrive and end terminal Ek where it starts and ends its
at a location after the end of the time window. duty respectively. The vehicle must leave its start
Each request furthermore has an associated pickup terminal at time bk even though this might intro-
precedence number, and a delivery precedence num- duce waiting time at the first customer visited.
ber. Each vehicle must visit the locations in non- The vehicle must return to the end terminal at time
decreasing order of precedence number (see e.g. ek or before.
 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775 753

The problem can be defined on a directed graph (A) If a route contains both linehaul and back-
where the locations are represented by a set of haul customers then the backhaul customers
nodes V = {1, . . . , 2n + 2m}, and for each edge must be served after the linehaul customers.
(i, j) we have an associated distance dij and travel (B) A route is not allowed to consist entirely of
time tij, where we assume that travel times satisfy backhaul customers.
the triangle inequality while the only assumption (C) The capacity of the vehicle should be
on the distances is that they must be non-negative. obeyed, that is, neither the sum of the
The locations will occasionally be referred to as demands of the linehaul customers nor the
visits. sum of the demands of the backhaul custom-
The task is to construct a set of valid routes for ers served by a vehicle may exceed the vehi-
a limited number of vehicles such that an associ- cle capacity.
ated objective function is minimized. The objective (D) The number of vehicles to use is given in
function is a weighted sum of (1) the sum of the advance. This means that even if it is possi-
distance traveled by the vehicles and (2) the num- ble to find better solutions using fewer or
ber of requests not assigned to a vehicle. The two more vehicles, we must report the best solu-
terms are weighted by the coefficients a and b. No- tion we can find that uses the specified num-
tice that this objective function does not necessar- ber of vehicles.
ily assign all requests to a vehicle. Requests not (E) All customers are serviced from a single
assigned to a vehicle are placed in a virtual request depot.
bank, which in a real world situation must be han- (F) All vehicles have the same capacity.
dled by a human dispatcher. Hence, normally a
high value is assigned to the coefficient b to stimu- Constraint (A) might seem artificial but it is jus-
late that as many requests as possible are to be tified by the fact that many vehicles are rear-
serviced. In the experiments performed in this loaded. This makes it problematic to try to load
paper, b was chosen sufficiently high to avoid situ- the vehicle with goods heading for the depot be-
ations were some requests where left in the request fore we have delivered all goods to the customers
bank upon termination. as the pickup goods might block access to the
delivery goods. The constraint is also justified by
the fact that the linehaul customers frequently pre-
fer early deliveries while backhaul customers pre-
3. Overview of vehicle routing problems with
fer late pickups.
backhauls
A recent survey of the VRPB was presented by
Toth and Vigo [43]. Exact methods for the VRPB
This section gives an overview of the vehicle
are proposed by Mingozzi et al. [26] and Toth and
routing problems with backhauls proposed in the
Vigo [42]. Heuristics have been developed by Anily
literature. We restrict ourselves to multi-vehicle
[3], Casco et al. [5], Crispim and Brandao [7],
problems. Single-vehicle problems have been stud-
Goetschalckx and Jacobs-Blecha [16,22] and Toth
ied by for example Gendreau et al. [14], Ghaziri
and Vigo [41].
and Osman [15] and Süral and Bookbinder [37].
3.2. The Mixed Vehicle Routing Problem with
3.1. The Vehicle Routing Problem with Backhauls Backhauls (MVRPB)
(VRPB)
The Mixed Vehicle Routing Problem with Back-
In the Vehicle Routing Problem with Backhauls hauls (MVRPB) is derived from the VRPB by
(VRPB) we wish to minimize the total traveled dis- relaxing limitations (A), (B) and (D). That is, we
tance and we are allowed to serve linehaul and can mix linehaul and backhaul customers freely
backhaul customers on the same routes subject within a route and we are free to use as many vehi-
to the following limitations. cles as we want. We still have to obey the capacity
754 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775

limit of the vehicles. The capacity check is slightly An exact algorithm for the VRPBTW based on
more complicated in the MVRPB problem as the column generation was proposed by Gelinas et al.
vehicle load fluctuates during the route. Further- [13], and heuristics were proposed by Duhamel
more, some MVRPB also have a duration limit et al. [12], Hasama et al. [20], Reimann et al.
that implies that routes should be completed with- [30], Thangiah et al. [39] and Zhong and Cole [47].
in a certain time frame; for such problems the tra-
vel time between customers and the service time at 3.5. The Mixed Vehicle Routing Problem with
the customers is given. Backhauls and Time Windows (MVRPBTW)
The name Vehicle Routing Problem with Pickups
and Deliveries (VRPPD) is sometimes used instead The Mixed Vehicle Routing Problem with Back-
of MVRPB. Heuristics for this problem are pre- hauls and Time Windows (MVRPBTW) is derived
sented by Halse [19], Nagy and Salhi [27,33] and from VRPBTW by relaxing limitation (A) saying
Wade and Salhi [44]. that backhaul customers should be visited after
linehaul customers. The objective that has been
3.3. The Multiple Depot Mixed Vehicle Routing considered in the literature is to minimize the num-
Problem with Backhauls (MDMVRPB) ber of vehicles as the first priority and the distance
traveled as the second priority. Two heuristics
The Multiple Depot Mixed Vehicle Routing have been proposed in Kontoravdis and Bard
Problem with Backhauls (MDMVRPB) is a gener- [23] and Zhong and Cole [47].
alization of the MVRPB. In the MDVRPB limita-
tion (E) is relaxed such that we instead of just 3.6. The Vehicle Routing Problem with
considering a single depot are faced with problems Simultaneous Deliveries and Pickups (VRPSDP)
where several depots are present. At each depot a
limited fleet of vehicles is available, and a vehicle In the Vehicle Routing Problem with Simultane-
should start and end its duty at the same depot. ous Deliveries and Pickups (VRPSDP) a subset of
Heuristics for the problem are proposed by Nagy the customers simultaneously demand goods
and Salhi [27,33]. They denoted the problem the from––and supply goods to––the depot, and thus
Multi Depot Vehicle Routing Problem with Pickup both a delivery and a pickup should occur at these
and Deliveries. customers. The pickup and delivery should be per-
formed simultaneously such that each customer is
3.4. The Vehicle Routing Problem with Backhauls visited only once by a vehicle. Unloading is obvi-
and Time Windows (VRPBTW) ously done before loading at these customers.
The simultaneous pickup and delivery operation
The Vehicle Routing Problem with Backhauls decreases the customersÕ expenses or inconven-
and Time Windows (VRPBTW) extends VRPB by ience associated with handling vehicles, but may
assigning a time window to each customer, by hav- result in longer routes as illustrated in Fig. 2.
ing travel times associated with each pair of loca- This problem was first introduced by Min [25]
tions, and by having service times associated with in the context of transportation material between
the customers. Visits at a customer should start public libraries and a library administration center
within the time window. If the vehicle arrives too (acting as a depot). Halse [19] presented exact and
early at a customer it has to wait until the start heuristic methods for the problem and Dethloff
of the time window. If the vehicle arrives too late [9,10] considered heuristic algorithms. Nagy and
the route is invalid. Limitations (B) and (D) from Salhi [33] used their MVRPB heuristic to solve
the VRPB are relaxed in the VRPBTW. The objec- the problem, but apparently the ‘‘simultaneous’’
tive of VRPBTW is either to minimize the total constraint is not handled by the heuristic. This is
traveled distance or to minimize the number of discussed in further detail by Dethloff [10]. Two
vehicles as the first priority and then minimize variants of the problem have been proposed re-
the total traveled distance as the second priority. cently. Nagy and Salhi [33] introduce a multi depot
 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775 755

simultaneously. The tour is ended by visiting the

first couple of customers again, this time in the re-
verse order to perform the omitted pickups. This
creates a tour that looks like a lasso, as the first
customers that are visited twice form the spoke
of the lasso, while the customers that are visited
once form the loop of the lasso.
These two problem variants cannot be solved
by the heuristic presented in this paper in its
present form. It would only require minor
modifications to the heuristic and the underlying
Fig. 2. An example showing that simultaneous pickup and model to be able to solve these problems
delivery at customers may increase the overall route lengths. though.
The four customers have pickup/delivery requests of 2/2, 1/2, 1/
2, 2/0 respectively. The vehicle has a capacity C of six units, and
normal Euclidean distances are used. In a MVRPB setting, the
shortest route is D1, P2/D2, P4/D4, P3/D3, P1 of total length
4. Problem transformations
7.66. If simultaneous pickup and deliveries are demanded, the
shortest route becomes P3/P3, P2/D2, P4/D4, P1/D1 of total This section describes how each of the problems
length 8.65. discussed in Sections 3.1–3.6 can be transformed
to a Rich PDPTW. The basic transformation is
version of the problem, while Angelelli and Man- to represent a linehaul customer by a request with
sini [2] solve a version with time windows to opti- a pickup at the depot and a delivery at the linehaul
mality using column generation. The heuristic customer. Backhaul customers are represented by
proposed in the present paper is not tested on a request with a pickup at the backhaul customer
the two last problem types although the underlying and a delivery at the depot. This transformation
PDPTW model without modifications could han- might seem sufficient to represent the MVRPB
dle these problem classes also. but it has the flaw that it allows a vehicle to go
back to the depot for re-stocking or offloading
3.7. Other backhauling problems and afterwards continue its duty. This is not al-
lowed in a standard MVRPB. The problem is eas-
Wade and Salhi [45] introduce a problem that ily solved by assigning precedences to the different
generalizes VRPB and MVRPB. In this problem tasks: pickups at the depot get precedence 1, deliv-
one is not allowed to mix linehaul and backhaul eries at linehaul customers and pickups at back-
customers on a route freely. A vehicle can only haul customers get precedence 2 and deliveries at
start to serve backhaul customers after a certain the depot get precedence 3.
percentage of the linehaul load has been delivered. The backhaul after linehaul constraint (A)
If this percentage is set to 0% then we get the found in VRPB is also easily modeled using prec-
MVRPB and if the percentage is set to 100% then edences. Instead of giving linehaul and backhaul
we get the VRPB. Percentages in between 0% and customers identical precedences, we assign prece-
100% result in a blend between VRPB and dence 2 to the linehaul deliveries, precedence 3 to
MVRPB. the backhaul pickups and precedence 4 to the
Halskau et al. [17] propose a backhauling prob- deliveries at the depot.
lem with so called lasso tours. In their problem In the VRPB we have to use a specified number
most customers require both a pickup and a deliv- of vehicles as stated by constraint (D). Our model
ery. At the first few customers visited on a route a only allows us to set an upper bound on the num-
delivery is performed to free up some room in the ber of vehicles, so we need to model a vehicle
vehicle, at the customers in the middle of the route, equality constraint. This is done by modifying
the delivery and pickup operation is performed the distance matrix by setting the distance from
756 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775

the start terminal to the end terminal of each vehi-

cle to M, where M is a sufficiently large number.
This forces the heuristic towards solutions with
at least one request on each route in order to avoid
the penalty M.
The VRPB constraint (B) saying that no route
can consist of backhauls only, is handled in a sim-
ilar way. Here we add the penalty M to the cost of
each edge from a start terminal to one of the back-
haul pickup locations. This drives the heuristic to-
wards solutions where such edges are not used,
which means that at least one linehaul customer
is served before a backhaul customer.
The simultaneous delivery and pickup con-
straint in VRPSDP is also modeled using penal- Fig. 3. Modeling of simultaneous delivery and pickup. Request
1 is a delivery to a customer, request 2 represents the
ties. As before, the delivery to a customer is simultaneous pickup at the same customer and request 3 is
modeled by a request from the depot to the cus- another unrelated request. The names ‘‘Px’’ denotes ‘‘the
tomer and a pickup at a customer is modeled as pickup of request x’’ and ‘‘Dx’’ denotes ‘‘the delivery of
a request going from the customer to the depot. request x’’. Edge weights are the distances dij. In order to ensure
In order to ensure that the delivery and pickup that D1 is followed by P2 we increase all other distances from
D1 with M, while the distance from D1 to P2 is set to 0. In this
occur ‘‘simultaneously’’ we modify the distance way, the algorithm will first visit the pickup site of request 1 (the
matrix. The distance from a delivery visit to the depot) and then travel to the delivery site of request 1 (the
simultaneous pickup visit is set to 0, while the dis- customer site). We might perform other visits along the dashed
tances from the pickup to all other visits are in- edges. After performing the delivery of request 1, only one edge
creased by the penalty term M. This forces the has cost less than M, hence we go to P2 which is the
simultaneous pickup.
heuristic to create routes that visit the simultane-
ous pickup after a delivery. The situation is illus-
trated in Fig. 3.
The multiple depots in the MDMVRPB are set of vehicles Fi contain that one vehicle only.
harder to model even though the underlying We still represent each linehaul customer by
PDPTW model already supports multiple depots. one request. All pickups of these linehaul re-
The problem is that we until now have modeled quests take place at a virtual depot. All distances
a linehaul customer by a pickup at the depot and to and from the virtual depot are set to 0. Back-
a delivery at the customer, and vice versa for the haul customers are represented in the same
backhaul customers. In the multi depot problems way––by a pickup at the backhaul customer
we cannot assign a request to a given depot in and a delivery at the virtual depot. The idea is
advance as we do not know where the pickup that linehaul requests should travel via the dum-
of a linehaul request or the delivery of a back- my pickup location and backhaul requests
haul request should occur. To model this kind should travel via the dummy delivery location.
of constraint we do the following. For each vehi- This is ensured using precedences: Linehaul pick-
cle in the problem (remember that in the ups get precedence 1, pickups of the dummy re-
MDMVRPB a fixed number of vehicles is avail- quests get precedence 2, linehaul deliveries and
able in each depot) we create a dummy request backhaul pickups get precedence 3, deliveries of
with pickup and delivery locations at the depot the dummy requests get precedence 4 and line-
of the vehicle. There is no demand associated haul deliveries get precedence 5. This forces
with the dummy requests. A dummy request the dummy request to ‘‘surround’’ the linehaul
should only be served by the vehicle it is de- deliveries and backhaul pickups such that the
signed for, which is ensured by letting its feasible distance to and from the right depot is used.
 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775 757

Fig. 4. An example of a MDMVRPB route with two linehaul customers and one backhaul customer. The linehaul customers are
represented by requests 1 and 2 and the backhaul customer is represented by request 3. Request 4 is the dummy request. The start and
end terminals are represented by squares, the visits of the normal requests are represented by circles and the visits of the dummy request
are represented by hexagons. Pickups and deliveries at the depot are shown in grey and the precedence of the visits is displayed
underneath the route. One can observe that the actual MDMVRPB route can be inspected by looking at the white visits; here the
hexagons should be viewed as depot visits and the normal deliveries and pickups correspond to the linehaul and backhaul customers
respectively.

Fig. 4 shows an example of a MDMVRPB route i + n + 2. Pickups and deliveries that corresponds
with two linehaul customers and one backhaul to visits at the customers gets precedence n + 1.
customer. The same idea can be used for the five other prob-
A remark should be made about penalty based lems as well.
modeling: If a feasible solution exists that does
not violate any of the constraints, the optimal
solution will not contain any of the penalty terms. 5. Solution method
However, since we use heuristics for solving the
model, we may end up with a solution which still Recent work on local search methods indicate
contains some penalties. This can easily be de- that larger neighborhoods may be needed to solve
tected by inspecting the objective value and the some difficult optimization problems as shown by
heuristic can either be repeated (hoping that a sec- e.g. Ahuja et al. [1]. Due to the size of the neigh-
ond run will find a better solution) or some man- borhoods, various heuristics are generally used to
ual adjustment of the data may be needed, e.g. by search the neighborhood in order to keep the time
increasing the number of vehicles or by removing complexity at a reasonable level. This means, that
some customers which cannot be handled. It the performance of a local search algorithm is lim-
should, however, be pointed out that the heuristic ited by the quality of the heuristic that searches the
has never produced any infeasible solutions dur- neighborhood. To work around this bottleneck,
ing the computational experiments performed in Ropke and Pisinger [31] proposed to use several
Section 6. heuristics to search the neighborhood, where the
We made heavy use of precedences in the trans- frequency of using each heuristic is based on some
formations described above. The precedences can empirical evidence from the search. An extended
also be used to speed up the heuristic when faced version of this heuristic is used to solve our
with the problem types described in this paper. PDPTW model.
Consider for example the MVRPB where several The heuristic is based on Large Neighborhood
pickup and deliveries occur at the depot and all Search (LNS) as proposed by Shaw [36] and it
permutations of the pickups at the depot within has similarities with the Ruin and Recreate
a route are feasible and equally good as long as (R&R) framework proposed by Schrimpf et al.
the deliveries stay fixed (and similarly for the back- [34]. Our heuristic repeatedly runs through the fol-
haul deliveries). We can use precedences to create lowing steps:
an ordering on the pickups and deliveries at the
depot such that only one permutation is valid. LNS iteration
We enumerate the request from 1 to n. If request 1. Choose a removal heuristic R and an insertion
i involves a pickup at the depot, then this pickup heuristic I.
gets precedence i, if request i involves a delivery 2. Remove a number q of requests from the routes
at the depot then this delivery gets precedence using heuristic R.
758 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775

3. Insert the free requests into the existing routes • Cluster removal: Attempt to partition the nodes
using heuristic I. into subsets so that the nodes in each subset are
4. Evaluate the objective function of the new somehow ‘‘close to each other’’. For a more
solution. detailed description of this removal heuristics
5. If the objective function is improved, accept the see Section 5.3.
new solution. Otherwise accept the new solution • History based removal: This heuristic makes use
with a probability that depends on the increase of historical information when removing
of the objective function. requests. Two variants of this heuristic have
been considered as will be described in Sections
The heuristic differs from the ordinary LNS 5.4 and 5.5.
and R&R methods by incorporating several
large neighborhood heuristics, which are applied The first three removal heuristics have been
with a variable frequency controlled by a learn- used previously [31] while the three last are new.
ing layer. Each insertion or removal heuristic in In order to insert the requests we use the five
the LNS heuristic may have various properties. insertion heuristics proposed by Ropke and Pi-
Some heuristics are used to intensify the search singer [31]. The heuristics can be divided into
while other heuristics mainly play the role of two classes:
diversifying the search. In this way, the learning
layer not only distributes CPU-time among the • Basic insertion heuristics: which are similar to
various heuristics involved, but also controls the insertion heuristic of Solomon [38]. In each
the intensification or diversification of the search iteration a request is inserted into the solution
based on empirical information. This can be such that the cost function is increased the least
seen as an extension of the tabu search methods possible.
described by Hertz et al. [21]. One may also see • Regret insertion heuristics: which are similar to
the LNS algorithm as a variant of Variable heuristics proposed by Potvin and Rousseau
Neighborhood Search (VNS) described by Han- [29] and Tillman and Cain [40]. In each iteration
sen and Mladenovic [18], the main difference of the standard version of the heuristic a request
being that VNS operates on one type of is inserted so as to maximize the gap in the cost
neighborhood with variable depth, while LNS function between inserting the request into its
operates with structurally different neigh- best route and its second best route.
borhoods.
In the PDPTW heuristic the removal heuristic R The insertion heuristics are described in more
removes up to 40% of the requests in each itera- details in [31].
tion. This enables the heuristic to make significant In each step of the PDPTW heuristic one re-
changes to the current solution in a single itera- moval and one insertion heuristic are used. Com-
tion. We use six different removal heuristics in putational experiments have shown that in order
our LNS heuristic; each removal heuristic has its to reach high-quality solutions all removal and
own strategy for choosing the requests to remove. insertion heuristics are necessary, but their contri-
The heuristics are: bution to the solution process may vary during the
search.
• Random removal: The requests are chosen at The monitoring and learning layer observes how
random. often a given removal or insertion heuristic con-
• Shaw removal: Remove related requests, i.e. tributes to a new, accepted solution, and increases
requests that are geographically close to each the probability of choosing the given heuristic
other [36]. according to its success. This is done using roulette
• Worst request removal: Remove the request wheel selection where each heuristic has a probabil-
whose removal decreases the cost function the ity corresponding to its success-rate. In order to
most. ensure that statistical information is collected for
 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775 759

all heuristics throughout the search, each heuristic 5.3. Cluster removal
is used not less than a given lower limit.
The LNS algorithm is basically a local search Given a set of points in the plane we can ask to
algorithm, and hence it can be combined with partition the set into k P 2 disjoint subsets such
most state-of-art local search paradigms. Using that the points within each subset are close to-
the simulated annealing paradigm, we evaluate gether with respect to the distance d(r1, r2). We
the cost function after each LNS step. If the cost say that we partition the points into k clusters.
has decreased or is unchanged, the new solution A heuristic for finding such a partition can be
is always accepted. If the cost has increased, the constructed by modifying KruskalÕs algorithm
solution is randomly accepted with a probability [24] for the minimum spanning tree problem. In-
exponentially decreasing with the increase of the stead of running KruskalÕs algorithm to the end,
cost. it can be stopped when k connected components
are left. These connected components are our
approximation of the desired clusters.
5.1. Measuring the distance between two requests
The clustering algorithm is used in a removal
heuristic as follows. First a route is selected at
In the removal heuristics we need a measure for
random. Then the requests on this route are par-
the distance d(r1, r2) between two requests r1 and
titioned into two clusters. One of these clusters is
r2. Ropke and Pisinger [31] used the following
chosen at random and the requests from the cho-
expression: dðr1 ; r2 Þ ¼ d a1 ;a2 þ d b1 ;b2 where a1 and
sen cluster are removed. If we need to remove
a2 are the pickups of the requests and b1 and b2
more requests then we pick one of the removed
are the deliveries. This works fine for the pure
requests and find a request that is close to the
PDPTW problems but the definition is problem-
chosen request. The new request should come
atic for backhaul problems. Consider for example
from a route that has not been touched by remov-
two requests corresponding to a linehaul and a
als in the current iteration. The route of the new
backhaul customer located far from the depot.
request is partitioned into two clusters and so
Using the old distance function, the distance be-
the process continues until the desired number
tween these two requests would be large even
of requests has been removed. The motivation
though the linehaul and backhaul customer are
for the heuristic is to remove large chunks of re-
located close to each another. Instead we use
lated requests from a few routes instead of remov-
dðr1 ; r2 Þ ¼ 14 ðd a1 ;a2 þ d a1 ;b2 þ d b1 ;a2 þ d b1 ;b2 Þ. If a
ing a few requests from each route. Fig. 5
pickup or a delivery is located at the depot then
illustrates when the cluster removal heuristic can
the distances involving this visit are removed from
be useful.
the formula and the denominator is decremented
accordingly.
5.4. Neighbor graph removal

5.2. Simplified Shaw removal None of the removal heuristics proposed so

far have made any use of historical information
Shaw [36] defines a removal method that re- when removing requests. The decision about
moves related requests. Ropke and Pisinger [31] which requests to remove has been made solely
defines the relatedness between two requests in by using the information available in the current
terms of the distance between the two requests, state.
their capacity demands, temporal information The neighbor graph removal heuristic uses both
and information about which vehicles can serve historical information and the current state to se-
the requests. In this paper we take a simpler ap- lect the requests to remove. The historical informa-
proach as we define the relatedness between two tion is stored in a complete, directed, weighted
requests solely by the distance d(r1, r2) between graph called the neighbor graph. The graph con-
the requests. tains a node for each visit in the problem. The
760 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775

Fig. 5. Cluster Removal example: The circles mark the delivery locations, all pickups take place at the depot (marked by the square).
In the figure to the left we have a suboptimal solution and we would like to move to the solution shown in the right part of the figure
where requests h–k are placed on the same route as requests a–f. To reach this solution we need to remove requests h, i, j and k at once.
If just one of the requests h, i, j or k is left on route 2 then the insertion heuristics most likely are going to insert the rest of the requests
back into route 2. The removal heuristics presented so far may not be able to remove all of the requests at once, but the cluster removal
heuristic does just that. The result of applying the clustering algorithm on route 2 would be the two clusters g, l, m, n and h, i, j, k and
the last cluster would be removed with probability 0.5.

weight of all edges is initially set to plus infinity. each node in the graph corresponds to a request in
The weight of an edge (a, b) stores the cost of the the PDPTW problem. The weight of an edge (a, b)
best solution encountered so far in which the visit denotes the number of times the two requests cor-
corresponding to a is performed just before the vis- responding to a and b have been served by the
it corresponding to b. Each time a new solution is same vehicle in the t best unique solutions ob-
discovered during the search, the edge weights in served so far in the search. The weights of all edges
the graph are updated if necessary. are initially set to 0, and in all experiments the
The graph is used to remove requests that seem parameter t was set to 100.
to be placed in an unsuitable place. When the re- This graph could be used in a similar fashion as
moval heuristic is invoked it calculates a score for the graph described in Section 5.4. That is, we
each request in the current solution. The score is could examine all planned requests r and calculate
calculated by summing the edge weights in the the score,
neighbor graph corresponding to the neighbor X
scoreðrÞ ¼ wri ;
configuration in the current solution. The requests
i2RðrÞ;i6¼r
with high scores seem to be misplaced and are re-
moved. Every time a request has been removed where R(r) is the set of requests in the route con-
the scores of the surrounding requests are recalcu- taining r and wri is the weight of the edge between
lated. Some randomness is introduced in the re- r and i in the requests graph. A request with a low
moval process in order to avoid removing the score is situated in an unsuitable route according
same requests over and over again. Specifically to the request graph and should be removed.
the randomness ensures that we sometimes do Our initial experiments indicated that this was an
not remove the requests with the highest score unpromising approach, probably because it
but instead remove some with slightly lower strongly counteracts the diversification mecha-
scores. nisms in the LNS heuristic.
Instead, the graph is used to define the relatedness
5.5. Request graph removal between two requests, such that two requests are
considered to be related if the weight of the corre-
In the request graph removal heuristic we store sponding edge in the request graph is high. This
historical information in a graph called the request relatedness measure is used as in the removal heuris-
graph. This graph is complete and undirected and tic proposed by Shaw [36], mentioned in Section 5.2.
 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775 761

6. Computational experiments to the 3 ‘‘old’’ removal heuristics: The simplified

Shaw removal, the worst removal and the ran-
6.1. Parameter tuning dom request removal. This configuration is
denoted standard in the following.
Even though the proposed heuristic is control- • A configuration that uses all six removal heuris-
led by quite a few parameters, we have tried to tics but has disabled the learning layer. This
keep the parameter tuning to a minimum in this implies that all removal and insertion heuristics
paper. This is achieved by using the same param- are equally likely to be selected during the
eters that were found in the parameter tuning per- search. This configuration is denoted 6R––no
formed by Ropke and Pisinger [31], where learning in the following (the ‘‘6R’’ indicates
applicable. The only parameters that have been that six removal heuristics are in use).
tuned are the two parameters that control the • The last configuration is similar to the second,
simulated annealing: the cooling rate c and the but in the third configuration the learning layer
start temperature control parameter w. After each is activated again. The configuration is denoted
LNS iteration the temperature T is updated using 6R––normal learning.
the recursion T := cT. The parameter w controls
the start temperature T0. In order to set the start These three configurations allow us to see if the
temperature T0 we use an estimate of the objective new removal heuristics improve the quality of the
value of a reasonable solution to the problem. heuristic and enable us to judge the effectiveness
This estimate is found by obtaining an initial of the learning layer.
solution using one of our insertion heuristics The second major purpose of the test is to
and calculating the modified objective value z 0 of compare the solution quality obtained by the uni-
this solution. The modified objective value is ob- fied heuristic to the results obtained by more spe-
tained by setting the coefficient b to 0, such that cialized heuristics proposed for the various
unplanned requests do not make the estimate of problem types. We want to know whether a gen-
the objective value unreasonably high. Now the eral heuristic can be competitive with specialized
start temperature is set such that a solution that heuristics.
is 1 + w times larger than z 0 is accepted with The stopping criterion employed is to stop when
probability 0.5 when the current solution has the heuristic has performed 25 000 remove–insert
objective z 0 . We have tested the algorithm on 11 iterations. Each configuration of the heuristic is
problems chosen from 5 of the 6 problem catego- applied 10 times to each problem instance. The re-
ries. The configuration w = 0.05 and c = 0.9998 ported computation times are, however, for a sin-
proved to be the best among the 30 configurations gle run of the algorithm.
tested. The same parameters were used for all All problems considered in the following are
problem types considered in the following geometric problems where distances and travel
sections. times are defined by the Euclidean distance, hence
the triangle inequality is satisfied for both param-
6.2. Test strategy eters. When it has been necessary to calculate dis-
tances from a set of coordinates we have used
The LNS heuristic is tested on nine data sets double precision calculations unless otherwise sta-
proposed in the literature. The test serves two ma- ted. For many of the problem classes we only pre-
jor purposes. The first purpose is to compare three sent a summary of the experiments performed.
configurations of the LNS heuristic against each We refer the reader to our technical report [32]
other. The three configurations are: for the full tables for these problems. All experi-
ments were performed on a Linux based PC,
• A configuration similar to the one used by equipped with 256 MB RAM and a 1.5 GHz Pen-
Ropke and Pisinger [31]. This configuration tium IV processor. The heuristic was implemented
benefits from the learning layer but is limited in C++.
762 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775

6.3. The Vehicle Routing Problem with Backhauls noted that the best solution found by Osman and
(VRPB) WassanÕs heuristic was found in 8 experiments,
while we used 10 experiments for each LNS config-
The first problem type we study is the symmet- uration. If one looks at the sum of the best solu-
ric VRPB. This problem along with the VRPBTW tion costs identified by the heuristics, it is
is probably the most studied of the backhaul prob- observed that the LNS heuristics overall only mar-
lems. Two data sets are proposed in the literature, ginally improve the solutions found by Osman and
the first was proposed by Goetschalckx and Ja- WassanÕs heuristic; for all LNS heuristics the
cobs-Blecha [16] and contains 62 instances with be- improvement is within 0.1%. All together the
tween 20 and 150 customers. The second data set LNS heuristics improved the solution of 26 of
was proposed by Toth and Vigo [41] and contains the 62 problem instances. Finally we see that the
33 instances with between 21 and 100 customers. average solution costs found by the LNS heuristics
We denote the two data sets the Goetschalckx are quite good as they on average are less than
and the Toth–Vigo data sets respectively. 0.5% from the best known solution costs.
Comparing results on the Goetschalckx data set Generally it is hard to compare the running
are a little problematic as at least three different time of our heuristic to that of the heuristics pro-
rounding conventions have been used for calculat- posed in the literature, as the computational exper-
ing the distances between the customers in the data iments have been performed on different
sets. We report our results obtained using two of computers. According to the Linpack benchmarks
the three rounding conventions and refer to our reports [11], our computer has a TPP rating (To-
technical report [32] for a discussion about the ward Peak Performance) of 1311 MFlops while
third rounding convention and the results ob- Osman and WassanÕs Computer has a TPP rating
tained using it. of 25 MFlops, implying that our computer is
Currently the two best heuristics for the VRPB around 53 times faster. The average time for solv-
are probably the heuristic proposed by Toth and ing one problem was between 69 and 73 seconds
Vigo [41] and the heuristic by Osman and Wassan for the LNS heuristics. Osman and Wassan tested
[28]. The heuristic by Toth and Vigo finds good two versions of their heuristic, the fastest version
solutions in a short time while the heuristic pro- using around 2800 seconds to solve one problem
posed by Osman and Wassan spends more time and the slower version using 4000 seconds. This
but on the overall finds better solutions. We com- corresponds to 52 and 75 seconds on our compu-
pare our heuristic with the results found by ter, which is very comparable to the time used by
Osman and Wassan as the running time of our our algorithm. Hence our general heuristic is on
algorithm is comparable to that of Osman and par with Osman and WassanÕs specialized heuristic
WassanÕs heuristic. In order to calculate the dis- both with respect to solution quality and solution
tance between two customers, Osman and Wassan times.
used floating point arithmetic, hence we do the The second way to calculate the distances is to
same (using double precision) in the tests reported round them to one decimal, and store them as an
in Table 1. integers using a fixed point representation. The
The tests show that the configurations using all final result is rounded to an integer. This type of
6 removal heuristics are better than the one using rounding is used in the exact methods developed
only three removal heuristics. This test also shows by Toth and Vigo [42] and Mingozzi et al. [26].
that the configuration that does not include the 34 of the 62 instances have been solved to optimal-
learning layer overall is slightly better than the ity and a good solution is provided for 13 more
configuration including the learning layer, which problems without proving optimality. Table 2
is a bit surprising. All configurations of the LNS summarizes the results obtained by applying the
heuristics do better than Osman and WassanÕs heuristic to these 47 problems (problems A1–K4)
heuristic when looking at how many best known using the same rounding conventions as the exact
solutions the heuristics have found. It should be methods. These results also show that the configu-
Table 1
Goetschalckx problems
Best known Standard 6R––no learning 6R––normal learning
n Cost Avg. sol. Best sol. Avg. Avg. Avg. Best Avg. Avg. Avg. Best Avg. Avg.
gap time sol. sol. gap time sol. sol. gap time
(%) (s) (%) (s) (%) (s)
A1 25 229885.65 229885.65 229885.65 0.00 7 229885.65 229885.65 0.00 7 229885.65 229885.65 0.00 7

S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775

A2 25 180119.21 180119.21 180119.21 0.00 8 180119.21 180119.21 0.00 8 180119.21 180119.21 0.00 8
A3 25 163405.38 163405.38 163405.38 0.00 9 163405.38 163405.38 0.00 10 163405.38 163405.38 0.00 9
A4 25 155796.41 155796.41 155796.41 0.00 10 155796.41 155796.41 0.00 10 155796.41 155796.41 0.00 11
B1 30 239080.15 239080.16 239080.16 0.00 9 239080.16 239080.16 0.00 9 239080.16 239080.16 0.00 9
B2 30 198047.77 198047.77 198047.77 0.00 10 198047.77 198047.77 0.00 10 198047.77 198047.77 0.00 10
B3 30 169372.29 169372.29 169372.29 0.00 13 169372.29 169372.29 0.00 14 169372.29 169372.29 0.00 14
C1 40 250556.77 250846.82 250556.77 0.12 14 250560.15 250556.77 0.00 14 250556.77 250556.77 0.00 13
C2 40 215020.23 215020.23 215020.23 0.00 16 215020.23 215020.23 0.00 16 215020.23 215020.23 0.00 16
C3 40 199345.96 199345.96 199345.96 0.00 18 199345.96 199345.96 0.00 20 199345.96 199345.96 0.00 18
C4 40 195366.63 195366.63 195366.63 0.00 19 195366.63 195366.63 0.00 19 195366.63 195366.63 0.00 19
D1 38 322530.13 322530.13 322530.13 0.00 12 322530.13 322530.13 0.00 12 322530.13 322530.13 0.00 12
D2 38 316708.86 316708.86 316708.86 0.00 11 316708.86 316708.86 0.00 12 316708.86 316708.86 0.00 12
D3 38 239478.63 239478.63 239478.63 0.00 13 239478.63 239478.63 0.00 13 239478.63 239478.63 0.00 13
D4 38 205831.94 205831.94 205831.94 0.00 16 205831.94 205831.94 0.00 16 205831.94 205831.94 0.00 15
E1 45 238879.58 238879.58 238879.58 0.00 18 238879.58 238879.58 0.00 18 238879.58 238879.58 0.00 18
E2 45 212263.11 212463.34 212263.11 0.09 23 212263.11 212263.11 0.00 23 212458.75 212263.11 0.09 22
E3 45 206659.17 206710.33 206659.17 0.02 26 206697.72 206659.17 0.02 27 206761.96 206659.17 0.05 26
F1 60 264299.6 268346.03 267060.43 1.53 31 268430.58 267060.43 1.56 30 268306.24 267060.43 1.52 29
F2 60 265653.47 265214.16 265214.16 0.00 29 265214.16 265214.16 0.00 29 265214.16 265214.16 0.00 28
F3 60 241120.77 241969.77 241969.77 0.35 37 241969.77 241969.77 0.35 36 241969.77 241969.77 0.35 35
F4 60 233861.85 235175.20 235175.20 0.56 43 235528.13 235175.20 0.71 44 235449.66 235175.20 0.68 42
G1 57 306305.4 306388.11 306305.40 0.03 23 306322.98 306305.40 0.01 23 306354.90 306305.40 0.02 22
G2 57 245440.99 245529.35 245440.99 0.04 29 245440.99 245440.99 0.00 28 245440.99 245440.99 0.00 27
G3 57 229507.48 229507.48 229507.48 0.00 33 230737.17 229507.48 0.54 32 230583.46 229507.48 0.47 30
G4 57 235251.47 232913.81 232521.25 0.17 32 233006.36 232521.25 0.21 32 233263.98 232521.25 0.32 31
G5 57 221730.35 221826.32 221730.35 0.04 35 222435.96 221730.35 0.32 36 222442.67 221730.35 0.32 35
G6 57 213457.45 213541.70 213457.45 0.04 40 214090.55 213457.45 0.30 42 213457.45 213457.45 0.00 39
H1 68 268933.06 269342.45 268933.06 0.15 41 269467.78 268933.06 0.20 42 269317.64 268933.06 0.14 39
H2 68 253365.5 253423.34 253365.50 0.02 49 253462.09 253365.50 0.04 49 254194.18 253365.50 0.33 47
H3 68 247449.04 247532.87 247449.04 0.03 56 247508.59 247449.04 0.02 55 247449.04 247449.04 0.00 53
H4 68 250220.77 250317.37 250220.77 0.04 52 250269.07 250220.77 0.02 53 250269.07 250220.77 0.02 52
H5 68 246121.31 246532.25 246121.31 0.17 58 246767.73 246121.31 0.26 58 246217.90 246121.31 0.04 55
H6 68 249135.32 249294.67 249135.32 0.06 55 249231.92 249135.32 0.04 57 249206.96 249135.32 0.03 55
I1 90 351606.91 350958.02 350258.81 0.20 55 350852.85 350245.28 0.17 54 350897.94 350247.61 0.19 52
I2 90 309955.04 312489.95 309943.84 0.82 66 311016.93 309943.84 0.35 65 310434.77 309943.84 0.16 63
I3 90 294507.38 295236.14 294507.38 0.25 86 294858.13 294507.38 0.12 83 294821.76 294507.38 0.11 81
I4 90 295999.65 296820.65 295988.45 0.28 79 296159.12 295988.45 0.06 77 296401.46 295988.45 0.14 76

763
(continued on next page)
 764
Table 1 (continued)
Best known Standard 6R––no learning 6R––normal learning
n Cost Avg. sol. Best sol. Avg. Avg. Avg. Best Avg. Avg. Avg. Best Avg. Avg.
gap time sol. sol. gap time sol. sol. gap time
(%) (s) (%) (s) (%) (s)
I5 90 302524.33 302707.04 301236.01 0.49 76 301909.59 301236.01 0.22 75 301980.98 301236.01 0.25 74
J1 95 335593.42 336680.78 335006.68 0.50 60 336522.31 335006.68 0.45 58 336789.92 335479.75 0.53 56

S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775

J2 95 310800.53 312206.97 310417.21 0.58 71 312458.56 310417.21 0.66 67 311763.08 310417.21 0.43 65
J3 95 279219.21 281807.92 279219.21 0.93 94 279423.74 279219.21 0.07 87 279729.03 279219.21 0.18 84
J4 95 296773.38 298412.68 297232.88 0.63 77 297781.22 296533.16 0.42 74 297344.74 297086.58 0.27 72
K1 113 395546.4 397774.56 394846.98 0.86 86 395993.78 394375.63 0.41 83 397076.46 395006.60 0.68 81
K2 113 363214.24 365791.18 362656.70 1.01 100 362998.61 362130.00 0.24 97 363253.47 362130.00 0.31 96
K3 113 366222.05 367806.64 365694.08 0.58 99 366218.02 365694.08 0.14 97 366388.14 365694.08 0.19 95
K4 113 349038.84 351441.74 348949.39 0.71 113 349266.17 348949.39 0.09 111 349241.78 348949.39 0.08 108
L1 150 426017.86 428037.41 426013.41 0.48 162 427658.80 426013.41 0.39 153 427641.03 426281.89 0.38 149
L2 150 402245.17 402073.43 401466.27 0.21 192 401587.25 401228.80 0.09 181 401492.36 401247.70 0.07 176
L3 150 403886.22 404784.84 402677.72 0.52 187 403029.19 402677.72 0.09 176 402860.67 402677.72 0.05 174
L4 150 384844.01 387660.68 384636.33 0.79 220 385207.32 384636.33 0.15 207 385073.14 384636.33 0.11 205
L5 150 388061.69 390091.24 387564.55 0.65 210 388677.62 387564.55 0.29 211 389778.12 387564.55 0.57 200
M1 125 400860.79 402962.88 401006.99 1.02 108 401540.39 398913.70 0.66 104 401666.48 398913.70 0.69 102
M2 125 398908.71 400924.09 399001.11 0.53 108 401724.68 399336.27 0.73 102 401347.29 398827.67 0.63 100
M3 125 377352.81 379362.69 377411.62 0.85 122 378502.30 377212.23 0.62 115 378031.96 376159.13 0.50 114
M4 125 348624.42 349984.33 348624.42 0.45 147 348663.06 348417.94 0.07 140 348905.97 348532.69 0.14 137
N1 150 408926.4 414655.53 409210.18 1.40 162 414044.03 410789.32 1.25 156 414915.65 410419.05 1.46 155
N2 150 409280.16 413434.54 410595.02 1.02 164 413124.59 409385.19 0.94 155 415985.72 411131.25 1.64 153
N3 150 396167.85 402418.80 398841.27 2.05 181 399363.23 394337.86 1.27 177 400984.40 396827.00 1.69 170
N4 150 397753.86 401362.13 397363.45 1.67 178 402131.56 398965.12 1.86 172 400553.31 394788.36 1.46 170
N5 150 376431.84 380168.38 375895.96 1.79 222 377447.83 373476.30 1.06 214 378201.49 375201.45 1.27 210
N6 150 377665.19 381099.86 377368.09 1.96 216 376612.61 373758.65 0.76 211 376966.15 373789.70 0.86 209
Tot. 18 058 230 18 124 900 18 055 590 4536 18 093 048 18 042 916 4405 18 098 312 18 044 860 4299
Avg. 0.43 73 0.29 71 0.31 69
BTPB 20 24 23
#B 36 43 53 46
The table compares the results obtained by the three configurations of the LNS heuristics with the best results obtained by Osman and WassanÕs heuristic [28]. The two
first columns show the problem name and the number of customers in the problem. The third column displays the best solution found by Osman and WassanÕs heuristic.
The rest of the columns are divided into three sections, one for each configuration. These should be interpreted as follows: avg. sol.––the average of the solution costs
obtained in the 10 experiments, best sol.––the cost of the best solution found in the 10 experiments, avg. gap (%)––the gap between average and best known solution cost,
avg. time (s)––the average time needed to perform one experiment (in seconds). The best solution for each problem instance is marked with bold. The row Tot. at the
bottom of the table gives the sum of the given column and the row Avg. gives the average of the column. The row BTPB reports the number of problem instances where a
particular configuration found solutions that were better than the previous best known solution, the row #B contains the number of times the heuristic found the best
known solution to a problem.
 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775 765

Table 2
Solving the 47 first Goetschalckx problems using distances rounded to one decimal
Avg. gap (%) #B Avg. time (s) Opt. BTPB
Standard 0.28 35 39 28 8
6R––no learning 0.18 38 40 28 8
6R––normal learning 0.17 36 40 28 8
Each row in the table corresponds to one of the three LNS configurations. The columns Avg. gap (%) and Avg. time (s) should be
interpreted like the corresponding entries in the Avg. row in Table 1. The rest of the columns are: #B––the number of problems where
the best known solution was reached, Opt. the number of optimal solutions found (out of 34 known optimal solutions), BTPB––the
number of problems for which the heuristic improved the solutions found by the branch and bound methods. The improved solutions
correspond to problems were the branch and bound algorithms did not reach optimality because they were stopped before optimality
was proved.

rations that use the new removal heuristics are bet- of the Goetschalckx problems, and it has been
ter than the one that only uses the three old re- studied by Halse [19] and Wade and Salhi [44].
moval heuristics. This time the configurations The other data set, which was proposed by Nagy
with and without the learning layer are virtually and Salhi [27], is constructed by transforming 14
equally good. All configurations find 28 optimal well-known CVRP instances into MVRPB in-
solutions out of the 34 optimal solutions reported stances. Three MVRPB instances are constructed
by Toth and Vigo [42] and Mingozzi et al. [26]. from each CVRP instance, having 10%, 25% and
Eight new best solutions were found in the tests. 50% of the customers transformed to backhaul
The Toth–Vigo data set have been approached customers. Heuristics are applied to the last data
by the exact methods of Toth and Vigo [42] and set by Dethloff [9] and Nagy and Salhi [27,33].
Mingozzi et al. [26] and by the heuristics of Cris- We decided to test our heuristic on the MVRPB
pim and Brandao [7], Osman and Wassan [28] by using the last data set.
and Toth and Vigo [41]. Table 3 reports the results The chosen data set contains 42 problems with
found by the LNS heuristic compared with the 50–199 customers. Table 4 compares the solutions
best known results from the literature. We see that obtained by the LNS heuristics to the solutions ob-
the configuration with learning enabled provides tained by Nagy and Salhi. Unfortunately it is not
the best solutions on the average; furthermore it possible to include the results obtained by Dethloff
is the only one which identifies all known optimal [9] in the table as Dethloff only tested his algorithm
solutions. The configuration without learning on a subset of the problems. The heuristic named
overall finds slightly better solutions compared to NS1 in the table is a construction algorithm and
the learning version when summing the best solu- the heuristic named NS2 is a construction heuristic
tion from the ten experiments. The LNS heuristics followed by an improvement algorithm. Both are
improve the best known solutions to 5 of the much faster than the LNS heuristics. The compar-
problems. ison shows that great improvements can be
A class of asymmetric problem instances was achieved by using a more advanced heuristics such
proposed by Toth and Vigo [42], but we have as the LNS heuristic proposed here, as we get re-
not included this data set in our test even though sults that are more than 10% better than those ob-
our PDPTW model would be able to handle the tained by the simpler heuristics. We succeeded in
asymmetric problems. improving the best known solution for 41 out of
the 42 problems. On the last problem we matched
6.4. The Mixed Vehicle Routing Problem with the solution reported by Nagy and Salhi. Notice
Backhauls (MVRPB) that the average solution cost decreases when more
customers are turned into backhaul customers in
Two data sets have been proposed for the the solutions provided by the LNS heuristic. This
MVRPB. The first set is based on a relaxed version is expected as a greater percentage of backhaul
 766
Table 3
Toth–Vigo data set
Best known Standard 6R––no learning 6R––normal learning
n Cost Opt Reference Avg. Best Avg. Avg. Avg. Best Avg. Avg. Avg. Best Avg. Avg.
sol. sol. gap time sol. sol. gap time sol. sol. gap time
(%) (s) (%) (s) (%) (s)
EIL22.50A 21 371 X TV + EHP 371 371 0.00 8 371 371 0.00 8 371 371 0.00 8
EIL22.66A 21 366 X TV + EHP 366 366 0.00 7 366 366 0.00 8 366 366 0.00 7

S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775

EIL22.80A 21 375 X TV + EHP 375 375 0.00 7 375 375 0.00 8 375 375 0.00 8
EIL23.50A 22 682 X TV + EHP 709 682 3.94 13 682 682 0.00 12 682 682 0.00 12
EIL23.66A 22 649 X TV + EHP 654 649 0.77 12 649 649 0.00 13 649 649 0.00 13
EIL23.80A 22 623 X TV + EHP 625 623 0.26 11 623 623 0.00 12 623 623 0.00 12
EIL30.50A 29 501 X TV + EHP 501 501 0.00 17 501 501 0.00 19 501 501 0.00 18
EIL30.66A 29 537 X TV + EHP 537 537 0.00 13 537 537 0.00 14 537 537 0.00 14
EIL30.80A 29 514 X TV + EHP 514 514 0.00 13 514 514 0.00 14 514 514 0.00 14
EIL33.50A 32 738 X TV + EHP 738 738 0.00 17 738 738 0.00 20 738 738 0.00 20
EIL33.66A 32 750 X TV + EHP 750 750 0.00 15 750 750 0.00 17 750 750 0.00 16
EIL33.80A 32 736 X TV + EHP 737 736 0.18 15 736 736 0.05 15 736 736 0.05 15
EIL51.50A 50 559 X TV + EHP 561 559 0.41 35 559 559 0.00 39 559 559 0.00 36
EIL51.66A 50 548 X TV + EHP 553 548 0.91 30 550 548 0.35 31 549 548 0.11 30
EIL51.80A 50 565 X TV + EHP 569 565 0.65 28 571 565 1.12 29 570 565 0.80 28
EILA76.50A 75 739 X TV + EHP 740 739 0.16 49 739 739 0.00 50 739 739 0.00 48
EILA76.66A 75 768 X TV + EHP 774 768 0.77 44 774 769 0.73 44 772 768 0.51 42
EILA76.80A 75 781 TV + EHP 794 783 1.63 41 794 783 1.72 40 791 783 1.22 39
EILB76.50A 75 801 X TV + EHP 804 801 0.31 42 802 801 0.12 42 803 801 0.25 40
EILB76.66A 75 873 X TV + EHP 876 873 0.38 38 875 873 0.22 38 873 873 0.01 37
EILB76.80A 75 919 X TV + EHP 927 919 0.90 36 924 919 0.58 38 922 919 0.37 37
EILC76.50A 75 713 X TV + EHP 715 713 0.21 60 713 713 0.04 61 713 713 0.00 59
EILC76.66A 75 734 X EHP 740 735 0.75 51 739 734 0.69 51 736 734 0.23 50
EILC76.80A 75 733 TV + EHP 738 734 0.71 48 741 736 1.09 48 738 737 0.70 47
EILD76.50A 75 690 X TV + EHP 702 690 1.77 71 696 690 0.81 75 691 690 0.20 71
EILD76.66A 75 715 TV + EHP 717 715 0.22 59 716 715 0.20 60 715 715 0.00 57
EILD76.80A 75 694 EHP 699 694 0.72 53 699 695 0.76 55 696 694 0.26 53
EILA101.50A 100 842 OSMAN 845 837 1.72 138 840 831 1.05 137 836 831 0.55 129
EILA101.66A 100 846 X TV + EHP 852 846 0.67 99 848 846 0.21 100 846 846 0.05 99
EILA101.80A 100 875 OSMAN 872 862 1.77 91 869 857 1.41 87 866 861 1.03 86
EILB101.50A 100 933 EHP 930 925 0.54 82 928 925 0.31 79 929 925 0.38 77
EILB101.66A 100 998 OSMAN 1007 994 1.79 69 1010 989 2.13 66 1001 991 1.24 66
EILB101.80A 100 1021 OSMAN 1022 1018 1.43 63 1021 1010 1.26 61 1015 1008 0.65 61
Tot. 23 189 23 314 23 160 1373 23 251 23 140 1394 23 201 23 142 1349
Avg. 0.71 42 0.45 42 0.26 41
BTPB 5 5 5
#B 28 26 28 29
The column opt indicates if optimality is proven for the particular instance and the column reference points to the algorithm that found the solution in the best known column. TV
refers to the exact method by Toth and Vigo [42], EHP refers to the exact algorithm by Mingozzi et al. [26] and OSMAN refers to the heuristic by Osman and Wassan [28].
 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775 767

Table 4
Nagy–Salhi MVRPB instances
NS1 NS2 Standard 6R––no learning 6R––normal learning
10% 1011 995 956 (3.9%) 955 (4.0%) 956 (3.9%)
25% 1034 998 923 (7.5%) 923 (7.5%) 922 (7.6%)
50% 1045 991 881 (11.1%) 881 (11.1%) 881 (11.1%)
This table compares the solutions obtained by the LNS heuristic to those obtained by Nagy and Salhi [27,33]. Each row reports the
average solution over 14 MVRPB instances with a particular percentage of backhaul customers (10%, 25% or 50%). The columns NS1
and NS2 contain the best results reported by Nagy and Salhi in [33] and [27] respectively. The last three columns show the results
obtained by the LNS heuristic. The numbers in parenthesis show how much better the LNS solutions are compared to the solutions
reported by Nagy and Salhi.

Table 5
Comparison of LNS configurations applied to the Nagy–Salhi MVRPB instances
Standard 6R––no learning 6R––normal learning
Avg. #B BTPB Avg. Avg. #B BTPB Avg. Avg. #B BTPB Avg.
gap (%) time (s) gap (%) time (s) gap (%) time (s)
10% 0.51 10 13 129 0.43 11 13 133 0.37 11 13 133
25% 0.49 11 14 135 0.38 9 14 142 0.30 11 14 143
50% 0.71 7 13 164 0.45 10 14 178 0.41 12 13 178
Each row summarizes 14 instances with the same percentage of backhaul customers. The meaning of the headings is as in Table 2.

customers leads to greater flexibility in the plan- ers is around 50%. Long routes imply that more
ning as long as the percentage of backhaul custom- time is spent in the insertion heuristics.
ers is not greater than 50%. It is worth noting that
Nagy and SalhiÕs results do not show this
behavior. 6.5. The Multiple Depot Mixed Vehicle Routing
Table 5 compares the three LNS configurations. Problem with Backhauls (MDMVRPB)
The results show that the configurations with six
removal heuristics overall are better than the one Only one data set has been proposed for the
with three removal heuristics when one compares MDMVRPB. This data set was proposed by Nagy
the gaps. The results also show that the configura- and Salhi [33] and is constructed from Gillett and
tion with the learning layer enabled is better than JohnsonÕs 11 multi depot vehicle routing problems.
the one without the learning layer. One can also Each of the 11 problems are turned into three
notice that the computation time increases as more MDMVRPB problems by creating problems with
customers are turned into backhaul customers. 10%, 25% and 50% backhaul customers; thus the
This behavior can most likely be explained by MDMVRPB data set contains 33 problems with
the fact that routes in general contain many cus- between 50 and 249 customers. The only heuristics
tomers when the percentage of backhauls custom- that have been applied to the problems so far are

Table 6
Nagy–Salhi MDMVRPB instances
NS1 NS2 Standard 6R––no learning 6R––normal learning
10% 2008 1996 1798 (9.9%) 1795 (10.1%) 1799 (9.9%)
25% 2050 2007 1671 (16.7%) 1663 (17.1%) 1662 (17.2%)
50% 2088 1993 1512 (24.1%) 1510 (24.2%) 1509 (24.3%)
The columns NS1 and NS2 contain the best results reported by Nagy and Salhi in [33] and [27] respectively.
768 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775

those by Nagy and Salhi which also were used for vehicles, as proposed by Ropke and Pisinger [31].
the MVRPB discussed in Section 6.4. Gelinas et al. [13] proposed a data set containing
In Table 6 we compare the results obtained by 15 problems with 100 customers and Thangiah
the LNS heuristic with those obtained by the best et al. [39] introduced a data set containing 24 large
heuristics of Nagy and Salhi [27,33]. It has been problems.
necessary to reconstruct the problems from Gillett Our heuristics are tested on both data sets. The
and JohnsonÕs original problems following the results obtained on GelinasÕ data set are presented
description in [33], as the original problems no in Table 8. Five papers have reported results on
longer were available from the authors. We believe this data set: Duhamel et al. [12], Hasama et al.
that the problems have been constructed properly. [20], Reimann et al. [30], Thangiah et al. [39] and
The reconstructed problems have been made avail- Zhong and Cole [47]. It should be noted that
able on the web [46] for future comparisons. apparently there is no standard for how distances
Again, we observe that the LNS heuristic offers should be represented internally in the heuristic,
huge improvements over the simpler heuristics. which makes comparisons a bit problematic. We
This time the solution costs are decreased by up have chosen to represent the distances using dou-
to 24% and the best known solutions to all prob- bles like Reimann et al. [30], as is standard in the
lems were improved. As before we note that the literature about VRPTW heuristics. The tables re-
heuristics proposed by Nagy and Salhi are faster veal that we are able to improve 10 out of the 15
than the LNS heuristic. solutions and reduce the number of vehicles
Table 7 compares the three LNS configurations needed for 5 of the problems. Again the configura-
with each other. The most interesting observation tions using all removal heuristics turns out to be
is that the multi depot problems seem to be the the best.
hardest problems considered so far, as the average The only heuristic that has been applied to the
solutions are farther from the best known solu- large VRPBTW problems is the heuristic by
tions than before, but the results must anyway be Thangiah et al. [39]. Table 9 compares the results
considered as very promising. obtained by this algorithm to the results obtained
by the LNS heuristic. We see that the LNS heuris-
6.6. The Vehicle Routing Problem with Backhauls tic is able to decrease the necessary number of
and Time Windows (VRPBTW) vehicles by a large amount and at the same time
also decrease the traveled distance. The best
The VRPBTW is another well-studied back- known solutions to all 24 problems were im-
hauling problem. The primary objective consid- proved by the LNS heuristic. Table 10 gives fur-
ered in the heuristics described in the literature is ther information about the performance of the
to minimize the number of vehicles used and the LNS heuristic, including the running time. The
secondary objective is to minimize the traveled dis- time increases with the problem size, but its
tance. These objectives are also used in our exper- growth is not alarming. Once again the configura-
iments. The vehicle minimization is done by tions using six removal heuristics found the best
solving the problem for a decreasing number of solutions.

Table 7
Comparison of LNS configurations applied to the Nagy–Salhi MDMVRPB instances
Standard 6R––no learning 6R––normal learning
Avg. #B BTPB Avg. Avg. #B BTPB Avg. Avg. #B BTPB Avg.
gap (%) time (s) gap (%) time (s) gap (%) time (s)
10% 0.93 7 11 204 0.63 10 11 217 0.61 6 11 216
25% 0.97 5 11 219 0.65 6 11 237 0.66 8 11 237
50% 0.88 8 11 258 0.71 6 11 288 0.66 7 11 288
Table 8
Gelinas et al. VRPBTW instances

S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775

Best known Standard 6R––no Learning 6R––normal learning
% BH m Cost Ref Avg. Best Best Avg. Avg. Best Best Avg. Avg. Best Best Avg.
#veh. sol. #veh. time (s) #veh. sol. #veh. time #veh. sol. #veh. time
(s) (s)
BHR101A 10% 22 1831.68 RDH 22.0 1818.86 22 98 22.0 1818.86 22 107 22.0 1818.86 22 109
BHR101B 30% 23 1999.16 RDH 23.0 1959.86 23 94 23.0 1959.56 23 101 23.0 1959.56 23 103
BHR101C 50% 24 1909.84 HKK 24.0 1939.10 24 93 24.0 1939.10 24 100 24.0 1939.10 24 101
BHR102A 10% 19 1677.62 RDH 19.0 1653.19 19 110 19.0 1653.19 19 118 19.0 1653.19 19 121
BHR102B 30% 21 1764.3 TPS 22.0 1750.70 22 103 22.0 1750.70 22 111 22.0 1750.70 22 114
BHR102C 50% 21 1745.7 TPS 22.0 1775.76 22 103 22.0 1775.76 22 111 22.0 1775.76 22 113
BHR103A 10% 15 1371.6 TPS 15.0 1387.57 15 117 15.0 1387.57 15 123 15.0 1387.57 15 128
BHR103B 30% 16 1395.88 RDH 15.0 1390.33 15 108 15.0 1390.33 15 112 15.0 1390.33 15 115
BHR103C 50% 16 1486.56 ZC 17.0 1457.31 17 106 17.0 1456.48 17 113 17.0 1456.48 17 115
BHR104A 10% 11 1205.78 RDH 11.0 1084.22 11 127 11.0 1084.17 11 130 11.0 1084.17 11 132
BHR104B 30% 12 1128.3 RDH 11.0 1163.24 11 119 11.0 1154.84 11 121 11.0 1154.84 11 122
BHR104C 50% 12 1208.46 RDH 11.0 1191.41 11 117 11.0 1191.38 11 119 11.0 1191.38 11 119
BHR105A 10% 16 1544.81 RDH 15.5 1564.88 15 104 15.3 1561.28 15 110 15.4 1561.28 15 109
BHR105B 30% 16 1592.23 RDH 16.0 1583.30 16 97 16.0 1583.30 16 102 16.0 1583.30 16 102
BHR105C 50% 17 1633.01 RDH 16.6 1711.36 16 96 16.6 1710.75 16 100 16.5 1710.19 16 100
Tot. 261 23 495 260.2 23 432 259 1593 260.0 23 418 259 1679 259.9 23 417 259 1703
Avg. 106 112 114
BTPB 10 10 10
B# 5 4 9 10
The first column shows the name of the problem, the next columns are: %BH-ratio of backhaul customers, m-number of vehicles in best known solution, cost-distance
traveled in best known solution, ref-HKK = Hasama et al. [20], RDH = Reimann et al. [30], TPS = Thangiah et al. [39] and ZC = Zhong and Cole [47]. The rest of the
columns report the solutions found by the LNS heuristics: avg. #veh.-average number of vehicles best #veh.-lowest number of vehicles found. The other columns should
be interpreted as in Table 1. The original data files do not specify the latest return time to the depot and the maximum capacity of the vehicle. In our experiments these
parameters have been set to the values they have in the original Solomon problems from which the Gelinas problems were created.

769
770 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775

Table 9
Large VRPBTW instances
TPS Standard 6R––no learning 6R––normal learning
#veh. Cost #veh. Cost #veh. Cost #veh. Cost
250 517 57 509 449 54 256 444 54 711 445 54 499
500 799 94 144 677 83 498 676 82 946 675 82 796
This table compares the three LNS configurations to the heuristics by Thangiah et al. (TPS). The data set contains 12 problems
containing 250 customers and 12 containing 500 customers. The best solutions found by the heuristics have been accumulated and the
table shows the total number of vehicles needed and the total traveled distance for all instances of a particular size. The vehicle capacity
was set to 200 for all problems and no latest arrival time was specified for the depot.

Table 10
Comparison of LNS configurations applied to the large VRPBTW instances
Customers Standard 6R––no learning 6R––normal learning
Avg. #B BTPB Avg. Avg. #B BTPB Avg. Avg. #B BTPB Avg.
#veh. time (s) #veh. time (s) #veh. time (s)
250 37.5 1 12 489 37.3 6 12 492 37.4 5 12 504
500 57.1 0 12 1562 56.8 4 12 1651 56.7 8 12 1570
The Avg. #veh column displays the average of the average number of vehicles needed to serve all customers.

6.7. The Mixed Vehicle Routing Problem with pared to the previous heuristics in Table 11. Again
Backhauls and Time Windows (MVRPBTW) the LNS heuristic is able to find solutions of better
quality compared to the older heuristics. It is inter-
Two datasets have been proposed for the esting to note that the LNS heuristic reaches the
MVRPBTW. Hasama et al. [20] use GelinasÕ data lower bound on the number of vehicles needed to
set by relaxing the linehaul-before-backhaul con- solve the problems on all but one instance. The
straint while Kontoravdis and Bard [23] construct LNS heuristics improved all the previously best
27 new problems from SolomonÕs VRPTW prob- known solutions to the problem instances.
lems. We test our heuristics using Kontoravdis Table 12 provides the usual comparison of the
and BardÕs data set which also has been considered three LNS configurations. It should be observed
by Zhong and Cole [47]. The LNS heuristic is com- that the MRC2 problems turn out to be hard to

Table 11
Kontoravdis MVRPBTW problems
LB KB ZC Standard 6R––no learning 6R––normal learning
#veh. #veh. Cost #veh. Cost #veh. Cost #veh. Cost #veh. Cost
MR2 4 4 1168.53 4 1016.66 4 904.55 4 902.73 4 903.00
MC2 4 4 1094.94 4.625 903.56 4 731.38 4 732.38 4 732.13
MRC2 4 4.5 1496.91 4.125 1330.31 4.125 1125.00 4.125 1129.25 4.125 1127.63
The table compares the results reported by Kontoravdis and Bard [23] (KB) and Zhong and Cole [47] (ZC) with the results obtained
using the LNS heuristics. The primary objective in these problems is to minimize the number of vehicles needed to serve the customers.
The data set is divided into three classes according to the geographical distribution of the customers in the problems: randomly
distributed customers (MR2), clustered customers (MC2), and a mix between the two first categories (MRC2). The MRC2 and MC2
classes both contain 8 problems while the MR2 class contains 11 problems. Each row in the table summarizes the performance on each
class. The column LB #veh. shows the lower bound on the number of vehicles as given by Kontoravdis and Bard.
 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775 771

Table 12
Comparison of LNS configurations applied to KontoravdisÕ MVRPBTW instances
Standard 6R––no learning 6R––normal learning
Avg. #B BTPB Avg. Avg. #B BTPB Avg. Avg. #B BTPB Avg.
gap (%) time (s) gap (%) time (s) gap (%) time (s)
MR2 1.34 4 11 362 0.63 8 11 375 0.63 8 11 368
MC2 0.62 6 8 162 0.60 5 8 165 0.65 5 8 163
MRC2 2.83 5 8 183 1.99 1 8 183 1.76 4 8 180
In all test runs the heuristics reached the same number of vehicles when applied to the same problem. This allows us to report the
avg.gap, which does not make sense if the heuristics use a different number of vehicles to solve the same problem.

solve, as indicated by the rather large gaps. This is nally Angelelli and Mansini [2] presented a class of
not surprising as the MRC2 problems were con- VRPSDP problems with time windows.
structed from SolomonÕs RC2 VRPTW problems, As mentioned earlier we are not going to test
which are known to be hard to solve. One cannot our heuristic on the multi depot and time window
expect that adding the extra complexity of back- variants of the VRPSDP. The problems we choose
haul customers should make the problems easier for our tests are MinÕs problem, DethloffÕs prob-
to solve. lems and the first class of Nagy and SalhiÕs VRP-
SDP problems (the one denoted with an X in
[33]). The results are summarized in Tables 13
6.8. The vehicle routing problem with simultaneous and 14. Again it must be stressed that the heuris-
deliveries and pickups (VRPSDP) tics by Dethloff and Nagy and Salhi are simple
construction heuristics that are substantially faster
Although the VRPSDP is not the problem in than the LNS heuristics.
the backhauling family that has received the most The LNS heuristics find the optimal solution to
attention, there exist nevertheless quite a few data MinÕs problem (the optimal solution was found by
sets for the problem. The first data set was pro- Halse [19]) and are able to improve all of the best
posed by Min [25] and contained only one known solutions to DethloffÕs problems which
problem, which originated from a real-life applica- were found using DethloffÕs construction heuristic.
tion. Halse [19] proposed a set containing 16 prob- The 6R––normal learning configuration is able to
lems constructed from CVRP problems and improve the best known solutions by more than
Dethloff [10] proposed 40 new problems contain- 9%. Having said that, it should be noticed that
ing 50 customers each. Nagy and Salhi [33] con- the LNS heuristics are fairly slow when faced with
structed two classes of VRPSDP problems and this type of problems, because each order is repre-
two classes of multi depot VRPSDP problems. Fi- sented by two requests and introduces significant

Table 13
Summary of the results obtained on the VRPSDP instances
Dethloff NS1 NS2 Standard 6R––no learning 6R––normal learning
Dethloff 824 – – 747 (9.3%) 746 (9.5%) 745 (9.6%)
NS-X 1006 1096 991 927 (6.5%) 925 (6.7%) 919 (7.3%)
The table should be interpreted like Table 4. The row denoted Dethloff summarizes the results obtained on DethloffÕs 40 instances [10]
and the single instance provided by Min [25]. Each of DethloffÕs instances contains 50 customers. The row marked NS-X summarizes
Nagy and SalhiÕs 14 VRPSDP instances of class X [33]. These problems contain between 50 and 200 customers. Results for these
problems are reported by Dethloff [10] and Nagy and Salhi [33,27]. The columns Dethloff, NS1 and NS2 summarize the best results
reported in [10], [33] and [27] respectively.
772 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775

Table 14
Comparison of LNS configurations applied to VRPSDP instances
Standard 6R––no learning 6R––normal learning
Avg. #B BTPB Avg. Avg. #B BTPB Avg. Avg. #B BTPB Avg.
gap (%) time (s) gap (%) time (s) gap (%) time (s)
Dethloff 1.07 24 40 128 0.96 23 40 129 0.58 36 40 155
NS-X 2.81 6 11 685 2.73 7 13 686 2.00 7 12 772

overhead in the algorithm. This also suggests that with learning enabled and using all six removal
this problem type would benefit greatly from a spe- heuristics clearly is the most robust configuration
cialized version of the LNS heuristic where the when faced with these hard problems.
overhead can be avoided. The LNS heuristic also
experiences difficulties when faced with the larger 6.9. Computational experiments conclusion
problems from Nagy and SalhiÕs data set. Here
the avg. gap increases to 2% for the best configura- In Section 6.2 we raised a number of questions
tion, but the heuristic nevertheless improves 13 of that the computational experiments should clarify.
the 14 best known solutions. The configuration The first question was whether it is possible to

Table 15
Summary of experiments
#prob Standard 6R––no learning 6R––normal learning
Avg. gap (%) #B Avg. gap (%) #B Avg. gap (%) #B
Goetschalckx 1 62 0.43 43 0.29 53 0.31 46
Goetschalckx 2 47 0.28 35 0.17 38 0.17 36
Toth–Vigo 33 0.71 26 0.45 28 0.26 29
MVRPB 50% 14 0.71 7 0.45 10 0.41 12
MVRPB 25% 14 0.49 11 0.38 9 0.3 11
MVRPB 10% 14 0.51 10 0.43 11 0.37 11
MDMVRPB 50% 11 0.88 8 0.71 6 0.66 7
MDMVRPB 25% 11 0.97 5 0.65 6 0.66 8
MDMVRPB 10% 11 0.93 7 0.63 10 0.61 6
VRPSDP 1 41 1.07 24 0.96 23 0.58 36
VRPSDP 2 14 2.81 5 2.73 7 2.00 7
MVRPBTW C 8 0.63 6 0.6 5 0.65 5
MVRPBTW R 11 1.34 4 0.63 8 0.63 8
MVRPBTW RC 8 2.83 5 1.99 1 1.76 3
VRPBTW 1 15 4 9 10
VRPBTW 2 24 1 10 13
Avg. 0.81 0.62 0.50
Sum 338 201 234 248
This table shows a summary of the tests performed in this paper. Each row in the table corresponds to a problem class. Most of the
titles in the first row should be fairly self explanatory: Goetschalckx 1––Goetschalckx VRPB without rounding distances, Goetschalckx
2––Goetschalckx VRPB where distances have been rounded to one decimal. VRPSDP 1––Dethloff VRPSDP, VRPSDP 2––Nagy–
Salhi VRPSDP, VRPBTW 1––Gelinas VRPBTW VRPBTW 2––Thangiah VRPBTW. The column #prob displays the number of
problems in each class. The Avg. row shows the averages of the Avg. gap (%) column. The numbers in the avg. row were calculated by
summing the products of the numbers in the #prob column with the numbers in the gap column and dividing the sum by the total
number of problems. This was done to take into account that some data sets contains more problems than others. The missing entries
in the VRPBTW rows have been left out because the primary objective of these problems is to minimize the number of vehicles and not
all test runs resulted in the same number of vehicles. Reporting the gap for these runs could make the heuristic that could not reach the
minimum number of vehicles look too good.
 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775 773

design a unified heuristic for a large class of vehicle transportation problems for a general fleet of
routing problems with backhauls that is able to vehicles.
provide solutions comparable to those obtained For several of the VRPB problem types pre-
by specialized heuristics. We believe that the exper- sented in this paper, we report the first applica-
iments conducted in this paper show that this tions of a metaheuristic to the problem. The
indeed is possible. This is an interesting achieve- results are very promising as we found a new best
ment, as it to a large extent allows practitioners solution to 67% of the problems tested. Even faster
to focus on a single heuristic and apply this to and better performing heuristics could be con-
the problems they are faced with instead of ‘‘rein- structed by specializing the proposed heuristic to
venting the wheel’’ each time a new problem type just one of the problem types. We have chosen
needs to be solved. not to do this to maintain the generality of the
The second question asked to give an evalua- solution approach.
tion of the effect of the three new removal heuris- The present experiments indicate that the com-
tics and the consequence of disabling the learning bination of several neighborhoods makes it easier
layer. Table 15 provides an overview of the exper- for the local search heuristic to explore the solu-
iments performed. The Avg. row displays the over- tion space, and hence to find solutions of high
all gaps between average solutions and best known quality. This conforms to similar observations
solutions. This gap is an indication of the robust- for simpler neighborhoods.
ness of the heuristic. The Sum row contains the The monitoring and learning layer to control
number of problems for which the particular the choice of neighborhoods can be seen as a layer
LNS configuration found the best known solution. which maintains a proper balance between intensi-
The table clearly shows the impact of adding the fication and diversification. Several other ap-
three new removal heuristics, as we see a great proaches have been working with this balance,
improvement in the quality of the heuristic from see e.g. Reactive Tabu Search [4]. In the proposed
configuration 1 to configuration 3. The table also framework we do not explicitly care about which
shows that disabling the learning layer decreases heuristics intensify or diversify the search. The
the overall quality of the results as expected. layer steadily maintains a proper balance of the
Although comparable results can be obtained heuristics so that new, improved solutions are
without the learning layer for specific problem found. The computational results show that the
types, the learning layer apparently helps the algo- learning layer overall is able to increase the robust-
rithm to adapt to all the various problem types. ness of the heuristic but also indicate that further
refinements may be possible as the configuration
without the learning layer occasionally outper-
7. Conclusion formed the configuration that included the learn-
ing layer.
This paper is the first to present a unified heuris- An interesting topic for further research would
tic for a large class of vehicle routing problems be to apply the framework proposed in this paper
with backhauls. For this purpose we have intro- to combinatorial optimization problems outside
duced a Rich VRPTW model which extends the the vehicle routing domain.
ordinary VRP model with time windows, pickup
and delivery pairs, as well as precedence con-
straints. The model is very expressive, and it allows Acknowledgments
us to model all of the most common VRPB models
within the framework, as well as other routing The authors wish to thank Jan Dethloff, George
problems from the literature. The unified model Kontoravdis, Marc Reimann, Sam R. Thangiah
has the additional benefit that it allows us to com- and Daniele Vigo for kindly providing us with
bine pickup and delivery request with a more clean the data sets used in this paper and for answering
VRPB or VRPSPD, as well as scheduling mixed questions regarding the data sets. Furthermore we
774 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775

wish to thank Jakob Birkedal Nielsen for propos- and time windows, Transportation Science 31 (1997) 49–
ing the Cluster Removal heuristic and Gabor 59.
[13] S. Gelinas, M. Desrochers, J. Desrosiers, M.M. Solomon,
Nagy for sending us his working paper. Finally A new branching strategy for time constrained routing
we want to thank the anonymous referees for val- problems with application to backhauling, Annals of
uable comments and corrections. Operations Research 61 (1995) 91–109.
[14] M. Gendreau, G. Laporte, D. Vigo, Heuristics for the
traveling salesman problem with pickup and delivery,
Computers & Operations Research 26 (1999) 699–714.
References [15] H. Ghaziri, I.H. Osman, A neural network algorithm for
the traveling salesman problem with backhauls, Computers
[1] R.K. Ahuja, O. Ergun, J.B. Orlin, A.P. Punnen, A & Industrial Engineering 44 (2003) 267–281.
survey of very large scale neighborhood search [16] M. Goetschalckx, C. Jacobs-Blecha, The vehicle routing
techniques, Discrete Applied Mathematics 123 (2002) problem with backhauls, European Journal of Operational
75–102. Research 42 (1989) 39–51.
[2] E. Angelelli, R. Mansini, The vehicle routing problem [17] Ø. Halskau, I. Gribkovskaia, K.N.B. Myklebost, Models
with time windows and simultaneous pick-up and delivery, for pick-up and deliveries from depots with lasso solutions,
in: A. Klose, M.G. Speranza, L.N. Van Wassenhove in: Proceedings of the 13th Annual Conference on Logis-
(Eds.), Quantitative Approaches to Distribution Logistics tics Research––NOFOMA 2001, Collaboration in logistics:
and Supply Chain Management, Springer-Verlag, 2002, Connecting Islands using Information Technology, Rey-
pp. 249–267. kjavik, Iceland, 2001-06-14–2001-06-15, Chalmers Univer-
[3] S. Anily, The vehicle-routing problem with delivery and sity of Technology, Göteborg, Sweden, 2001, pp. 279–293.
back-haul options, Naval Research Logistics 43 (1996) [18] P. Hansen, N. Mladenovic, An introduction to varia-
415–434. ble neighborhood search, in: S. Voss et al. (Eds.),
[4] R. Battiti, G. Tecchiolli, The reactive tabu search, ORSA Meta-Heuristics, Advances and Trends in Local Search
Journal of Computing 6 (1994) 126–140. Paradigms for Optimization, Kluwer, Boston, 1999,
[5] D.O. Casco, B.L. Golden, E.A. Wasil, Vehicle routing pp. 433–458.
with backhauls: Models, algorithms and case studies, in: B. [19] K. Halse, Modeling and Solving Complex Vehicle Routing
Golden, A. Assad (Eds.), Vehicle Routing: Methods and Problems, PhD thesis, Institute of Mathematical Statistics
Studies, North-Holland, Amsterdam, 1988, pp. 127–147. and Operations Research (IMSOR), Technical University
[6] J.-F. Cordeau, G. Laporte, A. Mercier, A unified tabu of Denmark, 1992.
search heuristic for vehicle routing problems with time [20] T. Hasama, H. Kokubugata, H. Kawashima, A heuristic
windows, Journal of the Operational Research Society 52 approach based on the string model to solve vehicle
(2001) 928–936. routing problem with backhauls, in: Proceedings of the 5th
[7] J. Crispim, J. Brandao, Reactive tabu search and variable World Congress on Intelligent Transport Systems (ITS),
neighbourhood descent applied to the vehicle routing Seoul, 1998.
problem with backhauls, in: MICÕ2001 4th Metaheuristic [21] A. Hertz, E.D. Taillard, D. de Werra, A tutorial on tabu
International Conference, Porto, Portugal, July 16–20, search, in: E.H.L. Aarts, J.K. Lenstra (Eds.), Local Search
2001. in Combinatorial Optimization, Wiley, 1997, pp. 121–136.
[8] G. Desaulniers, J. Desrosiers, A. Ercmann, M.M. Solo- [22] C. Jacobs-Blecha, M. Goetschalckx, The vehicle routing
mon, F. Soumis, VRP with pickup and delivery, in: P. problem with backhauls: Properties and solution algo-
Toth, D. Vigo (Eds.), The Vehicle Routing Problem, rithms, Technical Report, 1992–1998, Georgia Tech
SIAM Monographs on Discrete Mathematics and Appli- Research Corporation.
cations, vol. 9, SIAM, Philadelphia, 2002, pp. 225–242. [23] G. Kontoravdis, J.F. Bard, A GRASP for the vehicle
[9] J. Dethloff, Relation between vehicle routing problems: An routing problem with time windows, ORSA Journal on
insertion heuristic for the vehicle routing problem with Computing 7 (1995) 10–23.
simultaneous delivery and pick-up applied to the vehicle [24] J.B. Kruskal, On the shortest spanning subtree of a graph
routing problem with backhauls, Journal of the Opera- and the traveling salesman problem, Proceedings of the
tional Research Society 53 (2002) 115–118. American Mathematical Society 7 (1956) 48–50.
[10] J. Dethloff, Vehicle routing and reverse logistics: The [25] H. Min, The multiple vehicle routing problem with
vehicle routing problem with simultaneous delivery and simultaneous delivery and pickup, Transportation
pick-up, OR Spektrum 23 (2001) 79–96. Research Part A 23 (1989) 377–386.
[11] J.J. Dongarra, Performance of various computers using [26] A. Mingozzi, S. Giorgi, R. Baldacci, An exact method for
standard linear equation software, University of Tennessee the vehicle routing problem with backhauls, Transporta-
Computer Science Technical Report, CS-89-85, 2004. tion Science 33 (1999) 315–329.
[12] C. Duhamel, J.-Y. Potvin, J.-M. Rousseau, A tabu search [27] G. Nagy, S. Salhi, Heuristic algorithms for single and
heuristic for the vehicle routing problem with back-hauls multiple depot vehicle routing problems with pickups and
 S. Ropke, D. Pisinger / European Journal of Operational Research 171 (2006) 750–775 775

deliveries, European Journal of Operational Research, in [37] H. Süral, J.H. Bookbinder, The single-vehicle routing
press. problem with unrestricted backhauls, Networks 41 (2003)
[28] I.H. Osman, N.A. Wassan, A reactive tabu search meta- 127–136.
heuristic for the vehicle routing problem with backhauls, [38] M.M. Solomon, Algorithms for the vehicle routing and
Journal of Scheduling 5 (2002) 263–285. scheduling problems with time window constraints, Oper-
[29] J.Y. Potvin, J.-M. Rousseau, A parallel route building ations Research 35 (1987) 254–265.
algorithm for the vehicle routing and scheduling problem [39] S.R. Thangiah, J.-Y. Potvin, T. Sun, Heuristic approaches
with time windows, European Journal of Operational to vehicle routing with backhauls and time windows,
Research 66 (1993) 331–340. Computers & Operations Research 23 (1996) 1043–1057.
[30] M. Reimann, K. Doerner, R.F. Hartl, Insertion based ants [40] F.A. Tillman, T.M. Cain, An upper bound algorithm for
for vehicle routing problems with backhauls and time the single and multiple terminal delivery problem, Man-
windows, LNCS 2463 (2002) 135–148. agement Science 18 (1972) 664–682.
[31] S. Ropke, D. Pisinger, An adaptive large neighborhood [41] P. Toth, D. Vigo, A heuristic algorithm for the symmetric
search heuristic for the pickup and delivery problem with and asymmetric vehicle routing problems with backhauls,
time windows, Technical Report 04/13, DIKU, University European Journal of Operational Research 113 (1999)
of Copenhagen, 2004. 528–543.
[32] S. Ropke, D. Pisinger, A unified heuristic for vehicle [42] P. Toth, D. Vigo, An exact algorithm for the vehicle
routing problems with backhauls, Technical Report 04/14, routing problem with backhauls, Transportation Science
DIKU, University of Copenhagen, 2004. 31 (1997) 372–385.
[33] S. Salhi, G. Nagy, A cluster insertion heuristic for single [43] P. Toth, D. Vigo, VRP with backhauls, in: P. Toth, D.
and multiple depot vehicle routing problems with back- Vigo (Eds.), The Vehicle Routing Problem, SIAM Mon-
hauling, Journal of the Operational Research Society 50 ographs on Discrete Mathematics and Applications 9,
(1999) 1034–1042. SIAM, Philadelphia, 2002, pp. 195–221.
[34] G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt, G. [44] A. Wade, S. Salhi, An ant system algorithm for the vehicle
Dueck, Record breaking optimization results––using the routing problem with backhauls, in: MICÕ2001––4th
ruin & recreate principle, Journal of Computational Metaheuristic International Conference.
Physics 159 (2000) 139–171. [45] A.C. Wade, S. Salhi, An investigation into a new class of
[35] M. Sigurd, D. Pisinger, M. Sig, The pickup and delivery vehicle routing problem with backhauls, Omega 30 (2002)
problem with time windows and precendences, Transpor- 487–497.
tation Science 38 (2004) 197–209. [46] Web page: www.diku.dk/~sropke.
[36] P. Shaw, Using constraint programming and local search [47] Y. Zhong, M.H. Cole, A simple approach to linehaul–
methods to solve vehicle routing problems, in: Proceedings backhaul problems: A guided local search approach for the
CP-98 (Fourth International Conference on Principles and vehicle routing problem, Transportation Research Part E,
Practice of Constraint Programming), 1998. in press.