Project topics and materials
Get Complete Project Material File(s) Now! »
Bidding language for transportation procurement com- binatorial auctions
In an auction, bidders have to formulate bids according to their private prefer-ences, information, and bidding strategies (Nisan & Ronen, 1999). A bidding language in the auction defines the standard way (the format of the communi-cated messages and the interpretation) that the bidders are allowed to formulate their bids. In transportation procurement, it refers to how carriers communicate their true valuation of the lanes, we give three inter-relationships between lanes as defined in Song & Regan (2003a):
Definition 2.1 Denote v(A) as a carrier’s true valuation of a set of lanes A if and only if these lanes are assigned, two disjoint sets of lanes A and B are:
• Complementary: if v(A) + v(B) > v(A [ B);
• Substitutable: if v(A) + v(B) < v(A [ B);
• Additive: if v(A) + v(B) < v(A [ B).
In transportation logistic network, a set of lanes is complementary to another set of lanes when it can refill each others’ empty movements; a set of lanes is substitute to another set of lanes when one of these two sets can be contained by the other one; a set of lanes is additive to another set of lanes when they do not exist connection. For example, a lane from Paris to Lille is a complementary to a lane from Lille to Paris, as they can reduce the empty backhaul; a set of lanes from Paris to Lyon, Lyon to Marseille is a substitute to the direct lane from Paris to Marseille; and the lane from Paris to Lille is additive to the lane from Lyon to Marseille as share no relation.
For CAs, bidders need to make sets of bids for « bundles » of items, where the bid for the different bundles can be either exclusive or non-exclusive. The basic bidding languages of this form are classified and given in Nisan (2000, 2006). Hereafter in this section, we give the most general used bid form in CAs.
Definition 2.2 (Atomic bids) Each bidder can submit a pair (S; p) where S is a subset of the items and p is the price that he is willing to pay for S. Thus the valuation of a set T is v(T ) = p for S T and v(T ) = 0 otherwise. Such a bid is called an atomic bid.
Atomic bids are called single-minded bids in Lehmann et al. (2002). It is clear that many simple bids cannot be represented by this language.
Definition 2.3 (OR bids) Each bidder can submit an arbitrary number of atomic bids, i.e., a collection of pairs (Si; pi), where each Si is a subset of the items, and pi is the maximum price that he is willing to pay for that subset.
Under OR bids, each bidder is willing to obtain any number of disjoint atomic bids for the sum of their respective prices. Thus an OR bid is equivalent to a set of separate atomic bids from different bidders. More formally, for a valuation
v = (S1; p1)OR:::OR(Sk; pk), the value of v(S) is defined to be the maximum over all possible valid collections W , of the value of Pi2W pi, where W is valid if for all i 6= j 2 W; Si \ Sj = ;.
Proposition 2.4 OR bids can represent all bids that don’t have any substitutabil-ities, i.e., those where for all S \ T = ;, v(S [ T ) v(S) + v(T ), and only them.
Definition 2.5 (XOR bids) Each bidder can submit an arbitrary number of pairs (Si; pi), where Si is a subset of the items, and pi is the maximum price that he is willing to pay for that subset. Under XOR bids, each bidder is willing to obtain at most one of these bids. More formally, for a valuation v = (S1; p1)XOR:::XOR(Sk; pk), the value of v(S) is defined to be maxijSi Spi. Proposition 2.6 XOR bids can represent all valuations. XOR is formally defined from Sandholm (2002), and it is widely used in most CAs literature as it can represent OR bids and also those with substitutabilities.
In Nisan (2006), the author also discuss the combinations of OR and XOR to represent more desirable simple valuations. Implicit here is that he is willing to obtain any number of these bids, each for its respectively offered price. Definition 2.8 (XOR of OR bids) Each bidder can submit an arbitrary num-ber of OR bids, as defined above. Implicit here is that he is willing to obtain just one of these bids.
Combinatorial Auctions (CAs) for transportation procurement problem
Over the past two decades, CAs has gained more and more attentions both in theoretical and practical studies (Peter et al., 2006), which allow bidders to bid on combinations of items as a packages instead of bidding only on individual items. The advantage of CAs is that the bidders can fully express their preferences when items are complements and substituents due to the economies of scope and economies of scale, in such a sense, the bidders can generate more profit or save more cost.
While in a competitive transportation procurement system, if carriers can combine multiple lanes as a tour or a continuous move, they can decrease their empty mileage and thereby reduce cost (Chen et al., 2009) or generate greater profits (Chang, 2009; Jothi Basu et al., 2015). Due to the synergies available on the transportation pathways (Triki, 2016; Wang & Wang, 2015; Xu & Huang, 2014a,b), CAs has attracted increasing attentions in transportation procurement as it allows carriers to submit bundle bids that can express their preferences when they group transportation lanes into packages (Sheffi, 2004a; Triki et al., 2014).
In transportation procurement, CAs generally follows a 5-phase procedure (Berger & Bierwirth, 2010), see Figure 2.3:
• Carriers determine request lanes and put them into the auction pool, request lanes are selected based on carriers’ time and truck capacity availability;
• Bid Generation Problem (BGP): Auctioneer (Shipper or Third-party logis-tics – 3PL) generates bundles of requests and shows them to the carriers, a request bundle is generally a feasible path tour respecting each carrier’s resource constraints;
• Bid Generation Problem (BGP): Carriers give their bids for the offered bundles;
• Winner Determination Problem (WDP): Auctioneer allocates bundles to carriers based on their bids;
• Gained profits are distributed among the carriers.
Bidding generation problem for transportation procurement problem
CAs has attracted increasing attention in transportation procurement market because of the synergies ∗ available on the transportation pathways (Triki, 2016; Wang & Wang, 2015; Xu & Huang, 2014a,b) as transportation request lanes can be grouped into packages or bundles of various products (Sheffi, 2004a; Triki et al., 2014), request bundle is defined as a path tour from one location to another.
In the transportation procurement, the carriers’ major goal is to discover and take advantage of inter-dependencies in their transportation operations, and then determine the optimal packages to bid for. A carrier’s pricing decision involves choosing right prices for right transport request bundles in order to maximize his profit, this is known as price-based revenue management (Talluri & Van Ryzin, 2006; Ting* & Tzeng, 2004). It consists two decision making problems as we define as two phases. In first phase, potential tours (bundles, bids of requests) are determined that a carrier could bid for. Each tour is constructed so that all relevant operating constraints can be met, this problem is defined as Bundle Construction Problem (BCP). In second phase, incentive pricing strategies are employed that each carrier could win his desired bids, this problem is defined as Bundle Pricing Problem.
Table of contents :
Acknowledgements
Table of Contents
List of Figures
List of Tables
1 General Introduction
1.1 Research context
1.2 Objectives and research methodology
1.3 Outline of the dissertation
2 State of the art of Decentralized Logistics and Transportation Systems
2.1 Decentralized logistics and transportation systems
2.2 Transportation procurement auctions
2.2.1 Auction types
2.2.2 Auctions for transportation procurement
2.2.3 Bidding language for transportation procurement combinatorial auctions
2.3 Combinatorial Auctions (CAs) for transportation procurement problem
2.3.1 Bidding generation problem for transportation procurement problem
2.3.1.1 Bundle construction problem
2.3.1.2 Bundle pricing problem
2.3.2 Winner determination problem for transportation procurement problem
2.4 Bilevel programming and its application to CAs
2.4.1 Problem description
2.4.2 Optimistic and pessimistic bilevel formulation
2.4.2.1 Optimistic formulation
2.4.2.2 Pessimistic formulation
2.4.2.3 Rewarding and deceiving solutions
2.4.3 Bilevel resolution
2.4.4 Bilevel application and its application to CAs
3 The Winner Determination Problem in CAs
3.1 Problem formulation
3.1.1 General formulation of WDP
3.1.2 Variants of WDP
3.1.2.1 Bi-objective WDP (2WDP-SC)
3.1.2.2 WDP under uncertainty (sWDP)
3.2 Methodology of the WDP problem
3.2.1 Complexity of WDP
3.2.2 Exact algorithms for WDP
3.2.2.1 Branch-and-bound (B&B)
3.2.2.2 Branch-and-cut (B&C)
3.2.2.3 Branch-and-price (B&P)
3.2.2.4 Dynamic programming (DP)
3.2.3 Approximate algorithms for WDP
3.2.3.1 Stochastic local search (SLS)
3.2.3.2 Limited discrepancy search (LDS)
3.2.3.3 Hybrid algorithm (HA)
3.2.3.4 Tabu search (TS)
3.2.3.5 Memetic algorithm (MA)
3.2.3.6 Greedy algorithm
3.2.3.7 Genetic algorithm (GA)
3.2.3.8 Lagrangian heuristic (LAHA)
3.2.3.9 Clique-based heuristic
3.2.3.10 Ant Colony Optimization (ACO)
3.2.3.11 Other algorithms
3.2.4 Algorithms for 2WDP-SC
3.3 Benchmarks
3.3.1 Sandholm
3.3.2 CATS
3.3.3 REL
3.3.4 Complementary data
3.4 Performance of the algorithms
3.4.1 Exact algorithms
3.4.2 Approximate algorithms
3.5 Investigated papers
3.6 Conclusions
4 Bundle Construction Problem in CAs for Full Truckload Transportation Procurement
4.1 Literature review
4.2 Problem statement
4.3 Resolution of bundle construction problem
4.3.1 Simplified requests network
4.3.2 Bundle construction problem formulation
4.4 Bounded exact bi-directional dynamic programming
4.4.1 Forward and backward extension and extension rules
4.4.2 Dominance test
4.4.3 Matching forward and backward states
4.4.4 Solution uniqueness and optimality
4.5 Numerical results
4.5.1 Data-sets
4.5.2 Computational results
4.6 Conclusions
5 Single-leader Single-follower Pricing-Allocation Bilevel Model in CAs for Full Truckload Transportation Procurement
5.1 Problem Definition
5.1.1 Assumptions, definitions and notations
5.1.2 The shipper’s Winner Determination Problem (WDP)
5.1.3 The carrier’s optimal Bidding Generation Problem (BGP)
5.2 Price update and bilevel formulation for informed carriers
5.2.1 Price update and bilevel formulation
5.2.2 Reformulation as a single level optimization problem
5.3 Second bilevel model
5.3.1 Lower level problem
5.3.2 Special case of the problem: 1-to-1 pricing-allocation
5.3.2.1 Optimistic and pessimistic single level formulation
5.3.2.2 Illustration between the optimistic and pessimistic cases
5.3.3 General case of the bilevel problem
5.3.3.1 Linearization procedure for UP and LP
5.4 Risk cost in shipper’s objective function
5.5 Experimental Results
5.5.1 Individual lane pricing
5.5.1.1 Case 1
5.5.1.2 Case 2
5.5.2 Bundle pricing
5.5.2.1 Case 3
5.5.2.2 Case 4
5.5.3 Bundle pricing with informed carriers
5.6 Conclusions
6 Multi-leader Single-follower Pricing-Allocation Bilevel Model in CAs for Full Truckload Transportation Procurement
6.1 Multi-leader single-follower bilevel formulation
6.1.1 Carrier interaction
6.1.2 Carrier-shipper intersection
6.1.3 Multi-leader single-follower bilevel formulation
6.2 Solution approach
6.2.1 Best response
6.2.1.1 1-to-1 pricing-allocation
6.2.1.2 Bundle-to-carrier pricing-allocation
6.3 Experimental results
6.3.1 Instance 1
6.3.2 Instance 2
6.3.3 Instance 3
6.4 Conclusions
Conclusions and Perspectives
References
