Data Analytics

I need help with a review, please.

DOI 10.1007/s00291-005-0003-6

REGULAR ARTICLE

Ieke le Blanc . Maaike van Krieken .

Harold Krikke . Hein Fleuren

Vehicle routing concepts

in the closed-loop container network of ARN

—a case study

Published online: 17 November 2005

© Springer-Verlag 2005

Abstract In this paper we discuss a real-life case study to optimize the logistics

network for the collection of containers from end-of-life vehicle dismantlers in the

Netherlands. Advanced planning concepts, such as dynamic assignment of dis-

mantlers to logistic service providers, are analyzed using a simulation model.

Based on this model, we periodically solve a vehicle routing problem to gain

insight into the long-term performance of the system. The vehicle routing problem

considered is a multi-depot pickup and delivery problem with alternative delivery

locations. A special characteristic of the problem is the limited vehicle capacity of

two containers. We solve this problem with a heuristic based on route generation

and set partitioning.

Keywords Reverse logistics . Closed-loop supply chain management . Vehicle

routing . Set partitioning . Distribution planning

1 Introduction

Concern for the environment has led to EU legislation for the recovery of discarded

products. The original equipment manufacturer (OEM), as the creator of the prod-

ucts, is responsible for and pays for the reverse chain activities. Extended Producer

Responsibility (EPR) is the starting point for all EU legislation on end-of-life waste

(Spicer and Johnson 2004). EPR extends the responsibility of the producer to cover

the entire life cycle, including end-of-life disposal. The way EPR is implemented is

left to the member states. In this paper we will address a case involving containers

The authors would like to thank Roelof Reinsma and Annemieke van Burik of Auto Recycling

Nederland for their assistance and support during the project. Furthermore, we thank the two

anonymous referees for their valuable comments on the manuscript.

H. M. le Blanc (*) . M. van Krieken . H. Krikke . H. Fleuren

CentER Applied Research, Tilburg University, P.O. Box 90153,

5000 LE Tilburg, The Netherlands

E-mail: h.m.leblanc@uvt.nl, m.g.c.vankrieken@uvt.nl, krikke@uvt.nl, fleuren@uvt.nl

OR Spectrum 28:53–71 (2006)

used by the national Dutch auto recycling system. Based on this case, we will

analyze new route planning concepts that are based on central planning.

1.1 Developments in end-of-life vehicle recycling

The automotive industry is one of the major European industries confronted with a

massive number of end-of-life products. A total of 14.2 million passenger cars were

sold in Europe in 2003, all of which will be discarded at some time. With the

approaching deadline for implementation of the European directive on the re-

cycling of end-of-life vehicles (Directive 2000/53/EC), many EU member states

are taking initiatives in this direction (ACEA 2004). EU legislation prescribes a

recovery target of at least 85% of each car, 80% of which through reuse and

recycling by 2006. In some EU member states, national legislation is even stricter.

In the Netherlands, the national representatives of the automotive industry,

including all car manufacturers, joined hands with the founding of Auto Recycling

Nederland (ARN). ARN is responsible for the funding and the physical operations

entailed in implementing the national legislation on EPR for its members. In the

terms of Spicer and Johnson (2004), ARN is a producer responsibility organi-

zation. Under the authority of ARN, certain materials are dismantled at the col-

lection points for separate recovery; administration and reporting are essential.

Krikke et al. (2004) describe this type of reverse supply chain as a “control-type.”

These “control-type” supply chains assure that recovery is carried out in ac-

cordance with formal requirements by reporting mass-balances, showing the rela-

tionship between input, output and the degree of recovery. The costs of the logistic

network for collection, consolidation, disposition and transport of these materials

are high. Pressure from the market, together with the harmonization of national

legislations, will hopefully lead to more efficiency in the “control-type” reverse

supply chains.

1.2 Outline of the paper

The aim of the present study is to quantify the expected benefits of new advanced

planning concepts for the logistic network for containers of Auto Recycling

Nederland. The problem and its real-life setting will be discussed in Section 2. We

will limit this presentation to the part of the recycling network involving con-

tainers. In Section 3 we will discuss literature relating to the problem at hand.

Vehicle routing literature describing similar problems is scarce. On account of the

particular characteristics of the problem, we needed to develop a new heuristic.

This heuristic is described in Section 4. In Section 5, the results of the case study

are discussed. These results incorporate sensitivity analysis and analysis of alter-

native scenarios. Finally, in Section 6, the results are summarized and suggestions

for further research are given.

The various aspects of end-of-life vehicle recycling will not be described here;

the interested reader is referred to Püchert et al. (1994) for a discussion of the

business aspects of ELV recycling and for more details on the Dutch system of

ARN to Van Burik (1998) and Le Blanc et al. (2004).

54 H. M. le Blanc et al.

2 Problem description and background

2.1 Case study

The case study deals with optimizing the collection of containers that are used to

transport end-of-life materials from dismantled vehicles. Due to pressures from

the market, the ARN system will need to further improve the reverse chain for the

processing of end-of-life vehicles (ELVs). As chain director, ARN outsources the

actual processes to existing ELV-dismantlers, shredder companies, recyclers and

logistic service providers (LSPs). The LSPs are contracted for a period of three

years and are responsible for the logistics activities in a certain province. Their

activities include the transportation of the containers to a depot, consolidation at the

depot, in some cases value-adding activities such as sorting and finally transpor-

tation to the recycling company. The current logistic planning activities are decen-

tralized and performed by the individually contracted LSPs. LSPs are assigned to

ELV-dismantlers on the basis of province boundaries. In a central planning sce-

nario, transportation orders are not sent directly to the individual LSPs, but col-

lected on a centralized level and assigned in clusters to the LSPs, making use of the

cost benefits of combining orders. Allocation of ELV-dismantlers to LSPs is no

longer fixed, but adjusted regularly based on the optimization of routes on a central

level. Cruijssen and Salomon (2004) call this the principle of transportation order

sharing and find savings up to 15% in an empirical study, depending on the

characteristics of the network. In the literature, this concept is referred to as fourth

party logistics (4PL), representing an entity outside the organization that assembles

and integrates third-party capabilities to achieve transformational efficiencies not

attainable by the organization on its own (Bumstead and Cannons 2002).

In this paper, we consider manually dismantled, high-volume materials stored

and collected in containers. Table 1 gives an overview. An ELV-dismantler who has

a full container submits a request for collection to the logistic service provider

(LSP). Within five working days, the LSP visits the dismantler and exchanges the

full container for an empty one. Glass, rubber strips and PU-foam are collected in a

compartmented container, specially designed for ARN. Tires and bumpers are

collected in 35m3 containers for all ELV-dismantlers. Currently, all materials are

brought to the depot. Here, all materials, except tires, are sorted and processed and

then transferred by bulk transport to recyclers, mostly located in neighboring

countries. Since tires need no processing at the depot and the four contracted

recycling companies are located in the Netherlands, they can be sent directly to

Table 1 The materials collected in containers with their applications after recycling

Material Average amount per wreck Application of the recovered material

Tires 27.9 kg High quality: retreaded and sold as tire

Low quality: paving tiles and insulation mats

Bumpers 5.6 kg Engine covers and wheel arches

Glass 25.4 kg Bottles and glass fiber

PU-foam 6.7 kg Car seat padding and mattresses

Rubber strips 7.7 kg High purity: as roll container wheels

Low purity: as fuel in cement kilns

Vehicle routing concepts in the closed-loop container network of ARN—a case study 55

recyclers, bypassing the depot. In our computational experiments, we examine

the cost benefit of this option. We focus on the planning of requests from ELV-

dismantlers to have containers collected. Since the recyclers of materials other than

tires are located abroad, transport of these materials to the recyclers usually takes

the form of a linehaul trip. Linehaul trips offer no combination possibilities and the

costs of these trips are assumed to be fixed. Figure 1 gives an overview of the

processes in the ARN network.

Currently, LSPs use two types of lifting mechanisms for loading and unloading

containers onto a truck. The first system uses an iron chain to drag the container up

onto the truck, while the second system uses a pneumatic hook to pickup the

container and place it on the truck. Although both systems work fine, they are not

compatible. A container or truck suitable for the hook system is not suitable for the

chain system and vice versa. This restriction must be taken into account in planning

the trips, since LSPs do not have both lifting mechanisms, which leads to a com-

plexity-reducing separable structure. Figure 2 shows the map of the Netherlands

with province boundaries and the lifting mechanism in use (hook or chain). We feel

that standardization of the lifting mechanism would be an improvement.

The goal of the study is to analyze and improve the system of collecting

containers. To this end, we examine the following situations:

– Allowing direct shipment of containers from dismantler to recycler, bypassing

the consolidation depot.

– Changing the allocation of dismantlers to LSPs from the current assignment,

based on province boundaries, to optimal fixed assignment or to dynamic as-

signment based on optimal routing decisions in each planning period.

– Standardizing the lifting mechanism for loading and unloading containers onto a

truck.

Although this is mainly a tactical study, we choose to solve the operational

problem as well, to get a good estimate of transportation costs and performance.

This is because the small nuances in different scenarios cannot be adequately

expressed in tactical models, hence the need for detailed operational routes. The

problem resembles a unique multiple logistic service provider vehicle routing

model with pickup and delivery allowing alternative delivery locations and with

small vehicle capacity (two containers), which has not been described in the

Fig. 1 An overview of the processes in the ARN network for the recycling of ELVs

Consumer hands in

ELV for dismantling

Dismantling

Shredder

Carcass

Material storage

(container)

Depot for freight

consolidation

Material

recycler

Collection within 5

working days after

request

Materials

56 H. M. le Blanc et al.

literature before. We call this the 2-container collection problem. In the next sub-

section we will give a formal description of the problem.

2.2 The 2-container collection problem

The 2-container routing problem consists of a set of ELV-dismantlers, a set of

depots, owned by an LSP and a set of recyclers. Distance and travel times between

all locations are known. Both ELV-dismantlers and depots can initiate transporta-

tion orders for containers. At an ELV-dismantler, empty containers are exchanged

for full ones, while at a recycling facility full containers are exchanged for empty

Fig. 2 Overview of the ARN network indicating the two lifting mechanism (hook and chain) in

use per province

Vehicle routing concepts in the closed-loop container network of ARN—a case study 57

ones of the same type. Since a shortage of containers never occurs in practice in a

closed-loop system, the depot locations are assumed to have sufficient storage of

all container types to exchange. Orders may be for either one or two containers; all

orders concern containers of the same type. Full containers coming from ELV-

dismantlers can be delivered either to a depot or to a recycling facility; full con-

tainers coming from a depot can only be delivered to a recycling facility. Which

delivery location is selected depends on policy, practical restrictions, the estimated

gate fee for dropping the order at the location and the costs of including the delivery

location in the route. The gate fee depends on the residual value of the product and

can even be negative, i.e. money is paid by the recycler to acquire the material.

Figure 3 gives a conceptual mapping of the problem.

A vehicle’s route starts and ends at the depot. A route may take no longer than

nine hours, one hour of which is overtime for a 50% higher rate. For each stop, a

fixed stopping time and a variable loading and unloading time are incurred. The

costs of a route are composed of a distance and a time component. The model

allows for differentiating the kilometer and hourly rates per LSP. Vehicle capacity

in the model is limited to two containers. Each LSP is deemed to have an unlimited

number of vehicles. This is realistic since these types of trucks are widely used. In

the next section we will explore relevant literature dealing with similar problems.

3 Literature

Literature on vehicle routing is abundant, (see Bodin et al. 1983; Toth and Vigo

2002). In reverse supply chains, variants of the classical vehicle routing problem

occur that have been less extensively studied (Dethloff 2001). Beullens (2001)

provides an excellent overview of vehicle routing models and the special types of

models occurring in reverse logistics.

The problem closest to the situation at hand is the skip problem (SP) as de-

scribed in De Meulemeester et al. (1997). Vehicles start at a depot and have to

deliver empty skips to customers, collect full skips from customers and deliver the

full skips to either the depot or one of the disposal facilities. A vehicle has the

ELV –

dismantlers

Depots

Recyclers

All materials

except tires

Only tires

abroad

Recyclers in

the

Netherlands

Vehicle capacity of 2

containers

Fig. 3 Conceptual overview of the collection problem

58 H. M. le Blanc et al.

capacity to carry one skip at a time. Skips can be of multiple types and this is a

restriction in exchanging full for empty. De Meulemeester et al. (1997) develop two

heuristics and an exact procedure for solving this real-life problem. The exact

procedure is based on enumeration. The first heuristic is based on the classical

Clarke and Wright savings heuristic. The second heuristic calculates a solution to a

formulated transportation problem, providing a lower bound to the optimal solu-

tion. The solution to the transportation problem is made feasible in a number of

heuristic steps. On average, the variant of the Clarke and Wright savings algorithm

performed best.

Bodin et al. (2000) describe a variant of the skip problem called the rollon-

rolloff vehicle routing problem (RRVRP). In a RRVRP trip, a truck with a capacity

for one container departs from a depot to serve customers who need a container

placed, collected or exchanged (full for empty). The network consists of only one

depot and one disposal facility and all containers are of the same type. In that sense

the model of Bodin et al. (2000) is a simplification of the real-life case of De

Meulemeester et al. (1997). Bodin et al. (2000) develop four types of algorithms.

The first algorithm is again an adaptation of the Clarke and Wright heuristic. The

second algorithm is a trip insertion and trip improvement heuristic. The third

algorithm is a so-called decomposition algorithm, which starts by enumerating

routes, followed by solving a set covering problem. The resulting solution is

improved with some swaps. The last and most advanced algorithm is a truncated

dynamic programming heuristic, generating partial solutions that are completed by

adding the not covered orders by solving a bin-packing model. The contribution of

Bodin et al. (2000) is of a theoretical nature, since they only test the heuristics using

a set of randomly generated instances. The dynamic programming algorithm per-

forms the best, although calculation times are long. The other algorithms are faster,

but the trip insertion and trip improvement heuristics in particular are not com-

petitive in terms of solution quality.

Archetti and Speranza (2004) describe another variant of the problem, the so-

called 1-skip collection problem (1-SCP). As the name indicates, vehicle capacity

is limited to one skip or container. Since Archetti and Speranza deal with a real-life

problem, they consider several practical restrictions such as multiple container

types, time windows, different priorities for different customers and a limited fleet

size. Archetti and Speranza develop a three-phase algorithm. In phase 1, the set of

skips that needs to be collected that day is determined and ranked in priority. In

phase 2, a solution for the subset of skips is constructed. In phase 3, the solution is

further improved by using local search procedures.

Although some of the models come close to the situation at hand, none of them

has the same characteristics. All of these models consider the vehicle capacity to be

limited to precisely one skip or container instead of two as in our case. Extending

the algorithms described in literature to the situation with two containers is not

trivial. Techniques known from more general vehicle routing models could be

used; however, these techniques do not exploit the discrete capacity of only two

containers. Hence, in this paper we develop a new heuristic for tackling the prob-

lem at hand.

Vehicle routing concepts in the closed-loop container network of ARN—a case study 59

4 Description of the heuristic

The heuristic we developed to handle the case described is a two-step heuristic. In

the first step a large number of candidate routes is generated. In the second step, a

combination of routes is selected, minimizing the costs of drawing up a complete

route plan, while satisfying all the requirements. This combination of route gen-

eration and set partitioning is referred to in vehicle routing literature as the set

partitioning approach, see for example Fleuren (1988). This type of algorithms

where a promising set of possibilities is generated and a solution is found by set

partitioning is referred to as petal algorithms (Laporte et al. 2000). An alternative

way of applying set partitioning in this setting is by using column generation, see

for example Agarwal et al. (1989). Since we have a fast set partitioning solver at

our disposal and our average number of orders per route is limited, we chose to do

an enumeration of a large set of feasible routes. Figure 4 gives an overview of the

heuristic.

4.1 Route generation

The purpose of route generation is to construct a set of feasible routes, such that

the route selection procedure can make a “good” choice from the set. To tackle

this multi-depot pickup and delivery problem with alternative delivery locations,

we introduce the concept of root-orders and sub-orders. This is described in

Section 4.1.1.

While the number of feasible routes grows exponentially, we suffice with the

generation of a promising subset of routes. To restrict the number of candidate

routes generated, we use the concept of order neighborhoods; this is the topic of

Section 4.1.2.

Finally, the route generation procedure is described in Section 4.1.3.

4.1.1 Root and sub-orders

To handle the pickup and delivery problem with alternative delivery locations and

selection of logistic service providers, we distinguish root- and sub-orders. Every

transportation order has a general root-order with location- and LSP-specific sub-

orders. Since each sub-order has a unique pickup and delivery location as well as a

logistic service provider, our algorithm can proceed along the same lines as a

standard pickup and delivery heuristic. However, we have to add some constraints

to ensure that only one sub-order is performed per root-order.

Fig. 4 The framework for the routing heuristic

Input

(root-) orders

Determine

sub-orders

Calculate

neighborhood

sub-orders

Route generation

Route selection

(set partitioning)

Output route

schedule

Step 1 Step 2

60 H. M. le Blanc et al.

Example. ELV-dismantler WreckRec has a container of tires that needs to be

transported either to the tire recycler TireRec or to a depot of a logistic service

provider. There are two competing logistic service providers with a depot: LogOpt

and LogCheap. This single root-order results in four sub-orders as shown in

Table 2.

If a sub-order is selected with delivery to the depot, where delivery to the

recycler was also an option, we have to correct the route costs for the future

transportation costs from the depot to a recycler. In this situation, the sub-order

generates a new root-order in the next planning period for the transport to the

recycler. Since planning periods are short, three working days, this heuristic step is

not a severe limitation. These costs are estimated using the Eq. [1].

CostCorso ¼ � � LHCso � Loadso (1)

where:

α=Correction factor between 1/4 and 1

LHCso=Linehaul costs to deliver a container from the depot of sub-order so to

the cheapest recycler in transportation costs and gate fee.

Loadso=Number of containers in sub-order so

The correction factor α expresses the combination possibilities for the trans-

portation orders from depot to recycler. If α=1 no combinations are made and the

full linehaul costs are charged to collect a single container. The perfect combination

would be two containers from the depot to the recycler and two containers from an

ELV-dismantler adjacent to the recycler back to the depot, which corresponds with

α=1/4. In our implementation we use α=0.8, which follows from empirical anal-

ysis in cooperation with ARN.

4.1.2 Neighborhoods

While the total number of feasible routes can be very large, up to several million,

we use the concept of neighborhoods to limit the set of candidate routes. Every

order has a set of neighbors, ordered on a distance-based criterion. When we add

orders to a route, we only consider orders that are in the neighborhood of the route,

which is the union of neighborhoods of the orders in the route.

Formally, we can describe this as follows. At the start of an empty route, every

sub-order can be inserted. Since we develop a set of routes, each root-order can

occur on several routes. For each sub-order we define a set of neighboring sub-

orders belonging to different root-orders. Let nb_subordso denote this set of

neighboring sub-orders for sub-order so. RouteSubOrdersr denotes the set of sub-

Table 2 The sub-orders in the example of WreckRec

Sub-order LSP performing the order Pickup location Delivery location

1 LogOpt WreckRec LogOpt depot

2 LogOpt WreckRec TireRec

3 LogCheap WreckRec LogCheap depot

4 LogCheap WreckRec TireRec

Vehicle routing concepts in the closed-loop container network of ARN—a case study 61

orders in route r. The neighborhood of a route r, denoted as nb_router, is the union

of the neighborhoods of the sub-orders in a route, i.e. nb router ¼ [

so2RouteSubOrdr

nb subordso:

To determine the neighborhood of a sub-order we need a distance measure. This

is a heuristic step in the procedure. Consider two sub-orders so_A and so_B, with

pso and dso denoting the respective pickup and the delivery location of sub-order so.

Our distance measure is based on the best way to combine two orders rather than

drive them separately. Mathematically this criterion is given in [2].

distso A;so B ¼ min d pso A; dso Að Þ þ d dso A; pso Bð Þ þ d pso B; dso Bð Þ;f

d pso A; pso Bð Þ þ d pso B; dso Að Þ þ d dso A; dso Bð Þ;

d pso A; pso Bð Þ þ d pso B; dso Bð Þ þ d dso B; dso Að Þ;

d pso B; dso Bð Þ þ d dso B; pso Að Þ þ d pso A; dso Að Þ;

d pso B; pso Að Þ þ d pso A; dso Bð Þ þ d dso B; dso Að Þ;

d pso B; pso Að Þ þ d pso A; dso Að Þ þ d dso A; dso Bð Þg

�d pso A; dso Að Þ � d pso B; dso Bð Þ

For each sub-order, we list the distances to all suborders belonging to a different

root-order and include the nearest nb_size sub-orders in nb_subordso. Experiments

with the required size of the neighborhood to find suitable solutions in acceptable

computational time for the given study indicated that nb_size=6 performs well; we

will use this value in the rest of this paper. Figure 5 shows the diminishing im-

provements found by extending the neighborhood size is shown for a represen-

tative sample of 25 real-life instances consisting of an average of 54 root-orders and

114 sub-orders. Further increasing the neighborhood size will marginally improve

the solution and cause a big increase in the route generation times. Note that above

a certain threshold the route generation is no longer restricted and all feasible

combinations are generated.

(2)

Influence neighborhoodsize

90

92

94

96

98

100

1 2 3 4 5 6 7 8 9 10

0

20

40

60

80

100

Cost Route generation time

C

o

s

t

in

d

e

x

C

o

n

m

p

u

ti

n

g

t

im

e

in

d

e

x

Neighborhood size

Fig. 5 The influence of changing the size of the neighborhood on the quality of the solution based

on a representative sample of 25 real-life instances (computing time index 100=1498 s)

62 H. M. le Blanc et al.

4.1.3 Outline of the route generation algorithm

The aim of the route generator is to create a large number of attractive and feasible

routes. As stated in Section 4.1.2, we restrict the enumeration of routes by only

appending orders from the neighborhood. A route is feasible if the maximum time

allowed for one day and the maximum vehicle capacities along the route are not

exceeded. Every time a full container is picked up from an ELV dismantler, it must

be exchanged for an empty container of the same type. If this is not possible, the

route is infeasible. We make use of a recursive function implementation for the

systematic generation of routes. The RouteGenerator function describes the main

idea behind the route generation algorithm.

A sub-order is added to a route by inserting the pickup stop and the delivery

stop of the sub-order in the route. Since we deal with the pickup and delivery

situation, for each possible position where the pickup stop (StopP) can be in-

serted, we find the cheapest position to insert the delivery stop (StopD). The

InsertSubOrder function describes the main ideas behind the insertion of a sub-

order in a route.

Although the number of routes generated is restricted by the size of the order

neighborhood, it can still be very large in some cases. Occasionally, over 2.5

Function RouteGenerator

IF ( Route empty )

RouteNeighborHood := Set of all SubOrders

ENDIF

FOR ( SubOrder in RouteNeighborHood AND RootOrder unplanned ) DO

InsertSubOrder( SubOrder )

UpdateRouteNeighborhood

IF( RouteFeasible )THEN

WriteRouteToRouteSelectionProblem

RouteGenerator

ENDIF

RemoveSubOrder

UpdateRouteNeighborhood

ENDFOR

Function InsertSuborder( SubOrder)

FOR ( Position in Route ) DO

Insert StopP

FOR ( Position in Route after Stop P ) DO

Insert StopD

UpdateRoute

IF ( BestInsertion AND RouteFeasible ) THEN

StoreBestInsertionPosition

ENDIF

Remove StopD

ENDFOR

Remove StopP

ENDFOR

IF ( BestInsertionExists ) THEN

Insert StopD and StopP at best position

UpdateRoute

ENDIF

Vehicle routing concepts in the closed-loop container network of ARN—a case study 63

million routes are generated. In that case, because of memory limitations of our

computers, we reduce the maximum allowed size of the neighborhood by one and

restart the route generation.

4.2 Route selection

The problem of finding the optimal combination of routes such that all orders are

performed at minimal costs is formulated as a set partitioning problem. After

introducing some notation, the problem is given in Eq. [3]–[5].

Parameters

δso,ro = 1 if sub-order so belongs to root-order ro, 0 otherwise.

aso,r = 1 if sub-order so is contained in route r, 0 otherwise.

cr = denotes the costs of driving route r in euro.

pr = denotes the profit or costs (negative pr) of route r as a result of the chosen

delivery locations for the orders in route r in euro.

Variables

Xr=1 if route r is selected, 0 otherwise.

The route selection problem

min

P

r

cr � prð Þ � Xr (3)

s:t:

P

r

P

so

�so;ro � aso;rð Þ � Xr ¼ 1 8ro (4)

Xr 2 0; 1f g 8r (5)

Note that

P

so

�so;ro � aso;r is either 0 or 1 by construction of the route generator

and therefore the route selection problem is a pure set partitioning problem. To

exploit the special structure of the set partitioning problem we make use of a special

set partitioning solver, rather than more generic mixed-integer linear programming

solvers such as Cplex (http://www.ilog.com). We use the solver developed by Van

Krieken et al. (2004). This solver uses Lagrangean relaxation and dual heuristics to

determine the lower bound and branch and bound for finding the optimal solution.

Furthermore, several problem reduction techniques are used to reduce the number

of variables and constraints in the problem (Van Krieken et al. 2003). The solver is

very effective at solving the set partitioning instances under consideration, al-

though the number of variables can become very large. Problems with over a

million variables are solved in a couple of minutes on a normal desktop computer.

64 H. M. le Blanc et al.

5 Structure of the analysis

5.1 Simulation

We use a simulation model to analyze the performance of the system. The

transportation orders from E