A combinatorial intra-enterprise exchange for logistics services

Abstract

The exchange of cargo capacities is a well established approach in logistics. However, only few logistics marketplaces are able to take into consideration synergies that can be generated by combining different transportation routes of different logistics carrierps. In order to exploit these synergies, we designed and implemented the combinatorial exchange mechanism ComEx for the intra-enterprise exchange of delivery orders in a logistics company organized in a profit center structure. Each profit center is able to release delivery orders to an adjacent profit center if the geographic locations of the customers allow for a reduced-cost delivery by the adjacent profit center. We demonstrate that by using the ComEx mechanism, the total cost of transportation of our logistics company can be reduced by up to 14%. Since our iterative auction mechanism is very complex and therefore resource-intensive, we reduce the complexity by applying a convex hull approach combined with a distance-based cost estimator.

1 Introduction

The rising cost of energy, infrastructural bottlenecks, restrictive legal regulations and increased competition in the transportation sector are forcing carriers to increase the efficiency of their transportation services. Customers also expect higher standards of planning flexibility, response time, and delivery time (Wendt et al. 2006). In addition to this, a cost reduction potential, which is commonly estimated as 15% of total transportation cost (Cruijssen et al. 2007b; Ergun et al. 2007b; Gujo and Schwind 2007), environmental concerns and sustainability also play a very important role in modern logistics management (Quariguasi et al. 2006). One promising approach often used in this context is to avoid needless traffic by optimizing the use of capacities in existing transportation networks. The optimization method is to bundle free resources by using exchanges for freight capacity. Few of these mostly web-based market places, however, are able to take into consideration the synergies that can be generated by the appropriate combination of transportation lanes of different carriers. One way to achieve this is to employ combinatorial auctions that allow to bid on bundles of lanes (Cantillon and Pesendorfer 2005). To be able to utilize the synergy effects resulting from the reallocation of delivery orders between transportation providers effectively, we created the electronic exchange ComEx to work in conjunction with the route planning system DynaRoute.

In the context of this work, ComEx provides a combinatorial auction for the exchange of delivery orders in a medium-sized logistics company organized in a profit center structure. Each profit center has a specified area in which to deliver goods to customers. In the ComEx system, the profit centers are able to release delivery orders to an adjacent profit center if the delivery costs are relatively high and the adjacent profit center is able to perform the delivery at lower costs. As will be shown, the ComEx mechanism is able to reduce the total delivery costs for our medium-sized company at about 14% compared to a solution without a combinatorial exchange. However, our combinatorial auction approch encounters some severe problems that have to be solved in order to achieve this result. Four major issues have been identified as being critical for the application of combinatorial auctions (Schwind 2005):

• the bid formation and preference elicitation problem,

• the bid valuation and pricing problem,

• the winner determination problem, and

• the incentive compatibility problem.

All these issues have been addressed in recent research. We want to focus on the first two issues because they provide the most promising potential to improve the cost reduction that can be achieved by the application of ComEx. In the ComEx mechanism, the winner determination problem does not play a dominant role since the mechanism reduces the computational complexity of the underlying optimization problem (Schwind et al. 2003). However, the incentive compatibility problem still remains unresolved (Gujo et al. 2007).

ComEx addresses the bid formation and bid valuation problem in two ways. A clustering algorithm automatically constructs combinations of delivery orders that provide potentially better solutions in terms of costs, if they are exchanged between the profit centers and integrated into their delivery route planning while using the ComEx mechanism. The pricing of clusters (bids) is achieved by employing a cost-based calculation relying on the integrated route planning software DynaRoute. In order to reduce the combinatorial complexity of the winner determination problem, only a selection of clusters is fed into the exchange process. This is done by defining core delivery areas for the profit centers. Because this process might provide suboptimal results, we introduce an iterative auction and a convex hull mechanism for the definition of the delivery areas in the outsourcing process. The combination of both mechanisms yields a cost reduction of up to 14%.

The remainder of this article is organized as follows. In the next section, we will discuss alternative approaches that attempt to provide cost reduction for transportation by introducing collaborative solutions, whereas Sect. 3 describes the exchange mechanism performed by the ComEx system. In Sect. 4, the ComEx system architecture and the system components are presented. Furthermore, the section provides insights into the algorithmic features of the system components. Section 5 introduces possible ways of improving the exchange mechanism, while Sect. 6 presents some simulation results based on real-world data. The article ends with a summary of the results and a brief overview of further work.

2 Collaboration in logistics

Both recent academic literature and industrial practice address the need for efficient collaboration planning and exchange solutions in modern logistics. For this reason, we first point out the importance of collaborative planning and exchange solutions for transportation tasks and delivery routes in logistics networks. Whereas collaborative planning mainly uses methods of operations research to directly search for optimal solutions by merging the transportation plans of different freight forwarding enterprises, exchange solutions rely on an economic optimization calculus to determine the optimal allocation of transportation tasks and delivery orders to transportation service providers. In the second part of this section, we briefly address the basic elements of combinatorial auctions that are especially appropriate to foster efficient collaborations using logistics exchanges.

2.1 Collaborative planning and logistics exchanges

Collaborative transportation planning and the application of logistics exchanges are closely related topics because both approaches strive to (re)optimize joint tour plans. The main difference is that logistics exchanges are a more economically driven mechanism than collaborative transportation planning and therefore do not require the direct cooperation of the participating partners. Additionally, logistics exchanges can be used at all stages of the transportation planning process, whereas collaborative planning should be applied at an early stage of the process.

Collaborative planning in logistics focuses on the (re)optimization of delivery routes by the (de)composition and (re)combination of existing transportation tours (Cruijssen et al. 2007a; Ergun et al. 2007c). Examples of this approach can be found in the recent literature. Some approaches integrate the pickup-and-delivery problem with time windows (PDPTW) to guarantee usability for real-world transportation problems (Savelsbergh and Sol 1995; Goel and Gruhn 2007; Nowak et al. 2008). Despite the fact that this collaborative approach was not motivated directly by economic optimization calculus, recent literature has dealt with the issues of the fair distribution of the cost reduction or of the rise in yield achieved by the collaboration, especially with respect to the incentives necessary to motivate partners to participate in the collaborative planning process (Krajewska and Kopfer 2006; Özener and Ergun 2008). In many cases the Shapley value is employed to construct models with side payments in order to assure incentive compatibility (Krajewska et al. 2008). Some approaches make direct use of game theory to model the behavior of the collaborating partners with respect to yield division (Houghtalen 2007), as is done in the paper of Slikker et al. (2005) that presents a multiple-vendor game with transshipments, or in the work of Xiao and Yang (2006) describing a non-cooperative profit-maximizing game among shippers, carriers, and infrastructure companies.

The use of logistics exchanges is constructed in such a way that economic incentives are employed as part of the optimization process. Transportation service exchanges have been used by logistics service providers for a long time (Song and Regan 2001). However, few of these marketplaces are able to take into consideration the synergies that can be generated by appropriate combinations of the transportation lanes of different carriers. One way to exploit these synergies is to employ a combinatorial auction for the exchange process, which allows the participants to bid for bundles of lanes that fit into their current route plans. Our combinatorial exchange for logistics services is one of the first approaches that makes use of this systematical advantage.

The ComEx approach is designed and implemented as a decentralized optimization system to reflect and regard the autonomy of the profit centers. In order to optimize the transportation routes, each profit center has to consider a great deal of data concerning the delivery orders, e.g., the location and the delivery time windows of the customers, the weight of the goods, the load capacity of the trucks. Due to the computational complexity of the planning problem, a centralized optimization method cannot find an optimum solution in acceptable time (Gomber et al. 1999). For this reason, the application of a decentralized method facilitated by a combinatorial auction provides a way to reduce the computational complexity of the entire logistics planning problem.

2.2 Combinatorial auctions for logistics exchanges

Combinatorial auctions are increasingly gaining influence as an allocation method for industrial procurement and distribution processes (Schwind 2005). Typical domains are supply chain management, resource allocation in distributed computer systems, and exchanges for logistics services (Stockheim and Schwind 2004; Schwind et al. 2006). Combinatorial auctions allow bidders to bid for bundles of goods (services or resources) while the valuation of bundles depends on synergies between the individual goods, services or resources (Cramton et al. 2006). Two types of valuation effects are of interest in this context:

• Subadditivity: If substitutionalities between the goods in the package lead to a lower utility of the entire bundle compared to the sum of the utilities of the individual goods, subadditivity has to be assumed.

• Superadditivity: If the valuation of a bid bundle is higher than the valuation of the individual goods the effect is described as superadditivity. This results from complementarities in the bidder’s utility function for the single goods.

The ComEx system exploits the complementarities arising from the different locations of the transportation services’ customers in the delivery network to reduce the total transportation cost.

An early approach to introducing the application of combinatorial auctions in the logistics sector was made by Caplice (1996). Caplice and Sheffi (2003) combine a route planning process with the allocation of transportation capacity by using a combinatorial auction that selects the cost-minimal combination of delivery orders. A related approach was proposed by Regan and Song (2003), who suggested a spot market for logistic services that are required in the short term. Some providers of logistics software and operators of freight exchanges have already introduced simple combinatorial auction mechanisms into their route planning and freight allocation methods¹ Elmaghraby and Keskinocak (2005) document a two-step procurement auction for transportation capacities organized by the home improvement chain Home Depot to ensure the logistics supply of about a thousand stores. In cooperation with i2-Technologies, a flexible auction software has been developed to support the bidders in formulating appropriate bid combinations to provide the optimal synergy effects between the routes (An et al. 2005). Cantillon and Pesendorfer (2005) present a combinatorial auction mechanism used for the allocation of transportation services providers to bus routes for ‘London Regional Transport’. The incentive compatibility issue is addressed by employing the Vickrey–Clarke–Groves mechanism (Parkes et al. 2001) to distribute the cost reduction or the increase in yield fairly. The model presented by Krajewska et al. (2008) additionally includes a solution of the PDPTW coupled with the allocation of transportation tasks. Ergun et al. (2007a) focus on the optimization of bid prices in a simultaneous truckload transportation procurement auction in order to increase the synergy from the combination of lanes. The underlying problem is formulated as a competitive game between shippers and carriers.

3 Combinatorial exchange for logistics services

In the following, we provide an overview of the functional principle of the combinatorial auction for logistics services exchange and illustrate the interaction between the optimization process and the auction in the ComEx system.

3.1 Scenario description

The development of the ComEx system was motivated by a German logistics company whose different branches are organized as profit centers. Each profit center has an individual set of customer delivery orders and generates revenue in excess of its expenses. It is expected that, through the delivery of goods, the branch will make a profit. This is in contrast to a cost center, which is a unit inside a company that generates expenses but has no responsibility for creating revenue. The only incentive a cost center has is to lower expenses whenever possible while staying within a specific budget determined at the corporate level.

Figure 1 illustrates the three profit centers of the relevant logistics company (represented by triangles) and the locations of their customers (represented by points). It can be seen that the three delivery areas overlap. Thus, it is to be expected that delivery to some customers in these overlapping areas can be made more cost-effective by outsourcing ² them to a neighboring profit center. The scenario is close to that presented in an approach by Krajewska and Kopfer (2006) which is also based on a logistics company with branches organized as profit centers and makes use of a variant of the combinatorial auction called matrix auction (Gomber et al. 1999).

Fig. 1

Overlapping delivery areas of three profit centers

Since each customer delivery order is associated with the customer’s coordinates and an individual delivery time window, the exchange mechanism has to consider many constraints. Capacity constraints do not play an important role in our application because time constraints are the only limiting factor in our optimization example. Furthermore, synergies between different delivery orders have to be considered in order to minimize the delivery costs of the logistics company.

The following section describes the exchange mechanism of the ComEx system that is based on a combinatorial auction.

3.2 Exchange mechanism

Figure 2 depicts the initial scenario where each profit center (represented by triangles) has an individual set of customers (represented by points) requiring delivery of goods. The exchange mechanism can be subdivided into four main phases:

• Initialization phase: In the first phase, the profit centers wanting to participate at the exchange mechanism have to register at the auction by sending the identification data to the auctioneer.

• Outsourcing phase: After the registration, each profit center tries to outsource the most cost-intensive delivery orders in order to minimize the delivery costs of the entire logistics company. In this context, it has to be noted that for delivery orders of customers located close to each other, the delivery should be performed by only one vehicle in order to realize the cost synergies between these orders provided that the given delivery time windows are not violated. Therefore, a clustering mechanism has been designed to identify delivery orders of customers in close proximity to one another, which can therefore be fulfilled on the same delivery route taking the time windows into consideration. Each cluster represents a delivery path where the maximum distance between two neighboring customers within the cluster is given by a parameter r to be set prior to activating the ComEx exchange mechanism. The result of the clustering process is shown in Fig. 3.

  After the clustering process has taken place, each profit center needs to identify the order clusters that are likely to be cost-intensive. For this reason, a parameter a, 0 < a ≤ 1, is introduced to define the percentage share of clusters that should be outsourced to another profit center. For a = 1, all clusters of a profit center are able to be outsourced, whereas, e.g., for a = 0.6, the 6 out of 10 most distant clusters (in reference to the average distance between the location of the profit center and the locations of the customers grouped in the cluster) are designated as outsourcing candidates (see Fig. 4). Thereafter, an information interchange between the profit centers is performed, aimed at defining all outsourcing candidates as insourcing candidates for all profit centers.

• Insourcing phase: Given the set of insourcing candidates C*, each profit center can generate bids on any cluster. In particular, due to the synergies between clusters with close proximity and with respect to the given time window constraints, the profit centers have the opportunity to bid on any non-empty cluster combination $B {\subseteq} C^*$ and thus generate combinatorial bids (B _i , p _i ), whereby p _i denotes the bid price for cluster bundle B _i . This is done by investigating whether some insourcing candidates can be connected together taking into account the coordinates and the time windows of the customers contained in the clusters. As depicted in Fig. 5, both profit centers A and B individually generate the combinatorial bids for the cluster bundles C ₁, C ₂, C ₃, C ₄, C ₅, C ₆, C ₂ C ₃, and C ₅ C ₆.

  In order to determine the bid prices for each combinatorial bid (B _i , p _i ), the route planning and optimization software DynaRoute is used to calculate the difference in delivery costs resulting from excluding and including the cluster combination B _i to the set of all delivery orders. This cost difference is then used as the bid price p _i for the bundle B _i .

• Final evaluation phase: After each profit center has submitted its bids, the combinatorial auction is performed by finding the cost-minimal allocation of order clusters to the profit centers. The objective is to minimize the total delivery costs for the entire logistics company (see Fig. 6). After the closing of the auction, the delivery routes and the delivery costs of each profit center are recalculated by the DynaRoute software taking the information about the in- and outsourced customer delivery orders into account.

Fig. 2

Initial scenario with two profit centers

Fig. 3

Result of the clustering process

Fig. 4

Determination of outsourcing candidates

Fig. 5

Generation of combinatorial bids

Fig. 6

Cost-minimal allocation of cluster bundles

4 System description of ComEx

The ComEx architecture consists of four components (see Fig. 7): the ComEx server that serves as the auctioneer and controls the entire auction process, the ComEx clients that administer all customer delivery orders of the profit centers while formulating, submitting and receiving in- and outsourcing bids, the DynaRoute server that determines the optimal routing information and the associated delivery costs, and the ComEx engine which is responsible for the calculation of the optimal allocation of the delivery orders to the profit centers. In the following, we describe the interaction of the system components in the four phases of the ComEx auction:

• Initialization phase: In order to evaluate the effectiveness of the exchange mechanism, the delivery costs prior to and after the auction have to be compared. Therefore, all profit centers (ComEx clients) send requests to the DynaRoute server to determine the delivery costs of the initial order set 1 (see Fig. 7, step 1). Thereafter, the auction format and the registration and licensing data of the profit centers participating at the auction process are transmitted to the ComEx server that acts as the auctioneer (see Fig. 7, step 2).

• Outsourcing phase: Then, each ComEx client groups the customer delivery orders into clusters taking the customers’ time windows and coordinates into account. The outsourcing candidates (order clusters) are then determined based on the average distance between the location of the profit center and the coordinates of the customers contained in an order cluster. Finally, the profit centers send the information about the outsourcing candidates to the ComEx server and in return receive the list of all order clusters that have been designated by the ComEx clients to be outsourced (see Fig. 7, step 3).

• Insourcing phase: Given the set of all outsourcing candidates, each ComEx client has the opportunity to bid on the order clusters that can be integrated into or connected to other clusters by taking the customers’ time windows and coordinates into account. In order to determine the bid price for each selected cluster combination, the ComEx clients send requests to the DynaRoute server to determine the additional delivery costs (see Fig. 7, step 4). These delivery costs are used as the bid price for the relevant cluster bundle.

  Thereafter, the combinatorial bids are sent to the ComEx server (see Fig. 7, step 5) and passed on to the ComEx engine (see Fig. 7, step 6) responsible for the initialization of the combinatorial auction and the calculation of the cost-minimal allocation of order clusters to the ComEx clients.

• Final evaluation phase: After the combinatorial auction has taken place, each ComEx client updates its route plans based on the result of the auction. In order to evaluate the effectiveness of the exchange mechanism, the final delivery costs of each ComEx client have to be determined by the DynaRoute server (see Fig. 7, step 7). Finally, the ComEx clients’ delivery costs prior to and after the auction are sent to the ComEx server to calculate the total delivery costs of the entire logistics company (see Fig. 7, step 8). If a reduction in cost could be achieved for the entire company, the auction result is confirmed. Otherwise, the auction result is rejected.

Fig. 7

Communication and process flow in the ComEx system architecture

In the following, we provide insights into the four main components of the ComEx architecture: the DynaRoute server, the ComEx client, the ComEx server, and the ComEx engine.

4.1 DynaRoute server

Each ComEx client has to solve an instance of the time dependent vehicle routing problem with time windows (TD-VRPTW) which extends the ${{\mathcal{NP}}}$-complete vehicle routing problems with time windows (VRPTW) by driving times that depend on the time of day and different categories of time windows. Case studies show that the time window’s start can vary to a certain degree while leading to an acceptable optimization result. The degree to which a tour does not comply with the time windows is penalized in the evaluation function. By using DynaRoute, the clients are able to optimize their individual delivery routes (Wendt et al. 2005). The optimization algorithm of the DynaRoute server is an extended version of cooperative simulated annealing (COSA), a combination of the meta-heuristics simulated annealing (SA) and genetic algorithms (GA) proposed by Wendt (1995). Due to the high complexity that results from the TD-VRPTW, the COSA algorithm is extended by several concepts to improve performance:

• Compression of the solution space: Due to the fact that the evaluation function of the TD-VRPTW consumes a considerable number of time cycles, the performance of the algorithms can be increased by excluding solution candidates by using stochastic stop criteria when evaluating new candidates. Moreover, DynaRoute identifies patterns by using algorithms similar to ant systems (Bullnheimer et al. 1999) to direct the search to efficient ‘regions of the search space’.

• Tabu lists: In the context of SA algorithms, the use of tabu lists resulted in considerable improvement of the performance (Li and Lim 2003). By using tabu lists (Glover 1986), DynaRoute is able to temporarily exclude solutions or solution regions from the search space. This results in greater diversity in the search process and thus in a higher probability of finding the optimal solution.

• Approximation of the fitness of inferior solutions: By reducing the time required for the process of solution evaluation, the overall performance of the algorithm can be improved considerably. An exact evaluation of the candidates is not always necessary but can be replaced by an approximation if the accuracy of the approximation is within certain limits. DynaRoute uses the dynamic approximization rules which adapt the accuracy of the evaluation depending on the optimization progress.

In the context of the ComEx framework, the DynaRoute server optimizes the client specific TD-VRPTW and approximates the additional costs resulting from insourcing customer delivery orders. The ComEx client specifies existing clusters of customer orders or generates order bundles. Based on the generated population of solutions, the DynaRoute server approximates the impact of these order clusters on the cumulative costs of the delivery route. By running a reactivation of the optimization process it is possible to integrate or exclude the given clusters in a new ‘near optimal’ solution. In this way, the cost of adding a new cluster or the savings made when removing a cluster can be calculated very quickly by comparing the original solution to the new solution. The population-based approach allows the server to check the k-best solutions of both populations, which provides a strong indication of the optimality of the solution. This strongly reduces the risk of inaccurate calculations by minimizing the error that may occur in a single solution due to a ‘weaker optimization’. This enables the DynaRoute server to deal with the complex cost estimates for the clusters identified by the ComEx client.

4.2 ComEx client

Each profit center is represented by a ComEx client that is responsible for the clustering of delivery orders, the identification of outsourcing candidates and the generation of combinatorial bids. In the following, the clustering process is presented in detail.

Clustering and Outsourcing: It is obvious that for delivery orders of customers located close to each other, the delivery should be performed by the same vehicle in order to realize cost synergies between these orders provided that the given delivery time windows are not violated. In this context, a cluster represents a delivery path (sequence of customers) where the maximum distance between two neighboring customers within the cluster is given by a parameter r that has to be set prior to the ComEx exchange mechanism. Besides the realization of cost synergies, the clustering process aims at reducing the complexity of the underlying combinatorial optimization problem.

At the beginning of the clustering process, each customer represents one cluster. The clustering algorithm is related to Kruskal’s algorithm for the Minimum Spanning Tree problem (Kruskal 1956) that searches through the edges of a given graph to find the edge with the minimum weight and adds it to the tree, provided that the edge does not create a cycle. In a similar way, the clustering mechanism tries to extend a cluster at its beginning or end by attaching another cluster to it. First, the mechanism calculates the distances between all pairs of customers that are represented by vertices v _i . Beginning with the minimum distance d _i,j between the two customer vertices v _i and v _j with d _i,j  ≤ r, the algorithm connects the two vertices of the two different clusters by the undirected edge {v _i , v _j }. If a vehicle is able to deliver to the two customers in the sequence v _i → v _j or v _j → v _i within the given time windows, the two customers are grouped into the same cluster C _k .

In the subsequent step, the pair of second nearest customers are connected in order to merge the two respective clusters into one cluster. If the same vehicle can deliver to the customers contained in this merged cluster within the given time windows, the cluster is valid. It is obvious that two different clusters can only be merged by adding the undirected edge {v _i , v _j } if both vertices v _i and v _j are terminal vertices. If v _i or v _j are not terminal vertices, any connection of the two vertices cannot lead to a sequence of customers. In this case, the mechanism continues with the next shortest distance and investigates the two relevant customers (or clusters) which are to be merged into one cluster.

Let V be the set of (customer) vertices in an undirected graph G. Figure 8 illustrates the corresponding clustering algorithm with pseudo code.

Fig. 8

Pseudo-code of the clustering algorithm

Initially, the algorithm identifies the set of connections that can be constructed by generating the permutations of all pairs of customers v _i and v _j in the delivery area of the profit center with |{v _i , v _j }| ≤ r (line 2). The customer pairs are then sorted according to the increasing distance |{v _i , v _j }| (line 3) and considered by the algorithm following this order (line 4). If the customers v _i and v _j of such a pair are both terminal vertices of two different clusters, the two clusters are connected by the edge {v _i , v _j } (lines 5 and 6). Subsequently, the validity of the newly generated cluster is checked. An order cluster is valid if the customers of a cluster can take delivery from the same delivery vehicle within the given time windows. If the cluster is valid, it (the sequence of customers) is stored (lines 7 and 8) and the edge is added to the graph G (line 9).

The test of whether a given sequence of customers can be supplied with goods without violating the customers’ time windows, is illustrated in Fig. 9. The cluster of delivery orders awaiting validation where each customer has to take delivery within a specific time window is depicted in Fig. 9a. Starting with customer 2, the customer’s time window is shifted by adding the service time at customer 2 and the driving time to customer 3 (see Fig. 9c). If the resulting time window of arrival intersects with the given time window of customer 3, customer 3 can take delivery without violating his time window. In the next step, the intersection of the arrival time window and the time window of customer 3 is shifted by the service time at customer 3 and the driving time to customer 1. This process is continued until the last customer is reached. If the time window of the last customer intersects with the last arrival time window, the cluster of delivery orders being tested is valid. If at least one time window is violated, the validation mechanism tests the reverse customer sequence. If that test fails too, the merger of the two different clusters is canceled.

Fig. 9

Validation of the order cluster

After the generation of delivery order clusters, each ComEx client has to determine which clusters are likely to be cost intensive and can therefore be outsourced to another ComEx client in order to reduce the delivery costs. Since it is assumed that delivery orders of customers located far away from the the profit center can only be delivered at high cost, the average distance from each cluster to the location of the profit center is calculated. The parameter a (0 < a ≤ 1), introduced in Sect. 3.2, is used to define the percentage share of clusters that should be outsourced to another profit center. Finally, each ComEx client sends the information about the outsourcing candidates to the ComEx server. In return, the ComEx server sends back the list of all order clusters that the ComEx clients have been designated to be outsourced.

Bid Formation and Insourcing: Given the set C* of all order clusters designated by the ComEx clients for outsourcing, each ComEx client can bid on any non-empty cluster combination $B \subseteq C^*$ and thus generate combinatorial bids (B _i , p _i ), where p _i represents the bid price for cluster bundle B _i . The generation of cluster bundles uses the clustering mechanism described above. The mechanism aims at connecting clusters together while respecting the maximum distance r between two neighboring customers within the combined cluster and the given time windows of the customers.

In order to determine the bid price p _i for cluster bundle $B_i \subseteq C^*,$ a request is sent to the DynaRoute server to calculate the delivery costs for fulfilling the delivery orders contained in the order cluster bundle. At this point, we will not discuss the game theory implications concerning truthful bidding and incentive compatibility, because the delivery costs that provide the basis for the formation of the bid prices in each profit center are calculated solely by the DynaRoute server and are therefore difficult to manipulate (Schwind 2005). Figure 10 illustrates three ComEx clients generating combinatorial bids (B _i , p _i ) with bid prices p _i (represented by squares) for cluster bundle B _i (represented by ovals) and send them to the ComEx server.

Fig. 10

Generation of combinatorial bids

The ComEx system provides a graphical user interface (GUI) for the ComEx client (see Fig. 11) to support the profit centers in administering each of the customer delivery orders associated with the coordinates and the time window of the customer, the service time at the customer, and a specific ID. As some delivery orders have the potential to create a high turnover for a profit center, the profit centers are able to exclude delivery orders from the exchange process. Such orders are then not regarded in the outsourcing process. After initiating the route optimization process, the results of the particular optimization steps are visualized in the GUI (e.g. the outsourced delivery orders, the bid prices for the insourcing candidates, and the delivery orders taken over from other profit centers). After the optimization process, the ComEx system indicates the costs saved in the entire logistics company by employing the combinatorial exchange process. Based on the result of the optimal allocation of delivery orders to the ComEx clients, the delivery routes are optimized by the DynaRoute server and visualized on a map.

Fig. 11

Graphical user interface for the ComEx client application

4.3 ComEx server

The ComEx server application is implemented as a servlet responsible for controlling the entire auction process by distributing the information about the order clusters determined by the ComEx clients to be outsourced and by receiving and collecting the combinatorial bids sent by the ComEx clients via web-based requests. The information interchange between the clients and the server is performed using SOAP messages that are digitally signed and encrypted to ensure their integrity and to prevent unauthorized viewing and modification of the SOAP messages.

After receiving the bids from the clients, the ComEx server forwards them to the ComEx engine that calculates the optimal allocation of order clusters to the profit centers by solving the ${{\mathcal{NP}}}$-complete combinatorial auction problem (CAP) (Vries and Vohra 2001). The result is then reported to the ComEx clients. Finally, the ComEx server accumulates the profit centers’ delivery costs prior to the auction and the delivery costs after the auction in order to determine the cost savings for the entire logistics company and hence the economic effectiveness of the combinatorial exchange.

4.4 ComEx engine

The ComEx engine receives the combinatorial bids (B _i , p _i ) from the ComEx server and determines the optimal allocation by solving the CAP.

Let z be the to-be-minimized delivery costs, C* with |C*| = n the set of order clusters the bidders j ∈ M, |M| = m, can bid on. C _k  ∈ C*, 1 ≤ k ≤ n, represents a single cluster whereas $B_i \subseteq C^*,$ 1 ≤ i ≤ 2ⁿ − 1, denotes a non-empty cluster bundle.

Furthermore, p _ij is used as the bid price of bidder j ∈ M for cluster bundle B _i and x _ij  ∈ {0,1} indicates whether cluster bundle B _i is allocated to bidder j (x _ij = 1) or not (x _ij = 0).

The CAP can be formulated as the following linear program:

$$ z = \hbox{min} \sum^{m}_{j=1}\; {\sum^{2^{n}-1}_{i=1}{ p_{ij}\;x_{ij}}} $$

(1)

$$ \sum^{m}_{j=1}\; \sum_{\mathop{B_i \subseteq C^*}\limits_{B_i \ni C_k}} x_{ij} = 1,\; \forall C_{k} \in C^* $$

(2)

$$ x_{ij} \in \{0,1\} $$

(3)

Equation 1 is responsible for the determination of the optimal allocation whereas Eq. 2 ensures that each cluster is allocated to exactly one ComEx client.

In the ComEx system, the open source software package LP_SOLVE 5.5 is used to solve the CAP. The package can provide an exact solution of the ${{\mathcal{NP}}}$-complete problem for up to hundreds of bids within acceptable computation time. For greater problem complexity, the use of heuristics is recommended (Schwind et al. 2003).

5 Improvement of the ComEx mechanism

The application of our system to a medium-sized logistics company has revealed three shortcomings in the ComEx mechanism.

The first problem arises with the calculation of bid prices for the clusters exchanged during the in- and outsourcing phase. As described in Sect. 4, the DynaRoute software is used to determine the cost of in- and outsourcing for a cluster of delivery orders. Because the cost calculation may be very time consuming for complex routes with many delivery orders included³, DynaRoute is the bottleneck in the entire optimization process. In order to make the system faster we introduce a bid formation process that uses the distance-based estimation of delivery costs to circumvent the time consuming route calculation process for each cluster. It turns out that the loss of accuracy in the pricing of the clusters does not have a significant impact on the cost reduction of the ComEx exchange process (Gujo and Schwind 2007).

The second problem of the ComEx system that turns out to be of a practical relevance is also related to the performance improvement of the in- and outsourcing process. In order to reduce the number of bids in the bid formation process, we defined a circular area around the profit centers. As described in Sect. 3.2, customers in this area are not fed into the outsourcing process, but retained by the profit center. However, frequently the circular boundary of the outsourcing area is not the appropriate shape to guarantee the optimal selection of outsourcing candidates for the customer delivery orders of a profit center. In order to solve this problem, we introduce a convex hull mechanism that dynamically calculates the appropriate delivery areas of the profit centers.

The third problem that has been identified in the application phase of the ComEx system is related to the selection of bid combinations in the clustering process. Because we do not consider all 2ⁿ−1 possible bids in the combinatorial auction process, there may be synergies that are not exploited by the exchange mechanism. Introducing an iterative auction coupled with the determination of the convex hull provides the possibility of finding undiscovered synergies between delivery orders.

In the following we describe the three improvements of the ComEx mechanism in detail.

5.1 Distance-based bid formation

As already mentioned, the calculation of bid prices is performed by the DynaRoute server that calculates the delivery costs for each cluster bundle by solving a route optimization problem. Since the route optimization is very time consuming, a distance-based strategy has been implemented for the insourcing phase in order to gain a massive reduction in the computing time. It is assumed that the distance between a customer and the profit center is positively correlated with the delivery costs. Therefore, in the distance-based strategy, the average distances between the location of the profit center and the cluster bundles the profit centers can bid on are calculated and used as the bid price. Let v ₁,..., v _n  ∈ B _j be the customers of a cluster bundle $B_j \subseteq C^*$ and d _i be the distance between customer v _i and the location of the profit center. Then, the average distance $\widetilde{d}_{j}$ between a cluster bundle B _j and the profit center is defined as follows:

$$ \widetilde{d}_{j} = {\frac{\sum^{n}_{i=1}{d_i}}{n}} $$

(4)

Clearly, the calculation of the average distances is not very time consuming so that the entire exchange process can be accelerated by performing the distance-based strategy. Finally, the ComEx engine strives to minimize the total distance between the order clusters and the profit centers instead of the delivery costs.

5.2 Convex hull mechanism

Another way of reducing the computing time of the entire exchange process is to reduce the number of bids, which can be achieved by limiting the number of order clusters the profit centers can bid on. To do this, each profit center identifies its delivery area by performing a convex hull mechanism. Thereafter, each profit center can only bid on the order clusters whose customers are located in the delivery area or with a maximum distance of Δ kilometers outside of the delivery area. Figure 12 shows the principle of the convex hull mechanism.

Fig. 12

Determination of the delivery area and the extended delivery area

Based on the coordinates of the profit center’s initial customers, the convex hull (representing the delivery area) is determined (see Fig. 12a, area surrounded by dotted lines). Given the vertices’ coordinates and the distance Δ, the convex hull is extended to the extended delivery area as depicted in Fig. 12b (area surrounded by solid lines). Finally, profit center A can only bid on order clusters with at least one customer located in the extended delivery area, namely clusters C ₁, C ₂, C ₃, and C ₄.

Given that for two similar triangles (angles of the first triangle are equal to the angles of the second triangle) the corresponding sides are in the same ratio, the following equations are used for the determination of the extended delivery area (cp. Fig. 13):

$$ {\frac{\Updelta_{x}}{d_x}} = {\frac{d + \Updelta}{d}} $$

(5)

$$ {\frac{\Updelta_{y}}{d_y}} = {\frac{d + \Updelta}{d}} $$

(6)

Taking these equations into account, the vertices of the extended delivery area can be derived from the vertices of the delivery area as follows:

$$ x_{\rm new} = d_{x} \cdot \left(1 + {\frac{\Updelta}{d}}\right) + x_{\rm depot} $$

(7)

$$ y_{\rm new} = d_{y} \cdot \left(1 + {\frac{\Updelta}{d}}\right) + y_{\rm depot} $$

(8)

Fig. 13

Determination of vertices of the extended delivery area

5.3 Iterative auction mechanism

The aim of the iterative auction mechanism is to reduce the delivery costs of the entire logistics company step by step. To do so, the delivery costs z _i of the entire company are determined after each auction round i and compared to the costs z _i-1 in the previous round. This ComEx exchange process is repeated as long as a cost reduction can be achieved, i.e., as long as z _i < z _i-1. After each round, the allocation of delivery orders to the profit centers determined by the ComEx engine is used as the initial allocation of delivery orders for the next round. The according pseudo-code algorithm is depicted in Fig. 14.

Fig. 14

Pseudo-code of the iterative auction algorithm

First, the initial delivery costs z ₀ of the entire logistics company are calculated by summing up the delivery costs of the profit centers taking part in the exchange process (line 2). After performing the combinatorial exchange and solving the CAP (line 3), the total delivery costs are determined (line 4). If a cost reduction could have been realized, the order allocation is used in order to perform a new round (i.e., a combinatorial exchange). This process is repeated until no cost reduction for the entire company can be realized (lines 5 to 8). Finally, the minimum delivery costs are compared to the initial delivery costs z ₀ in order to measure the effectiveness of the iterative auction process.

6 Simulation results

In this section, we present the results of a simulation study which was performed using the real-world transportation data of a medium-sized company in order to demonstrate the cost reduction potential of the three mechanism improvements of ComEx proposed in the previous section.

Four types of simulation runs were performed in order to evaluate the effect of the mechanism improvements. We use the following acronyms to denote these auction variants in the remainder of this article:

• OneRound: denotes the application of a one round combinatorial auction in the ComEx system using the distance-based strategy for the clustering process as it is described in Sect. 5.1.

• MultiRound: denotes an iterative combinatorial auction as it is described in Sect. 5.3. The auction uses exactly the same settings as in the one round case, however the entire ComEx process is repeated until no further cost cutting is achieved in the following auction round.

• OneRoundHull: this mechanism is identical to the one round combinatorial auction but uses the convex hull approach described in Sect. 5.2 in order to determine the optimal delivery areas for the profit centers.

• MultiRoundHull: this auction type uses the multi round combinatorial auction and additionally integrates the convex hull approach, which means that in each round of the iterative auction the delivery areas of profit centers are recalculated according to the convex hull mechanism.

Table 1 shows the simulation results for the four auction types. The values denote the cost reduction potential of the improved ComEx mechanism, using distance-based clustering, in relation to the average delivery cost achieved with the original ComEx approach using DynaRoute-based cost calculation for bid pricing. For each value in Table 1 the results of 20 simulation runs have been averaged in order to eliminate stochastic fluctuation. Simulation parameter a (the share of order clusters to be outsourced to another profit center) was varied from 0.2 to 1.0 in steps of 0.2. Additionally, the maximum distance r between two customers within a cluster in the clustering process was varied from 2 to 20 km in steps of 6 km.

Table 1 Cost savings of the improved ComEx mechanism compared with the DynaRoute-based mechanism

For a convenient visualization of the cost reduction potential of the four auction types, we present Fig. 15 that depicts the performance of the MultiRound, the OneRoundHull, and the MultiRoundHull auction relative to the performance of the OneRound auction using the values given in Table 1.

Fig. 15

Cost savings achieved with the different auction types relative to the performance of the plain single round auction

As can be seen in Fig. 15, multi-round strategies (MultiRound and MultiRoundHull) are all able to achieve higher cost savings compared with one round strategies, OneRound and OneRoundHull. Especially for a smaller share a (a < 0.6), the iterative auction outperforms the single round auctions significantly. This is because the iterative auction provides the best improvement potential if the initial outsourcing areas are small and can be expanded systematically after each round. Higher maximum distances r < 8 km allowed between the customers within clusters generally lead to a better performance of the iterative auction mechanisms. This is because an increasing r increases the complexity of bids in the clustering process and with it the ability of the ComEx system to express synergy effects. Iterative auction mechanisms enable better exploitation of these effects.

For the convex hull mechanism both types of strategy (single round and iterative) yield fewer cost savings than the auctions that do not make use of the convex hull mechanism. However, if we consider bids with greater distance r between the customers of a clusters created (r = 14 to 20 km), the performance of the multi round convex hull mechanism is comparable or even better than that of all alternative approaches.

The left hand graphic in Fig. 16 shows the absolute difference in number of bids submitted to the ComEx auction using the simple multi-round mechanism (MultiRound) compared with the multi-round auction using the convex hull approach (MultiRoundHull). The right hand graphic shows the reduction of bids when using the convex hull approach, relative to the total number of bids submitted. The convex hull approach helps to reduce the number of bids submitted to the ComEx auction by up to 50%. This significantly reduces the problem of complexity that must be dealt with during the winner determination process. This is a valuable property of the convex hull approach, especially when the ComEx system has to deal with large-scale, real-world problems. Figure 16 also shows that the greatest reductions can be achieved with small maximum distance r between customers within a cluster (r = 2 km) combined with a higher share a of customers released to the outsourcing process (a = 1). This can be explained by the fact that these parameter settings produce a high number of delivery orders being submitted to the outsourcing process in succession.

Fig. 16

Bid reduction using the convex hull mechanism compared with the simple iterative auction (absolute values on the left side and percentage on the right side)

Thus, the advantages of the MultiRoundHull auction process are illustrated. Together with a cost saving performance comparable to the plain iterative auction, the iterative convex hull approach reduces the problem complexity by 50% in the best case. This makes the MultiRoundHull mechanism the most efficient approach for increasing the performance of our ComEx system.

7 Conclusion

We presented a client-server system ComEx for the auction-based exchange of transportation services which is used in conjunction with the tour optimization system DynaRoute. Our approach focuses on the search for an optimal mechanism that supports system users in the formation of the appropriate in- and outsourcing bids for the exchange of delivery orders between neighboring profit centers, such that a significant reduction of transportation costs results for the entire logistics company. To further enhance the performance of the ComEx system, we introduced three improvements to the bid formation and exchange process. The first measure is to simplify the delivery cost calculation in the bid formation process using a distance-based cost estimator. The second measure is to introduce a convex hull mechanism in order to determine the optimal selection of in- and outsourcing candidates. The third measure concerns the auction itself. By introducing an iterative mechanism we allow the ComEx system to compensate for loss of effectiveness caused by the reduction of bids.

Using the real-world delivery data of a medium-sized logistics company, we were able to show that our system can reduce the delivery cost in the entire company by a maximum of 14%. Additionally, we demonstrated that the system’s performance can be further improved using the three improvement measures: distance-based cost estimation, iterative auction mechanism, and convex hull approach. The convex hull approach combined with the iterative auction mechanism reduces both complexity and costs sufficiently for this approach to be a good candidate for a widespread industrial application.

One such question worth thinking about would be the application to the ComEx system in the inter-enterprise sector, e.g., as a general combinatorial freight exchange. Such a realization of a logistics marketplace, however, raises questions about an incentive-compatible method for evaluating the bids, for example the Vickrey–Clarke–Groves mechanism. A fair and incentive-compatible distribution of the cost savings between the profit centers, the implementation of a general exchange for logistic services in cooperation with a major logistic provider, and the improvement of the clustering and pricing mechanism, will be the next topics for our research.