A Note on a Simple Dynamic Programming Approach to the Single-Sink, Fixed-Charge Transportation Problem

Alidaee, Bahram; Kochenberger, Gary A.
February 2005
Transportation Science;Feb2005, Vol. 39 Issue 1, p140
Academic Journal
The single-sink, fixed-charge transportation problem has a variety of applications, including supplier selection, product distribution/fleet selection, and process selection. In this paper we present a dynamic programming algorithm for solving this important problem that is very easy to implement and that improves considerably in terms of computational attractiveness on the best methods in the literature.


Related Articles

  • COMPUTATIONAL ASPECTS OF DYNAMIC PROGRAMMING. Dreyfus, Stuart E. // Operations Research;Jun57, Vol. 5 Issue 3, p409 

    This article focuses on the computational aspects of dynamic programming. Dynamic programming is a method of solving multi-stage decision-process problems. Several computational difficulties are characteristic of all dynamic-programming solutions. In the theory of dynamic programming one find...

  • An Effective Deflected Subgradient Optimization Scheme for Implementing Column Generation for Large-Scale Airline Crew Scheduling Problems. Subramanian, Shivaram; Sherali, Hanif D. // INFORMS Journal on Computing;Fall2008, Vol. 20 Issue 4, p565 

    We present a new deflected subgradient scheme for generating good quality dual solutions for linear programming (LP) problems and utilize this within the context of large-scale airline crew planning problems that arise inpractice. The motivationfor the development of this method came from the...

  • LP solvable models for portfolio optimization: a classification and computational comparison. Mansini, Renata; Ogryczak, Wlodzimierz; Speranza, M. Grazia // IMA Journal of Management Mathematics;Jul2003, Vol. 14 Issue 3, p187 

    The Markowitz model of portfolio optimization quantifies the problem in a lucid form of only two criteria: the mean, representing the expected outcome, and the risk, a scalar measure of the variability of outcomes. The classical Markowitz model uses the variance as the risk measure, thus...

  • COMPUTATIONAL DIFFICULTIES OF BILEVEL LINEAR PROGRAMMING. Ben-Aved, Omar; Blair, Charles E. // Operations Research;May/Jun90, Vol. 38 Issue 3, p556 

    We show, using small examples, that two algorithms previously published for the Bilevel Linear Programming problem (BLP) may fail to find the optimal solution and thus must be considered to be heuristics. A proof is given that solving BLP problems is NP-hard, which makes it unlikely that there...

  • CONVERGENCE CONDITIONS FOR NONLINEAR PROGRAMMING ALGORITHMS. Zangwill, Willard I. // Management Science;Sep69, Vol. 16 Issue 1, p1 

    Conditions which are necessary and sufficient for convergence of a nonlinear programming algorithm are stated. It is also shown that the convergence conditions can be easily applied to most programming algorithms. As examples, algorithms by Arrow, Hurwicz and Uzawa; Cauchy; Frank and Wolfe; and...

  • DYNAMIC NETWORK TRAFFIC ASSIGNMENT CONSIDERED AS A CONTINUOUS TIME OPTIMAL CONTROL PROBLEM. Friesz, Terry L.; Luque, Javier; Tobin, Roger L.; Wie, Byung-wook // Operations Research;Nov/Dec89, Vol. 37 Issue 6, p893 

    Two continuous time formulations of the dynamic traffic assignment problem are considered, one that corresponds to system optimization and the other to a version of user optimization on a single mode network using optimal control theory. Pontryagin's necessary conditions are analyzed and given...

  • Adaptive memory tabu search for binary quadratic programs. Glover, Fred; Kochenberger, Gary A.; Alidaee, Babram // Management Science;Mar98, Vol. 44 Issue 3, p336 

    Recent studies have demonstrated the effectiveness of applying adaptive memory tabu search procedures to combinatorial optimization problems. In this paper we describe the development and use of such an approach to solve binary quadratic programs. Computational experience is reported, showing...

  • Controlled Optimization of Phases at an Intersection. Sen, Suvrajeet; Head, K. Larry // Transportation Science;Feb97, Vol. 31 Issue 1, p5 

    This paper presents a general purpose algorithm for real-time traffic control at an intersection. Our methodology, based on dynamic programming, allows optimization of a variety of performance indices such as delay, stops and queue lengths. Furthermore, optimal phase sequencing is a direct...

  • A DYNAMIC PROGRAMMING APPROACH ALGORITHM FOR THE ALLOCATION OF LIMITED RESOURCES. Ralevic, Predrag; Dobrodolac, Momcilo; Mladenovic, Sne´┐Żana; Cicevic, Svetlana; Cubranic-Dobrodolac, Marjana // Metalurgia International;Nov2012, Vol. 17 Issue 11, p91 

    Optimization of material, organizational or financial resource allocation is a challenge for every company in any production or service sector. Basic assumption is that these resources are limited and their optimal use is a necessity for companies in order to survive in a competitive market, in...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics