A Transportation model with multiple criteria and multiple constraint levels

In this paper, a transportation model with multiple criteria and multiple constraint levels (MC²) is formulated by using the framework of MC² linear programming. An algorithm is developed to solve such MC² transportation problems. In this algorithm, the traditional northwest corner rule is adopted to find an initial basic feasible solution for a given MC² transportation problem. Then the MC²-simplex method is applied to locate the set of all potential solutions over possible changes of the objective coefficient parameter and the supply and demand parameter for the MC² transportation problem. A numerical example is illustrated to demonstrate the applicability of the algorithm in solving the MC² transportation problems.     

Partial Geometric Regularity of Some Optimal Connected Transportation Networks

We consider a continuous optimization model of a one-dimensional connected transportation network under the assumption that the cost of transportation with the use of network is negligible in comparison with the cost of transportation without it. We investigate the connections between this problem and its important special case, the minimization of the average distance functional. For the average distance minimization problem we formulate a number of conditions for the partial geometric regularity of a solution in ℝⁿ with an arbitrary dimension n ⩾ 2. The corresponding results are applied to solutions to the general optimization problem. Bibliography: 26 titles. Illustrations: 1 Figure. __________ Translated from Problemy Matematicheskogo Analiza, No. 31, 2005, pp. 129–157.     

An effective algorithm for the two-stage location problem on a tree-like network

A two-stage facility location problem on a tree-like network is considered under the restriction that the transportation costs for a unit of production from one node to another is equal to the sum of the edges in the path connecting these nodes. Some exact algorithm with time complexity O(nm ³) is suggested for this problem, where n is the number of the production demand points and, m is an upper bound on the number of possible facility location sites of each stage.     

Applied systems and cybernetics,volume III: Human systems,sociocybernetics, management and organizations: G.E. LASKER (Ed.) Proceedings of the international congress on applied Systems research and cybernetics; Pergamon Press,New York, 1981, xxx + 515 pages, $80.00

This note considers a special case of the assignment problem when n jobs are to be grouped together into a set of m categories (m > 3). Solving this particular case through the available transportation or assignment algorithms would entail a heavy computational burden, particularly in problems involving dense matrices. A preprocessing technique requiring sorting of (₂^m) n-arrays once is outlined, which is capable of reducing the dimension and eliminating several arcs for such a problem. The procedure offers an overall computational advantage over the other available algorithms applied directly. An illustrative example is included.     

Transportation problems which can be solved by the use of hirsch-paths for the dual problems

Balinski uses his signature method for the proof of the Hirsch-conjecture for dual transportation polyhedra to obtain an efficient algorithm for the assignment problem. We will show how to extend this method to other primal transportation problems, including transportation problems with unit demands. We then prove that Balinski's assignment algorithm is equivalent, cycle by cycle, to that of Hung and Rom. We demonstrate that, under some assumptions for our probability model, a modification of the latter algorithm has an average complexity of O(n ²logn) and present some computational results confirming this. We also present results that indicate that this modification compares favorably with Balinski's algorithm and other codes. Research of both authors supported, in part, by grants of the Alexander von Humboldt-Stiftung. Supported, in part, by NSF grant DMS-8504050.     

The structure of branched transportation networks

The transportation problem can be formalized as the problem of finding the optimal paths to transport a measure μ ⁺ onto a measure μ ⁻ with the same mass. In contrast with the Monge–Kantorovich formalization, recent approaches model the branched structure of such supply networks by an energy functional whose essential feature is to favor wide roads. Given a flow s in a road or a tube or a wire, the transportation cost per unit length is supposed to be proportional to s ^α with 0 < α < 1. For the Monge–Kantorovich energy α = 1 so that it is equivalent to have two roads with flow 1/2 or a larger one with flow 1. If instead 0 < α < 1, a road with flow is preferable to two individual roads s ₁ and s ₂ because . Thus, this very simple model intuitively leads to branched transportation structures. Such a branched structure is observable in ground transportation networks, in draining and irrigation systems, in electric power supply systems and in natural objects like the blood vessels or the trees. When such structures can irrigate a whole bounded open set of . The aim of this paper is to give a mathematical proof of several structure and regularity properties empirically observed in transportation networks. It is first proven that optimal transportation networks have a tree structure and can be monotonically approximated by finite graphs. An interior regularity result is then proven according to which an optimal network is a finite graph away from the irrigated measure. It is also proven that the branching number of optimal networks has everywhere a universal explicit bound. These results answer questions raised in two recent papers by Xia.     

Two-machine open shop scheduling with special transportation times

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimise the makespan, provided that preemption is not allowed and the interstage transportation times are involved. In general, this problem is known to be NP-hard. We present a linear time algorithm that finds an optimal schedule if no transportation time exceeds the smallest of the processing times. We also describe an algorithm that creates a heuristic solution to the problem with job-independent transportation times. Our algorithm provides a worst-case performance ratio of 8/5 if the transportation time of a job depends on the assigned processing route. The ratio reduces to 3/2 if all transportation times are equal.     

A note on asymptotic formulae for one-dimensional network flow problems

This note develops asymptotic formulae for single-commodity network flow problems with random inputs. The transportation linear programming problem (TLP) where N points lie in a region of R¹ is one example. It is found that the average distance traveled by an item in the TLP increases with N^1/2; i.e., the unit cost is unbounded when N and the length of the region are increased in a fixed ratio. Further, the optimum distance does not converge in probability to the average value. These one-dimensional results are a useful stepping stone toward a network theory for two and higher dimensions. Research supported in part by the University of California Transportation Center.     

The 1-median and 1-highway problem

In this paper we study a facility location problem in the plane in which a single point (median) and a rapid transit line (highway) are simultaneously located in order to minimize the total travel time of the clients to the facility, using the L₁ or Manhattan metric. The highway is an alternative transportation system that can be used by the clients to reduce their travel time to the facility. We represent the highway by a line segment with fixed length and arbitrary orientation. This problem was introduced in [Computers & Operations Research 38(2) (2011) 525–538]. They gave both a characterization of the optimal solutions and an algorithm running in O(n³logn) time, where n represents the number of clients. In this paper we show that the previous characterization does not work in general. Moreover, we provide a complete characterization of the solutions and give an algorithm solving the problem in O(n³) time.     

The interactive fixed charge inhomogeneous flows optimization problem

An optimization problem of interactive inhomogenous flows (Steiner multicommodity network flow problem) is formulated. The problem's main characteristic is a fixed charge change when combining multicommodity communications. In this paper we propose a method for solving this problem which, in order to restrict the search on the feasible domain, reduces the original problem to a concave programming problem in the form: min {f(x)|xX} wheref:ⁿ is a concave function, andX ₀ ⁿ is a flow polytope defined by network transportation constraints. For practical large-scale problems arising from planning transportation networks on inhomogeneous surfaces defined by a digital model, a method of local optimization over a flow polytope vertex set is proposed, which is far more effective in comparison with the Gallo and Sodini method under polytope strong degeneracy conditions.     

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.     

The Transportation Problem and its Variants

For 54 unimodular linear programming problems it is shown that either (i) the objective function is unbounded, or (ii) the problem is infeasible, or (iii) the problem can be solved by solving a related transportation problem. The related transportation problem is obtained by adding at the most two new constraints to the original problem.     

Branch and Bound Algorithm for the <Emphasis Type="Italic">p</Emphasis>-Median Transportation Problem

The p-median transportation problem is to determine an optimal solution to a transportation problem having an additional constraint restricting the number of active supply points. The model is discussed as an example of a public sector location/allocation problem. A branch and bound procedure is proposed to solve the problem. Lagrangian relaxation is used to provide lower bounds. Computational results are given.     

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.     

Solving the transportation problem with mixed constraints

Summary Variants of the standard transportation problem in which availability or requirement constraints are specified as inequalities can be solved by means of related standard transportation problems. In this paper we show that to each transportation problem with mixed constraints a standard transportation problem with two additional constraints can be related. The method of solution proposed also applies to the case that a lexicographic optimization is to be performed.

---

Zusammenfassung Gegenstand dieses Beitrags sind unkapazitierte einstufige Transportprobleme, deren Nebenbedingungen nicht ausschließlich in Gleichungsform vorliegen. Einem einstufigen Transportproblem mit gemischten Restriktionen läßt sich ein erweitertes klassisches Transport-problem zuordnen, aus dessen optimaler Lösung eine optimale Lösung des Ausgangsproblems ermittelt werden kann. In diesem Beitrag soll gezeigt werden, daß zur Generierung eines erweiterten klassischen Transportproblems die Einführung einer Zeilenrestriktion und einer Spaltenrestriktion ausreichen. Die hier vorgestellte Vorgehensweise bietet sich auch im Falle einer lexikographischen Optimierung an.

     

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.     

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

Optimization model of transport currents

An optimization model of a one-dimensional transportation network is considered under the condition that the distribution of sources and sinks (for example, the population and workplaces in urban planning problems) is expressed in terms of finite Borel measures ϕ⁺ and ϕ⁻ of the same total masses, whereas the unknowns are one-dimensional Federer-Fleming currents T and S modeling transportation of people with or without the use of a public transportation network respectively. The choice of the network must provide the minimum for the cost of mass transfer from sources to sinks (for example, the transportation of people to workplaces) together with the cost of construction and exploitation of the network. Thus, the problem is to minimize the functional

A bad network problem for the simplex method and other minimum cost flow algorithms

For any integern, a modified transportation problem with 2n + 2 nodes is constructed which requires 2 ⁿ + 2 ^n–2–2 iterations using all but one of the most commonly used minimum cost flow algorithms.As a result, the Edmonds—Karp Scaling Method [3] becomes the only known good (in the sense of Edmonds) algorithm for computing minimum cost flows.     

A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources

We investigate a special case of the bottleneck transportation problem where the number s of sources is bounded by a constant and not part of the input. For the subcase s=2, a best-possible linear-time algorithm has been derived by Varadarajan [Oper. Res. Lett. 10 (1991) 525–529]. In this note we show that for any fixed number s⩾1, the bottleneck transportation problem with s sources can be solved in linear-time. The algorithm is conceptually simple, and easy to implement.