Data Analytics

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 ELV-dismantlers are generated following empirical distributions. To obtain representative results, each simulation run consists of 10 replications of one year. In the simulation, the operational vehicle routing problem is solved twice a week for a planning horizon of three workdays. This means that over 1000 set partitioning problems are generated and solved per simulation run.

Orders generated during a certain collection period are planned and executed the next planning period. For containers of tires brought to the depot, the orders for shipping the containers to the recycler are also issued at the beginning of the next planning period. In this way transportation orders are fixed at the beginning of a planning period.

5.2 Data and scenarios

The scenarios are constructed in cooperation with the logistic experts of ARN and in cooperation with the logistic service providers hired by ARN. Distances and driving times used in the analysis were obtained from Evo-IT (http://www.evo-it.nl). The cost figures used were obtained from the NEA (2004), which is an authority on traffic and transportation issues in the Netherlands. We use cost prices rather than the commercial rates of individual LSPs. The data used for simulating the processes at the ELV-dismantlers are empirical data available in the corporate databases of ARN. A detailed description of these data can be found in Schreurs (2004).

Scenarios are defined along three dimensions:

– The lifting mechanisms used by the LSPs:

– The current situation: two different lifting mechanisms are used. – The standardized situation: all LSPs use the same lifting mechanism.

– The assignment of transportation orders to the logistics service providers

– Current fixed assignment: ELV dismantlers are assigned to LSPs and recyclers on the basis of province boundaries.

– Optimized fixed assignment: ELV-dismantlers are assigned to the closest LSP/recycler based on a distance criterion.

– Central planning: no fixed assignment exists; the LSP with the best com- bination possibilities executes the transportation order.

– The allowed routes for containers of tires:

– No direct shipment: all tire containers pass the depot. – Direct shipment: this is allowed if it is advantageous to ship tire containers

directly to a tire recycler instead of the depot.

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

Figure 6 shows six scenarios defined along the last two dimensions and their scenario IDs. These six scenarios can be applied to both lifting mechanisms, the first dimension, resulting in a total of twelve. Scenario Cur-indirect is our reference scenario and corresponds to the current situation of ARN.

The current assignment of ELV-dismantlers to depots and recyclers is based on province boundaries, for historic reasons. In many cases, this assignment is far from efficient, since provinces can have irregular shapes. We resolve this by simply assigning each ELV-dismantler to the nearest depot with the proper lifting mech- anism. In the central planning scenario, the effect of a fixed assignment is analyzed by letting go of this restriction altogether and using dynamic planning on a central level.

Currently, nearly all tire containers are transported to the recycler via a depot, since the container must be weighed at the depot. Nowadays, recyclers also have accurate weighing facilities for trucks, making a stop at the depot no longer necessary. Direct shipment of containers filled with tires is possible as long as the date of delivery is communicated.

6 Results

6.1 Current logistic network

The results for the current logistic network with LSPs having different types of lifting mechanisms are presented in Table 3. For reasons of confidentiality, the cost figures have been indexed. A comparison of the various scenarios for the yearly indexed costs is also presented in Fig. 7.

Allowing the logistic service providers to ship tire containers directly from ELV-dismantlers to recyclers, results in cost savings ranging from 6.3% to 9.1%, depending on the way in which ELV-dismantlers are assigned to LSPs. The average route length increases both in time and distance, since it is more attractive to make a

Allow direct shipments Current assignment

Allow direct shipments Optimized assignment

Allow direct shipments Central planning

Only indirect shipments Current assignment

Only indirect shipments Optimized assignment

Only indirect shipments Central planning

Scenarios

A s

s ig

n m

e n

t o

f o

rd e

rs

Types of shipment allowed

Cur-direct

Opt-direct

CP-direct

Cur-indirect

Opt-indirect

CP-indirect

Fig. 6 An overview of the scenarios

66 H. M. le Blanc et al.

small detour to drop tire containers at a tire recycler rather than bring them first to the depot and then to the recycler. This phenomenon is responsible for the drastic decreases in the number of routes driven, since most tire containers are transported only once. Implementation of direct shipment is fairly easy and only requires some further arrangements with the recyclers.

Optimizing the assignment of ELV-dismantlers to depots and recyclers results in cost decreases ranging from 4.4% to 4.7%. This effect is small, since the di-

Table 3 Results for the current network with restrictions on the lifting mechanisms (Case 1)

Scenario ID Cur- indirect

Opt- indirect

CP-indirect Cur- direct

Opt- direct

CP-direct

Assignment Fixed, current

Fixed, optimized

Free, central planning

Fixed, current

Fixed, optimized

Free, central planning

Type of shipments for tires

Only indirect

Only indirect

Only indirect

Allow direct

Allow direct

Allow direct

Average costs per year (indexed)

100 95.3 94.8 93.4 89.3 86.1

Average distance per year (km)

505,779 471,610 467,188 483,092 458,972 433,735

Average number of routes per year

2,887 2,906 2,907 2,346 2,336 2,226

Average number of containers per route

2.45 2.44 2.44 2.39 2.32 2.42

Average route distance (km)

175.2 162.3 160.7 205.9 196.4 194.8

Average route duration (min)

291.0 277.6 276.1 331.3 319.7 325.4

Average driving time per route (min)

177.1 164.3 162.8 208.7 198.4 198.2

Average load and unloadtime per route

114.0 113.3 113.3 122.6 121.3 127.1

Fig. 7 Comparison of scenarios with current and standardized lifting mechanism

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

versity in container lifting mechanisms allows little freedom for optimization. It is fairly easy to change to another fixed assignment: it merely requires renegotiation of contracts with LSPs.

Compared to the optimal fixed assignment, the extra savings of dynamic allocation by central planning are limited, ranging from 0.6% to 3.6%. These marginal cost savings are not offset by the changes in the planning and control mechanisms to implement dynamic assignment.

6.2 Network with uniform lifting mechanism for containers

The differences in lifting mechanisms in use by logistic service providers are likely to cause inefficiencies. ARN is lobbying for standardizing container lifting mechanisms at the logistic service providers. This situation is compared to the current situation in Table 4. Figure 7 shows the yearly indexed costs of the various scenarios for the current situation as well as for uniform lifting mechanisms. Currently, the assignment of dismantlers to depots and recyclers takes differences in lifting mechanisms into account. Therefore, standardization of the lifting mech- anism only makes sense when the assignment is changed. We compare the current situation with the optimized assignment and central planning scenarios with a uniform lifting mechanism.

Table 4 Results for the current network after loosening the restrictions on the lifting mechanisms (Case 2)

Scenario ID Cur- indirect

Opt- indirect

CP-indirect Cur- direct

Opt- direct

CP- direct

Assignment Fixed, current

Fixed, optimized

Free, central planning

Fixed, current

Fixed, optimized

Free, central planning

Type of shipments for tires Only indirect

Only indirect

Only indirect Allow direct

Allow direct

Allow direct

Average costs per year (indexed)

100 87.2 86.9 93.4 81.6 80.8

Average distance per year (km)

505,779 411,893 408,954 483,092 402,125 394,886

Average number of routes per year

2,887 2,891 2,876 2,346 2,254 2,280

Average number of con- tainers per route

2.45 2.45 2.47 2.39 2.39 2.36

Average route distance (km)

175.2 142.5 142.2 205.9 178.4 173.2

Average route duration (min)

291.0 258.8 259.4 331.3 306.6 301.1

Average driving time per route (min)

177.1 145.1 145.0 208.7 181.4 177.2

Average load and unloadtime per route

114.0 113.7 114.4 122.6 125.1 123.9

68 H. M. le Blanc et al.

Using optimal fixed assignment, the cost savings of standardizing the lifting mechanism are about 8.7% when we allow direct shipments. If direct shipments are not allowed the cost savings are 8.5%.

The cost savings of standardizing the lifting mechanism in the case of central dynamic planning are 8.3% when direct shipment is not allowed and 6.1% when direct shipment is allowed. Given standardized lifting mechanisms, the cost savings of dynamic central planning over optimized fixed assignment are less than 1%, whether we allow direct shipment or not, which does not offset the costs of the organizational changes. Standardizing the lifting mechanism is comparable with increasing the network density for the LSPs. Improving the combination pos- sibilities in a dense network has a marginal effect on the costs since, in a dense network, there are already abundant combination possibilities. These results on central planning are supported by the findings of Cruijssen and Salomon (2004), who showed that the benefits of central planning are limited when orders are large compared to the vehicle capacity. Moreover, our orders are not randomly assigned to depots, but on the basis of province boundaries. Although, as we have seen, province boundaries are far from optimal, they still have some logic and are much better than random assignment as was initially the case in Cruijssen and Salomon (2004).

When we optimize the assignment of recyclers to LSPs, standardizing the lifting mechanism results in considerable cost savings that justify the necessary investment to implement this in the chain of ARN.

7 Conclusions and outlook

In this paper we have described a real-life project in optimizing the logistic network for containers with materials from end-of-life vehicles. The underlying vehicle routing model is a unique multi-depot pickup and delivery model with alternative delivery locations. The heuristic we used is based on generating a set of promising routes and selecting the optimal combination of routes by solving a set partitioning problem.

The reasons for the limited research on this type of problems probably lies in the fact that it is considered a typical reverse logistics problem where waste or cores for recycling are collected, bundled and brought to a central recovery center. We are not aware of forward logistic problems with similar characteristics. Although we developed a new heuristic and the heuristics described in the literature stem from problem instances that are typically product recovery or waste disposal networks, we do not have the impression that the mathematical techniques differ. Relating this project to earlier projects in the same recycling network, we conjecture that, although logistic concepts differ from forward logistics, the mathematical tech- niques and models in this network are not fundamentally different.

From a business point of view, we analyzed the consequences of a better assignment of waste generators to logistics service providers and of routing de- cisions made by central planning. Furthermore, we analyzed the influence of a policy that did not allow the direct shipment from waste generator sites to recycling facilities and the effects of the different lifting mechanisms used for containers.

With respect to the assignment of recyclers to logistics service providers, we recommend changing the current fixed assignment, which is based on province

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

boundaries, to the optimal fixed assignment. Considerable effort would be in- volved in implementation of the dynamic assignment option, while the additional savings over the optimal fixed assignment are limited. Since the study shows that allowing direct shipment will result in cost savings and the organizational burden is not very large, we recommend allowing direct shipment of tires to recyclers. With respect to the lifting mechanism, the study has shown that standardization will result in significant cost savings, making it worth the effort to standardize the lifting mechanism in the ARN network. The total percentage cost savings of the recommended new system with standardized lifting mechanism, the option of direct shipments and the optimal fixed assignment are over 18% compared to the current system.

Since cost reductions in closed-loop supply chains for EOL products are crucial, they can make the difference between recycling for profit or for loss. In the latter case, OEMs will not recycle as long as they are not forced to do so by legislation. The best way towards a sustainable society is through business moti- vations. Since we have only just started to set up and design product recovery networks, there are great opportunities for operations research to assist by offering advanced planning systems from the operational to the strategic level.

References

Agarwal Y, Mathur K, Salkin HM (1989) A set-partitioning-based exact algorithm for the vehicle routing problem. Networks 19:731–749

Archetti C, Speranza MG (2004) Vehicle routing in the 1-skip collection problem. J Oper Res Soc 55:717–727

ACEA, Association des Constructeurs Européens d’ Automobiles (2004) Country report charts on end-of-life vehicle treatment status, February 2004. Downloadable from: http://www.acea. be/

Beullens P (2001) Location, process selection and vehicle routing models for reverse logistics. PhD thesis, University of Leuven, Belgium

Bodin L, Golden B, Assad A, Ball M (1983) Routing and scheduling of vehicles and crews: the state of the art. Comput Oper Res 10:63–211

Bodin L, Mingozzi A, Baldacci R (2000) The rollon-rolloff vehicle routing problem. Transp Sci 43(3):271–288

Bumstead J, Cannons K (2002) From 4PL to Managed Supply Chain Operations. Logist Transp Focus 4(4):19–25

Cruijssen F, Salomon M (2004) Empirical study: order sharing between transportation companies may result in cost reductions between 5 to 15 percent. Center Discussion Paper 80–2004

De Meulemeester L, Laporte G, Louveaux FV, Semet F (1997) Optimal sequencing of skip collections and deliveries. Journal of Operational Research Society 48:57–64

Dethloff J (2001) Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR Spectrum 23:79–96

Directive 2000/53/EC of the European parliament and of the council of 18 September 2000 on end-of-life vehicles. Official Journal of the European Communities, L 269/34

Fleuren HA (1988) A computational study of the set partitioning approach for vehicle routing and scheduling problems. Dissertation, University of Twente, The Netherlands

Krikke HR, Le Blanc HM, Van de Velde SL (2004) Product modularity and the design of closed- loop supply chains. Calif Manage Rev 46(2):23–39

Laporte G, Gendreau M, Potvin JY, Semet F (2000) Classical and modern heuristics for vehicle routing problem. Int Trans Oper Res 7:285–300

Le Blanc HM, Fleuren HA, Krikke HR (2004) Redesign of a recycling system for LPG-tanks. OR Spectrum 26:283–304

NEA (2004) Kostencalculaties in het beroepsgoederenvervoer over de weg, prijspeil 1-1-2004. Rijswijk, The Netherlands

70 H. M. le Blanc et al.

Püchert H, Walter A, Conradt P, Rentz O (1994) Autorecycling, Demontage und Verwertung. Wirtschaftliche Aspekte, Logistik und Organisation. Economica Verlag, Bonn, Germany

Schreurs RP (2004) Voorspelbaarheid van de inzameling van materialen afkomstig van autowrakken en de impact op de distributieplanning. Master thesis, Tilburg University, The Netherlands

Spicer AJ, Johnson MR (2004) Third-party demanufacturing as a solution for extended producer responsibility. J Clean Prod 12:37–45

Toth P, Vigo D (2002) The vehicle routing problem. Society for Industrial and Applied Mathematics, SIAM Monographs on Discrete Mathematics and Applications

Van Burik AMC (1998) Retourstroomproblematiek van materialen afkomstig uit autowrakken. In: Van Goor AR, Flapper SDP, Clement C (eds) Handboek reverse logistics. Samson Bedrijfsinformatie, Alphen aan den Rijn, The Netherlands, F3600 pp 1–12

Van Krieken MGC, Fleuren HA, Peeters MJP (2003) Problem reduction in set partitioning problems. Center Discussion Papers 2003–80

Van Krieken MGC, Fleuren HA, Peeters MJP (2004) A Lagrangean relaxation based algorithm for solving set partitioning problems. Center Discussion Papers 2004–44

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