Information Technology Reference
In-Depth Information
A request exchange mechanism using a combinatorial auction (CA) [1] under the
assumption that the fulfillment costs for any bundle of requests can be exactly
evaluated is proposed in [15]. In [25] a one-round auction and an iterative auction
are proposed for a scenario with several warehouses supplying single commodity
goods to customers, while the VRP with time windows has to be solved for
each warehouse. In these auctions, only requests located between neighboring
profit centers are exchanged. In [3] the CTP is solved for the traveling salesman
problem with pickup and delivery using both a Vickrey auction [30] and a CA.
Vehicle capacity is not considered in this approach. In [24] a CA-based approach
is proposed for a similar problem, in which also time windows of requests have
been considered. Since the introduction of time windows makes it impossible for
the coalition to fulfill all the requests, subcontracting is also considered. In [31]
a route-based request exchange mechanism is proposed for less-than-truckload
requests with time windows and capacity restrictions, while each member has
only a limited fixed number of vehicles in his fleet. This approach is similar to
the CA-based mechanisms as it also allows the exchange of bundles of requests.
Besides the mechanisms that exchange request bundles, pair-wise exchange
based approaches are also proposed to solve the static CTP problems. An incen-
tive compatible approach using cryptographic techniques for swapping pickup
and delivery requests among independent carriers is proposed in [5]. A protocol
is developed that is secure against a centralized model referred to as the “trusted
broker” model, where all parties give their input to the broker and the broker
computes and returns the result [5]. Bilateral exchange mechanisms enabling
FTL forwarders exchanging lanes to be served are proposed in [19]. Four set-
tings concerning information transparency and transfer payments between the
two sides of an exchange are studied.
From a methodological point of view, these approaches are developed based
on two different strategies. The first one is used in [3,5,19,25]. It depends on the
calculation of the marginal costs for single requests or request bundles. The basic
idea is to choose those requests with the highest marginal costs and to offer them
for exchange. If an exchange resulting in a better solution for all parties is found,
it will be accepted and the exchange process continues. Otherwise the process
ends. The approaches in [24] and [31] follow the Dantzig-Wolfe decomposition
principle [11]. They decompose the CTP problems into several sub-problems
reflecting the routing decisions of single carriers and a coordinating problem in
form of a CA and a set partitioning problem (SPP) or a set covering problem
(SCP). Using this decomposition scheme, each member in the coalition decides
only for his part without regarding the feasibility of any other part [11] and
without having to expose private information.
In contrast to static CTP problems, little research was conducted on DCTPP.
To the best of our knowledge, only in [26] a variant of DCTPP of a coalition of
SMC fulfilling FTL pickup and delivery requests is studied. Whenever a member
acquires a customer request, he launches an auction for the assignment of this
request and acts as an auctioneer. Other coalition members acting as bidders
calculate the marginal costs of inserting this request into their existing routes.
