On minimizing the duration of transportation

The problem of minimizing the duration of transportation has been studied. The problem has been reduced to a goal programming-type problem which readily lends itself to solution by the standard transportation method. This approach to the solution of the problem is very much different from all other existing ones.     

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.     

Partially-linear transportation problems

The nonlinear relationship between quantities and the real cost for their transportation causes interest in some nonlinear transportation problems. Partially-linear transportation problems may be successfully applied in economics because every nonlinear function may be approximated by partially-linear functions. In this work we consider transportation problems with partially-linear dependence of the transportation costs and give the necessary and sufficient conditions for local optimality. A constructive method for solving such problems is suggested.     

Uncertain solid transportation problems

The solid transportation problem arises when bounds are given on three item properties. Usually, these properties are source, destination and type of product or mode of transport, and often are given in a uncertain way. This paper deals with two of the ways in which uncertainty can appear in the problem: Interval solid transportation problem and fuzzy solid transportation problem. The first arises when data problem are expressed as intervals instead of point values, and the second when the nature of the information is vague. Both models are treated in the case in which the uncertainty affects only the constraint set. For interval case, an auxiliary problem is obtained in order to find a solution. This auxiliary problem is a standard solid transportation problem which can be solved with the efficient methods existing. For fuzzy case, a parametric approach which makes it possible to find a fuzzy solution to the former problem is used.     

One-parametric bottleneck transportation problems

We discuss the bottleneck transportation problem with one nonlinear parameter in the bottleneck objective function. A finite sequence of feasible basic solutions which are optimal in subsequent closed parameter-intervals is generated using a primal method for the nonparametric subproblems. The best among three primal codes for solving these subproblems is selected on extensive computational comparisons. We discuss computational experience with the sequential method for the case of linear and quadratic dependence on one parameter. Observed computational behaviour is O((n ·m)), with 2.     

Variational minimizing solutions for the 2-fixed center problems

Using variational minimizing methods, we study the 2-fixed center problems.     

Partitional clustering via successive transportation problems

We propose to extend the spherical separation approach, amply used in supervised classification, to clustering problems by assigning each datum to a suitable sphere. Our idea consists in designing a heuristic approach based on solving successive transportation problems aimed at providing the radii of the clustering spheres, whose centers are fixed in advance as the barycenters of each current cluster, similarly to the well known K-Means algorithm. Numerical results show the effectiveness of our proposal.     

Degeneracy in fixed cost transportation problems

A perturbation method is introduced which transforms any fixed cost transportation problem F into a degeneracy-free equivalent F′. If a basic optimal solution to F′ is known, an optimal solution to F can be obtained by means of simple rounding.     

Non-archimedean transportation problems and Kantorovich ultra-norms

We study a non-archimedean (NA) version of transportation problems and introduce naturally arising ultra-norms which we call Kantorovich ultra-norms. For every ultra-metric space and every NA valued field (e.g., the field Q _p of p-adic numbers) the naturally defined inf-max cost formula achieves its infimum. We also present NA versions of the Arens-Eells construction and of the integer value property. We introduce and study free NA locally convex spaces. In particular, we provide conditions under which these spaces are normable by Kantorovich ultra-norms and also conditions which yield NA versions of Tkachenko-Uspenskij theorem about free abelian topological groups.     

A note on bi-criteria transportation problems

The present note reveals a drawback in an algorithm ofAneja/Nair [1979] for the determination of efficient solutions in a bi-criteria transportation problem with an additional time objective function and develops a modified procedure that overcomes this weakness.

---

Zusammenfassung In der vorliegenden Arbeit wird ein Fehlschluß im Algorithmus vonAneja/Nair [1979] zum Auffinden aller effizienten Lösungen eines Transportproblems mit zwei Summen- und einer Engpaßzielfunktion aufgezeigt. Ferner wird ein Verfahren angegeben, in dem diese Unstimmigkeiten nicht mehr auftreten.

     

Weber problems with alternative transportation systems

In this paper we address a planar p-facility location problem where, together with a metric induced by a gauge, there exists a series of rapid transit lines, which can be used as alternative transportation system to reduce the total transportation cost. The location problem is reduced to solving a finite number of (multi)-Weber problems, from which localization results are obtained. In particular, it is shown that, if the gauge in use is polyhedral, then the problem is reduced to finding a p-median.     

An algorithm for semi-infinite transportation problems

In this paper we consider a class of semi-infinite transportation problems. We develop an algorithm for this class of semi-infinite transportation problems. The algorithm is a primal dual method which is a generalization of the classical algorithm for finite transportation problems. The most important aspect of our paper is that we can prove the convergence result for the algorithm. Finally, we implement some examples to illustrate our algorithm.     

Minimum norm problems over transportation polytopes

We consider the problem of updating input-output matrices, i.e., for given (m,n) matrices A ? 0, W ? 0 and vectors u ? $\text{R}$^m, v?$\text{R}$ⁿ, find an (m,n) matrix X ? 0 with prescribed row sums Σⁿ_j=1X_ij = u_i (i = 1,…,m) and prescribed column sums Σ^m_i=1X_ij = v_j (j = 1,…,n) which fits the relations X_ij = A_ij + λ_iW_ij + W_ij + W_ijμ_j for all i,j and some λ?$\text{R}$^m, μ?$\text{R}$ⁿ. Here we consider the question of existence of a solution to this problem, i.e., we shall characterize those matrices A, W and vectors u,v which lead to a solvable problem. Furthermore we outline some computational results using an algorithm of [2].     

Regularity and relaxed problems of minimizing biharmonic maps into spheres

For and , we show that any minimizing biharmonic map from to S^k is smooth off a closed set whose Hausdorff dimension is at most n-5. When n = 5 and k = 4, for a parameter we introduce a -relaxed energy of the Hessian energy for maps in so that each minimizer of is also a biharmonic map. We also establish the existence and partial regularity of a minimizer of for .Received: 5 April 2004, Accepted: 19 October 2004, Published online: 10 December 2004     

An improved disaggregation method for transportation problems

A method is given to disaggregate the solution to an aggregated transportation problem. The resulting solution to the original problem is feasible, all-integer, and has lower cost that those of solutions produced by earlier methods.     

Polyhedral combinatorics of multi-index axial transportation problems

This paper studies integer points (IP) and integer vertices (IV) of the p-index axial transportation polytope (p  -ATP) of order _n1×_n2×?×_np$n_1\times n_2\times ?\times n_p$, _n1,_n2,…,_np?2$n_1\text{,}{n}_2\text{,}\dots \text{,}{n}_p?2$, p?2$p?2$, defined by integer vectors, as well as noninteger vertices of the 3-ATP. In particular, for the p  -ATP, we establish criteria for the minimum and maximum number of IPs and describe the class of polytopes for which the number of IPs coincides with the number of IVs. For the 3-ATP of order n×n×n$n\times n\times n$, we prove the theorem on the exponential growth of denominators of fractional components of the polytope vertices. Three conjectures are stated regarding the maximum number of vertices of the p-ATP, the maximum number of IVs, and the structure of the nondegenerate polytopes with the maximum number of IPs.     

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

On lexicographic optimal solutions in transportation problems

Lexicographic versions of the cost minimizing transportation problem (CMTP) and the time minimizing transportation problem (TMTP) are presented in this paper. In addition to minimizing the quantity sent on the costliest routes in a cost minimizing transportation problem. an attempt is made to minimize the quantity transported on the second-costliest routes. if the shipment on the costliest routes is as small as possible and the quantity shipped on the third-costliest routes, if the shipments on the costliest and the second- costliest routes are as small as possible. and so on. In a lexicographic time minimizing transportation problem one is not only interested in minimizing the transportation cost on the routes of the longest duration but also on the routes of second longest, third-longest duration and so on. For finding lexicographic optimal solutions (LOS) of lexicographic cost minimizing and time minimizing transportation problems a standard cost minimizing transportation problem is formulated whose optimal solution is shown to provide the answer. Some extensions are also discussed     

Planar three-index transportation problems with dominating index

Summary A class of planar three-index transportation problems is described which can be reduced to classical transportation problems. Moreover an example of a polytope with full dimension having this property is given.

---

Zusammenfassung Es wird eine Klasse von dreidimensionalen Transportproblemen beschrieben, deren Lösung auf das Lösen klassischer Transportprobleme zurückgeführt werden kann. Es wird ferner ein Beispiel für ein derartiges Problem angegeben, dessen zugehöriger Polyeder die volle Dimension hat.

---

---

On leave from Byelorussian Polytechnical Institute Leninski pr. 65, 220027 Minsk, USSR.