# Transportation Service Procurement Bid Construction Problem from Less Than Truckload Perspective

Authors: Fang Yan; Yanfang Ma; Manjing Xu; Xianlong Ge
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

This paper presents mixed integer programming for a transportation service procurement bid construction problem from a less than full truckload perspective, in which the bidders (carriers) generate their best bid (package) using a bundled price to maximize their utility and increase the chance of winning the business. The models are developed from both the carriers and shippers perspectives to establish a relationship between the quoted price and the likelihood of winning to assist the carriers in balancing the potential benefits and the possibility of winning the bid. An intelligent algorithm based on Particle Swarm Optimization is then designed to solve the proposed model and hypothetical data sets are used to test the effectiveness and efficiency of the proposed model and algorithm.


---

## Body

## 1. Introduction

Combinatorial auctions (CA), which allow bidders to submit bids on a combination of products or services, can generate greater profits [1, 2]. Therefore, for transportation service procurement, CA has attracted increasing attention because of the synergies available on the transportation pathways [3–7] as it allows carriers to submit bids to the shipper for the transportation loads they prefer which are grouped into packages or bundles of loads of various products [8, 9]. Generally, there are three CA stages needed for transportation service procurement. First, the auctioneer (on behalf of the buyer) announces the multiple loads available for bidding (henceforth, bid loads) at the auction. Second, the bidders (here, the carriers) submit bids for sets of bid loads (or bundles), rather than bidding on each bid load individually. Third, the auctioneer determines the best set of bundles that collectively contain each bid load exactly once and awards contracts for these bundles (rather than awarding individual bid loads) to the corresponding bidders [10]. These three stages are known as a Shipper Lane Selection Problem (SLSP) [11, 12], bid generation problem (BGP) [7], and a Winner Determination Problem (WDP) [13, 14], in which the BGP is the main focus in this paper.BGP is a complex challenge for bidders as it is necessary to evaluate an exponential number of potential bundles that represent all possible subsets of the auctioned loads [8]. For example, if there are n loads posted, each carrier can theoretically submit up to 2n-1 different combinations to the auctioneer; therefore, this is highlighted as a NP-hard problem [15, 16]. Most studies researched BGP from truckload perspective, while in fact if permitted, less than truckload procurement could bring more benefits for both shipper and carriers. Carriers could make full use of not only their existing network (as concerned from truckload perspective) but also their capacities, which means the empty load rate and the loading rate could be optimized simultaneously. However, to date, there has been little research that has specifically focused on this type of bid generation problem.Apart from the lanes combinations, the bidding price is another issue that must be considered by the carriers for higher price may bring more benefits but also increase the chance of losing business [8, 17]. Hence, the likelihood of winning business is taken into account in this paper. This paper considers bundled lane selections with the prices set from the carrier’s perspective for this transportation service procurement. The shipper has some new transportation loads that need to be serviced and the carrier has their own transportation networks and the ability to undertake additional loads. The problem focus is how to give the carrier the ability to choose loads on different lanes to maximize their utility revenue minus costs. It is obvious that while higher prices could generate higher revenue, this could also lead to the business failure and that while lower prices could increase the likelihood of winning business, this could lead to a loss of potential profits. Therefore, this paper seeks to establish stochastic mixed integer programming to allow for the proper bundle of loads to be chosen based on price, which could improve the likelihood that carriers can earn their maximum utility. Although the model is proposed based on previous research [1, 8, 18], the highlights can be summarized as follows:(i)
It considers less than truckload freight transportation service procurement and depicts the variable costs based on the truck’s true load.(ii)
It considers that the likelihood of winning the business has been rarely examined in previous research [8, 17]; in this paper, we describe the likelihood using a function related to the service price of the bundled lanes.(iii)
It considers the bundle price to be a decision variable rather than a parameter equal to the sum of the prices on each lane [1].(iv)
It considers the space-time network [18], which is more difficult than common transportation networks.The remainder of this paper is organized as follows: Section2 gives a scientific literature review. Section 3 describes the problem under study. Section 4 establishes the stochastic mixed integer programming to allow for the proper load bundle and prices to be chosen to give carriers a higher likelihood of earning maximum utility. Section 5 proposes the solution approach to solve the proposed model and Section 6 uses hypothetical data sets to test the proposed model and algorithm. Section 7 summarizes the main findings and suggests extensions to this research.


## 2. Literature Review

There are some researches studying BGP from different point of views. Crainic and Gendreau [19] claimed that carriers need to analyze the complex available market information and combine it with their own fleet and personnel management to determine the most profitable bid strategies. To do this, “advisors” are needed to assist the carriers in making their decisions by efficiently combining market information, planning, and the operating procedures to evaluate the best load selection [20, 21]. Caplice and Sheffi [22] proposed an approach that allowed both the shipper and carriers to benefit using a collaborative approach to secure and manage their strategic relationship and argued that it was better to allow carriers to identify packages based on their own individual perspectives and networks as the shippers’ specified package results were often less successful for the available carrier transportation. For example, if there are n loads posted, each carrier can theoretically submit up to 2n-1 different combinations to the auctioneer; therefore, this is highlighted as a NP-hard problem [15, 16]. However, to date, there has been little research that has specifically focused on this type of bid generation problem.Some research into studying the BGP has established optimal models. Song and Regan [23] presented a CA for a truckload transportation procurement problem, which was the first carrier model to use an optimization-based approximation to determine the useful packages on the lanes that a carrier could bid for in the context of CA for truckload transportation procurement. Song and Regan [23] then modified the procedures to incorporate substitutable bids by creating an appropriate set cover model and bid augmentation method. In simulations to validate the model, it was found that carriers that employed the optimization model benefitted more than carriers that followed a simple bid selection strategy. Wang and Xia [24] clarified the bidder’s optimality criterion in a combinatorial bid and then studied a bundling method in which an OR bid language was used. Li et al. [25] studied the BGP for each carrier in CA and assumed that these carriers form an alliance which aims at maximizing the total profit so as to generate more profit for each carrier.There has also been research considering transportation procurement auctions from the truckload carrier’s perspective. Lee et al. [18] developed a utility maximization decision problem in which the carriers determined the best packages to bid for in a combinatorial auction and presented a column generation approach to solve the underlying nonlinear quadratic integer program. Chang [1] developed a bidding advisor to assist truckload (TL) carriers in overcoming the challenges in the one-shot combinatorial auctions. The bidding advisor integrated the load information in the e-marketplace with the carriers current fleet management plans and then chose the most suitable load bundles. The TL carriers bid generation and evaluation in the one-shot combinatorial auction were formulated as a synergistic minimum cost flow problem by estimating the average synergy values between the loads and using the proposed approximation and column generation approach to solve the specific network flow problem. Chen et al. [10] presented an approach to combinatorial auctions for truckload procurement that enabled the complete set of all possible bids to be implicitly considered without placing the corresponding burden of an exponential number of bids on either the bidders or the auctioneer and provided extensive computational results to demonstrate the tractability of the proposed approach. Ueasangkomsate and Lohatepanont [26] introduced a bidding strategy for carriers facing a hard valuation problem on all possible routes. A bid-to-cost ratio example was given for carriers surveyed in Thailand to demonstrate the bidding behavior for combinatorial freight procurement, which required the carriers to value the bid price for their desired packages that included transportation service patterns under different competitive environments. Triki et al. [8] dealt with the generation of load bundles to be submitted by carriers participating in combinatorial auctions for long-haul full truckload transportation services and developed a probabilistic optimization model that integrated the bid generation and pricing problems together with the carriers fleet routing. Two heuristic procedures are proposed to solve models with up to 400 auctioned loads. Kuyzu et al. [17] formulated a stochastic bid price optimization model aimed at maximizing the carriers expected profit which accounted for lane synergies and competing carriers bid patterns. An iterative coordinate search algorithm was then developed to find high quality solutions. Triki [7] developed an optimization approach based on the use of the location techniques by maximizing the synergy among the bundle’s auctioned loads from one side and between the auctioned and the preexisting loads from the other side.However, there has been little research focused on less than full truckload freight transportation. Mesa-Arango and Ukkusuri [27] provided some insights into the competitiveness and challenges associated with the development of consolidated bids (suitable for less than truckload operations). Consolidated bids were constructed using a multicommodity one-to-one pickup and delivery vehicle routing problem that was solved using a branch-and-price algorithm. A numerical experiment was presented to prove that the nonconsolidated bids were dominated by the consolidated bids, which implied that this type of operation can increase the carriers likelihood of winning the auctioned lanes, while increasing the profit margin over the truckload companies (nonconsolidated bids) and maintaining the benefits the shippers gained from such combinatorial auctions.Besides these studies, there have been numerous attempts to determine algorithms to solve this type of NP-hard problem [28]. Caplice [29] proposed some heuristic algorithms to assist carriers in generating open loop tours, closed loop tours, inbound/outbound reload packages, and short haul packages using expected savings based on historical load volumes. Tian et al. [30] formulated this problem as a linear integer programming model and proposed an iterative rounding heuristic algorithm that worked on a linear-relaxation of the integer programming model to solve it for moderate size instances. Ignatius et al. [14] proposed a multiobjective winner determination combinatorial auction mechanism for transportation carriers working on multiple transport lanes to allow for lane bundling as packet bids to the shippers ocean freight and allow the carriers to maximize their network of resources and pass on some of the cost savings to the shipper.It can be found from above literature review that although BGP has drawn many attentions in transportation field, few researches concern the likelihood of winning business by considering the shipper’s reaction from less than truckload perspective. This paper tries to enrich this problem based on the former research.


## 3. Problem Statement

The synergy between new lanes and carrier’s current network could be used in increasing the carrier’s profits with a little cost increasement, as seen in Figures1–3. Figure 1 gives a single period/single vehicle example; it can be found that adding some new lanes could increase the carrier’s profits by making full use of the vehicle and reduce the empty load rate. Figure 2 gives a single period/multivehicle example; it can be found that vehicle 2 could be idle if adding new land B → D to current network. Figures 3(a) and 3(b) give two multiperiod/multivehicle examples, which show the synergy between new lanes and current network. Hence, under their current transportation capabilities, carriers usually prefer to bid on profitable lanes [1]. However, as there are often multiple choices because different sets of different lanes generate different profits, the carriers have to select, bundle, and competitively price the profitable lanes to win the auctions (or business), which is known as a bid generation problem (BGP) or a bid construction problem (BCP). Therefore, there are three basic problems for the carriers: (1) how to choose the most profitable lanes from the potential choices; (2) how to determine the best service price to win the business; and (3) how to increase the likelihood of winning the business.Figure 1
The synergy between new lanes and current network (single period/single vehicle).Figure 2
The synergy between new lanes and current network (single period/multivehicle).Figure 3
The synergy between new lanes and current network (multiperiod/multivehicle) (a). The synergy between new lanes and current network (multiperiod/multivehicle) (b).
(a)
(b)There are more candidate choices when solving BGP from a less than truckload perspective; however, this makes the problem more complex, as seen in Figure4. Comparing with Figure 3(b), two more new transportation tasks are considered by the carrier, that is, A → B in period 1 and C → B in period 2, which are profitable for carrier because there exists a transportation task on them in current network but the trucks are not fully loaded. Obviously, the more candidate choices the carrier has, the more difficult the BGP is.Figure 4
The synergy between new lanes and current network (multiperiod/multivehicle) from less than truckload perspective.Different from previous BGP for less than truckload procurement, the problem considered in this paper has its own characteristics.(
1
) The transportation task is considered to be multiperiod, which is more difficult to solve than a single period transportation problem. When making plans, the carriers need to assign vehicles to the booked loads, move empty vehicles to other locations to pick up the booked or auctioned loads in the next period, or hold the loads at the same locations until they are needed in a subsequent period. Therefore, it is difficult to develop the transportation plan without considering the time variable.(
2
) The reactions of the shipper (or other competitors) are considered when determining the service price to ensure the basic (or certain) likelihood of winning the business. Obviously, even though the carriers desire to gain the highest price possible and to gain the greatest benefit, they need to also consider the shippers (or main competitors) decisions as these can affect the business results. In other words, as an auction price that is too high may lead to the failure, it is essential for the carriers to consider the actions of the shipper or competitors when quoting their prices. Therefore, it is necessary to determine the appropriate lane sets and the associated prices ensure satisfactory profits and a certain possibility of winning.(
3
) The bundle prices are treated as decision variables rather than calculating the sum of the prices for each lane.Figure1 illustrates the problem studied in this paper. Carriers need to consider how to make full use of the existing transportation network when they quote the lane bundles and associated prices. For example, they need to choose lanes that are included in the existing network or lanes that have empty moves or lanes that could link with the lanes in the existing network.


## 4. Modeling

In this section, the mathematical model for the above bid generation problem that includes all possible reactions from the shipper is described and built.


### 4.1. Assumptions and Notations

In this problem, each carrier has its own existing transportation network and has sufficient capacity to handle the bid [17]. The objective for the carrier is to maximize expected profit by providing transportation services on some lanes under consideration of their existing network and the shippers possible actions. In another words, the carrier seeks a reasonable price for the services provision they prefer to ensure maximum profits with a certain likelihood of acceptance by the shipper. Therefore, there are the following assumptions.(
1
) The carrier is permitted to submit a single optimal package S to the shipper and the shipper can buy the required services from the carrier or deal with them by itself.(
2
) The carrier has sufficient capacity to handle all the lanes that it bids for.(
3
) The carrier is familiar with the shipper but the information is not complete or accurate.(
4
) All trucks are identical.The notations to be used are listed as follows:Sets
L
0: the set of lanes encompassed by the existing carrier network
L
1: the set of lanes to be auctioned by the shipper
S: the set of lanes on which the carrier prefers to provide services
K
0: the used vehicle set of the carrier, K0=1,2,…,k0
K
1: the used vehicle set of the shipper if it takes charge of all auctioned loads, K1={1,2,…,k1}
K
2: the used vehicle set of the shipper if it takes charge of part of the auctioned loads, K2={1,2,…,k2}
T: the period set, T={1,2,…,t0}.Parameters
P
(
R
(
S
)
): the probability of serving lanes S
C
(
S
): the carriers incremental cost of serving lanes S
C
′: the total cost of the existing transportation plan
Y
(
S
): fuzzy variable denoting the lowest price offered by the competitors for lanes S
c
i
(
l
)
j
(
l
): the cost on lane l, that is, arc (i,j)
c
0: the carriers fixed cost of running a truck
c
1: the shippers fixed cost of running a truck
α: the carriers acceptable likelihood of winning the business, α∈[0,1]
β: the general markup in the transportation service market
d
i
k: the binary variable, dik=1 if vehicle k is available at node i when t=0; else dik=0
i
(
l
)
/
j
(
l
): the start/end node of lane l
g
i
j
t: the transport loads on arc (i,j) in period t
C
1
(
S
′
): the shippers costs dealing alone with the transportation services on lanes S′
Q: the capacity limit of the shipper’s vehicles.Decision Variables
R
(
S
): the quoted price for serving lanes S
y
i
j
k
t: the binary variable decided by the carrier, yijkt=1 if vehicle k travels from i to j at time t; otherwise yijkt=0
Y
i
j
k
t: the transportation volume of carrier vehicle k in period t on lane (i,j)
x
i
j
k
t: the binary variable decided by shipper, xijkt=1 if vehicle k travels from i to j at time t; otherwise, xijkt=0
X
i
j
k
t: the shippers transportation volume of vehicle k in period t on lane (i,j).


### 4.2. Mathematical Programming

#### 4.2.1. From the Carrier’s Perspective

The objective function of the carrier is to maximize the expected utilityΠ(S), as follows:(1)maxΠS=RS-CSPRSin which P(R(S)) is the carriers probability of serving lanes S. Therefore, P(R(S)) is related to the shipper’s decision (or reaction) based on the price placed by the carrier (i.e., R(S)). From the carrier’s view, winning the business has two essential conditions: the cost of collaborating with it could be no higher than (1) the cost of the shipper handling with all new volumes by itself, whose probability is defined as P(S), and (2) the cost of collaborating with other carriers, whose probability is defined as P(R(S)≤Y(S)). Hence, the likelihood of winning the business with quoted price R(S) is defined as P(R(S)) and P(R(S))=P(S)·P(R(S)≤Y(S)). The detailed description of P(S) is given in (23). C(S) is the incremental cost and is calculated as(2)CS=∑k∈K0∑l∈Sfciljl,Yiljlkt·Yiljlkt+c0k0-C′,1≤t≤t0in which fciljl,Yiljlkt are the unit variable costs on arc (i,j), which are related to the unit cost with full load i.e.,ciljl and the true transport volume of truck k  i.e.,Yiljlkt. In fact, fciljl,Yiljlkt is fluctuant when the truck takes different volumes, which we do not extend in this paper for there were many studies that have discussed it. c0k0 are the fixed costs of running the trucks, which is related to the unit variable cost and the true load on truck k.Constraints (3) impose an acceptable minimum likelihood of serving bundled lanes S at price R(S).(3)PRS≥α,∀S∈L1,where α could be predetermined by the carrier and reflects its risk preference style.Constraints (4) force the planned vehicles to be available according to the given location information dik.(4)∑jlyiljlk,1=dilk,∀il,∀l∈L0∪S,∀k∈K0.Constraints (5) ensure the flow balance at each node,(5)∑jlyiljlkt=∑jlyjlilk,t-1,∀il,∀l∈L0∪S,∀k∈K0,2≤t≤t0.Constraints (6) give the relationship between yijkt and Yijkt,(6)Yliljkt=0,ifyliljkt=0,Yliljkt≥0,ifyliljkt=1.If yl(i)l(j)kt=1, then Yl(i)l(j)kt could be 0 or larger than 0; while if yl(i)l(j)kt=0, then Yl(i)l(j)kt have to be 0. In order to keep the constraints linear, we use the following constraints:(7)Yliljkt≤Myliljkt,∀l∈L0∪S,∀k∈K0,2≤t≤t0,in which M is a larger enough number.Constraints (8) force the existing loads to be satisfied,(8)∑k∈K0∑t∈Tyiljlkt≥1,∀l∈L0∪S,∑k∈K0Yiljlkt=giljlt,∀l∈L0∪S,1≤t≤t0.Constraints (9) give the upper limit of the quoted price for lanes S considering the general markup rate β adopted by the market, which means that the shipper cannot accept a price that deviates too much from the normal market price.(9)RS≤β·CS,∀S∈L1.Therefore, the general decision-making model for the carrier is as follows:(10)maxΠb=RS-CSPRS,s.t.CS=∑k∈K0∑l∈Sfciljl,Yiljlkt+c0k0-C′,1≤t≤t0,PS≥α,∀S∈L1,PRS≤YS≥α,∀S∈L1,∑jlyiljlk,1=dilk,∀il,∀l∈L0∪S,∀k∈K0,∑jlyiljlkt=∑jlyjlilk,t-1,∀il,∀l∈L0∪S,∀k∈K0,2≤t≤t0,∑k∈K0∑t∈Tyiljlkt≥1,∀l∈L0∪S,Yliljkt≤Myliljkt,∀l∈L0∪S,∀k∈K0,2≤t≤t0,∑k∈K0Yiljlkt=giljlt,∀l∈L0∪S,1≤t≤t0,RS≤β·CS,∀S∈L1,yijkt=0,1,dik=0,1.


#### 4.2.2. From the Shipper’s Perspective

The shipper needs to make a choice between purchasing transportation services from the carrier and dealing with the transportation itself. Obviously, the decisions made by shipper are related to the decisions made by the carrier, that is, the transport service prices.Objective function (11) minimizes the shipper’s total costs,(11)minΠ=min⁡π1,π2in which π1 is the cost of the shipper handling with all services itself and π2 is the cost of accepting the services provided by the carrier at price R(S). Hence (12)π1=∑k∈K1∑t≤T∑l∈L1fciljl,Xiljlkt·Xiljlkt+c1k1,in which fciljl,Xiljlkt are the unit variable costs on arc (i,j) which are related to the unit variable costs with full load, that is, ci(l)j(l) and the true load of the truck, that is, Xi(l)j(l)kt. c1k1 are the shippers fixed costs for establishing its own transportation networks.Therefore,π1 can be optimized using the following model:(13)minπ1=∑k∈K2∑t≤T∑l∈L1fciljl,Xiljlkt·Xiljlkt+c1k1,(14)s.t.∑ilxiljlkt=∑ilxjlilk,t+1,∀k∈K1,t≤t0-1,∀l∈L1,j≠0,(15)∑k∈K1Xiljlkt=giljlt,∀l∈L1,1≤t≤t0,(16)xijkt=0,1in which constraint (14) ensures that the flow balance and constraint (15) ensures that all loads have to be serviced.π
2 is the sum of the costs of accepting the services provided by the carrier at price R(S) and the fixed costs and total variable costs of the shipper establishing its own transportation networks, which can be calculated using the following model:(17)minπ2=∑k∈K2∑t≤T∑l∈L1-Sfciljl,Xiljlkt·Xiljlkt+c1k2+RS(18)s.t.∑ilxiljlkt=∑ilxjlilk,t+1,∀k∈K2,t≤t0-1,∀l∈L1-S,j≠0,(19)∑k∈K2Xiljlkt=giljlt,∀l∈L1-S,1≤t≤t0,(20)xijkt=0,1, in which fciljl,Xiljlkt are the unit variable costs on arc (i,j) which are related to the unit variable costs with full load, that is, ci(l)j(l) and the true load of the truck, that is, Xi(l)j(l)kt. Constraints (18)~(19) are similar to constraints (14)~(15) except that l is defined in a different set.In order to win the business, the quoted price should make the total costπ2 lower than the cost of the shipper handling with all services itself, that is, π1. For the shipper accurate private data cannot be acquired by the carrier, so there may be a gap between the shipper’s true cost and the estimated total cost calculated by the model. Therefore, we give a tolerance interval to describe the chance.ThenP(S) can be defined as(21)PS=1ifπ2≤ρ1π1ρ2π1-π2ρ2-ρ1π1ifρ1π1<π2≤ρ2π10ifπ2>ρ2π1,in which ρ1 and ρ2 are parameters, ρ1≥1,ρ2≥1, and ρ1≠ρ2. If the shipper is entirely rational, then ρ1=ρ2=1, which indicates that the shipper takes cost as the only criterion when deciding whether or not to purchase the transportation services from the carrier; so (21) now degenerates as(22)PS=1ifπ2≤ρ1π10ifπ2>ρ1π1.Therefore, ρ1 and ρ2 describe the tolerances for the decision uncertainties of the shipper. If the outsourcing cost π1 is a little higher than that of running the transportation network by itself π2, then the shipper prefers to purchase the services to ensure more professional service quality; that is, P(S)=1; if ρ1π1<π2≤ρ2π1, this indicates that when π2 lies in the interval ρ1π1,ρ2π1, the shipper may purchase the transportation services but it is not certain; if π2 is too high, that is, when ρ2π1 is larger, the shipper does not cooperate with the carrier. As π2 increases, the willingness of the shipper to purchase transportation services from the carrier reduces, and the shipper prefers to establish its own network instead of cooperating with the carrier.From above description, it can be found thatP(S) is defined without considering the competitions from other carriers; hence to win the business should meet the following two constraints at the same time: (1) the quoted price cannot exceed that quoted by the competitors; that is, R(S)≤Y(S); and (2) the total cost to cooperate with the carrier should not exceed the cost of the shipper establishing its own network. The former condition depicts the competition with the other carriers and the latter condition depicts the competition with the shipper. Therefore, the likelihood of winning the business P(R(S)) could be defined as(23)PRS=PS·PRS≤YS.


## 4.1. Assumptions and Notations

In this problem, each carrier has its own existing transportation network and has sufficient capacity to handle the bid [17]. The objective for the carrier is to maximize expected profit by providing transportation services on some lanes under consideration of their existing network and the shippers possible actions. In another words, the carrier seeks a reasonable price for the services provision they prefer to ensure maximum profits with a certain likelihood of acceptance by the shipper. Therefore, there are the following assumptions.(
1
) The carrier is permitted to submit a single optimal package S to the shipper and the shipper can buy the required services from the carrier or deal with them by itself.(
2
) The carrier has sufficient capacity to handle all the lanes that it bids for.(
3
) The carrier is familiar with the shipper but the information is not complete or accurate.(
4
) All trucks are identical.The notations to be used are listed as follows:Sets
L
0: the set of lanes encompassed by the existing carrier network
L
1: the set of lanes to be auctioned by the shipper
S: the set of lanes on which the carrier prefers to provide services
K
0: the used vehicle set of the carrier, K0=1,2,…,k0
K
1: the used vehicle set of the shipper if it takes charge of all auctioned loads, K1={1,2,…,k1}
K
2: the used vehicle set of the shipper if it takes charge of part of the auctioned loads, K2={1,2,…,k2}
T: the period set, T={1,2,…,t0}.Parameters
P
(
R
(
S
)
): the probability of serving lanes S
C
(
S
): the carriers incremental cost of serving lanes S
C
′: the total cost of the existing transportation plan
Y
(
S
): fuzzy variable denoting the lowest price offered by the competitors for lanes S
c
i
(
l
)
j
(
l
): the cost on lane l, that is, arc (i,j)
c
0: the carriers fixed cost of running a truck
c
1: the shippers fixed cost of running a truck
α: the carriers acceptable likelihood of winning the business, α∈[0,1]
β: the general markup in the transportation service market
d
i
k: the binary variable, dik=1 if vehicle k is available at node i when t=0; else dik=0
i
(
l
)
/
j
(
l
): the start/end node of lane l
g
i
j
t: the transport loads on arc (i,j) in period t
C
1
(
S
′
): the shippers costs dealing alone with the transportation services on lanes S′
Q: the capacity limit of the shipper’s vehicles.Decision Variables
R
(
S
): the quoted price for serving lanes S
y
i
j
k
t: the binary variable decided by the carrier, yijkt=1 if vehicle k travels from i to j at time t; otherwise yijkt=0
Y
i
j
k
t: the transportation volume of carrier vehicle k in period t on lane (i,j)
x
i
j
k
t: the binary variable decided by shipper, xijkt=1 if vehicle k travels from i to j at time t; otherwise, xijkt=0
X
i
j
k
t: the shippers transportation volume of vehicle k in period t on lane (i,j).


## 4.2. Mathematical Programming

### 4.2.1. From the Carrier’s Perspective

The objective function of the carrier is to maximize the expected utilityΠ(S), as follows:(1)maxΠS=RS-CSPRSin which P(R(S)) is the carriers probability of serving lanes S. Therefore, P(R(S)) is related to the shipper’s decision (or reaction) based on the price placed by the carrier (i.e., R(S)). From the carrier’s view, winning the business has two essential conditions: the cost of collaborating with it could be no higher than (1) the cost of the shipper handling with all new volumes by itself, whose probability is defined as P(S), and (2) the cost of collaborating with other carriers, whose probability is defined as P(R(S)≤Y(S)). Hence, the likelihood of winning the business with quoted price R(S) is defined as P(R(S)) and P(R(S))=P(S)·P(R(S)≤Y(S)). The detailed description of P(S) is given in (23). C(S) is the incremental cost and is calculated as(2)CS=∑k∈K0∑l∈Sfciljl,Yiljlkt·Yiljlkt+c0k0-C′,1≤t≤t0in which fciljl,Yiljlkt are the unit variable costs on arc (i,j), which are related to the unit cost with full load i.e.,ciljl and the true transport volume of truck k  i.e.,Yiljlkt. In fact, fciljl,Yiljlkt is fluctuant when the truck takes different volumes, which we do not extend in this paper for there were many studies that have discussed it. c0k0 are the fixed costs of running the trucks, which is related to the unit variable cost and the true load on truck k.Constraints (3) impose an acceptable minimum likelihood of serving bundled lanes S at price R(S).(3)PRS≥α,∀S∈L1,where α could be predetermined by the carrier and reflects its risk preference style.Constraints (4) force the planned vehicles to be available according to the given location information dik.(4)∑jlyiljlk,1=dilk,∀il,∀l∈L0∪S,∀k∈K0.Constraints (5) ensure the flow balance at each node,(5)∑jlyiljlkt=∑jlyjlilk,t-1,∀il,∀l∈L0∪S,∀k∈K0,2≤t≤t0.Constraints (6) give the relationship between yijkt and Yijkt,(6)Yliljkt=0,ifyliljkt=0,Yliljkt≥0,ifyliljkt=1.If yl(i)l(j)kt=1, then Yl(i)l(j)kt could be 0 or larger than 0; while if yl(i)l(j)kt=0, then Yl(i)l(j)kt have to be 0. In order to keep the constraints linear, we use the following constraints:(7)Yliljkt≤Myliljkt,∀l∈L0∪S,∀k∈K0,2≤t≤t0,in which M is a larger enough number.Constraints (8) force the existing loads to be satisfied,(8)∑k∈K0∑t∈Tyiljlkt≥1,∀l∈L0∪S,∑k∈K0Yiljlkt=giljlt,∀l∈L0∪S,1≤t≤t0.Constraints (9) give the upper limit of the quoted price for lanes S considering the general markup rate β adopted by the market, which means that the shipper cannot accept a price that deviates too much from the normal market price.(9)RS≤β·CS,∀S∈L1.Therefore, the general decision-making model for the carrier is as follows:(10)maxΠb=RS-CSPRS,s.t.CS=∑k∈K0∑l∈Sfciljl,Yiljlkt+c0k0-C′,1≤t≤t0,PS≥α,∀S∈L1,PRS≤YS≥α,∀S∈L1,∑jlyiljlk,1=dilk,∀il,∀l∈L0∪S,∀k∈K0,∑jlyiljlkt=∑jlyjlilk,t-1,∀il,∀l∈L0∪S,∀k∈K0,2≤t≤t0,∑k∈K0∑t∈Tyiljlkt≥1,∀l∈L0∪S,Yliljkt≤Myliljkt,∀l∈L0∪S,∀k∈K0,2≤t≤t0,∑k∈K0Yiljlkt=giljlt,∀l∈L0∪S,1≤t≤t0,RS≤β·CS,∀S∈L1,yijkt=0,1,dik=0,1.


### 4.2.2. From the Shipper’s Perspective

The shipper needs to make a choice between purchasing transportation services from the carrier and dealing with the transportation itself. Obviously, the decisions made by shipper are related to the decisions made by the carrier, that is, the transport service prices.Objective function (11) minimizes the shipper’s total costs,(11)minΠ=min⁡π1,π2in which π1 is the cost of the shipper handling with all services itself and π2 is the cost of accepting the services provided by the carrier at price R(S). Hence (12)π1=∑k∈K1∑t≤T∑l∈L1fciljl,Xiljlkt·Xiljlkt+c1k1,in which fciljl,Xiljlkt are the unit variable costs on arc (i,j) which are related to the unit variable costs with full load, that is, ci(l)j(l) and the true load of the truck, that is, Xi(l)j(l)kt. c1k1 are the shippers fixed costs for establishing its own transportation networks.Therefore,π1 can be optimized using the following model:(13)minπ1=∑k∈K2∑t≤T∑l∈L1fciljl,Xiljlkt·Xiljlkt+c1k1,(14)s.t.∑ilxiljlkt=∑ilxjlilk,t+1,∀k∈K1,t≤t0-1,∀l∈L1,j≠0,(15)∑k∈K1Xiljlkt=giljlt,∀l∈L1,1≤t≤t0,(16)xijkt=0,1in which constraint (14) ensures that the flow balance and constraint (15) ensures that all loads have to be serviced.π
2 is the sum of the costs of accepting the services provided by the carrier at price R(S) and the fixed costs and total variable costs of the shipper establishing its own transportation networks, which can be calculated using the following model:(17)minπ2=∑k∈K2∑t≤T∑l∈L1-Sfciljl,Xiljlkt·Xiljlkt+c1k2+RS(18)s.t.∑ilxiljlkt=∑ilxjlilk,t+1,∀k∈K2,t≤t0-1,∀l∈L1-S,j≠0,(19)∑k∈K2Xiljlkt=giljlt,∀l∈L1-S,1≤t≤t0,(20)xijkt=0,1, in which fciljl,Xiljlkt are the unit variable costs on arc (i,j) which are related to the unit variable costs with full load, that is, ci(l)j(l) and the true load of the truck, that is, Xi(l)j(l)kt. Constraints (18)~(19) are similar to constraints (14)~(15) except that l is defined in a different set.In order to win the business, the quoted price should make the total costπ2 lower than the cost of the shipper handling with all services itself, that is, π1. For the shipper accurate private data cannot be acquired by the carrier, so there may be a gap between the shipper’s true cost and the estimated total cost calculated by the model. Therefore, we give a tolerance interval to describe the chance.ThenP(S) can be defined as(21)PS=1ifπ2≤ρ1π1ρ2π1-π2ρ2-ρ1π1ifρ1π1<π2≤ρ2π10ifπ2>ρ2π1,in which ρ1 and ρ2 are parameters, ρ1≥1,ρ2≥1, and ρ1≠ρ2. If the shipper is entirely rational, then ρ1=ρ2=1, which indicates that the shipper takes cost as the only criterion when deciding whether or not to purchase the transportation services from the carrier; so (21) now degenerates as(22)PS=1ifπ2≤ρ1π10ifπ2>ρ1π1.Therefore, ρ1 and ρ2 describe the tolerances for the decision uncertainties of the shipper. If the outsourcing cost π1 is a little higher than that of running the transportation network by itself π2, then the shipper prefers to purchase the services to ensure more professional service quality; that is, P(S)=1; if ρ1π1<π2≤ρ2π1, this indicates that when π2 lies in the interval ρ1π1,ρ2π1, the shipper may purchase the transportation services but it is not certain; if π2 is too high, that is, when ρ2π1 is larger, the shipper does not cooperate with the carrier. As π2 increases, the willingness of the shipper to purchase transportation services from the carrier reduces, and the shipper prefers to establish its own network instead of cooperating with the carrier.From above description, it can be found thatP(S) is defined without considering the competitions from other carriers; hence to win the business should meet the following two constraints at the same time: (1) the quoted price cannot exceed that quoted by the competitors; that is, R(S)≤Y(S); and (2) the total cost to cooperate with the carrier should not exceed the cost of the shipper establishing its own network. The former condition depicts the competition with the other carriers and the latter condition depicts the competition with the shipper. Therefore, the likelihood of winning the business P(R(S)) could be defined as(23)PRS=PS·PRS≤YS.


## 4.2.1. From the Carrier’s Perspective

The objective function of the carrier is to maximize the expected utilityΠ(S), as follows:(1)maxΠS=RS-CSPRSin which P(R(S)) is the carriers probability of serving lanes S. Therefore, P(R(S)) is related to the shipper’s decision (or reaction) based on the price placed by the carrier (i.e., R(S)). From the carrier’s view, winning the business has two essential conditions: the cost of collaborating with it could be no higher than (1) the cost of the shipper handling with all new volumes by itself, whose probability is defined as P(S), and (2) the cost of collaborating with other carriers, whose probability is defined as P(R(S)≤Y(S)). Hence, the likelihood of winning the business with quoted price R(S) is defined as P(R(S)) and P(R(S))=P(S)·P(R(S)≤Y(S)). The detailed description of P(S) is given in (23). C(S) is the incremental cost and is calculated as(2)CS=∑k∈K0∑l∈Sfciljl,Yiljlkt·Yiljlkt+c0k0-C′,1≤t≤t0in which fciljl,Yiljlkt are the unit variable costs on arc (i,j), which are related to the unit cost with full load i.e.,ciljl and the true transport volume of truck k  i.e.,Yiljlkt. In fact, fciljl,Yiljlkt is fluctuant when the truck takes different volumes, which we do not extend in this paper for there were many studies that have discussed it. c0k0 are the fixed costs of running the trucks, which is related to the unit variable cost and the true load on truck k.Constraints (3) impose an acceptable minimum likelihood of serving bundled lanes S at price R(S).(3)PRS≥α,∀S∈L1,where α could be predetermined by the carrier and reflects its risk preference style.Constraints (4) force the planned vehicles to be available according to the given location information dik.(4)∑jlyiljlk,1=dilk,∀il,∀l∈L0∪S,∀k∈K0.Constraints (5) ensure the flow balance at each node,(5)∑jlyiljlkt=∑jlyjlilk,t-1,∀il,∀l∈L0∪S,∀k∈K0,2≤t≤t0.Constraints (6) give the relationship between yijkt and Yijkt,(6)Yliljkt=0,ifyliljkt=0,Yliljkt≥0,ifyliljkt=1.If yl(i)l(j)kt=1, then Yl(i)l(j)kt could be 0 or larger than 0; while if yl(i)l(j)kt=0, then Yl(i)l(j)kt have to be 0. In order to keep the constraints linear, we use the following constraints:(7)Yliljkt≤Myliljkt,∀l∈L0∪S,∀k∈K0,2≤t≤t0,in which M is a larger enough number.Constraints (8) force the existing loads to be satisfied,(8)∑k∈K0∑t∈Tyiljlkt≥1,∀l∈L0∪S,∑k∈K0Yiljlkt=giljlt,∀l∈L0∪S,1≤t≤t0.Constraints (9) give the upper limit of the quoted price for lanes S considering the general markup rate β adopted by the market, which means that the shipper cannot accept a price that deviates too much from the normal market price.(9)RS≤β·CS,∀S∈L1.Therefore, the general decision-making model for the carrier is as follows:(10)maxΠb=RS-CSPRS,s.t.CS=∑k∈K0∑l∈Sfciljl,Yiljlkt+c0k0-C′,1≤t≤t0,PS≥α,∀S∈L1,PRS≤YS≥α,∀S∈L1,∑jlyiljlk,1=dilk,∀il,∀l∈L0∪S,∀k∈K0,∑jlyiljlkt=∑jlyjlilk,t-1,∀il,∀l∈L0∪S,∀k∈K0,2≤t≤t0,∑k∈K0∑t∈Tyiljlkt≥1,∀l∈L0∪S,Yliljkt≤Myliljkt,∀l∈L0∪S,∀k∈K0,2≤t≤t0,∑k∈K0Yiljlkt=giljlt,∀l∈L0∪S,1≤t≤t0,RS≤β·CS,∀S∈L1,yijkt=0,1,dik=0,1.


## 4.2.2. From the Shipper’s Perspective

The shipper needs to make a choice between purchasing transportation services from the carrier and dealing with the transportation itself. Obviously, the decisions made by shipper are related to the decisions made by the carrier, that is, the transport service prices.Objective function (11) minimizes the shipper’s total costs,(11)minΠ=min⁡π1,π2in which π1 is the cost of the shipper handling with all services itself and π2 is the cost of accepting the services provided by the carrier at price R(S). Hence (12)π1=∑k∈K1∑t≤T∑l∈L1fciljl,Xiljlkt·Xiljlkt+c1k1,in which fciljl,Xiljlkt are the unit variable costs on arc (i,j) which are related to the unit variable costs with full load, that is, ci(l)j(l) and the true load of the truck, that is, Xi(l)j(l)kt. c1k1 are the shippers fixed costs for establishing its own transportation networks.Therefore,π1 can be optimized using the following model:(13)minπ1=∑k∈K2∑t≤T∑l∈L1fciljl,Xiljlkt·Xiljlkt+c1k1,(14)s.t.∑ilxiljlkt=∑ilxjlilk,t+1,∀k∈K1,t≤t0-1,∀l∈L1,j≠0,(15)∑k∈K1Xiljlkt=giljlt,∀l∈L1,1≤t≤t0,(16)xijkt=0,1in which constraint (14) ensures that the flow balance and constraint (15) ensures that all loads have to be serviced.π
2 is the sum of the costs of accepting the services provided by the carrier at price R(S) and the fixed costs and total variable costs of the shipper establishing its own transportation networks, which can be calculated using the following model:(17)minπ2=∑k∈K2∑t≤T∑l∈L1-Sfciljl,Xiljlkt·Xiljlkt+c1k2+RS(18)s.t.∑ilxiljlkt=∑ilxjlilk,t+1,∀k∈K2,t≤t0-1,∀l∈L1-S,j≠0,(19)∑k∈K2Xiljlkt=giljlt,∀l∈L1-S,1≤t≤t0,(20)xijkt=0,1, in which fciljl,Xiljlkt are the unit variable costs on arc (i,j) which are related to the unit variable costs with full load, that is, ci(l)j(l) and the true load of the truck, that is, Xi(l)j(l)kt. Constraints (18)~(19) are similar to constraints (14)~(15) except that l is defined in a different set.In order to win the business, the quoted price should make the total costπ2 lower than the cost of the shipper handling with all services itself, that is, π1. For the shipper accurate private data cannot be acquired by the carrier, so there may be a gap between the shipper’s true cost and the estimated total cost calculated by the model. Therefore, we give a tolerance interval to describe the chance.ThenP(S) can be defined as(21)PS=1ifπ2≤ρ1π1ρ2π1-π2ρ2-ρ1π1ifρ1π1<π2≤ρ2π10ifπ2>ρ2π1,in which ρ1 and ρ2 are parameters, ρ1≥1,ρ2≥1, and ρ1≠ρ2. If the shipper is entirely rational, then ρ1=ρ2=1, which indicates that the shipper takes cost as the only criterion when deciding whether or not to purchase the transportation services from the carrier; so (21) now degenerates as(22)PS=1ifπ2≤ρ1π10ifπ2>ρ1π1.Therefore, ρ1 and ρ2 describe the tolerances for the decision uncertainties of the shipper. If the outsourcing cost π1 is a little higher than that of running the transportation network by itself π2, then the shipper prefers to purchase the services to ensure more professional service quality; that is, P(S)=1; if ρ1π1<π2≤ρ2π1, this indicates that when π2 lies in the interval ρ1π1,ρ2π1, the shipper may purchase the transportation services but it is not certain; if π2 is too high, that is, when ρ2π1 is larger, the shipper does not cooperate with the carrier. As π2 increases, the willingness of the shipper to purchase transportation services from the carrier reduces, and the shipper prefers to establish its own network instead of cooperating with the carrier.From above description, it can be found thatP(S) is defined without considering the competitions from other carriers; hence to win the business should meet the following two constraints at the same time: (1) the quoted price cannot exceed that quoted by the competitors; that is, R(S)≤Y(S); and (2) the total cost to cooperate with the carrier should not exceed the cost of the shipper establishing its own network. The former condition depicts the competition with the other carriers and the latter condition depicts the competition with the shipper. Therefore, the likelihood of winning the business P(R(S)) could be defined as(23)PRS=PS·PRS≤YS.


## 5. Solution Approach

In this section, the procedure to determine the carriers optimal bid strategy is introduced to solve the above mathematical model. Seemingly, the problem is about submitting which lanes at what price to the shipper; however, it is actually more complex. The quoted price for chosen lanesS is related to the lanes incremental costs, which can be determined by developing an optimal transportation plan, which has been proven to be NP-hard. Further, different lane sets influence the incremental costs. Suppose there are n lanes that need to be serviced, so then there are 2n-1 possible lane bundles that may be considered by the carrier; therefore, the 2n-1 transportation optimization problem needs to be solved to determine the best solution. Therefore, this problem is much more complicated than transportation planning with determined tasks. Because of this complexity, the Particle Swarm Optimization (PSO) is chosen to solve the proposed problem. PSO, an evolutionary algorithm, was first proposed by Kennedy and Eberhart [31], and has become one of the most useful and efficient techniques. Compared to other evolutionary algorithms based on population, PSO presents a superior dominance when dealing with difficult optimization problems and has shown good results in static, noisy, and continuously changing environments with little influence on the continuity of the objective function Song and Gu [32]. As a result, it has been widely applied in many transportation planning and optimization fields, Masdari et al. [33]; Akhand et al. [34]; Afkar and Babazadeh [35]; Xu et al. [36]; Yan et al. [37]. Because it has been proven to be effective in solving NP-hard problems, it was adopted in this paper to handle the proposed model. The velocity and position are updated according to (24)wτ=wT+τ-T1-Tw1-wT,vldτ+1=wτvldτ+cpr1pldbestτ-pldτ+cgr2pgdbestτ-pldτ,pldτ+1=pldτ+vldτ+1,where τ is the iteration index, vld(τ) is the velocity of the lth particle at the dth dimension in the τth iteration, w(τ) is the inertia weight in the τth iteration, cp and cg are the personal best and global best position acceleration constants, r1 and r2 are uniform random numbers in the interval [0,1], pldbest(τ) and pgdbest(τ) are personal best position (pbest) and the global best position (gbest) of the lth particle at the dth dimension in the τth iteration, and pld(τ) is the position of the lth particle at the dth dimension in the τth iteration (Algorithm 1).Algorithm 1:Solution approach to proposed model.
Input: Booked and auctioned loads, i.e. L0 and L1;
Loaded and empty movement costs, i.e., cij;
Current transportation network.
Output: Generated bids with prices;
Expected benefits for carrier.
(
1
)
Calculate current transportation network total costs;
(
2
)
Generate N particles, with each particle including one lane bundle randomly chosen from the auctioned loads;
(
3
)
for for each particle do
(
4
)
Determine the optimal transportation plan under consideration of the constraints in the proposed model;
(
5
)
Calculate the cost of the new transportation plan;
(
6
)
Calculate the incremetal costs of the transportation tasks on the chosen lane bundles C(S);
(
7
)
Generate the price for the chosen lane set based on the incremental costs R(S);
(
8
)
Compare the auction price by carrier π2 and the shipper’s costs π1 for personally handling the services;
(
9
)
Calculate the possibility that the carrier wins the bid P(S);
(
10
)
Calculate the expected benefit from lane bundle S with price R(S) and take this as the fitness value for this particle;
(
11
)
Set this particle as personal best particle Ppbest;
(
12
)  end for
(
13
) Determine the particle with the maximum benefit and set as the global best particle Pgbest;
(
14
)  for  t=1 to T  do
(
15
)
Update the particle velocities and positions using Eq. (24);
(
16
)
Repeat (3) to (10);
(
17
)
for for each particle do
(
18
)   if if the current fitness value is larger than that of the personal best particle Ppbest, then; then
(
19
)
Set current particle as personal best particle Ppbest;
(
20
)
end if
(
21
)
end for
(
22
)
Determine the particle with the maximum benefit and compare the fitness value with that of the global best particle Pgbest;
(
23
)
if The fitness value larger than that of global best particle Pgbest; then
(
24
)
Set this particle as global best particle Pgbest;
(
25
)
end if
(
26
)
end for
(
27
)
Output the global best particle, including lane bundle S and price R(S) and the expected benefit.


## 6. Computational Study

### 6.1. Test and Analysis Using Small Scale Instance

In this section, hypothetical data sets are used to test the proposed model and algorithm as real data from combinatorial auctions are generally not publicly available [1, 38]. In this case, the shipper has no vehicles and the carrier has some transportation tasks on certain lanes, as seen in Figure 5, which involves 12 regions and 6 periods. The vehicles are homogeneous and have a maximum capacity load of 60 tonnes. The distances between any two regions are listed in Table 1, which were randomly generated so are not on a main diagonal symmetry (similar with practical cases). Suppose that the carrier has arranged the current tasks to be optimal; that is, at least 7 vehicles are being used on the transportation network, and extra fixed costs will be incurred if new vehicles are needed. The proposed algorithm is adopted by using MATLAB 7.5 on an Intel Core 2, 2.99 GHz clock pulse with 3.0 GB memory. Figure 6 shows the carriers transportation plan for their existing tasks and the total current cost of 1294770. The fuzzy variable Y(S) are defined as the 0.7∗C,C,1.3∗C, where C is the total transportation cost of lanes set S, calculated using the industrial unit cost. The unit variable cost is variational as the true load of the truck, which is 2 when the truck is empty-loaded and 3 when the truck is full-loaded. The fixed cost is set to be 500 per truck on each lane for the carrier and 900 for the shipper. The empty load rate is 50%, which can be optimized by undertaking more tasks on those lanes carrying empty loads.Table 1
Distance between two regions (unit: Km).
Region
Region
1
2
3
4
5
6
7
8
9
10
11
12
1
–
19
21
43
21
37
28
15
42
41
10
50
2
15
–
28
29
36
39
37
35
45
37
45
14
3
32
37
–
20
23
17
17
35
35
31
49
41
4
15
22
23
–
44
42
37
48
12
37
36
41
5
41
32
10
30
–
38
42
19
47
28
39
11
6
37
48
19
48
41
–
25
49
49
11
45
23
7
13
26
41
27
48
16
–
12
46
20
23
40
8
12
20
23
45
44
18
10
–
48
49
22
26
9
50
39
43
30
42
41
46
41
–
14
22
20
10
14
36
28
15
21
31
35
48
32
–
42
23
11
35
34
48
50
22
23
17
29
17
29
–
38
12
43
43
34
22
21
39
21
19
20
29
32
–Figure 5
Computational case.Figure 6
Existing transportation plan.Consider the shipper’s transportation requirements shown in Figure5 and Table 2. Figure 5 shows the carriers booked lanes and the shippers auctioned lanes and Table 2 gives details of the different lanes and the loads on each lane. The proposed model and algorithm are now adopted to select the carriers optimum lane set and the expected price, and α is set to be 0.9. After running the program 10 times, the optimal bidding strategy is shown in Figure 7 at a price of 733567; the possibility of winning the business is at 0.9931 and an overall benefit of 78596. This indicates that the shipper would be almost certain to accept the business (possibility is 0.9931) as personally completing these tasks would cost much more than the carrier’s quoted price. Let us analyze the differences between the carrier’s existing transportation plan and that after adding the new transportation tasks, as seen in Table 3. It can be seen that this bidding strategy would result in the following benefits for the carrier: (1) the average empty loads are reduced from 1.43 to 0.7, a 51% improvement on the existing transportation plan. As empty loads are an unnecessary cost for the carrier, empty load travel reductions would save carrier costs; (2) the average number of loaded lanes in the network rises from 3 to 4, a 33% improvement. As loaded lanes bring additional benefits to the carrier, this improvement would result in greater carrier profits; (3) the average empty load rate reduces from 50% to 33.2%, a 34% improvement. When calculating this data, “empty load lanes” are dealt with “traveling with empty loads” (such as vehicle 3 in period 3 in Figure 8) and “awaiting actions” means the “awaiting action in the same region” (such as vehicle 3 in period 2 in Figure 8). It can be seen that bidding for these loads (Figure 7) and planning the transportation networks again can significantly reduce the average empty load rate. From the above three findings, it can be concluded that adopting the bidding strategy using the proposed model and algorithm can save the carrier costs, increase benefits, and increase the possibility of winning the business.Table 2
Required loads for booked and auctioned lanes (unit: tons).
Period
1
2
3
4
5
6
Booked loads
d
b
(
1,2
)
=
20
d
b
(
2,10
)
=
30
d
b
(
2,7
)
=
30
d
b
(
1,4
)
=
60
d
b
(
8,3
)
=
40
d
b
(
2,4
)
=
20
d
b
(
6,3
)
=
40
d
b
(
5,4
)
=
40
d
b
(
5,3
)
=
50
d
b
(
3,11
)
=
40
d
b
(
12,5
)
=
50
d
b
(
5,9
)
=
50
d
b
(
12,6
)
=
20
d
b
(
7,9
)
=
60
d
b
(
11,8
)
=
40
d
b
(
6,5
)
=
40
d
b
(
10,7
)
=
40
d
b
(
11,5
)
=
40
d
b
(
12,10
)
=
60
d
b
(
9,10
)
=
30
Auctioned loads
d
a
(
3,2
)
=
60
d
a
(
1,2
)
=
40
d
a
(
3,2
)
=
60
d
a
(
4,7
)
=
20
d
a
(
1,5
)
=
50
d
a
(
3,6
)
=
60
d
a
(
7,11
)
=
20
d
a
(
7,3
)
=
60
d
a
(
4,11
)
=
20
d
a
(
7,5
)
=
30
d
a
(
5,2
)
=
30
d
a
(
7,10
)
=
60
d
a
(
9,8
)
=
20
d
a
(
8,11
)
=
50
d
a
(
6,8
)
=
30
d
a
(
12,8
)
=
50
d
a
(
9,11
)
=
40
d
a
(
10,12
)
=
40
d
a
(
2,4
)
=
50
d
a
(
4,7
)
=
60
d
a
(
2,7
)
=
30
d
a
(
4,1
)
=
50
d
a
(
1,6
)
=
30
d
a
(
3,6
)
=
40
d
a
(
11,12
)
=
60
d
a
(
8,10
)
=
50Table 3
Comparison before and after auction using the proposed model.
Vehicle
Before
After
Number of empty load lanes
Percent
Number of loaded lanes
Percent
Awaiting actions
Average empty load rate
Number of empty load lanes
Percent
Number of loaded lanes
Percent
Awaiting actions
Average empty load rate
1
1
17%
3
50%
2
50%
0
0%
6
100%
0
0%
2
0
0%
3
50%
3
50%
1
17%
4
67%
1
33%
3
2
33%
2
33%
2
67%
0
0%
4
67%
2
33%
4
2
33%
4
67%
0
33%
1
17%
4
67%
1
33%
5
2
33%
3
50%
1
50%
1
17%
4
67%
1
33%
6
2
33%
3
50%
1
50%
1
17%
4
67%
1
33%
7
1
17%
3
50%
2
50%
0
17%
5
83%
1
17%
8
–
–
–
–
–
–
1
17%
3
50%
2
50%
9
–
–
–
–
–
–
1
17%
3
50%
2
50%
10
–
–
–
–
–
–
1
17%
3
50%
2
50%
Average
1.43
23.7%
3
50%
1.57
50%
0.7
13.6%
4
66.8%
1.4
33.2%Figure 7
Bidding lanes found using the proposed model.Figure 8
Adjusted transportation plan after bidding consideration.


### 6.2. Analysis about Parameterα Values

Now the influence ofα on the carriers’ decisions will be analyzed. First, we set a different value for α and then calculated the hypothetical case using our proposed model. We then adopted different values for α and listed the results in Table 4. From Table 4, it can be seen that, as α reduces, the profit without likelihood of winning business increases. The optimal bidding strategy was found when α was set to 0.7, as, at this value, the carrier can serve more lanes at higher quotes than at a higher α value. We analyzed this situation as follows: (1) without the likelihood of winning means that there is no competition; therefore, the carrier can choose to serve more profitable lanes at a higher price and gain greater benefit. If the market lacks competition, this bidding strategy could be the better choice for the carrier; (2) a lower α means that the carrier will accept a higher risk of losing the business. At α=0.7, for example, the carrier only requires a possibility that their quoted price is lower than the other carriers and that the cost to the shipper of doing their own transportation is no less than 0.7. Therefore, the computational likelihood of winning the business for the optimal bidding strategy is 0.7282, which is lower than the values in the first two lines in the table and indicates that the optimal bidding strategy has a higher risk of losing the business. (3) Although a lower α and a higher quoted price appear to result in greater benefits to the carrier, the expected profit rise is not as significant as the likelihood of winning the business is reduced. Therefore, in this situation, the carrier has to consider whether it is worth taking the higher risk of losing the business by generating the bid with a higher price.Table 4
Results analysis by adopting differentα values.
α
Computational results
Profits without considering the likelihood of winning
Possibility of winning the business
Expected profits
0.9
78596
0.9931
78054
0.8
83527
0.8521
71173
0.7
93523
0.7282
68103From this, it is possible to deduce the quoted price for the optimal bidding strategy without considering the likelihood of winning the business. Obviously, as the carrier wants to quote as high a price as possible if the competition with other carriers and the shipper’s reactions are not considered, there is no upper bound for the quoted price. Therefore, if it is assumed that a reasonable profit rate for the carrier is20%, a reverse derivation of the quoted price for the optimal bidding lanes can be calculated using the proposed model, as shown in Figure 7. After calculation, the quoted price was found to be 803904, which was higher than the price calculated using the proposed model (733567), and the likelihood of winning the business was found to be 0.5123, which was much lower than that calculated using the proposed model (0.9931). In fact, without considering the activities of the other carriers and the shipper, the carrier’s expected profit was 67108, which was lower than that calculated by our model (78054). The above analysis shows that, by adopting the proposed model, the carrier could quote a competitive price for the set lanes and theoretically gain greater profits.


### 6.3. Test and Analysis of Different Scale Instance

For each scale instance, we ran the program 10 times and calculated the average CPU times, which are listed in Table5. According to Table 5, it can be seen that the proposed approach was able to solve the differently scaled problems in an acceptable time. Using our office computer, the largest scale instance we could deal with had 50 nodes, 30 periods, and 500 auctioned lanes, but larger instances could be tested using cloud computing and a large-scale distributed server, which is the direction of our future research.Table 5
Computational performance of different scale instance.
Problem instance
The number of nodes
The number of periods
The number of auctioned lanes
Population sizeN
IterationT
Time (s)
1
12
6
26
20
50
41.37
2
20
20
100
20
100
198.32
200
20
300
581.23
300
40
500
1149.16
30
100
20
100
237.81
200
20
300
786.56
300
40
500
1321.34
3
30
20
100
20
100
244.73
200
20
300
856.38
300
40
500
1289.34
30
100
20
100
279.62
200
20
300
933.57
300
40
500
1432.86
4
40
20
200
40
200
733.27
300
40
300
1019.81
500
40
500
1473.88
30
200
40
300
1219.46
300
40
500
1519.31
500
100
500
2733.96
5
50
20
200
40
300
1313.28
300
100
500
2736.52
500
100
500
2988.44
30
200
40
300
1447.17
300
100
500
2953.29
500
100
500
3028.63


## 6.1. Test and Analysis Using Small Scale Instance

In this section, hypothetical data sets are used to test the proposed model and algorithm as real data from combinatorial auctions are generally not publicly available [1, 38]. In this case, the shipper has no vehicles and the carrier has some transportation tasks on certain lanes, as seen in Figure 5, which involves 12 regions and 6 periods. The vehicles are homogeneous and have a maximum capacity load of 60 tonnes. The distances between any two regions are listed in Table 1, which were randomly generated so are not on a main diagonal symmetry (similar with practical cases). Suppose that the carrier has arranged the current tasks to be optimal; that is, at least 7 vehicles are being used on the transportation network, and extra fixed costs will be incurred if new vehicles are needed. The proposed algorithm is adopted by using MATLAB 7.5 on an Intel Core 2, 2.99 GHz clock pulse with 3.0 GB memory. Figure 6 shows the carriers transportation plan for their existing tasks and the total current cost of 1294770. The fuzzy variable Y(S) are defined as the 0.7∗C,C,1.3∗C, where C is the total transportation cost of lanes set S, calculated using the industrial unit cost. The unit variable cost is variational as the true load of the truck, which is 2 when the truck is empty-loaded and 3 when the truck is full-loaded. The fixed cost is set to be 500 per truck on each lane for the carrier and 900 for the shipper. The empty load rate is 50%, which can be optimized by undertaking more tasks on those lanes carrying empty loads.Table 1
Distance between two regions (unit: Km).
Region
Region
1
2
3
4
5
6
7
8
9
10
11
12
1
–
19
21
43
21
37
28
15
42
41
10
50
2
15
–
28
29
36
39
37
35
45
37
45
14
3
32
37
–
20
23
17
17
35
35
31
49
41
4
15
22
23
–
44
42
37
48
12
37
36
41
5
41
32
10
30
–
38
42
19
47
28
39
11
6
37
48
19
48
41
–
25
49
49
11
45
23
7
13
26
41
27
48
16
–
12
46
20
23
40
8
12
20
23
45
44
18
10
–
48
49
22
26
9
50
39
43
30
42
41
46
41
–
14
22
20
10
14
36
28
15
21
31
35
48
32
–
42
23
11
35
34
48
50
22
23
17
29
17
29
–
38
12
43
43
34
22
21
39
21
19
20
29
32
–Figure 5
Computational case.Figure 6
Existing transportation plan.Consider the shipper’s transportation requirements shown in Figure5 and Table 2. Figure 5 shows the carriers booked lanes and the shippers auctioned lanes and Table 2 gives details of the different lanes and the loads on each lane. The proposed model and algorithm are now adopted to select the carriers optimum lane set and the expected price, and α is set to be 0.9. After running the program 10 times, the optimal bidding strategy is shown in Figure 7 at a price of 733567; the possibility of winning the business is at 0.9931 and an overall benefit of 78596. This indicates that the shipper would be almost certain to accept the business (possibility is 0.9931) as personally completing these tasks would cost much more than the carrier’s quoted price. Let us analyze the differences between the carrier’s existing transportation plan and that after adding the new transportation tasks, as seen in Table 3. It can be seen that this bidding strategy would result in the following benefits for the carrier: (1) the average empty loads are reduced from 1.43 to 0.7, a 51% improvement on the existing transportation plan. As empty loads are an unnecessary cost for the carrier, empty load travel reductions would save carrier costs; (2) the average number of loaded lanes in the network rises from 3 to 4, a 33% improvement. As loaded lanes bring additional benefits to the carrier, this improvement would result in greater carrier profits; (3) the average empty load rate reduces from 50% to 33.2%, a 34% improvement. When calculating this data, “empty load lanes” are dealt with “traveling with empty loads” (such as vehicle 3 in period 3 in Figure 8) and “awaiting actions” means the “awaiting action in the same region” (such as vehicle 3 in period 2 in Figure 8). It can be seen that bidding for these loads (Figure 7) and planning the transportation networks again can significantly reduce the average empty load rate. From the above three findings, it can be concluded that adopting the bidding strategy using the proposed model and algorithm can save the carrier costs, increase benefits, and increase the possibility of winning the business.Table 2
Required loads for booked and auctioned lanes (unit: tons).
Period
1
2
3
4
5
6
Booked loads
d
b
(
1,2
)
=
20
d
b
(
2,10
)
=
30
d
b
(
2,7
)
=
30
d
b
(
1,4
)
=
60
d
b
(
8,3
)
=
40
d
b
(
2,4
)
=
20
d
b
(
6,3
)
=
40
d
b
(
5,4
)
=
40
d
b
(
5,3
)
=
50
d
b
(
3,11
)
=
40
d
b
(
12,5
)
=
50
d
b
(
5,9
)
=
50
d
b
(
12,6
)
=
20
d
b
(
7,9
)
=
60
d
b
(
11,8
)
=
40
d
b
(
6,5
)
=
40
d
b
(
10,7
)
=
40
d
b
(
11,5
)
=
40
d
b
(
12,10
)
=
60
d
b
(
9,10
)
=
30
Auctioned loads
d
a
(
3,2
)
=
60
d
a
(
1,2
)
=
40
d
a
(
3,2
)
=
60
d
a
(
4,7
)
=
20
d
a
(
1,5
)
=
50
d
a
(
3,6
)
=
60
d
a
(
7,11
)
=
20
d
a
(
7,3
)
=
60
d
a
(
4,11
)
=
20
d
a
(
7,5
)
=
30
d
a
(
5,2
)
=
30
d
a
(
7,10
)
=
60
d
a
(
9,8
)
=
20
d
a
(
8,11
)
=
50
d
a
(
6,8
)
=
30
d
a
(
12,8
)
=
50
d
a
(
9,11
)
=
40
d
a
(
10,12
)
=
40
d
a
(
2,4
)
=
50
d
a
(
4,7
)
=
60
d
a
(
2,7
)
=
30
d
a
(
4,1
)
=
50
d
a
(
1,6
)
=
30
d
a
(
3,6
)
=
40
d
a
(
11,12
)
=
60
d
a
(
8,10
)
=
50Table 3
Comparison before and after auction using the proposed model.
Vehicle
Before
After
Number of empty load lanes
Percent
Number of loaded lanes
Percent
Awaiting actions
Average empty load rate
Number of empty load lanes
Percent
Number of loaded lanes
Percent
Awaiting actions
Average empty load rate
1
1
17%
3
50%
2
50%
0
0%
6
100%
0
0%
2
0
0%
3
50%
3
50%
1
17%
4
67%
1
33%
3
2
33%
2
33%
2
67%
0
0%
4
67%
2
33%
4
2
33%
4
67%
0
33%
1
17%
4
67%
1
33%
5
2
33%
3
50%
1
50%
1
17%
4
67%
1
33%
6
2
33%
3
50%
1
50%
1
17%
4
67%
1
33%
7
1
17%
3
50%
2
50%
0
17%
5
83%
1
17%
8
–
–
–
–
–
–
1
17%
3
50%
2
50%
9
–
–
–
–
–
–
1
17%
3
50%
2
50%
10
–
–
–
–
–
–
1
17%
3
50%
2
50%
Average
1.43
23.7%
3
50%
1.57
50%
0.7
13.6%
4
66.8%
1.4
33.2%Figure 7
Bidding lanes found using the proposed model.Figure 8
Adjusted transportation plan after bidding consideration.


## 6.2. Analysis about Parameterα Values

Now the influence ofα on the carriers’ decisions will be analyzed. First, we set a different value for α and then calculated the hypothetical case using our proposed model. We then adopted different values for α and listed the results in Table 4. From Table 4, it can be seen that, as α reduces, the profit without likelihood of winning business increases. The optimal bidding strategy was found when α was set to 0.7, as, at this value, the carrier can serve more lanes at higher quotes than at a higher α value. We analyzed this situation as follows: (1) without the likelihood of winning means that there is no competition; therefore, the carrier can choose to serve more profitable lanes at a higher price and gain greater benefit. If the market lacks competition, this bidding strategy could be the better choice for the carrier; (2) a lower α means that the carrier will accept a higher risk of losing the business. At α=0.7, for example, the carrier only requires a possibility that their quoted price is lower than the other carriers and that the cost to the shipper of doing their own transportation is no less than 0.7. Therefore, the computational likelihood of winning the business for the optimal bidding strategy is 0.7282, which is lower than the values in the first two lines in the table and indicates that the optimal bidding strategy has a higher risk of losing the business. (3) Although a lower α and a higher quoted price appear to result in greater benefits to the carrier, the expected profit rise is not as significant as the likelihood of winning the business is reduced. Therefore, in this situation, the carrier has to consider whether it is worth taking the higher risk of losing the business by generating the bid with a higher price.Table 4
Results analysis by adopting differentα values.
α
Computational results
Profits without considering the likelihood of winning
Possibility of winning the business
Expected profits
0.9
78596
0.9931
78054
0.8
83527
0.8521
71173
0.7
93523
0.7282
68103From this, it is possible to deduce the quoted price for the optimal bidding strategy without considering the likelihood of winning the business. Obviously, as the carrier wants to quote as high a price as possible if the competition with other carriers and the shipper’s reactions are not considered, there is no upper bound for the quoted price. Therefore, if it is assumed that a reasonable profit rate for the carrier is20%, a reverse derivation of the quoted price for the optimal bidding lanes can be calculated using the proposed model, as shown in Figure 7. After calculation, the quoted price was found to be 803904, which was higher than the price calculated using the proposed model (733567), and the likelihood of winning the business was found to be 0.5123, which was much lower than that calculated using the proposed model (0.9931). In fact, without considering the activities of the other carriers and the shipper, the carrier’s expected profit was 67108, which was lower than that calculated by our model (78054). The above analysis shows that, by adopting the proposed model, the carrier could quote a competitive price for the set lanes and theoretically gain greater profits.


## 6.3. Test and Analysis of Different Scale Instance

For each scale instance, we ran the program 10 times and calculated the average CPU times, which are listed in Table5. According to Table 5, it can be seen that the proposed approach was able to solve the differently scaled problems in an acceptable time. Using our office computer, the largest scale instance we could deal with had 50 nodes, 30 periods, and 500 auctioned lanes, but larger instances could be tested using cloud computing and a large-scale distributed server, which is the direction of our future research.Table 5
Computational performance of different scale instance.
Problem instance
The number of nodes
The number of periods
The number of auctioned lanes
Population sizeN
IterationT
Time (s)
1
12
6
26
20
50
41.37
2
20
20
100
20
100
198.32
200
20
300
581.23
300
40
500
1149.16
30
100
20
100
237.81
200
20
300
786.56
300
40
500
1321.34
3
30
20
100
20
100
244.73
200
20
300
856.38
300
40
500
1289.34
30
100
20
100
279.62
200
20
300
933.57
300
40
500
1432.86
4
40
20
200
40
200
733.27
300
40
300
1019.81
500
40
500
1473.88
30
200
40
300
1219.46
300
40
500
1519.31
500
100
500
2733.96
5
50
20
200
40
300
1313.28
300
100
500
2736.52
500
100
500
2988.44
30
200
40
300
1447.17
300
100
500
2953.29
500
100
500
3028.63


## 7. Conclusions and Future Research

This paper examined a transportation service procurement BGP from less than full truckload perspective. The major works in this paper were(1) the establishment of mixed integer programming to assist the carrier in constructing optimal bids (bundled lanes) and determine the appropriate price; (2) a consideration of the likelihood of winning business when developing the proposed model; (3) the proposal of an intelligent algorithm based on the PSO to solve the model; and (4) an analysis of the effectiveness of the proposed model and algorithm using hypothetical data sets.Different from previous research, the main contribution of this paper lies in the development of a model and a corresponding algorithm. The model was established from both the carriers and the shippers perspective as transportation service procurement characteristics require the carriers decisions. While higher prices may result in greater profits for the carrier, there is also the risk of losing business, and on the other hand, while lower prices may increase the chance of winning, there may be a loss of potential utility. Therefore, in this model the relationship between the quoted prices and likelihood of winning business is linked. The proposed model was demonstrated from which it was found that it was able to determine the optimal bid (package of lanes) and the bundled price rather than having to sum the prices of each single lane. To solve the proposed model, an intelligent algorithm based on the PSO was proposed. The model and algorithm were tested using hypothetical data sets and were proven to be more efficient than traditional BGP methods. Therefore, the managerial implication is that advice can be given to carriers about how to generate the most profitable bid from the price. Further, using the proposed approach, the carriers are able to take the shipper’s reaction into account and ensure that the likelihood of winning the business is at an acceptable level.However, in this paper, the uncertainty of the auctioned loads was not considered, a problem that may occur in real life situations. As the auction generally occurs before the transportation activities, the auctioned loads may not be accurate. Therefore, taking uncertainty into account could be an important extension of this paper.



---

*Source: 1728512-2018-01-17.xml*