1 Introduction

Transportation spot markets have become popular platforms where shippers and carriers meet and sign short-term transportation contracts in a quick and cost-efficient manner. In these spot markets, shippers list their shipment requests, and carriers submit quotes on the requests they are interested in. This process is effectively a reverse auction mechanism [6], where the carrier quotes are essentially bids on the shipment requests. Spot procurement auctions pose significant challenges for the participating carriers, who must make decisions intelligently to prosper in this dynamic and competitive environment. Selecting the requests to bid on, and determining the bid prices are two of the most important challenges for the carriers in such auctions. A carrier’s bid on a request should be low enough to win but high enough for the carrier to be profitable. The carrier may submit a very high bid if the request is not very attractive.

A carrier that actively pursues customers in spot procurement markets is likely to participate in multiple auctions simultaneously. If the carrier is not careful, it may end up with a set of requests which do not form a good combination. This situation is known as the exposure problem in the auction theory literature (see Bykowsky et al. [11]; Kwasnica et al. [11]). Although, combinatorial auctions (CAs) can alleviate the exposure problem for carriers [11], they are not commonly used in transportation spot markets as each shipper is most likely to list a single request at a time. Since the outcome of each auction is uncertain, the carrier is faced with a pricing problem in a highly competitive environment.

Kuyzu et al. [7] are the first to study the bid determination problem for multiple independent simultaneous sealed-bid first-price single-request truckload (TL) transportation auctions in spot procurement markets. They formulate a stochastic bid price optimization model with the objective of maximizing total expected profit, and show that the objective function is non-concave in general. They propose to use historical data to predict the probability distribution of the winning bid. The formulation of the model involves determining the cost of serving each subset of requests, which entails solving an exponential number of NP-hard routing problems, even for just calculating the objective value. They use a coordinate search heuristic to obtain good solutions to the model efficiently. However, since the heuristic works on the formulated model, which requires the cost of serving all possible subsets, applying the overall method requires significant computational effort when a large number of auctions are involved.

The distinctive aspects and literature contributions of our study can be summarized as follows:

  • We develop a bidding heuristic for carriers participating in simultaneous independent TL transportation auctions. The proposed heuristic uses synergy between a carrier’s existing lanes and auction requests, estimated through a computationally efficient procedure.

  • Compared to previous studies the proposed heuristic requires neither the probability distribution of the winning bid (as in Kuyzu et al. [7]) nor the cost of serving every possible subset of requests the carrier is competing for (as in Kuyzu et al. [7] and Olcaytu and Kuyzu [10]).

  • Our computational experiments show that the approach performs comparable to studies of Kuyzu et al. [7] and Olcaytu and Kuyzu [10] in terms of carrier profitability with much less computational effort.

The rest of the paper is organized as follows. In Sect. 2, we review the related literature. In Sect. 3, we describe the proposed bidding heuristic. In Sect. 4, we present the results of our computational experiments involving a simulated marketplace. Finally, we present concluding remarks in Sect. 5.

2 Related literature

In this section, we will only discuss existing literature on bid determination methods for TL carriers, which can be classified into three main categories by the type of auction environment involved: combinatorial bidding, sequential bidding, and simultaneous bidding. The common goal is maximizing profit by submitting the most competitive bids for the right auctions. It is critical for the carriers to utilize capacity efficiently. In the case of TL carriers, this translates into minimizing empty repositioning distance of vehicles.

In CAs, the aim of the carrier is to select the best bundles and the associated prices to maximize its profit. There are studies in the literature that focus on various aspects of CAs from the carriers’ perspective, such as identifying possible bundles, calculating the cost of serving the bundles, and determining the bid prices on the bundles, with the goal of minimizing empty repositioning and maximizing profitability. Song and Regan [12], An et al. [1], Lee et al. [8], Chang [2], Mesa and Ukkusuri [9], and Triki [13] present bundle synergy approaches to minimize deadhead mileage and maximize carrier profitability.

Sequential auctions differ from CAs. A sequential auction is an auction where various items are sold one after another. The implementation of sequential auction is simpler and more widespread in practice. However, bidders should make strategic decisions for subsequent auctions. Figliozzi et al. [4] study sequential auctions for TL service procurement in spot markets. Figliozzi et al. [5] use a simulation framework to evaluate opportunity costs in sequential TL transportation auctions.

When spot transportation procurement markets are examined, it is seen that they commonly constitute a set of sealed-bid first-price single lane auctions that are run simultaneously and independently. In the literature, there exist very few studies on TL carriers’ bidding strategies in independent simultaneous transportation procurement auctions. Kuyzu et al. [7] are the first to study the problem. They formulate a stochastic bid price optimization model with the objective of maximizing a TL carrier’s expected profit. The model requires the probability distribution of the winning bid for each auction request, and the evaluation of the synergy of every possible subset of auction request with each other and the pre-existing lanes of the carrier. They use a coordinate search heuristic to obtain a good solution to the model. Since synergy evaluation for a subset of auction requests entails solving an NP-Hard optimization problem on them, even setting up the model requires significant computational effort. Olcaytu and Kuyzu [10] propose a synergy-based method which calculates the per kilometer cost of every possible subset of auction requests, and use these values to calculate the carrier’s bid prices without using any probability distribution. In both Kuyzu et al. [7] and Olcaytu and Kuyzu [10], the proposed method determines bids for all auction requests, without any preliminary filtering.

In this paper, we extend the works of Kuyzu et al. [7] and Olcaytu and Kuyzu [10] by developing an efficient bidding heuristic, which identifies the auction requests to be bid on and their bids by evaluating only a very small subset of the selected auction requests. The efficiency of this heuristic makes it suitable for determining bids for a high number of auctions in a short period of time.

3 Methodology

In this paper, we propose a heuristic for the bid price optimization problem for a TL carrier participating in multiple independent simultaneous sealed-bid first-price transportation procurement auctions for complementing its existing lanes with requests from a logistics spot market. In the problem setting we consider, multiple single-request auctions with common bidding deadlines are announced at the same time. Each auction request is a single TL move, which must be transported by a single truck directly between its origin and destination. The carrier and its competitors place bids on the requests in their respective interests. Submitting bundle bids is not possible. The carriers cannot change their bids, either. All of the auctions close at the same time. Each request is awarded to the lowest bidding carrier, which receives a revenue equal to its bid on the request. Each carrier routes its own or contracted vehicles to determine the cost of serving the requests it won in the auctions.

Our bidding heuristic is based on the marginal contribution of each auctioned request to a limited number of subsets. As in Kuyzu et al. [7], we assume that the carrier must solve a lane constrained lane covering problem (LCLCP) to determine the cost of serving any subset of requests and it can always find a feasible solution for any combination of requests it may be awarded. The LCLCP is an NP-hard problem where the lanes of a carrier must be covered by cycles such that the length of each cycle used in the cover cannot exceed a predefined upper bound [3]. We apply the greedy merge heuristic proposed in Ergun et al. [3] to estimate the costs of serving subsets of requests and the marginal costs of requests. In the rest of the paper, we will refer to the auction requests as auction lane for ease of writing.

The notation we use in this study is as follows:

  • L : Set of lanes being auctioned.

  • \(L_0\) : Carrier’s existing lanes.

  • \(b_l\) : Bid price of auction lane \(l~(\forall l \in L)\).

  • \(d_l\) : Length of auction lane \(l~(\forall l \in L)\).

  • \(MC_S\) : Marginal cost of auction lane set \(S~(S \subseteq L)\).

The steps of our proposed bidding approach are presented in Algorithm 1. The algorithm uses marginal cost comparisons to determine the carrier’s bid prices. In order to avoid unnecessary calculations, the algorithm makes the comparison order wisely.

Between lines 2 through 8, the algorithm computes the marginal cost of each auction lane by adding the auction lane to the carrier’s existing lanes. The function F(S) calculates the cost of the LCLCP solution using the greedy merge heuristic on the lane set S. If the marginal cost of lane l, i.e. \(MC_{\{ l \}}\), is greater than twice the length of lane l, then the carrier’s bid price for that lane is set to twice the length of the lane, i.e. \(2d_l\). Such auction lanes are removed from set S. In other words, the cost of adding the auction lane to the carrier’s existing network is greater than that of creating a new cycle to serve only that lane.

Between lines 12 through 16, the marginal cost of each pair of auction lanes remaining in S is calculated, and the bid price for each lane in S is set to the maximum marginal cost among the pairs including that lane. The algorithm avoids redundant marginal cost calculations.

figure a

The proposed approach by Kuyzu et al. [7] requires \(2^{|L|}\) marginal cost calculations, complex computations and historical data. Likewise, the synergy-based bidding method by Olcaytu and Kuyzu [10] requires \(2^{|L|}\) marginal cost calculations to obtain all possible outcomes of the auctions. Whereas our algorithm requires at most \(\left( {\begin{array}{c}|L|\\ 2\end{array}}\right) = \frac{|L|(|L|-1)}{2}\) cost calculations. All of the aforementioned approaches use the function \(F(\cdot )\) for calculating the cost serving subsets of lanes. The computational effort required for computing all possible subsets increases drastically as the number of auction lanes increase which makes it impractical for moderate and large instances. Computational experiments, presented in the next section, show that our proposed algorithm performs comparable to that of Kuyzu et al. [7] with much less computation effort.

4 Computational studies

We evaluate the impact of using our proposed heuristic on carrier profitability with the help of a simulated marketplace, which was created with the same parameter settings in the study of Kuyzu et al. [7]. We run several simulations with a high number of replications under different parameter configurations. The simulated market area is 1500 km x 1500 km and divided into nine equal size square regions. For each square region 100 random origin-destination (o-d) points are generated in the beginning of each replication.

The marketplace includes seven carriers with each one having a pre-defined size: small, medium, or large. A small-size carrier has 30 existing lanes, corresponding to long term commitments, the o-d pairs of which are chosen randomly from 3 randomly selected adjacent regions. Similarly, a medium size carrier has 60 existing lanes from 4 adjacent regions, while a large size carrier has 90 existing lanes from 5 adjacent regions.

In each simulation run, we generate a carrier which determines its bids using the heuristic approach described in Sect. 3. We refer to this carrier as Smart. We generate six competitors, each of which compute the individual marginal cost of each auction lane with respect to its set of existing lanes and applies a fixed markup (MU) to determine its final bid on each auction lane. The competitors consist of two small size carriers (SC1, SC2), two medium size carriers (MC1, MC2), and two large size carriers (LC1, LC2). To calculate the cost of adding auction lane to existing lane network greedy merge heuristic is used both for Smart and the competitive carriers.

We vary the size of Smart and the MU values of the competitors between different simulation runs. Smart has either of 30, 60 and 90 lanes. The MU value of the competitors is either of 0.10, 0.15, 0.20, 0.30, or 0.40. All competitors use the same MU during a simulation run. combining each possible network size for Smart with each competitor MU value, a total of 15 simulations are run.

One hundred replications are done for each parameter set. The sets of existing lanes of all the carriers are randomly determined for each replication, each of which consists of 52 periods. Ten randomly generated lanes are auctioned in each period. At the beginning of each period, every carrier offers a price for the auction lane, and it is assumed that the carriers do not have a fleet size limitation to serve these lanes. We assume that one period is equal to one week. We assume that a truck can travel 720 km, hence each truck route can be at most 5040 km.

The results of each simulation run are obtained by taking the average of the replications. We report three types of statistics: unit profit, total profit, and number of auctions won. Total profit is the difference between total revenue earned from the auctions won and the sum of the costs of adding them to the carrier’s existing lane network. Total profit is equal to total profit divided by the total length of auctions won. Unit profits are presented in Table 1, total profits are presented in Table 2, and number of auctions won are presented in Table 3. When the obtained values are examined, it is observed that when the competitors’ MU values increase, their total profits increase, as expected. Both Smart and competitive carriers have greater profits when they have large size existing lane network. When carriers have a larger existing lane network, the auction lane is expected to be more likely to be added with less marginal cost, in other words with lower empty travel. It is observed that Smart obtains greater total profits regardless of the sizes of the competitive carriers and MU values.

Table 1 Unit profits
Full size table
Table 2 Total profits
Full size table
Table 3 Number of auctions won
Full size table

For the auction setting we are considering in this paper, Kuyzu et al. [7] propose a stochastic bid price optimization model with the objective of maximizing the carrier’s expected profit combined with a coordinate search algorithm. Their approach requires the cost of adding each subset of the auction lanes to the carrier’s existing lane networks, which entails computing F(S) on each possible \(S \subseteq L\) with the help of a greedy heuristic. We use exactly the same parameter sets to see the effectiveness of our heuristic and use their results as a benchmark. The reader is referred to their work for more detailed information on their approach.

Comparison of the performance of the optimization method of Kuyzu et al. [7] (KM) and synergy-based bidding method of Olcaytu and Kuyzu [10] (OM) with that of our proposed heuristic (Smart) is presented in Table 4. It is observed that total profits are close to KM while the number of auctions won is higher and greater than OM. When the obtained total profits are examined, it can be noticed that the proposed synergy-based method not only makes much more profit than the competitor carriers but also achieves close results to those of KM and better results of OM.

Table 4 Comparisons of KM, OM and Smart carrier’s results
Full size table

The simulation is implemented on a desktop PC with a configuration of Intel(R) Core(TM) i7-4790 Opteron Processor and 16 GB RAM with Java(TM) programming language. The average running times of each replication of the simulations with KM and our heuristic are presented in Table 5. Considering the running times, Smart’s solution times are observed to increase in direct proportion to the existing lane sizes as expected. Considering the total profits and the running times, we observe that the proposed heuristic is an efficient method.

Table 5 Average running time per replication (in milliseconds)
Full size table

Our synergy-based bidding heuristic method yields solution much faster than KM and OM on average. Moreover, our computational study demonstrates that the heuristic method is evaluated to be efficient in that it doesn’t require historical data and complex computations, and also avoids carrier from possible financial loss.

5 Conclusions

In this study, we develop an efficient heuristic to generate carrier’s bids in multiple independent sealed-bid first-price procurement auctions simultaneously. To present the effectiveness of the developed heuristic, we simulate a competitive auction-based transportation marketplace. Analysis of the simulation results show that the proposed heuristic is effective and easy to implement without the need for complex computations and historical data.

Today, with many developments in the global sense, the importance of the transportation sector is increasing with globalization. The rapid pace of technological developments and the increasing use of electronic marketplaces for transportation procurement are causing the bidding time intervals to become much shorter. Hence, the carriers need to determine bid prices much more rapidly. We observe that bidding strategies for carriers participating multiple transportation auctions simultaneously are still largely unexplored. This study constitutes an important contribution to the literature.