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.     

满意度优化运输问题

传统运输问题只考虑配送方案的效率, 而不考虑参与者对配送方案的满意度. 通过引入参与者对配送方案的满意度这一概念, 提出了满意度优化运输问题, 构建了以最大化相对公平为目标的满意度优化运输模型, 并证明了: (1) 当运输问题的可行域不空时, 新模型的解集非空; (2) 从满意度的角度来看, 新模型的解是唯一的. 另外, 还给出了新模型的求解方法. 研究结果进一步丰富了运输问题的类型, 可为解决其他类型运输问题提供借鉴.     

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).     

Max-min sum minimization transportation problem

A non-convex optimization problem involving minimization of the sum of max and min concave functions over a transportation polytope is studied in this paper. Based upon solving at most (g+1)(< p) cost minimizing transportation problems with m sources and n destinations, a polynomial time algorithm is proposed which minimizes the concave objective function where, p is the number of pairwise disjoint entries in the m× n time matrix {t _ij } sorted decreasingly and T ^g is the minimum value of the max concave function. An exact global minimizer is obtained in a finite number of iterations. A numerical illustration and computational experience on the proposed algorithm is also included. We are thankful to Prof. S. N. Kabadi, University of New Brunswick-Fredericton, Canada, who initiated us to the type of problem discussed in this paper. We are also thankful to Mr. Ankit Khandelwal, Ms. Neha Gupta and Ms. Anuradha Beniwal, who greatly helped us in the implementation of the proposed algorithm.     

Two level hierarchical time minimizing transportation problem

A two level hierarchical balanced time minimizing transportation problem is considered in this paper. The whole set of source-destination links consists of two disjoint partitions namely Level-I links and Level-II links. Some quantity of a homogeneous product is first shipped from sources to destinations by Level-I decision maker using only Level-I links, and on its completion the Level-II decision maker transports the remaining quantity of the product in an optimal fashion using only Level-II links. Transportation is assumed to be done in parallel in both the levels. The aim is to find that feasible solution for Level-I decision maker corresponding to which the optimal feasible solution for Level-II decision maker is such that the sum of shipment times in Level-I and Level-II is the least. To obtain the global optimal feasible solution of this non-convex optimization problem, related balanced time minimizing transportation problems are defined. Based upon the optimal feasible solutions of these related problems, standard cost minimizing transportation problems are constructed whose optimal feasible solutions provide various pairs for shipment times for Level-I and Level-II decision makers. The best out of these pairs is finally selected. Being dependent upon solutions of a finite number of balanced time minimizing and cost minimizing transportation problems, the proposed algorithm is a polynomial bound algorithm. The developed algorithm has been implemented and tested on a variety of test problems and performance is found to be quite encouraging.     

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.     

A bicriteria solid transportation problem with fixed charge under stochastic environment

In this paper, a bicriteria solid transportation problem with stochastic parameters is investigated. Three mathematical models are constructed for the problem, including expected value goal programming model, chance-constrained goal programming model and dependent-chance goal programming model. A hybrid algorithm is also designed based on the random simulation algorithm and tabu search algorithm to solve the models. At last, some numerical experiments are presented to show the performance of models and algorithm.     

Stochastic optimization models for a single-sink transportation problem

In this paper, we study a single-sink transportation problem in which the production capacity of the suppliers and the demand of the single customer are stochastic. Shipments are performed by capacitated vehicles, which have to be booked in advance, before the realization of the production capacity and the demand. Once the production capacity and the demand are revealed, there is an option to cancel some of the booked vehicles against a cancellation fee; if the quantity shipped from the suppliers using the booked vehicles is not enough to satisfy the demand, the residual quantity is purchased from an external company. The problem is to determine the number of vehicles to book in order to minimize the total cost. We formulate a two-stage and a multistage stochastic mixed integer linear programming models to solve this problem and test them on a real case provided by Italcementi, the primary Italian cement producer and the fifth largest cement producer in the world. We test the influence of different scenario-tree structures on the solutions of the problem, as well as sensitivity of the results with respect to the cancellation fee.     

A solid transportation problem with mixed constraint in different environment

In this paper, we have introduced a Solid Transportation Problem where the constrains are mixed type. The model is developed under different environment like, crisp, fuzzy and intuitionistic fuzzy etc. Using the interval approximation method we defuzzify the fuzzy amount and for intuitionistic fuzzy set we use the ($\alpha,\beta$)-cut sets to get the corresponding crisp amount. To find the optimal transportation units a time and space based with order of convergence $O (MN^2)$ meta-heuristic Genetic Algorithm have been proposed. Also the equivalent crisp model so obtained are solved by using LINGO 13.0. The results obtained using GA treats as the best solution by comparing with LINGO results for this present study. The proposed models and techniques are finally illustrated by providing numerical examples. Degree of efficiency have been find out for both the algorithm.     

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.     

带有运输且加工具有灵活性的无等待流水作业排序问题

研究一类带有运输且加工具有灵活性的两阶段无等待流水作业排序问题, 其中每阶段只有一台机器, 每个工件有两道工序需要依次在两台机器上加工, 工件在两台机器上的加工及两道工序之间不允许等待. 给出两种近似算法, 并分别分析其最坏情况界. 第一种算法是排列排序, 证明了最坏情况界不超过5/2; 第二种算法将工件按照两道工序加工时间之和的递增顺序排序, 证明其最坏情况界不超过2. 最后, 通过数值模拟比较算法的性能. 对问题中各参数取不同值的情况, 分别生成若干个实例, 用算法得到的解与最优解的下界作比值, 通过分析这些比值的最大值、最小值和平均值来比较上述两个算法的性能.     

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.     

Bisection acceleration for the symmetric tridiagonal eigenvalue problem

We present new algorithms that accelerate the bisection method for the symmetric tridiagonal eigenvalue problem. The algorithms rely on some new techniques, including a new variant of Newton's iteration that reaches cubic convergence (right from the start) to the well separated eigenvalues and can be further applied to acceleration of some other iterative processes, in particular, of the divide-and-conquer methods for the symmetric tridiagonal eigenvalue problem. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Explicit construction of measure solutions of Cauchy problem for transportation equations

The transportation equations are a mathematical model of zero-pressure flow in gas dynamics and the adhesion particle dynamics system to explain the formation of large scale structures in the universe. With the help of convex hull of a potential function, the solution is explicitly constructed here. It is straightforward to prove that the solution is a global measure one. And Dirac delta-shocks explained as the concentration of particles may develop in the solution. Project supported by the Institute of Mathematics, Chinese Academy of Sciences and by the National Fundamental Research Program of State Commission of Science and Technology of China, and Chinese Academy of Sciences.     

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.     

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.     

关于可靠性设施布局问题的近似算法

设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量,以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小.现实生活中, 受自然灾害、工人罢工、恐怖袭击等因素的影响,修建的设施可能会出现故障, 故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性.针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题.参考经典设施布局问题的贪婪算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法.该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点.这对于之前的可靠性设施布局问题只有数值实验算法, 是一个很大的进步.