Rauff Lind Christensen, Tue6; Klose, Andreas7; Andersen, Kim Allan6
1 CORAL - Centre for Operations Research Applications in Logistics, Aarhus School of Business, Aarhus BSS, Aarhus University2 Department of Mathematical Sciences, Faculty of Science, Aarhus University, Aarhus University3 Department of Business Studies, Aarhus School of Business, Aarhus BSS, Aarhus University4 Department of Economics and Business Economics, Aarhus BSS, Aarhus University5 Department of Mathematics, Science and Technology, Aarhus University6 Department of Economics and Business Economics, Aarhus BSS, Aarhus University7 Department of Mathematics, Science and Technology, Aarhus University
The Single-Sink, Fixed-Charge, Multiple-Choice Transportation Problem (SSFCMCTP) is a problem with versatile applications. This problem is a generalization of the Single-Sink, Fixed-Charge Transportation Problem (SSFCTP), which has a fixed-charge, linear cost structure. However, in at least two important aspects of supplier selection, an important application of the SSFCTP, this does not reflect the real life situation. First, transportation costs faced by many companies are in fact piecewise linear. Secondly, when suppliers offer discounts, either incremental or all-unit discounts, such savings are neglected in the SSFCTP. The SSFCMCTP overcome this problem by incorporating a staircase cost structure in the cost function instead of the usual one used in SSFCTP. We present a dynamic programming algorithm for the resulting problem. To enhance the performance of the generic algorithm a number of enhancements is employed. The problem instance is reduced by variable pegging using a Lagrangean relaxation from which also a flow augmentation scheme is derived. Additionally a reduction in the search space is employed along with a variable transformation which generalizes a transformation known from the SSFCTP. Computational results indicate that this method is much faster than a standard mixed integer problem solver.