A Lagrangian relaxation approach to combinatorial exchange in freight logistics

Abstract : This paper addresses a Combinatorial Exchange (CE) problem raised in Collaborative Logistics (CL). The CE is a new transaction mechanism among less-than-truckload (LTL) carriers. With this mechanism, several carriers form an alliance and exchange some of their transportation requests for the purpose of gaining more profits. In the CE, each carrier plays a double role of buyer and seller. This characteristic brings some advantages compared with traditional Combinatorial Auctions (CA) in freight logistics. A 0-1 linear programming is formulated for this problem. A Lagrangian relaxation approach is then developed to solve the CE problem. The relaxed problem is transformed into a maximum vertex weight clique problem (MVWCP) which is solved either by a multi-neighborhood tabu search or by a commercial MIP solver. A repair heuristic is proposed to cope with any infeasibilities caused by the constraint relaxation. Extensive numerical experiments on randomly generated instances show that the Lagrangian relaxation approach can provide high quality solutions.