Vertiefung zu Logistik/SCM [1.5ex] Discrete Location with Stochastic

Transcrição

16.04.2013
Vertiefung zu Logistik/SCM
1 / 37
Discrete Location with Stochastic Demand
Univ.-Prof. Dr. Knut Haase
Institut für Verkehrswirtschaft
16. April 2013
16.04.2013
Inhalt
1. Introduction
Assumptions
Application in mind
2. Modeling the behavior of the potential customers
Choice Probability Derived from the Multinomial Logit Model
Independence of irrelevant alternatives (IIA-property)
Estimation of Discrete Choice Model
3. Integration of the MNL in location planning
Notation
4. Nonlinear location model
Linear reformulation by Benati/Hansen (2002)
Linear reformulation by Haase (2009)
Linear reformulation by Zhang et al. (2012)
5. Numerical investigations
6. Case study and numerical results
2 / 37
16.04.2013
3 / 37
Assumptions
I
I
I
I
Given set of potential locations
Static competition
Customer choose location with maximum utility
Choice behavior can be modeled by multinomial logit model
16.04.2013
Application in mind I
I
I
I
I
Network of branch offices of parcel service provider
City of Dresden
Considered company: Deutsche Post
Competitor: Hermes Logistics Group
4 / 37
16.04.2013
5 / 37
6 / 37
Application in mind II
16.04.2013
Inhalt
1. Introduction
Assumptions
Application in mind
Notation
16.04.2013
7 / 37
Choice Probability Derived from the Multinomial Logit Model I
Notation
ij
independently and identical extreme value distributed (i =
individual, j = alternative)
zijm value of attribute m
jm utility per unit of attribute m; variable to be estimated
16.04.2013
8 / 37
Density-function and cumulative distribution function of Gumbel
distribution (extreme value distribution)
F (ij ) = e
1
e
ij
0:8
0:6
0:4
0:2
f (ij ) = e
ij
0
2
0
2
ij
4
6
e
e
ij
16.04.2013
9 / 37
Utility of location j for individual i
uij = vij + ij
vij =
X
jm zijm
m
Choice probability (Train, 2009)
e vij
pij = P v
ik
ke
16.04.2013
10 / 37
I Ratio of choice probabilities of two alternatives j ; j 0 :
pij
pij 0
=
=
=
vij
Pe vik
ke
=
vij 0
Pe vik
ke
e vij
e vij 0
constant
I Adding or removing an alternative does not change the ratio of
choice probabilities (constant substitution patterns).
16.04.2013
11 / 37
Software packages for determination of ˆ :
I
I
I
I
16.04.2013
BIOGEME,
LIMDEP, NLOGIT,
SPSS and
R.
Estimation of an MNL with BIOGEME
BIOGEME is an acronym for BIerlaire Optimization toolbox for
Generalized Extreme value Model Estimation (see [Bie03] und [Bie08]).
The software public domain and can be downloaded under
http://biogeme.epfl.ch
for the standard operating systems.
Execution of BIOGEME from command window (cmd.exe).
12 / 37
16.04.2013
13 / 37
Files to be prepared
Model-file Includes the definition of the utility functions. File name
needs the extension .mod, e.g. mymodel.mod.
Data-file Contains the observations as table. Filename, e.g.:
mysample.dat
Excution of BIOGEME
biogeme mymodel mysample.dat
Result file
mymodel.rep.
16.04.2013
Example
Students which have no car available go to their university on foot
(j = 1), by bike (j = 2) or by bus (j = 3). The decision of student i
depends on the travel time dij [in minutes] and on the sex si (1= female,
0 = male). The deterministic component of the utiliy function is as
follows:
vi1
vi2
vi3
01 + 11 di1 + 21 si
= 02 + 12 di2 + 22 si
= 03 + 13 di3 + 23 si
=
For avoiding problems of identification we set (in this case)
01 = 11 = 21 = 0;
i.e. vi1 = 0 for all students n
14 / 37
16.04.2013
15 / 37
Our model file mymodel.mod is constructed as follows:
[Choice]
Choice
[Beta]
// Name
b01
b02
b03
b11
b12
b13
b21
b22
b23
Value
0
0
0
0
0
0
0
0
0
LowerBound
-10000
-10000
-10000
-10000
-10000
-10000
-10000
-10000
-10000
UpperBound
10000
10000
10000
10000
10000
10000
10000
10000
10000
status (0=variable, 1=fixed)
1
0
0
1
0
0
1
0
0
[Utilities]
// Id Name Avail linear-in-parameter expression
16.04.2013
1
2
3
Foot av1 b01 * one + b11 * d1 + b21 * s
Bike av2 b02 * one + b12 * d2 + b22 * s
Bus av3 b03 * one + b13 * d3 + b23 * s
[Expressions]
one = 1
av1 = 1
av2 = 1
av3 = 1
[Model]
$MNL
16 / 37
16.04.2013
17 / 37
Excerpt of our data file mysample.dat:
ID Choice
1
1
2
1
3
1
4
2
5
1
:
:
95
3
96
1
97
1
98
2
99
1
100
1
16.04.2013
d1
6
8
12
21
6
:
51
18
6
33
19
15
d2
8
9
9
12
7
:
21
11
9
15
11
12
d3
13
13
15
17
12
:
24
14
12
16
13
16
s
0
1
1
0
0
:
0
1
0
1
0
1
Excerpt of the output file of BIOGEME mymodel.rep:
Model:
Number of estimated parameters:
Number of observations:
Number of individuals:
Null log-likelihood:
Cte log-likelihood:
Init log-likelihood:
Final log-likelihood:
Likelihood ratio test:
Rho-square:
Adjusted rho-square:
Final gradient norm:
Diagnostic:
Iterations:
Run time:
Multinomial Logit
6
100
100
-109.861
-88.991
-109.861
-68.002
83.718
0.381
0.326
+4.082e-07
Convergence reached...
11
00:00
18 / 37
16.04.2013
Utility parameters
******************
Name Value Std err t-test p-val Rob. std err Rob. t-test Rob. p-val
---- ----- ------- ------ ----- ------------ ----------- ---------b01 0.00
--fixed-b02 -5.57 1.15
-4.84 0.00
1.01
-5.50
0.00
b03 -10.4 2.17
-4.78 0.00
2.02
-5.13
0.00
b11 0.00
--fixed-b12 0.324 0.0746
4.35
0.00
0.0665
4.87
0.00
b13 0.554 0.123
4.52
0.00
0.115
4.81
0.00
b21 0.00
--fixed-b22 -0.128 0.617
-0.21 0.84 * 0.580
-0.22
0.83
b23 -0.317 0.678
-0.47 0.64 * 0.666
-0.48
0.63
16.04.2013
*
*
Deterministic components of utility function:
vi1
=
vi2
=
vi3
=
Model statistics
L(ˆ ) -68.002
2
0.381
0
5:57 + 0:324 di2
10:4 + 0:554 di2
19 / 37
0:128 si
0:317 si
20 / 37
16.04.2013
21 / 37
Inhalt
1. Introduction
Assumptions
Application in mind
Notation
16.04.2013
22 / 37
Modified notation I
Notation typically in location literature
i
demand point (homogenous customers)
M
locations; indices j ; k
J
locations of considered company (J
M)
Utility of homogenous customer in i to choose location j
uij = vij + ij
(1)
16.04.2013
23 / 37
Modified notation II
Choice probability
pij =
P
=P
16.04.2013
e vij
vik
k 2M e
e vij
P vij
vik +
e
k 2M nJ
j 2J e
Inhalt
1. Introduction
Assumptions
Application in mind
Notation
(2)
(3)
24 / 37
16.04.2013
25 / 37
Nonlinear location model
Variables
2 J is established by considered company (0,
yj
=1, if location j
sonst)
xij
expected market share of location j in demand point i (corresponds
to pij )
16.04.2013
26 / 37
Model formulation
Assumption
In each demand point the in i : 1 unit
max F =
X
2
P
i I
subject to
X
2
P
2 n
j M J
2
j Je
e vij +
vij
y
Pj
vij
j 2J e yj
yj = r
j J
yj
2 f0; 1g
(4)
(5)
8j 2J
(6)
16.04.2013
27 / 37
Linearization by Benati/Hansen (2002)
Additional defined parameter
'ij =
max F =
P
e vij
(7)
vik
k 2M nJ e
XX
2 2
'ij (yj
xij )
(8)
i I j J
subject to (5), (6), and
yj
xij +
X
2
'ik (yk
xik )
1
8 i 2 I; j 2 J
(9)
xij
0
8 i 2 I; j 2 J
(10)
k J
16.04.2013
28 / 37
Non-negative variable (fraction of competitors): x̃i
max F =
XX
2 2
xij
(11)
i I j J
subject to (5), (6), (10), and
x̃i +
X
2
xij
1
8i 2I
(12)
j J
xij
'ij
yj
1 + 'ij
xij 'ij x̃i
x̃i
0
0
0
8 i 2 I; j 2 J
8 i 2 I; j 2 J
8i 2I
(13)
(14)
(15)
The model of [Haa09] has been analogously presented by [AVMM13].
16.04.2013
29 / 37
Linear reformulation by Zhang (2012)
Non-negative variable: zijk
(11) subject to (5), (6), (10), and
xij
'ij yj +
X
2
'ik zijk = 0
k J
zijk
xij
zijk
yk
xij + yk
zijk
zijk
16.04.2013
0
0
1
0
8 i 2 I; j 2 J
8 i 2 I;
8 i 2 I;
8 i 2 I;
8 i 2 I;
2J
j; k 2 J
j; k 2 J
j; k 2 J
j; k
Inhalt
1. Introduction
Assumptions
Application in mind
Notation
(16)
(17)
(18)
(19)
(20)
30 / 37
16.04.2013
31 / 37
Numerical investigations
I GAMS (23.7) and use CPLEX 12 on a 64-bit Windows Server 2008
with 1 Intel Xeon 2.4 GHz processor and 24 GB RAM
I Cartesian coordinates blocks (demand nodes) and locations by a
uniform distribution in the interval [0; 30]
I vri = 0:2 dri
jR j
jI j
200
25
50
400
25
50
S
CPU
[BH02]
GAP
DEV
CPU
[Haa09]
GAP
DEV
CPU
[ZBV12]
GAP
DEV
2
4
2
4
2
4
2
4
10.52
267.27
153.40
3591.20
35.41
976.47
745.41
3600.00
0
0
0
11.99
0
0
0
29.12
0
0
0
0.05
0
0
0
0.81
8.04
64.22
67.10
443.97
38.10
213.06
241.86
1548.51
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1348.36
3600.00
3600.00
3600.00
3323.68
3600.00
3600.00
3600.00
0
28.91
19.01
9.79
-
0
5.44
4.39
15.72
1.65
14.62
19.16
18.48
16.04.2013
Inhalt
1. Introduction
Assumptions
Application in mind
Notation
32 / 37
16.04.2013
33 / 37
Case study and numerical results I
Deutsche Post in City of Dresden
I
I
I
I
6.406 blocks (i)
Post: 49 shops (I )
Hermes (competitor): 69 shops
j M j= 49 + 69 = 118
16.04.2013
34 / 37
Case study and numerical results II
Utility function
Empirical investigation (revealed preferences) (Hoppe, 2009)
Variable
Log. distance to shop [m]
Distance to shop < 1800 m? (ja=1, nein=0)
Is shop of Deutsche Post? (ja=1, nein=0)
Shop located in centre (ja=1, nein=0)
business hours per week [h]
number of observations
¯2
ˆ
-1,86
1,02
1,48
1,60
0,028
637
0,689
t-Wert
-7,30
2,95
4,09
3,70
3,47
16.04.2013
35 / 37
Optimal solution of location model Haase (2009)
F :
0.6699
16.04.2013
CPU:
957.11 seconds
Literaturhinweise I
Aros-Vera, Felipe, Vladimir Marianov und John E. Mitchell: p-Hub approach for
the optimal park-and-ride facility location problem.
European Journal of Operational Research, 226(2):277 – 285, 2013.
Benati, Stefano und Pierre Hansen: The maximum capture problem with random
utilities: Problem formulation and algorithms.
European Journal of Operational Research, 143:518–530, 2002.
Bierlaire, M.:
BIOGEME: a free package for the estimation of discrete choice models.
In: 3rd Swiss Transport Research Conference, 2003.
Bierlaire, M.: An introduction to BIOGEME (Version 1.8), 2008.
Haase, Knut: Discrete Location Planning.
Technischer Bericht WP-09-07, Institute for Transport and Logistics Studies,
University of Sydney, 2009.
36 / 37
16.04.2013
Literaturhinweise II
Zhang, Yue, Oded Berman und Vedat Verter: The impact of client choice on
preventive healthcare facility network design.
OR Spectrum, 34:349–370, 2012.
37 / 37

Vertiefung zu Logistik/SCM [1.5ex] Discrete Location with Stochastic

Transcrição

Documentos relacionados

WWW.SYSTORECOLOMBIA.COM