An optimization approach for winner determination problem considering transportation cost discounts

作     者：Yang, Fang Huang, Yao-Huei 

作者机构：Chongqing Univ Posts & Telecommun Sch Econ & Management Chongqing 400065 Peoples R China Fu Jen Catholic Univ Dept Informat Management New Taipei 242062 Taiwan 

出 版 物：《JOURNAL OF GLOBAL OPTIMIZATION》 (全局最优化杂志)

年 卷 期：2021年第80卷第3期

页      面：711-728页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Ministry of Science and Technology of Taiwan [MOST109-2410-H-030-037-MY3] 

主　　题：Mixed-integer nonconvex programming Winner determination problem Discount function Big-M constraints Branch-and-bound trees 

摘      要：This study proposes a mixed-integer nonconvex programming (MINP) model for the winner determination problem (WDP) considering two discount functions in a combinatorial auction to save shipper s transportation cost. For the WDP, the shipper allows carriers to submit bids for a bundle of lanes. Then the winning carries are selected by solving the WDP. Specifically, this study considers the shipment distance-based and volume-based discounts for transportation cost, simultaneously. The state-of-the-art linearization technique is available to convert the MINP model into a mixed-integer linear program (MILP) to obtain a global optimum, but the solution time becomes inefficient when the problem size becomes large. To find efficient and effective linearization techniques for large-scale WDP, this study (1) proposes a novel WDP model with discount policies, (2) utilizes superior encoding formulation to avoid the unbalanced branch-and-bound trees in solving MILP, and (3) reduces big-M constraints to speed up the solving time. The proposed method leads to significant savings in computational efforts. Numerical experiments with real-world-sized truckload service procurement problems are solved by the proposed method and further confirmed the drastic reduction in computational time for solving the large-size WDP.