Information Technology Reference
In-Depth Information
approaches periodically solve static problems corresponding to the current states
triggered by specific incidences. The first type of such triggers is an update of
input data, which is practically the release of a new customer request. This
strategy is used in [21,32,33]. In [21] a dynamic programming approach is pro-
posed for the dynamic dial-a-ride problem. Rolling horizon approaches are used
to solve the real-time FTL PDP with time windows [32] and its extension by the
possibility of rejecting requests and soft time windows [33].
Alternatively, a re-optimization can be trigged whenever a predefined interval
is reached. A branch-and-price algorithm is applied in [23] to solve the static
PDP with time windows for each single re-optimization. Similarly, in [4] the
column generation scheme is used in a dynamic approach which solves each time
the vehicle routing problem (VRP) with time windows [6]. An ant colony system
is developed in [18] for a dynamic VRP in which encrypted information about
characteristics of good solutions are conserved in a pheromone matrix and passed
on to the next static problem after a predefined duration.
The second category of solution approaches is referred to as continuous re-
optimization. The general idea is to run the optimization routines and maintain
information on good solutions in an adaptive memory. Whenever an event occurs,
e.g., a new request is known or a vehicle has finished its current job, a decision
procedure stops the optimization routine and updates the routes. After that, the
optimization routine is restarted with the new generated solutions. Different from
periodic re-optimization approaches, a driver does not know the next customer
to serve until he has finished his current job. Diverse optimization routines are
used in these approaches. In [13] a parallel tabu search (TS) proposed in [28] is
applied. Another TS is proposed in [12] while the concept of ejection chains [14]
is used to construct a powerful neighborhood structure.
In addition to work on developing e
cient solution approaches for dynamic
routing problems, the influence of different waiting strategies on the quality of
solutions to dynamic routing problems is studied in [17]. In [29] it is analyzed
how valuable it is for carriers to have the load information in advance.
2.2 Collaborative Transportation Planning
Some general opportunities and impediments of horizontal cooperation in lo-
gistics are revealed in [8]. A review of the literature on horizontal cooperation
in logistics can be found in [9]. Through performing CTP with fellow carriers
in a horizontal coalition, SMCs can reduce their operational costs to a great
extent. Several studies on identifying this cost-saving potential show that CTP
can account to 5-30 percent cost reduction compared to the case without re-
quest exchange [7,10,16]. However, appropriate request exchange mechanisms
must be developed to exploit the cost-saving potential embedded in CTP. Such
mechanisms have to be (1) simple and implementable, (2) effective in terms of
generating high joint benefits [19], and (3) able to deal with distributed infor-
mation and decision-making competencies [31].
Some approaches have been proposed in literature to tackle this challenging
task for static CTP problems. In most approaches auction mechanisms are used.
