A strongly polynomial algorithm for the transportation problem

For the (linear) transportation problem withm supply nodes,n demand nodes andk feasible arcs we describe an algorithm which runs in time proportional tom logm(k + n logn) (assuming w.l.o.g.mn). The algorithm uses excess scaling. The complexity bound is a slight improvement over the bound achieved by an application of a min-cost-flow algorithm of Orlin to the transportation problem.Corresponding author. Research supported in part by grant no. I-84-095.06/88 of the German—Israeli-Foundation for Scientific Research and Development.     

A fuzzy approach to the transportation problem

The transportation problem with fuzzy supply values of the deliverers and with fuzzy demand values of the receivers is analysed. For the solution of the problem the technique of parametric programming is used. This makes it possible to obtain not only the maximizing solution (according to the Bellman-Zadeh criterion) but also other alternatives close to the optimal solution.     

Formulations for a problem of petroleum transportation

Oil tankers play a fundamental role in every offshore petroleum supply chain and due to its high price, it is essential to optimize its use. Since this optimization requires handling detailed operational aspects, complete optimization models are typically intractable. Thus, a usual approach is to solve a tactical level model prior to optimize the operational details. In this case, it is desirable that tactical models are as precise as possible to avoid too severe adjustments in the next optimization level. In this paper, we study tactical models for a crude oil transportation problem by tankers. We did our work on the top of a previous paper found in the literature. The previous model considers inventory capacities and discrete lot sizes to be transported, aiming to meet given demands over a finite time horizon. We compare several formulations for this model using 50 instances from the literature and proposing 25 new harder ones. A column generation-based heuristic is also proposed to find good feasible solutions with less computational burden than the heuristics of the commercial solver used.     

The value function of a transportation problem

We investigate the value of an optimal transportation problem with the maximization objective as a function of costs and vectors of production and consumption. The value is concave in production. For generic costs, the numbers of linearity domains and peak points are independent of costs and consumption. The peak points are determined by an auxiliary assignment problem. The volumes of the linearity domains are independent of costs while their dependence on consumption can be expressed via the multinomial distribution.     

The transportation problem with exclusionary side constraints

We consider the so-called Transportation Problem with Exclusionary Side Constraints (TPESC), which is a generalization of the ordinary transportation problem. We confirm that the TPESC is NP-hard, and we analyze the complexity of different special cases. For instance, we show that in case of a bounded number of suppliers, a pseudo-polynomial time algorithm exists, whereas the case of two demand nodes is already hard to approximate within a constant factor (unless P = NP). This research was partially supported by FWO Grant No. G.0114.03.     

The stochastic transportation problem with single sourcing

We propose a branch-and-price algorithm for solving a class of stochastic transportation problems with single-sourcing constraints. Our approach allows for general demand distributions, nonlinear cost structures, and capacity expansion opportunities. The pricing problem is a knapsack problem with variable item sizes and concave costs that is interesting in its own right. We perform an extensive set of computational experiments illustrating the efficacy of our approach. In addition, we study the cost of the single-sourcing constraints.     

Solving fixed charge transportation problem with interval parameters

In the present paper the fixed charge transportation problem under uncertainty, particularly when parameters are given in interval forms, is formulated. In this case it is assumed that both cost and constraint parameters are arrived in interval numbers. Considering two different order relations for interval numbers, two solution procedures are developed in order to obtain an optimal solution for interval fixed charge transportation problem (IFCTP). In addition, the two order relations are compared to give a better comprehension of their differences. Furthermore, numerical examples are provided to illustrate each of solution procedures.     

Capacitated transportation problem with bounds on RIM conditions

Motivated by dead-mileage problem assessed in terms of running empty buses from various depots to starting points, we consider a class of the capacitated transportation problems with bounds on total availabilities at sources and total destination requirements. It is often difficult to solve such problems and the present paper establishes their equivalence with a balanced capacitated transportation problem which can be easily solved by existing methods. Sometimes, total flow in transportation problem is also specified by some external decision maker because of budget/political consideration and optimal solution of such problem is of practical interest to the decision maker and has motivated us to discuss such problem. Various situations arising in unbalanced capacitated transportation problems have been discussed in the present paper as a particular case of original problem. In addition, we have discussed paradoxical situation in a balanced capacitated transportation problem and have obtained the paradoxical solution by solving one of the unbalanced problems. Numerical illustrations are included in support of theory.     

Approximation algorithms for the transportation problem with market choice and related models

Given facilities with capacities and clients with penalties and demands, the transportation problem with market choice consists in finding the minimum-cost way to partition the clients into unserved clients, paying the penalties, and into served clients, paying the transportation cost to serve them.     

A new index for measuring seasonality: A transportation cost approach

Seasonal fluctuations characterize many natural and social phenomena. Although the causes and impacts of seasonality are generally well documented in different study contexts, and many methods for isolating the seasonal component have been developed, considerably less attention has been paid to the measurement of the degree of seasonality. After reviewing the main indices used for measuring seasonality in different study contexts, we will propose a new approach in which seasonality is evaluated on the basis of the solution of a transportation problem. By considering the interdisciplinary nature of seasonal phenomena, the topic of measuring seasonality merits attention from a wide variety of perspectives.     

Persistency in the assignment and transportation problems

LetG = (U,V,E) be a bipartite graph with weights of its edgesc _ij . For the assignment and transportation problem given by such a graph we propose efficient procedures for partitioning the edge setE into three classes:E _o is the set of edgesij withx _ij = 0 for each optimum solution (0-persistent edges);E ₁ is the set of edges withx _ij > 0 and constant for each optimum (1-persistent edges) andE _w is the set of edges such that there are two optimum solutions x, x withx _ij x _ij ¹ (weakly persistent edges).     

A transportation problem with fuzzy-stochastic cost

In this paper, we consider some transportation problems (TPs) with different types of fuzzy-stochastic unit transportation costs and budget constraints. These fuzzy stochastic costs are reduced to corresponding crisp ones in two different ways. For the first method, using the definition of α$\alpha$-cut of the fuzzy numbers, expectation is taken separately on both lower and upper α$\alpha$-cuts and then mean expectation is calculated with the help of signed distance. In the second procedure, we realize fuzzy random events (ξ?r)$(\xi ?r)$ and (ξ?r)$(\xi ?r)$ for the fuzzy random variable (ξ)$(\xi )$. Using credibility measure of these events, mean chances for the above fuzzy random events are calculated and then expectation is taken to get the crisp expressions. The reduced deterministic problems of the fuzzy stochastic TP are solved using a real coded genetic algorithm with Roulette wheel selection, arithmetic crossover and random mutation. Few numerical examples are demonstrated to find the optimal solutions of the proposed models.     

A faster polynomial algorithm for the unbalanced Hitchcock transportation problem

We present a new algorithm for the Hitchcock transportation problem. On instances with n sources and k sinks, our algorithm has a worst-case running time of O(nk²(logn+klogk)). It closes a gap between algorithms with running time linear in n but exponential in k and a polynomial-time algorithm with running time O(nk²log²n).     

Cost operator algorithms for the transportation problem

A primal transportation algorithm is devised via post-optimization on the costs of a modified problem. The procedure involves altering the costs corresponding to the basic cells of the initial (primal feasible) solution so that it is dual feasible as well. The altered costs are then successively restored to their true values with appropriate changes in the optimal solution by the application of cell or area cost operators discussed elsewhere. The cell cost operator algorithm converges to optimum within (2T – 1) steps for primal nondegenerate transportation problems and [(2T + 1) min (m, n)] – 1 steps for primal degenerate transportation problems, whereT is the sum of the (integer) warehouse availabilities (also the sum of the (integer) market requirements) andm andn denote the number of warehouses and markets respectively. For the area cost operator algorithm the corresponding bounds on the number of steps areT and (T + 1) min (m, n) respectively.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie—Mellon University, under Contract N00014-67-A-0314-0007 NR 047-048 with the U.S. Office of Naval Research.     

A hybrid two-stage transportation and batch scheduling problem

We study the coordinated scheduling problem of hybrid batch production on a single batching machine and two-stage transportation connecting the production, where there is a crane available in the first-stage transportation that transports jobs from the warehouse to the machine and there is a vehicle available in the second-stage transportation to deliver jobs from the machine to the customer. As the job to be carried out is big and heavy in the steel industry, it is reasonable assumed that both the crane and the vehicle have unit capacity. The batching machine processes a batch of jobs simultaneously. Each batch occur a setup cost. The objective is to minimize the sum of the makespan and the total setup cost. We prove that this problem is strongly NP-hard. A polynomial time algorithm is proposed for a case where the job transportation times are identical on the crane or the vehicle. An efficient heuristic algorithm for the general problem is constructed and its tight worst-case bound is analyzed. In order to further verify the performance of the proposed heuristics, we develop a lower bound on the optimal objective function. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances.     

Which matrices are immune against the transportation paradox?

We characterize the m×n cost matrices of the transportation problem for which there exist supplies and demands such that the transportation paradox arises. Our characterization is fairly simple and can be verified within O(mn) computational steps. Moreover, we discuss the corresponding question for the algebraic transportation problem.     

Multi-choice stochastic transportation problem involving extreme value distribution

In this paper a multi choice stochastic transportation problem is considered where the supply and demand parameters of the constraints follow extreme value distribution. Some of the cost coefficients of the objective function are multi-choice type. At first all the probabilistic constraints are transformed into deterministic constraints. Further using the binary variables, multi-choice type cost coefficients are handled. Then the transformed problem is considered as a deterministic multi-choice transportation problem. Finally, a numerical example is presented to illustrate the solution procedure.     

Analysis of some greedy algorithms for the single-sink fixed-charge transportation problem

The single-sink fixed-charge transportation problem (SSFCTP) consists of finding a minimum cost flow from a number of nodes to a single sink. Beside a cost proportional to the amount shipped, the flow cost encompass a fixed charge. The SSFCTP is an important subproblem of the well-known fixed-charge transportation problem. Nevertheless, just a few methods for solving this problem have been proposed in the literature. In this paper, some greedy heuristic solutions methods for the SSFCTP are investigated. It is shown that two greedy approaches for the SSFCTP known from the literature can be arbitrarily bad, whereas an approximation algorithm proposed in the literature for the binary min-knapsack problem has a guaranteed worst case bound if adapted accordingly to the case of the SSFCTP.