Lehrstuhl Sicherheitstechnik/Risikomanagement
LABOR
Sustainable product and process development Focus: logistics Nachhaltige Produkt- und Prozessentwicklung Fokus: Logistik
Univ.-Prof. Dr.-Ing. Stefan Bracke Sicherheitstechnik / Risikomanagement
Prof. Ph.D. Ken-ichi Tanaka Department of Informatics Prof. Dr. Eng. Tetsuo Yamada Department of Informatics
Sustainable product and process development
Lehrstuhl Sicherheitstechnik/Risikomanagement
Agenda: Introduction Univ.-Prof. Dr.-Ing Stefan Bracke Keynote:
Disassembly system design with environmental and economic parts selection using the recyclability evaluation method
Prof. Dr. Eng Tetsuo Yamada Lecture:
Facility location problems and their application to sustainable logistics
Prof. Ph.D. Ken-ichi Tanaka
Sustainable product and process development
Facility location problems and their application to sustainable logistics International Workshop for Sustainable product and process development May 15, 2013
Ken-ichi TANAKA E-mail:
[email protected] Department of Informatics University of Electro-Communications Chofu, Tokyo, Japan
Part 1 Introduction to facility location problems: four important models
2013/2/20
2
Which plan is a better one and why?
10km
2013/2/20
10km
3
Fundamental facility location problems p-Median Problem Hakimi, S. (1964): Optimum location of switching centers and the absolute centers and medians of a graph, Operations Research, 12, 450--459.
p-Center Problem Hakimi, S. (1964): Optimum location of switching centers and the absolute centers and medians of a graph, Operations Research, 12, 450--459.
Set Covering Location Problem Toregas, C., Swain, R., ReVelle, C. and Bergman, L. (1971): The location emergency service facilities, Operations Research, 19, 1363--1373.
p-Maximal Covering Location Problem Church, R.L. and ReVelle, C. (1974): The maximal covering location problem, Papers of the Regional Science and Association, 32, 101--118. 2013/2/20
4
Notation: Input and Variables : Set of demand locations
Variables used for each model
: Set of candidate locations 0-1 variable
p-Median
○
○
: location variable
p-Center
○
○
: allocation variable
Set cover
○
: coverage variable
Max cover
○
○
candidate location demand location
illustration of 2013/2/20
illustration of
illustration of 5
Population data of Nara Prefecture
#
city
1
奈良市
2
大和高田市
369188
東吉野村吉野郡
70326 …
…
…
39
population
2526
10km
Nara Prefecture in Japan 2013/2/20
6
Formulation of p-Median Problem The p-Median problem locates p facilities to minimize the demand-weighted total distance between each demand and the nearest facility
min.
(1)
sub. to
(2) (3) (4)
Variables : location variables : allocation variables Data : number of facilities : demand : distance matrix
(5) 2013/2/20
7
Optimal solutions of p-Median Problem Facilities tend to be located closer to large demands
10km
p=3 Average distance：5.9km 2013/2/20
10km
p=5 Average distance：4.1km 8
Formulation of p-Center Problem The p-Center problem locates p facilities to minimize the maximum distance between each demand and the nearest facility min.
s. t.
(1)
nonlinear
(2)
Variables : location variables : allocation variables
(3)
Data : number of facilities : distance matrix
(4) (5) 2013/2/20
9
Formulation of p-Center Problem By using a variable which represent the maximum distance, a linear formulation can be obtained. min.
(1)
s. t.
(2)
(3)
(4)
linear Variables : maximum distance : location variables : allocation variables Data : number of facilities : distance matrix
(5) (6) 2013/2/20
10
Optimal solutions of p-Center Problem Facilities are more dispersed than those of p-Median problem
maximum distance
maximum distance
10km
p=3 2013/2/20
maximum distance：25.2km
10km
p=5 maximum distance ：17.1km
11
Formulation of Set Cover Problem The set covering location problem seeks the minimum number of facilities for all demands to be covered by at least one facility. A demand i is said to be covered by a facility located at j if the distance or time between i and j is less than some critical covering distance or time. min.
(1)
sub. to
(2)
Variables : location variables Data : number of facilities : coverage index
(3) 2013/2/20
12
Optimal solutions of Set Cover Problem
10km
coverage radius: 10km objective value: 15 2013/2/20
10km
coverage radius: 15km objective value: 8 13
Formulation of Max Cover Problem The maximal covering location problem seeks to maximize the number of demands covered by at least one facility.
max.
(1)
sub. to
(2)
(3)
Variables : location variables : coverage variables Data : number of facilities : coverage index
(4)
2013/2/20
14
Optimal solutions of Max Cover Problem
10km
2013/2/20
10km
p=3 coverage radius: 10km
p=5 coverage radius: 15km
covered demands: 90.5%
covered demands: 95.8% 15
Number of facilities and coverage covered demands [%] coverage radius: 10km
number of facilities to cover all the demands
15 number of facilities to be located
Marginal increase in coverage decreases with the number of facilities to be located 2013/2/20
16
Part 2 Bicriteria Drop-off Points Location Problems for Collecting Used Products
2013/2/20
17
Ink-cartridge homecoming project purpose: promote collection and recycling of used ink-cartridges
post office sorting facility owner
drop-off box 2013/2/20
http://www.city.shinjuku.lg.jp/seikatsu/seiso01_001016.html
18
Drop-off boxes in Shinjuku Ward Paper pack White tray Dry battery Ink-cartridge
Locations of drop-off boxes in Shinjuku Ward 2013/2/20
19
Drop-off Points Location Problem • Two types of used products: product A and product B • Destination locations for each product Locations of drop-off boxes are determined so as to • maximize total volume collected • minimize total transportation cost + space allocation cost product A product B destination location for product A
drop-off box for product A A
owner
A
A B
owner A B 2013/2/20
drop-off box for product B B destination B location for product B
owner
B 20
Outline of presentation 1. Basic assumptions 2. Notations 3. Problem formulation: Bi-objective model 4. Target area: Chofu City, Tokyo, Japan 5. Analysis of Pareto optimal solutions 6. Conclusion
2013/2/20
21
Basic assumptions nearest B box
1. Owners of used products bring them to the nearest drop-off box.
B A
nearest A box
B 100 products
2. Proportion of product owners to bring used products is a decreasing function of the distance to the nearest drop-off box. 2013/2/20
AB
owner
50 products
nearest B box B 200m 100 products
10 products nearest B box B 1km
22
Notation: Sets 𝐼: set of demand locations for used products A and B, indexed by 𝑖 𝐽: set of candidate locations for drop-off boxes for used products A and B, indexed by 𝑗 owner
A
owner
𝑖∈𝐼
owner
B
𝑗∈𝐽
2013/2/20
23
Notation: Parameters : number of drop-off boxes for products A to be located : number of drop-off boxes for products B to be located : cost of transporting a unit amount of product A per unit distance : cost of transporting a unit amount of product B per unit distance : distance between candidate location 𝑗 ∈ 𝐽 and destination location for product A
: distance between candidate location 𝑗 ∈ 𝐽 and destination location for product B destination location for A product A
2013/2/20
AB
B
destination location for product B 24
Notation: Parameters : space allocation cost at candidate location 𝑗 ∈ 𝐽 per period The fixed cost 𝑠𝑗 is required at location 𝑗 where at least one drop-off box is located.
e.g. personnel expenses for people who take care of collected used products at drop-off boxes allocated space = 5 B
A
A
AB
A B 2013/2/20
B B
25
Notation: Parameters : total amount of used product A at demand location 𝑖 ∈ 𝐼 generated per period
: total amount of used product B at demand location 𝑖 ∈ 𝐼 generated per period
：distance between 𝑖 ∈ 𝐼 and 𝑗 ∈ 𝐽
：amount of used products collected at a drop-off box for product A at 𝑗 ∈ 𝐽 from demand location 𝑖 ∈ 𝐼
：amount of used products collected at a drop-off box for product B at 𝑗 ∈ 𝐽 from demand location 𝑖 ∈ 𝐼 A
2013/2/20
26
Notation: Variables : binary variable which takes 1 when a space is allocated to 𝑗 ∈ 𝐽 for a drop-off box for products A or B, and 0 otherwise : binary variable which takes 1 when a drop-off box for product A is located at candidate location 𝑗 ∈ 𝐽, and 0 otherwise : binary variable which takes 1 when a drop-off box for product B is located at candidate location 𝑗 ∈ 𝐽, and 0 otherwise
2013/2/20
27
Notation: Variables : binary variable which takes 1 when owners of used product A at 𝑖 ∈ 𝐼 is allocated to a drop-off box for product A at 𝑗 ∈ 𝐽, and 0 otherwise
: binary variable which takes 1 when owners of used product B at 𝑖 ∈ 𝐼 is allocated to a drop-off box for product B at 𝑗 ∈ 𝐽, and 0 otherwise A A nearest A box A
2013/2/20
28
Formulation: Objectives (1) sum of the total volume collected for products A and B per period
(2) total space allocation cost per period 2013/2/20
total cost of transporting used products A and B collected at all drop-off boxes per period 29
Transportation and space allocation cost Desirable pattern of locations of drop-off points differs greatly depending on which cost we pay more attention to.
allocated space = 6 A
B A
A
allocated space = 3 AB
B
AB B
AB
𝑝A = 𝑝B = 3
When transportation cost is great drop-off boxes are located near destination locations 2013/2/20
When space allocation cost is great drop-off boxes tends to be co-located 30
Formulation: Constraints (3)
(4) (5) (6)
2013/2/20
31
Formulation: Constraints (7) (8) (9)
(10)
2013/2/20
32
Formulation: Constraints (11)
(12)
: index of 𝑚th closest candidate location from demand location 𝑖 Assumption 1 Closest assignment constraints Each owner is assigned to the nearest drop-off box A and to the nearest drop-off box B. 2013/2/20
33
Formulation: Constraints collected volume for product A collected volume for product B
(13)
(14)
: the value between 0 and 1 Elimination of imbalance in collected volume A and B At least 100𝛼% of used products of one type should be collected compared with the volume of the other type.
2013/2/20
34
Problem instance: Chofu city Chofu city
50km
destination location for product B
• Total population: 218,535 • demand locations: 105 • candidate locations: 25
Chofu
destination location for Assumptions product A • 𝑞𝑖A and 𝑞𝑖B are set equal
1km 2013/2/20
in June 1, 2011
to population of 𝑖; each person has one used product A and one for B. • Distances are measured by Euclidean distance. 35
Proportion of collected volume
proportion proportion decreases to 1⁄e at 500m away from the drop-off box
500m disntace [m] 2013/2/20
36
Pareto optimal solution “Good solution” in multi-objective optimization A given solution is a Pareto optimal solution when there is no other solution in which two objective values are better than or equal to those of the given solution, and at least one is strictly better than the given solution.
total cost
Pareto optimal solution no solutions
2013/2/20
total volume collected
37
Problem Instances • The cost of transporting a unit amount of products A and B: 𝑐 A = 𝑐 B = 0.005. • At least 80% of used products of one type should be collected compared with the volume of the other type: α = 0.8. • 𝑝A = 𝑝B = 3. emphasize transportation cost
Instance 1: 𝑠𝑗 = 1,000 ∀𝑗 ∈ 𝐽 Instance 2: 𝑠𝑗 = 10,000 ∀𝑗 ∈ 𝐽
emphasize space allocation cost 2013/2/20
38
Transportation and space allocation cost Desirable pattern of locations of drop-off points differs greatly depending on which cost we pay more attention to.
allocated space = 6 A
B A
A
allocated space = 3 AB
B
AB B
AB
𝑝A = 𝑝B = 3
When transportation cost is great drop-off boxes are located near destination locations 2013/2/20
When space allocation cost is great drop-off boxes tends to be co-located 39
Trade-off curve 1 Case where transportation cost is more important Instance 1: 𝑠𝑗 = 1,000 ∀𝑗 ∈ 𝐽 CPLEX 12.4 # Pareto optimal solutions： 153
1-d
26%
1-c
total cost
volume maximizer
8% 1-b cost minimizer
1-a total volume collected 2013/2/20
40
Pareto optimal solutions 1 Case where transportation cost is more important destination location for product B cost minimizer
destination location for product A allocated space = 5
allocated space = 3
allocated space = 4
volume maximizer allocated space = 3
2013/2/20
41
Trade-off curve 2 Case where space allocation cost is more important Instance 2: 𝑠𝑗 = 10,000 ∀𝑗 ∈ 𝐽 # Pareto optimal solutions： 89
total cost
2-d
volume maximizer
20%
2-c 8% cost minimizer
2-b
2-a
2013/2/20
total volume collected
42
Pareto optimal solutions 2 Case where space allocation cost is more important
cost minimizer
allocated space = 3
allocated space = 3
allocated space = 3
2013/2/20
volume maximizer allocated space = 3 43
Number of spaces allocated Average number of space allocated for drop-off boxes and the number of Pareto optimal solutions
𝑝A = 𝑝B = 3 𝑝A = 𝑝B = 4 𝑝A = 𝑝B = 5
𝑠𝑗 = 1,000 ∀𝑗 ∈ 𝐽 𝑠𝑗 = 10,000 ∀𝑗 ∈ 𝐽 5.08 （153）
3.09 （89）
6.20 （228）
4.07 （136）
7.31 （328）
5.03 （170）
• Greater space allocation cost induces drop-off boxes to be co-located. • The number of Pareto optimal solutions increases as the increase of the number of drop-off boxes. • It is also larger for the case of smaller space allocation cost than that of larger one. 2013/2/20
44
Conclusion • Proposed: Bicriteria Drop-off Points Location Problem • Applied: proposed problem to Population data of Chofu city • Obtained: good compromise solutions which perform well in the amount of collected volume, but their cost is much lower than those of the volume maximizing solution. Selected Literatures • Church, R.L., Roberts, K.L. (1984) Generalized coverage models and public facility location, Papers of the Regional Science Association, 53, 117-135. • Daskin, M.S. (1995) Network and Discrete Location: Models, Algorithms, and Applications, John Wiley and Sons, New York. • Dekker, R., Fleischmann, M., Inderfurth, K. and Wassenhove, L.N.V. (eds.) (2004) Reverse Logistics, Quantitative Models for Closed-Loop Supply Chain, Springer-Verlag, Berlin Heidelberg. 2013/2/20
45