Aarhus University Seal / Aarhus Universitets segl

Solving the Single-Sink, Fixed-Charge, Multiple-Choice Transportation Problem by Dynamic Programming

Research output: Contribution to conferenceConference abstract for conferenceResearch

  • CORAL - Centre for Operations Research Applications in Logistics
  • Department of Mathematical Sciences
  • Department of Business Studies
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.

Original languageEnglish
Publication year2010
Publication statusPublished - 2010
Event4th Nordic Optimization Symposium - Aarhus, Denmark
Duration: 30 Sep 20102 Oct 2010


Conference4th Nordic Optimization Symposium

See relations at Aarhus University Citationformats

ID: 240478