Information Technology Reference
In-Depth Information
Constraints (3) make sure that each request is assigned to exactly one winning
route and constraints (4) ensure that each vehicle is assigned no more than one
route. The agent solves the linear relaxation of this model and gets the dual
values related to (3) for requests
π
r
and related to (4) for vehicles
σ
k
.These
values are sent back to the carriers for the next iteration of route generation.
Using this feedback information, carriers can generate and submit new can-
didate routes in the
iterative route generation
step by solving another routing
problem with the following objective function:
min
k
β
k
d
uv
x
uvk
+
r
π
r
z
r
+
r∈R
p,a
γ
r
w
r
z
r
(5)
K
i
∈
(
u,v
)
∈A
p
∈
R
p,d
Again, only the first part of the routes in the solutions obtained by using
heuristic algorithms are proposed as candidate routes. They are then added
into the existing set of candidate routes. Readers are referred to [31] for a more
detailed presentation of the derivation of this objective function and more details
of the whole request exchange mechanism.
Iterative route generation ends when predefined criteria are satisfied. The
whole process ends with the
final winner determination
step, in which the agent
solves an SCP-based formulation of the WDP by replacing (3) with
b
R
p,d
a
rj
y
j
≥
∀
r
∈
1
(6)
j
=1
If some requests belong to more than one winning route in the WDP solution,
the agent calls a simple repair routine to obtain a feasible solution for the CTP
problem. The result of the WDP will only be accepted if its total costs are less
than the total transfer prices reported by all members in the first phase, which
indicates a cost reduction for the entire coalition.
5 Computational Experiments
In order to validate the functionality of the proposed solution approach for the
DCTPP and to evaluate the cost reduction potential embedded in the CTP
reachable by using the proposed approach, a computational study based on some
new theoretical instances is conducted.
5.1 Test Cases
In the first step, ten static instances are generated in total. The procedure of
generating static instances begins with generating request information in an
iterative fashion. The length per planning period is set as
τ
= 100. In each
iteration
it
,
it
=1
,...,
30, which corresponds to a time interval with (
τ
(
it
+
1)], about 40 requests for the entire coalition are generated. In order to introduce
fluctuation of customer demand, this number is adjusted with an amount up to
±
·
it,τ
·
20%. These requests are then assigned to three coalition carriers according
