# Multiobjective Combinatorial Auctions in Transportation Procurement

Authors: Joshua Ignatius; Seyyed-Mahdi Hosseini-Motlagh; Mark Goh; Mohammad Mehdi Sepehri; Adli Mustafa; Amirah Rahman
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

This paper presents a multiobjective winner determination combinatorial auction mechanism for transportation carriers to present multiple transport lanes and bundle the lanes as packet bids to the shippers for the purposes of ocean freight. This then allows the carriers to maximize their network of resources and pass some of the cost savings onto the shipper. Specifically, we formulate three multi-objective optimization models (weighted objective model, preemptive goal programming, and compromise programming) under three criteria of cost, marketplace fairness, and the marketplace confidence in determining the winning packages. We develop solutions on the three models and perform a sensitivity analysis to show the options the shipper can use depending on the existing conditions at the point of awarding the transport lanes.


---

## Body

## 1. Introduction

Shippers often rely on an auction or a tendering mechanism to attract the transport carriers to provide cost competitive logistics services on transport lanes either singly or as a bundle. In such an auction of transportation procurement services, the stakeholders often comprise shippers and carriers who attend to an electronic transportation market (ETM), involving a bid preparation stage (see Sheffi [1] for the details). In the maritime industry, a transport lane is treated as a shipping lane used to move a defined number of containers from origin port to destination port. In this situation, the carriers would bid for the right (usually at the lowest cost and with the best delivery time window reliability) to ship consigned goods for the shipper. The shipper has to decide which lanes (either all or part of them) to award to which carrier: the goods can completely be shipped in full and directly from source to destination with one carrier or its partners in the shipping conference or shipped to destination using transshipment ports.Shipping with a carrier using partner transport services naturally raises concerns of the quality of service and reliability of delivery. Sometimes such shipments experience delays, increased cost at the transit container terminals, off-loading of container boxes due to the lack of volume into the destination port, and higher than expected demurrage due to peak season surcharges. All of these affect the track record of the carrier who can offer the lowest price but less than desired quality of service to the shipper [2]. Also, for operational reasons, carriers tend to go into an ETM signaling the number of containers they can transport within a certain volume range so as to justify their cost of operations and achieve the best economies of scale for their and their partner’s network (see [3]).Therefore, given the various operational and business constraints, there exist variations in the auction design. For instance, Forster and Strasser [4] have studied auctions where the shipper opens up a list of individual transport lanes to the carriers to bid and uses a strict price criterion as the primary measure of carrier selection (the winner of the auction). More recently, Sheffi [1] presents a combinatorial auction mechanism whereby shippers request bids for a group(s) of lanes rather than individual transport lanes to eke out better cost efficiencies and economies of scale. A one-shipper to multicarrier network is considered as a combinatorial auction (CA) if the carriers are allowed to submit a combination of individual transport lanes as a packet.To date, combinatorial auctions, conducted effectively, have contributed to cost reduction and mutual satisfaction between the shipper and carriers, as a main source of cost, is the asset repositioning cost that involves a carrier having to relocate its resources (ships) to service a transport lane from one shipper to another [5]. This is observed from the empty backhaul movements when servicing a particular trade lane in the transport network. Nair [6] reports that even the most sophisticated carrier would have some excess capacity. Indeed, the US market contributed to US$165 billion in total estimated industry loss due to capacity inefficiencies [7].Under a CA setting, a shipper typically offers a series of lanes that they wish to “buy” separately, and each carrier will run their carrier routing optimization to determine the preferred packages that they can offer. In order to be competitive, each carrier would rationally try to offer the lowest price possible subject to operational and capacity constraints. Ideally, the bids tendered should minimize the carriers’ empty load movements throughout its own network [8, 9] and reduce the need to reposition the ships to another port for the pick-up of more committed freight. Cost uncertainty and shipment uncertainty are also covered in the literature of CA (see [10, 11]).The CA approach has been noted to also allow a carrier to complement its network and pass of the cost savings to the shipper. For instance, in Table1, consider a case where a carrier is interested to bid for lanes P
1
a, P
3
a, P
5
a, and P
7
a. In a single auction structure, the carrier has to place each interested lane (P
1
a, P
3
a, P
5
a, or P
7
a) as a bid. If lane P
7
a is not part of the carrier’s winning bid, then the carrier will have to return from location J to its origin P with an empty load, thus incurring higher transportation costs. Contrastingly, in a combinatorial auction market, the carrier can place a bid for lane P
7
b and refuse the entire package if one of the lanes is not part of the winning bid.Table 1
Simple versus combinatorial auction.
Lanes offered
Carrier’s bids in simple auction
Carrier’s bids in CA
P1a(P→K)P2a (K→P)P3a(K→S)P4a (S→K)P5a(S→J)P6a (J→S)P7a(J→P)
P1b(P→ K, K→P)P2b(K→ S, S→J)        P3b (P→K, K→S, S→K, K→P)P4b (S→J, J→S)P5b (K→S, S→J, J→S, S→K)P6b (P→K, K→S, S→ J, J→S, S→K, K→P) P7b (P→K, K→S, S→J, J→P)Thus, the rationale for bidding based on packages is based on the complementarity property, where the package is valued more than the sum of the individual lanes to the carrier. In addition, by allowing for carriers the option of denying an entire package when one of their lanes is not accepted in the bidding transaction eliminates a carrier’s asset repositioning costs, and in return for this the carrier typically offers shippers more competitive rates. This form of business transaction between the shipper and the carriers is often facilitated by an internet-based ETM. The auctioneer can be the shipper or any third party service provider. To date, combinatorial auctions for transportation procurement focus on a single objective cost minimization model. In this paper, we propose to include two other important criteria in the long-term sustainability of an auction market. These are (i) marketplace fairness and (ii) the shipper’s confidence of the carrier’s ability to provide the requisite service given that not all carriers have their own transit terminals and thus suffer from varying service times at the transit points, that is, quality of service. To handle these objectives, we will apply three multiobjective decision-making models to compare the solution approaches.The rest of the paper is organized as follows. Section2 provides the relevant review on multiobjective optimization models: the weighted objective, goal programming, and compromise programming. Section 3 presents the mathematical programming framework for the three models in the context of transportation procurement. The data preparation and test procedures are provided in Section 4. Section 5 discusses the solutions and concludes the paper.


## 2. Multiobjective Optimization

With conflicting and multiple objectives in an actual real world decision-making context, optimizing a single objective is no longer viable [12]. In the case of combinatorial auctions, the auctioneer usually needs to maintain other objectives for scenario planning. For instance, awarding lane contracts based on cost alone may lead to only a selected few large carriers being chosen as they have the needed capacity and network reach. This prevents other smaller players and other regional players from engaging in the marketplace. Other optimizing considerations include the quality of service and maintaining a ready pool of carriers through strategic resource allocation of containers. We now review some multiobjective mathematical programming techniques that we will use for this paper.


### 2.1. Weighted Objectives Model (WOM)

The WOM, considered to be the oldest method representing multiple objectives in a linear programming model [13], seeks to approximate the efficient set and provides a crude way of generating efficient solutions by varying their weights. Consider
(1)
max
⁡
Z
=
∑
i
=
1
J
w
i
f
i
(
x
)
s
.
t
.
x
∈
X
,
where w
i is the positive weight of the objective f
i
(
x
).


### 2.2. Goal Programming (GP)

Goal programming extends the basic LP and keeps part of the kernel of MODM. It guides a decision maker to attain a closest solution possible to the various conflicting objectives [14]. Today, GP techniques have been applied across disciplines, ranging from vendor selection [15] to berth allocation in ports [16]. Metaheuristic approaches have been used to solve the GP routines such as simulated annealing, genetic algorithms, and Tabu search [17]. Since GP allows one to adjust the target values and/or weights flexibly, it can also be used for scenario planning. This is especially useful in the context of CA especially for the shipper who may wish to reshift focus on other nonprice considerations after the bid exercise. Two forms of GP exist, weighted and preemptive. The former assigns weights to unwanted deviations, thus effectively allowing the decision maker to state their relative importance of the objectives. The objective is singly minimized as an Archimedean sum as follows:
(2)
min
⁡
Z
=
∑
i
=
1
m
w
i
-
d
i
-
+
w
i
+
d
i
+
s
.
t
.
f
i
(
x
)
+
d
i
-
-
d
i
+
=
b
i
,
i
=
1,2
,
3
,
…
,
x
∈
X
,
where f
i
(
x
) is the linear objective function with a target value of b
i, while w
i
- and w
i
+ are nonzero weights attached to the respective positive d
i
+ (overachievement) and negative deviations d
i
- (underachievement). This technique minimizes the sum of deviations from the target value.The second goal formulation minimizes deviations hierarchically,P
1
(
x
)
>
P
2
(
x
)
>
⋯
>
P
s
(
x
). This is akin to optimizing fully a goal that has a higher importance before moving to the next goal. In short, the goal of a higher order priority is infinitely more important than the goals of lower priority. Thus, the objective function in (2) can be replaced with
(3)
min
⁡
Z
=
∑
i
=
1
J
P
s
(
w
i
-
d
i
-
+
w
i
+
d
i
+
)
.


### 2.3. Compromise Programming (CP)

CP models conflicting objectives as a distance minimizing function so as to reach a point nearest to the ideal solution. The ideal solution is gathered by optimizing each objective with the hard constraints individually, while ignoring all other objectives. The CP approach can be viewed as an extension of the GP technique with some modifications to the deviation variables while fixing the root at unity [18]. The mathematical model is as follows:
(4)
min
⁡
Z
=
∑
i
=
1
m
[
w
i
p
(
b
i
-
f
i
(
x
)
Δ
i
)
p
]
1
/
p
s
.
t
.
x
∈
X
,
where w
i
p are the nonpreemptive weights of the pth metric, while Δ
i
=
f
i
+
(
x
)
-
f
i
-
(
x
) are the normalizing constants obtained by the distance between the maximum and minimum anchors for each objective function i. Tamiz et al. [12] show that, for p
=
α, it is equivalent to solving
(5)
min
⁡
α
s
.
t
.
α
≥
w
i
Δ
i
[
b
i
*
-
f
i
(
x
)
]
,
i
=
1,2
,
…
,
x
∈
X
,
where b
i
* is obtained by maximizing f
i
(
x
).


## 2.1. Weighted Objectives Model (WOM)

The WOM, considered to be the oldest method representing multiple objectives in a linear programming model [13], seeks to approximate the efficient set and provides a crude way of generating efficient solutions by varying their weights. Consider
(1)
max
⁡
Z
=
∑
i
=
1
J
w
i
f
i
(
x
)
s
.
t
.
x
∈
X
,
where w
i is the positive weight of the objective f
i
(
x
).


## 2.2. Goal Programming (GP)

Goal programming extends the basic LP and keeps part of the kernel of MODM. It guides a decision maker to attain a closest solution possible to the various conflicting objectives [14]. Today, GP techniques have been applied across disciplines, ranging from vendor selection [15] to berth allocation in ports [16]. Metaheuristic approaches have been used to solve the GP routines such as simulated annealing, genetic algorithms, and Tabu search [17]. Since GP allows one to adjust the target values and/or weights flexibly, it can also be used for scenario planning. This is especially useful in the context of CA especially for the shipper who may wish to reshift focus on other nonprice considerations after the bid exercise. Two forms of GP exist, weighted and preemptive. The former assigns weights to unwanted deviations, thus effectively allowing the decision maker to state their relative importance of the objectives. The objective is singly minimized as an Archimedean sum as follows:
(2)
min
⁡
Z
=
∑
i
=
1
m
w
i
-
d
i
-
+
w
i
+
d
i
+
s
.
t
.
f
i
(
x
)
+
d
i
-
-
d
i
+
=
b
i
,
i
=
1,2
,
3
,
…
,
x
∈
X
,
where f
i
(
x
) is the linear objective function with a target value of b
i, while w
i
- and w
i
+ are nonzero weights attached to the respective positive d
i
+ (overachievement) and negative deviations d
i
- (underachievement). This technique minimizes the sum of deviations from the target value.The second goal formulation minimizes deviations hierarchically,P
1
(
x
)
>
P
2
(
x
)
>
⋯
>
P
s
(
x
). This is akin to optimizing fully a goal that has a higher importance before moving to the next goal. In short, the goal of a higher order priority is infinitely more important than the goals of lower priority. Thus, the objective function in (2) can be replaced with
(3)
min
⁡
Z
=
∑
i
=
1
J
P
s
(
w
i
-
d
i
-
+
w
i
+
d
i
+
)
.


## 2.3. Compromise Programming (CP)

CP models conflicting objectives as a distance minimizing function so as to reach a point nearest to the ideal solution. The ideal solution is gathered by optimizing each objective with the hard constraints individually, while ignoring all other objectives. The CP approach can be viewed as an extension of the GP technique with some modifications to the deviation variables while fixing the root at unity [18]. The mathematical model is as follows:
(4)
min
⁡
Z
=
∑
i
=
1
m
[
w
i
p
(
b
i
-
f
i
(
x
)
Δ
i
)
p
]
1
/
p
s
.
t
.
x
∈
X
,
where w
i
p are the nonpreemptive weights of the pth metric, while Δ
i
=
f
i
+
(
x
)
-
f
i
-
(
x
) are the normalizing constants obtained by the distance between the maximum and minimum anchors for each objective function i. Tamiz et al. [12] show that, for p
=
α, it is equivalent to solving
(5)
min
⁡
α
s
.
t
.
α
≥
w
i
Δ
i
[
b
i
*
-
f
i
(
x
)
]
,
i
=
1,2
,
…
,
x
∈
X
,
where b
i
* is obtained by maximizing f
i
(
x
).


## 3. Modelling the Transportation Procurement Problem

We now model the combinatorial auction transportation procurement problem that supports multiple lanes, multiple packages, and multiple bidders, whereby the shipper attracts bids for a set of lanes as single packages that have different prices for each unit of volume in each lane (origin-destination). The volumes submitted for each package varies according to the carriers’ resource capacities. We introduce the following notation.


### 3.1. Indices

I:
Set of shipping origins
J:
Set of shipping destinations
K:
Set of packages
C:
Set of carriers.


### 3.2. Parameters

The set of bid bundles,B
k
c, can be specified as a 4-tuple (
a
k
c
,
p
k
c
,
L
k
c
,
U
k
c
), where(i)
a
k
c
=
(
a
c
11
k
,
…
,
a
c
i
j
k
,
…
,
a
c
m
n
k
) with a
k
c
∈
(
ℝ
+
)
m
×
n
:
a
c
i
j
k is the load volume per unit time (week), received from carrier c on transport lane from origin i to destination j, that are being bid out as part of package k,
(ii)
p
k
c
=
(
p
c
11
k
,
…
,
p
c
i
j
k
,
…
,
p
c
m
n
k
) with p
k
c
∈
(
ℝ
+
)
m
×
n
:
p
c
i
j
k is the bid price per load on lane i to j, received from carrier c as part of package bid k,
(iii)
L
k
c
=
(
L
c
11
k
,
…
,
L
c
i
j
k
,
…
,
L
c
m
n
k
) with L
k
c
∈
(
ℝ
+
)
m
×
n
:
L
c
i
j
k is the lower bound in loads on lane i to j, that carrier c is willing to accept as part of package bid k,
(iv)
U
k
c
=
(
U
c
11
k
,
…
,
U
c
i
j
k
,
…
,
U
c
m
n
k
) with U
k
c
∈
(
ℝ
+
)
m
×
n
:
U
c
i
j
k is the upper bound in loads on lane i to j, that carrier c is willing to accept as part of package bid k.Each bundle bid B
k
c is a placement order, that is, services that are to be sold by the auctioneer.


### 3.3. Decision Variables

We define the decision variable corresponding to each lane asx
c
i
j
k, where x
c
i
j
k is fraction of load per time unit (week), on lane i to j from carrier c on package bid k.Subsequently, each package is denoted asy
k
c, where y
k
c denotes that if carrier c is assigned package bid k, then y
k
c
=
1; otherwise, y
k
c
=
0.


### 3.4. The Model Formulation

We seek to simultaneously minimize cost, maximize marketplace fairness, and maximize shipper’s confidence.Cost Objective. The total cost of the accepted bids is minimized as
(6)
f
1
(
x
)
=
Min
⁡
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
p
c
i
j
k
a
c
i
j
k
x
c
i
j
k
.Marketplace Fairness Objective. The total number of accepted packages is maximized as
(7)
f
2
(
x
)
=
Max
⁡
∑
c
=
1
seller
∑
k
=
1
package
y
k
c
.Marketplace Confidence Objective. The difference between the lower bound volume sought by the carrier and the upper bound volume sought by the auctioneer is minimized as follows:
(8)
f
3
(
x
)
=
Min
⁡
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
i
j
k
|
y
k
c
-
x
c
i
j
k
|
.Supply-Demand Constraint. The total volume accepted as winning packages must be no less than the volume auctioned; that is,
(9)
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
i
j
k
x
c
i
j
k
≥
∑
k
=
1
destination
∑
i
=
1
origin
a
i
j
k
x
i
j
k
∀
i
∈
origin
,
j
∈
destination
.Transactional Constraints. Equation (10) allows the auctioneer to transact the entire package within a particular volume range specified by the carriers. The variable y
c
1
k in (10) ensures that the carrier must offer all lanes within the package, if one of the lanes is approved as a winning lane by the auctioneer. Consider
(10)
-
M
y
k
c
+
a
c
i
j
k
x
c
i
j
k
≤
0
∀
c
∈
seller
,
k
∈
package
,
i
∈
origin
,
j
∈
destination
,
-
L
B
c
i
j
k
y
k
c
+
a
c
i
j
k
x
c
i
j
k
≤
0
∀
c
∈
seller
,
k
∈
package
,
i
∈
origin
,
j
∈
destination
,
U
B
c
i
j
k
y
k
c
+
a
c
i
j
k
x
c
i
j
k
≤
0
∀
c
∈
seller
,
k
∈
package
,
i
∈
origin
,
j
∈
destination
.Business Guarantee Constraint. A shipper might not want to rely too heavily on a small number of winning carriers. In the longer term, it might be prudent for a shipper to ensure that the amount of traffic won by a carrier is within a certain bound. This will create a higher potential for carriers to revisit the marketplace to bid. The scope of the carrier set coverage is measured by the amount of volume (loads) won. The constraints below ensure that all carriers are awarded business within some preset volume bounds. Consider
(11)
Min
⁡
Value
c
≤
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
p
c
i
j
k
a
c
i
j
k
x
c
i
j
k
≤
Max
⁡
Value
c
.Carrier Base Size Constraints. This is an extension to the business guarantee constraint, with the restriction on the number of winning carriers for each lane. The system-based (or hard) approach adds the following constraints to limit the number of carriers assigned at the lane level:
(12)
-
M
w
c
i
+
a
c
i
j
k
x
c
i
j
k
≤
0
∀
c
∈
seller
,
k
∈
package
,
i
∈
origin
,

j
∈
destination
,





(13)
∑
c
=
1
seller
w
i
c
≤
L
i
∀
i
∈
origin
,
(14)
-
M
z
c
+
a
c
i
j
k
x
c
i
j
k
≤
0
∀
c
∈
seller
,
k
∈
package
,
i
∈
origin
,
j
∈
destination
,
(15)
∑
c
=
1
seller
z
c
≤
S
.
The number of carriers winning the right to haul at origin i is denoted as L
i in (13), while S is the system limit of winning carriers for the entire auction.Simple Reload Bids Constraint. This constraint denotes that the ratio of outbound volume to inbound volume must be at least β
j
c. Consider
(16)
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
j
i
k
c
c
j
i
k
≥
β
c
j
*
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
i
j
k
x
c
i
j
k
∀
c
,
k
.Nonnegativity and Binary Constraints. As the decision variables are expressed as percentages, we define x
c
i
j
k in (17) as real numbers. Carrier c is assigned package bid k when c
y
k
=
1 (or 0 otherwise) (18). Carrier c is assigned to origin i when w
i
c
=
1(or 0 else) (19). Also, carrier c is assigned to a network when z
c
i
=
1 (or 0 otherwise) (20). Consider
(17)
x
c
i
j
k
∈
R
+
,
(18)
y
k
c
=
{
0
,
1
}
,
(19)
w
i
c
=
{
0
,
1
}
,
(20)
z
c
=
{
0
,
1
}
.
We now present the three models for the CA transport procurement problem: WOM, preemptive GP, and CP.WOM. Consider
(21)
Min
⁡
w
1
(
∑
c
=
1
seller
∑
k
=
1
packag
∑
j
=
1
destination
∑
i
=
1
origin
p
c
i
j
k
a
c
i
j
k
x
c
i
j
k
)
Min
⁡
-
w
2
(
∑
c
=
1
seller
∑
k
=
1
package
y
k
c
)
Min
⁡
+
w
3
(
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
i
j
k
|
y
k
c
-
x
c
i
j
k
|
)
s
.
t
.
(
9
)

–

(
20
)
.Preemptive Goal Model (PGM). Consider
(22)
Min
⁡
P
1
d
1
+
+
P
2
d
2
-
+
P
3
d
3
+
,
P
1
>
P
2
>
P
s
(
x
)
Min
⁡
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
p
c
i
j
k
a
c
i
j
k
x
c
i
j
k
+
d
1
-
-
d
1
+
Min
⁡
=
Cost
Goal
Min
⁡
∑
c
=
1
seller
∑
k
=
1
package
y
k
c
+
d
2
-
-
d
2
+
Min
⁡
=
Marketplace
Reputation
Goal
Min
⁡
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
i
j
k
|
y
k
c
-
x
c
i
j
k
|
+
d
3
-
-
d
3
+
Min
⁡
=
Shipper's
Confidence
Goal
s
.
t
.
(
9
)

–

(
20
)
,
where d
i
- and d
i
+ are the underachievement and overachievement deviations of the ith goal.CPM. The combinatorial auction transportation procurement model in a CP is as follows:
(23)
Min
⁡
{
w
1
(
(
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
p
c
i
j
k
a
c
i
j
k
x
c
i
j
k
-
c
i
*
)
(
c
i
*
)
-
1
)
P
Min
⁡
-
w
2
(
∑
c
=
1
seller
∑
k
=
1
package
y
k
c
-
r
i
*
r
i
*
)
P
Min
⁡
+
w
3
(
(
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
i
j
k
|
y
k
c
-
x
c
i
j
k
|
-
s
i
*
(
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
i
j
k
|
y
k
c
-
x
c
i
j
k
|
)
×
(
s
i
*
)
-
1
)
P
}
1
/
P
s
.
t
.
(
9
)

–

(
20
)
,
where p
=
1,2
,
…
,
∞. The ideal values of cost, marketplace fairness, and shipper’s confidence are gathered from c
i
*
=
min
⁡
⁡
f
1
(
x
), r
i
*
=
max
⁡
⁡
f
2
(
x
) and s
i
*
=
min
⁡
⁡
f
3
(
x
), respectively (see (6)–(8)). The larger deviations receive greater importance as p increases. This is the penalizing effect placed on larger deviations from their respective ideal solutions. The compromise solutions satisfy 1
≤
p
≤
∞. The solution at p
=
∞ indicates that the largest deviation among all objectives is the most dominant in the optimal solution’s distance function.


## 3.1. Indices

I:
Set of shipping origins
J:
Set of shipping destinations
K:
Set of packages
C:
Set of carriers.


## 3.2. Parameters

The set of bid bundles,B
k
c, can be specified as a 4-tuple (
a
k
c
,
p
k
c
,
L
k
c
,
U
k
c
), where(i)
a
k
c
=
(
a
c
11
k
,
…
,
a
c
i
j
k
,
…
,
a
c
m
n
k
) with a
k
c
∈
(
ℝ
+
)
m
×
n
:
a
c
i
j
k is the load volume per unit time (week), received from carrier c on transport lane from origin i to destination j, that are being bid out as part of package k,
(ii)
p
k
c
=
(
p
c
11
k
,
…
,
p
c
i
j
k
,
…
,
p
c
m
n
k
) with p
k
c
∈
(
ℝ
+
)
m
×
n
:
p
c
i
j
k is the bid price per load on lane i to j, received from carrier c as part of package bid k,
(iii)
L
k
c
=
(
L
c
11
k
,
…
,
L
c
i
j
k
,
…
,
L
c
m
n
k
) with L
k
c
∈
(
ℝ
+
)
m
×
n
:
L
c
i
j
k is the lower bound in loads on lane i to j, that carrier c is willing to accept as part of package bid k,
(iv)
U
k
c
=
(
U
c
11
k
,
…
,
U
c
i
j
k
,
…
,
U
c
m
n
k
) with U
k
c
∈
(
ℝ
+
)
m
×
n
:
U
c
i
j
k is the upper bound in loads on lane i to j, that carrier c is willing to accept as part of package bid k.Each bundle bid B
k
c is a placement order, that is, services that are to be sold by the auctioneer.


## 3.3. Decision Variables

We define the decision variable corresponding to each lane asx
c
i
j
k, where x
c
i
j
k is fraction of load per time unit (week), on lane i to j from carrier c on package bid k.Subsequently, each package is denoted asy
k
c, where y
k
c denotes that if carrier c is assigned package bid k, then y
k
c
=
1; otherwise, y
k
c
=
0.


## 3.4. The Model Formulation

We seek to simultaneously minimize cost, maximize marketplace fairness, and maximize shipper’s confidence.Cost Objective. The total cost of the accepted bids is minimized as
(6)
f
1
(
x
)
=
Min
⁡
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
p
c
i
j
k
a
c
i
j
k
x
c
i
j
k
.Marketplace Fairness Objective. The total number of accepted packages is maximized as
(7)
f
2
(
x
)
=
Max
⁡
∑
c
=
1
seller
∑
k
=
1
package
y
k
c
.Marketplace Confidence Objective. The difference between the lower bound volume sought by the carrier and the upper bound volume sought by the auctioneer is minimized as follows:
(8)
f
3
(
x
)
=
Min
⁡
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
i
j
k
|
y
k
c
-
x
c
i
j
k
|
.Supply-Demand Constraint. The total volume accepted as winning packages must be no less than the volume auctioned; that is,
(9)
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
i
j
k
x
c
i
j
k
≥
∑
k
=
1
destination
∑
i
=
1
origin
a
i
j
k
x
i
j
k
∀
i
∈
origin
,
j
∈
destination
.Transactional Constraints. Equation (10) allows the auctioneer to transact the entire package within a particular volume range specified by the carriers. The variable y
c
1
k in (10) ensures that the carrier must offer all lanes within the package, if one of the lanes is approved as a winning lane by the auctioneer. Consider
(10)
-
M
y
k
c
+
a
c
i
j
k
x
c
i
j
k
≤
0
∀
c
∈
seller
,
k
∈
package
,
i
∈
origin
,
j
∈
destination
,
-
L
B
c
i
j
k
y
k
c
+
a
c
i
j
k
x
c
i
j
k
≤
0
∀
c
∈
seller
,
k
∈
package
,
i
∈
origin
,
j
∈
destination
,
U
B
c
i
j
k
y
k
c
+
a
c
i
j
k
x
c
i
j
k
≤
0
∀
c
∈
seller
,
k
∈
package
,
i
∈
origin
,
j
∈
destination
.Business Guarantee Constraint. A shipper might not want to rely too heavily on a small number of winning carriers. In the longer term, it might be prudent for a shipper to ensure that the amount of traffic won by a carrier is within a certain bound. This will create a higher potential for carriers to revisit the marketplace to bid. The scope of the carrier set coverage is measured by the amount of volume (loads) won. The constraints below ensure that all carriers are awarded business within some preset volume bounds. Consider
(11)
Min
⁡
Value
c
≤
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
p
c
i
j
k
a
c
i
j
k
x
c
i
j
k
≤
Max
⁡
Value
c
.Carrier Base Size Constraints. This is an extension to the business guarantee constraint, with the restriction on the number of winning carriers for each lane. The system-based (or hard) approach adds the following constraints to limit the number of carriers assigned at the lane level:
(12)
-
M
w
c
i
+
a
c
i
j
k
x
c
i
j
k
≤
0
∀
c
∈
seller
,
k
∈
package
,
i
∈
origin
,

j
∈
destination
,





(13)
∑
c
=
1
seller
w
i
c
≤
L
i
∀
i
∈
origin
,
(14)
-
M
z
c
+
a
c
i
j
k
x
c
i
j
k
≤
0
∀
c
∈
seller
,
k
∈
package
,
i
∈
origin
,
j
∈
destination
,
(15)
∑
c
=
1
seller
z
c
≤
S
.
The number of carriers winning the right to haul at origin i is denoted as L
i in (13), while S is the system limit of winning carriers for the entire auction.Simple Reload Bids Constraint. This constraint denotes that the ratio of outbound volume to inbound volume must be at least β
j
c. Consider
(16)
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
j
i
k
c
c
j
i
k
≥
β
c
j
*
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
i
j
k
x
c
i
j
k
∀
c
,
k
.Nonnegativity and Binary Constraints. As the decision variables are expressed as percentages, we define x
c
i
j
k in (17) as real numbers. Carrier c is assigned package bid k when c
y
k
=
1 (or 0 otherwise) (18). Carrier c is assigned to origin i when w
i
c
=
1(or 0 else) (19). Also, carrier c is assigned to a network when z
c
i
=
1 (or 0 otherwise) (20). Consider
(17)
x
c
i
j
k
∈
R
+
,
(18)
y
k
c
=
{
0
,
1
}
,
(19)
w
i
c
=
{
0
,
1
}
,
(20)
z
c
=
{
0
,
1
}
.
We now present the three models for the CA transport procurement problem: WOM, preemptive GP, and CP.WOM. Consider
(21)
Min
⁡
w
1
(
∑
c
=
1
seller
∑
k
=
1
packag
∑
j
=
1
destination
∑
i
=
1
origin
p
c
i
j
k
a
c
i
j
k
x
c
i
j
k
)
Min
⁡
-
w
2
(
∑
c
=
1
seller
∑
k
=
1
package
y
k
c
)
Min
⁡
+
w
3
(
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
i
j
k
|
y
k
c
-
x
c
i
j
k
|
)
s
.
t
.
(
9
)

–

(
20
)
.Preemptive Goal Model (PGM). Consider
(22)
Min
⁡
P
1
d
1
+
+
P
2
d
2
-
+
P
3
d
3
+
,
P
1
>
P
2
>
P
s
(
x
)
Min
⁡
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
p
c
i
j
k
a
c
i
j
k
x
c
i
j
k
+
d
1
-
-
d
1
+
Min
⁡
=
Cost
Goal
Min
⁡
∑
c
=
1
seller
∑
k
=
1
package
y
k
c
+
d
2
-
-
d
2
+
Min
⁡
=
Marketplace
Reputation
Goal
Min
⁡
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
i
j
k
|
y
k
c
-
x
c
i
j
k
|
+
d
3
-
-
d
3
+
Min
⁡
=
Shipper's
Confidence
Goal
s
.
t
.
(
9
)

–

(
20
)
,
where d
i
- and d
i
+ are the underachievement and overachievement deviations of the ith goal.CPM. The combinatorial auction transportation procurement model in a CP is as follows:
(23)
Min
⁡
{
w
1
(
(
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
p
c
i
j
k
a
c
i
j
k
x
c
i
j
k
-
c
i
*
)
(
c
i
*
)
-
1
)
P
Min
⁡
-
w
2
(
∑
c
=
1
seller
∑
k
=
1
package
y
k
c
-
r
i
*
r
i
*
)
P
Min
⁡
+
w
3
(
(
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
i
j
k
|
y
k
c
-
x
c
i
j
k
|
-
s
i
*
(
∑
c
=
1
seller
∑
k
=
1
package
∑
j
=
1
destination
∑
i
=
1
origin
a
c
i
j
k
|
y
k
c
-
x
c
i
j
k
|
)
×
(
s
i
*
)
-
1
)
P
}
1
/
P
s
.
t
.
(
9
)

–

(
20
)
,
where p
=
1,2
,
…
,
∞. The ideal values of cost, marketplace fairness, and shipper’s confidence are gathered from c
i
*
=
min
⁡
⁡
f
1
(
x
), r
i
*
=
max
⁡
⁡
f
2
(
x
) and s
i
*
=
min
⁡
⁡
f
3
(
x
), respectively (see (6)–(8)). The larger deviations receive greater importance as p increases. This is the penalizing effect placed on larger deviations from their respective ideal solutions. The compromise solutions satisfy 1
≤
p
≤
∞. The solution at p
=
∞ indicates that the largest deviation among all objectives is the most dominant in the optimal solution’s distance function.


## 4. Solution and Analysis

The following steps detail our dataset generation procedure and analysis.Step 1 (generate shipper’s lane offerings).
The condition of CA requires each shipper to put the amount of volume for a set of lanes on offer in separate auction markets. We set[
S
+
]
1
×
n as the shipper’s volume required in a CA of n lanes. The maximum amount of loads available for carriers to bid on each i
-
j origin-destination (lane) or cell a
0
i
j
∈
[
S
+
]
1
×
n is randomly generated from [
1000,10000
] using a uniform distribution.Step 2 (generate carriers’ bids).
We assume that the carriers are able to view the total available volumes for each lane and set their bids accordingly. For our simulated carrier’s amount of loads, we generate a seed numberα between [
1,100
] for each lane. A value of α greater than 50 enforces the rule of empty cells and signifies the refusal of a carrier to accept a particular lane. If α
<
50, another random number β is generated between [
0.6,1
], where β
*
a
0
i
j
=
a
1
i
j and a
c
1
i
j
∈
[
C
+
]
m
×
n correspond to the amount of loads offered by the mth carrier of the nth lane.Step 3 (solving routines).
The buy and sell prices of each lane are fixed at $3 and $1 per unit of load, respectively. The dataset is solved by WOM, PGM, and CPM, respectively, on Lingo version 8.Step 4 (results and sensitivity analysis).
Table2 shows the results, where a series of 8 tests were run. The ideal values of each objective are obtained by analyzing each objective independently, while keeping all the constraints in the model. We observe that the model that optimises the cost yields the lowest cost ($1166.5) out of all models tested. This trend continues with models that optimise marketplace fairness and shipper’s confidence respectively yielding the best result for marketplace fairness (100) and shipper’s confidence (0), when compared with other models. We define shipper’s confidence to be the distance between the carriers’ bid volume and the shipper’s request. The value of 0 indicates no distance and denotes that all requested volumes by shipper can be met.Table 2
Results experimental runs.
Test
Model
Cost ($)
Marketplace fairness
Shipper’s confidence
1
Ideal cost
1166.50
4
1583.8
2
Ideal marketplace fairness
25891.76
100
27242.2
3
Ideal shipper’s confidence
6733.84
34
0
4
Preemptive GP
1296.11
4
737.57
5
Equal weight
1945.05
12
2783
CP (equal weights)
6
p
=
1
4414.44
27
2308
7
p
=
2
1539.32
5
2038
8
p
=
∞
1294.41
4
747.55In the PGM, the preemptive weights are specified in the following order of importance: cost, marketplace fairness, and shipper’s confidence. Here, the cost value is close to the ideal cost as this objective was stated to be infinitely more important than the other objectives. The value of marketplace fairness in Test 4 is the same as Test 1. However, the difference in shipper’s confidence is expected as its inclusion as an objective renders that cost will be sacrificed by1296.11
-
1166.50
=
$
129.61. Thus, in considering the 3 objectives hierarchically, the feasible solution sacrificed in cost was passed onto satisfying shipper’s confidence. This can be seen from the reduced unawarded volume of 737.57 (Test 4) from 1583.8 (Test 1).In Test 5, we formulated a weighted-objectives model withw
1
=
w
2
=
w
3
=
1
/
3 to optimize a set of objectives simultaneously with the same priority for all objectives.A sensitivity analysis is conducted on the WOM by varying the weights of each objective while the other 2 objectives are restricted to sharing the remainder weights equally (Tables3–5). The results of the WOM model are also compared directly against the CP model, since the weights of the three objectives are standardized to be equal across the two techniques. It is observed that the CP method dominates on cost and shipper’s confidence. The CPM solution is obtained when p is set to ∞. Further, as p
→
∞, the cost and shipper’s confidence objectives improve at the expense of marketplace fairness (Table 2, Tests 6 to 8). However, the WOM results are not necessarily inferior to the CPM as the shipper now can now choose between the solutions of Test 5 or Test 8. Test 5 produces 12 winning bids, while Test 8 produces 4 winning bids. If all 12 winning bids are won by a single carrier in Test 5, but the 4 winning bids of Test 8 are won by different carriers, the shipper may strategically select the CPM solution. On the other hand, if some of the winning bids in Test 5 are won by a prominent carrier that is not part of the winning carrier in Test 8, the shipper may opt for the Test 5 WOM solution instead, to keep the service relationship intact as much as possible.Table 3
Varying cost objective weights: WOM method.
Weights
Cost
1
0.9
0.8
0.7
0.6
0.5
0.4
0.333
0.3
0.2
0.1
0
Marketplace fairness
0
0.05
0.1
0.15
0.2
0.25
0.3
0.333
0.35
0.4
0.45
0.5
Marketplace confidence
0
0.05
0.1
0.15
0.2
0.25
0.3
0.333
0.35
0.4
0.45
0.5
Values
Cost
1166.496
1166.496
1166.496
1166.496
1166.496
1166.496
1237.42
1945.05
2659.86
7582.31
30528.37
30528.37
Marketplace fairness
4
4
4
4
4
4
5
12
18
39
100
100
Marketplace confidence
1583.8
1583.8
1583.8
1583.8
1583.8
1583.8
1692.4
2783
3823.4
1.09
E
-
04
0
0Table 4
Varying marketplace fairness weights: WOM method.
Weights
Cost
0
0.05
0.1
0.15
0.2
0.25
0.3
0.333
0.35
0.4
0.45
0.5
Marketplace fairness
1
0.9
0.8
0.7
0.6
0.5
0.4
0.333
0.3
0.2
0.1
0
Marketplace confidence
0
0.05
0.1
0.15
0.2
0.25
0.3
0.333
0.35
0.4
0.45
0.5
Values
Cost
25891.76
24422.7
24422.7
24422.7
17523.09
7371.432
3894
1945.048
1426.2
1166.496
1166.496
1166.496
Marketplace fairness
100
100
100
100
82
45
27
12
7
4
4
4
Marketplace confidence
27242.2
35824.8
35824.8
35824.8
25687.2
10808.2
5557.6
2783
1970.8
1583.8
1583.8
1583.8Table 5
Varying marketplace confidence weights: WOM method.
Weights
Cost
0
0.05
0.1
0.15
0.2
0.25
0.3
0.333
0.35
0.4
0.45
0.5
Marketplace fairness
0
0.05
0.1
0.15
0.2
0.25
0.3
0.333
0.35
0.4
0.45
0.5
Marketplace confidence
1
0.9
0.8
0.7
0.6
0.5
0.4
0.333
0.3
0.2
0.1
0
Values
Cost
6733.84
2001.91
2001.91
2001.91
2001.91
2001.91
1950.118
1945.048
2170.84
2408.288
2532.848
3047.688
Marketplace fairness
34
100
100
100
100
100
11
12
14
16
17
21
Marketplace confidence
0
0
0
0
0
0
1846.2
2783
3135.8
3474
3647
4367.8The solutions of Table6 can be compared directly to Table 3, as can be Tables 7 and 4, as well as Tables 8 and 5, respectively. Generally, when the weights for the cost objective are reduced on a 0.05 step decrease from 1 to 0, the cost value steadily increases for the CPM. This trend is also true for marketplace confidence. However, the WOM model is insensitive to weight changes when the cost weights are in [
0.5,1
]. The same pattern is found for marketplace fairness and shipper’s confidence, where varying weights between [
0,0.15
] and [
0.05,0.25
] for the respective objectives did not change the values of those objectives (Tables 4 and 5). The CPM quickly reaches a minimum for marketplace fairness, with a slight change in weights from the maximum 1. Choosing a different P value will alter marketplace fairness. Thus, the WOM can provide solutions quickly for each weight variation. However, the CPM can provide many solutions for the same weight variations, albeit having to vary the parameter p.Table 6
Varying cost objective weights: CP method.
Weights
Cost
1
0.9
0.8
0.7
0.6
0.5
0.4
0.333
0.3
0.2
0.1
0
Marketplace fairness
0
0.05
0.1
0.15
0.2
0.25
0.3
0.333
0.35
0.4
0.45
0.5
Marketplace confidence
0
0.05
0.1
0.15
0.2
0.25
0.3
0.333
0.35
0.4
0.45
0.5
Values
Cost
1166.50
1180.66
1196.14
1213.16
1231.94
1252.78
1276.47
1294.41
1304.21
1336.86
1376.80
9118.12
Marketplace fairness
4
4
4
4
4
4
4
4
4
4
4
38
Marketplace confidence
1583.80
1489.41
1386.14
1272.69
1147.48
1008.55
856.95
747.55
689.88
497.82
273.13
1
E
-
04Table 7
Varying marketplace fairness weights: CP method.
Weights
Cost
0
0.05
0.1
0.15
0.2
0.25
0.3
0.333
0.35
0.4
0.45
0.5
Marketplace fairness
1
0.9
0.8
0.7
0.6
0.5
0.4
0.333
0.3
0.2
0.1
0
Marketplace confidence
0
0.05
0.1
0.15
0.2
0.25
0.3
0.333
0.35
0.4
0.45
0.5
Values
Cost
7637.39
1294.41
1294.41
1294.41
1294.41
1294.41
1294.41
1294.41
1294.41
1294.41
1294.41
1294.41
Marketplace fairness
42
4
4
4
4
4
4
4
4
4
4
4
Marketplace confidence
10459
747.55
747.55
747.55
747.55
747.55
747.55
747.55
747.55
747.55
747.55
747.55Table 8
Varying marketplace confidence weights: CP method.
Weights
Cost
0
0.05
0.1
0.15
0.2
0.25
0.3
0.333
0.35
0.4
0.45
0.5
Marketplace fairness
0
0.05
0.1
0.15
0.2
0.25
0.3
0.333
0.35
0.4
0.45
0.5
Marketplace confidence
1
0.9
0.8
0.7
0.6
0.5
0.4
0.333
0.3
0.2
0.1
0
Values
Cost
9118.12
1412.46
1395.81
1378.23
1358.60
1336.86
1312.61
1294.41
1284.66
1252.78
1214.54
1166.49
Marketplace fairness
38
4
4
4
4
4
4
4
4
4
4
4
Marketplace confidence
1
E
-
04
79.86
167.52
265.17
374.24
497.83
640.46
747.55
805.72
1008.55
1263.51
1583.80


## 5. Conclusions

While research on transportation procurement has benefited from the use of CA, the literature does not explicitly provide model solutions and formulation for the multiobjective context. This may be due to the difficulty in operationalising concepts such as marketplace fairness and shipper’s confidence. This paper treating the MODM problem in the context as a multiobjective optimization model allows the shipper to include nonfinancial carrier selection measures. Future work can consider a service index that can be incorporated and updated from one auction to another to allow carriers to be tracked on performance. Our results suggest that there is no dominant MODM technique. However, this is good for the shipper as shipper now has at its disposal a variety of techniques to compare against when making a final decision on the winner for the auction. Alternatively, the shipper can use the results for a further bargaining process with the carriers. There may be a situation where the shipper intends to use a particular carrier who has a high quality service level but has a higher service cost too. The shipper may then ask the carrier whether it could provide the service at the next lower price. For incorporating a bargaining phase into a CA mechanism, readers may be interested in the work of Huang et al. [19]. Another alternative would be to introduce trust-based mechanism by observing the discrepancy between the results and the services offered. One step further would be to use this as a means to validate the sensitivity results. Trust mechanisms have been used in agent-based research to support decisions made on economic exchange (see [20]). Future work may also include soft computing approaches that allow the shipper to automate and filter the solutions based on other criteria, such as the business relationships.



---

*Source: 951783-2014-02-16.xml*