Information Technology Reference
In-Depth Information
the weight of 1 while other requests have a weight less than 1. Next, each carrier
declares the total costs for his own request portfolio
R
p,
i
as a transfer price,
which is the maximum payment for the fulfillment of these requests without
cooperation. In case of FL, a route may have both due and non-due requests.
Only the first part containing the due requests are considered, i.e., the partial
route costs until the delivery location of the last due request in a route are used.
Denote this transfer price as
C
p,d
i
IP
=
i
=1
C
p,d
. The total transfer prices
TC
p,d
i
represent the total costs for this single planning period
p
without cooperation.
This piece of information is used for the acceptance of CTP solutions. A solution
of CTP will only be accepted, when it is better than the solution of IP, i.e.,
TC
p,d
CTP
<TC
p,d
IP
.
The next step is the
initial route generation
. Each carrier
i
solves a routing
problem for his own available vehicles
K
i
and generates a set of routes fulfilling
selected requests from the request pool
R
p,a
. The objective function of this
routing problem is the same as (1) except the sets
A
i
and
R
p,
i
are replaced by
A
p
and
R
p,a
, respectively. Through solving this problem in a heuristic manner,
a set of different solutions can be obtained. The first part of the routes in these
solutions containing only the due requests are reported as candidate routes to
an “agent” of the coalition. The costs of the partial routes will be declared as
the costs of these candidate routes.
After the set of candidate routes has been initialized, the iterative process
starts. In each iteration, the agent solves the winner determination problem
(WDP) in form of a linear relaxed SPP such that the total costs of the fulfillment
of all due requests are minimized. The option that the requests can be outsourced
to common carriers is also considered in the WDP such that each due request
r
R
p,d
is either to be assigned to a winning candidate route or common carriers
for the price
γ
r
. This price is the same to all coalition members.
Suppose that there are
n
p
requests in
r ∈ R
p,d
and
b
i
candidate routes have
been proposed by carrier
i
in the
initial route generation
step. For each request
r
,
a fictive route representing the common carrier option with the route cost of
γ
r
∈
is also added into the set of candidate routes. Thus,
b
=
i
=1
b
i
+
n
p
candidate
routes are there in total. Let
a
rj
= 1 indicate that request
r
is in route
j
and
a
rj
=0otherwise,
j
=1
,
2
,...,b
.Weuse
f
kj
= 1 to indicate that route
j
is
proposed for vehicle
k
,
k
K
p
. The cost of a candidate route is denoted by
c
j
.
The WDP can be formulated as follows by introducing the binary variable
y
j
,
j
=1
,
2
,...,b
, to indicate whether a route is chosen as a winning route:
∈
b
min
TC
CTP
=
c
j
y
j
(2)
j
=1
subject to:
b
R
p,d
a
rj
y
j
=1
∀
r
∈
(3)
j
=1
b
K
p
f
kj
y
j
≤
∀
k
∈
1
(4)
j
=1
