Search

The multi-index transportation problem is defined and a summary of the algorithm described in an earlier paper is given. This paper discusses the theorems justifying the use of the algorithm and gives a necessary condition for the existence of a solution. It also describes the formulation of three special-structure linear-programming problems as examples of multi-index problems. The three problems discussed are the capacitated Hitchcock problem, transportation where there is more than one method of transport available, and the transformation of one type of multi-index problem into another. A final section describes problems that have restrictions in the form of inequalities. [ABSTRACT FROM AUTHOR]

This paper treats the optimal location of nuclear-power plants in the Pacific Northwest with respect to capital-construction, operating, and transmission costs. It presents a mathematical formulation of this two-product (peak and energy power) plant-location problem, using the simplex method in conjunction with a branch-and-bound process, and indicates a check procedure using Vogel's approximation method in conjunction with an algorithm for solving the transportation problem and a branch-and-bound process. The paper gives results for demand-growth rates of 4, 5, 6 and 7 percent and alternative designs and their costs. It also discusses the stability of the optimal solution. [ABSTRACT FROM AUTHOR]

The purpose of the present paper is to extend the loop-technique of the stepping-stone algorithm to the generalized transportation problem. The main result (Theorem and Corollary of §6) is, that passing from a basic feasible solution to another one may always be carried out by constructing a simple symmetrical or a double loop (as defined in §2) and computing new values for the variables only along this path. The amount of computations needed for this turns out to be substantially reduced as compared to the usual way of solving the system of equations relating the new basis to the old one. [ABSTRACT FROM AUTHOR]

This paper defines a problem type, called the transportation-location problem, that can be considered a generalization of the Hitchcock transportation problem in which, in addition to seeking the amounts to be shipped from origins to destinations, it is also necessary to find, at the same time, the optimal locations of these sources with respect to a fixed and known set of destinations. This new problem is characterized mathematically, and exact and approximate methods are presented for its solution. [ABSTRACT FROM AUTHOR]

This paper attempts to present the major methods, successful or interesting uses, and computational experience relating to integer or discrete programming problems. Included are descriptions of general algorithms for solving linear programs in integers, as well as some special purpose algorithms for use on highly structured problems. This reflects a belief, on the author's part, that various clever methods of enumeration and other specialized approaches are the most efficacious means existent by which to obtain solutions to practical problems. A serious try at gathering computational experience has been made—but facts are difficult to uncover. The paper is written with intent to enable readers to read selected sections without having to read the whole. [ABSTRACT FROM AUTHOR]

The topology of the Generalized Transportation Problem, at the end of each iteration of the stepping-stone method, is characterized by a variable number of loops to which are attached multiple branched side chains or trees. An efficient computer representation of this structure and methods for updating it are described in this paper. [ABSTRACT FROM AUTHOR]

This paper proposes an algorithm for making a sensitivity analysis on a flow network, specifically, the problem of removing n arcs in a network such that the reduction in the maximum flow between an origin and destination node is maximized. Such an algorithm might be helpful in determining how sensitive a transportation system is to having its roads closed for repairs. [ABSTRACT FROM AUTHOR]

This paper develops a dynamic programming model for selecting an optimal combination of transportation modes over a multiperiod planning horizon. The formulation explicitly incorporates uncertainty regarding future requirements or demands for a number of commodity classes. In addition to determining the optimal modes to employ, the model assigns individual commodity classes to various modes, determines which supply points serve which destinations, and reroutes carriers from destinations to alternative sources where they will be most effective. The model is formulated as an optimal discrete time stochastic control problem where cost is quadratic and dynamic equations linear in the state and control variables. This model may be solved in closed form by an efficient dynamic programming algorithm that permits the treatment of relatively large scale systems. A iso developed is an alternative, generally suboptimal method of solution, based upon wiving a sequence of convex programming problems over time. This technique may be employed for a more general class of problems. In both methods the use of 'shadow prices' that arise is discussed. [ABSTRACT FROM AUTHOR]

This paper reports on an application of computer technology to a significant and costly school administration problem: the transportation of students between home and school. The problem, as it is generally thought of, has been complicated by the consideration of attempting racial balance via busing. We present an algorithm to find a feasible solution which tends to minimize the number of required routes and mileage. After setting down the basic approach used and the results of an application, we will present possible extensions of the approach to school location planning, bus fleets composition and timing conditions on particular bus stops. [ABSTRACT FROM AUTHOR]

The article presents a list of papers published in the 1973 issue of the periodical. Some papers are "Announcements," "API Method Extended," "Airline Crew-Scheduling," "Air-Cargo Deployment Combat Personnel," "Aircraft Average Number Collisions," "Collision Probabilities," "Large Relative Velocity," "Special Cases, Velocity," "Air Fleet Evaluation Model (AFEM)," "Airports, Parallel Runways," "Air Routes, Potential Conflict," "Air-Route Network Planning," "Augmented Predecessor Indexing Method," "Books of Interest," "Brisbane City Council Transport Services, Note," "Broken Shifts, Bus Scheduling," "Bus Crew Scheduling," "Chesapeake Bay Bridge Traffic Control," "Column Generation Algorithm," "Combat Personnel, Equipment, Deployment," "Comparison, Steady-State and Simulation Methods," "Designing Transportation Networks," "Digital Simulation, Freeway Traffic, Long Island Expressway, New York," "Facility Location Algorithm," "Feeder Transit Lines," "Freeway Traffic, Digital Simulation," "General Networks Lemmas," "Generalized Network Problems," and "Generalized Transportation Problems."

The traffic assignment problem associated with a given transportation network is the process of distributing zone-to-zone trips on links of the network. A number of methods have been proposed to solve this problem, but none have been found to be entirely satisfactory. This paper is concerned with the nonlinear mathematical model of the problem, where the link-traveling costs are increasing functions of the link flows and no explicit capacity constraint is imposed on individual links. An efficient algorithm is developed, using a node-arc formulation of the problem. It is an adaptation of the convex-simplex method that takes advantage of the very special network structure of the traffic assignment problem formulated in this way. Numerical results obtained with a moderate size street network are presented. [ABSTRACT FROM AUTHOR]

This paper presents a method for serial combination of truck trips to minimize the total cost of deadheading, subject to constraints on the allowed combinations. The problem is initially formulated as an integer transportation problem with extra compatibility constraints, and then reduced to a classical transportation problem. Modifications of the classical algorithm led to a fifty-fold reduction in computer time, and permit solution of a 1000 × 1000 problem in less than two minutes of computer time. Implementation of the method led to considerable cost savings over the older manual procedure. [ABSTRACT FROM AUTHOR]

This paper is addressed to the problem of locating the absolute and vertex centers (minimax criterion) of an undirected tree graph. Based upon a convexity property of the criterion function a very simple and efficient algorithm is offered that locates the minimax point by locating first a maximax point. The minimax is at the mid-point of the maximum path from the maximax point. The vertex center is located simultaneously. [ABSTRACT FROM AUTHOR]

The general problem is that of locating a central facility in a network so as to minimize the sum of its distances from the sources of flow to it, each distance being appropriately weighted to reflect the associated flow volume and/or cost. In this paper, simple one-pass solution algorithms are given for two classes of topologically simple networks, namely those which are either acyclic or contain exactly one cycle. The first algorithm is based on a reduction procedure that may also yield useful simplification of problems involving general networks. [ABSTRACT FROM AUTHOR]

This paper presents a method for developing efficient timetables for the operation of fixed schedule common-carrier passenger transportation systems. The ability to compute such timetables is needed in the consideration of planning alternatives for future transportation systems and/or the efficient operation of existing systems. Here, time- table optimization is accomplished by maximizing an objective function consisting of three basic components: operating costs, revenues, and traveler benefits. Traveler benefits are computed using a consumer preference model that specifies a traveler's willingness to pay for alternative trips, based on the scheduling of those trips. The optimization is based on successive iterations of a dynamic programming algorithm that develops timetables for each vehicle in the system. Solutions are termed optimal to within a 'first-order passenger exchange! Examples are presented to illustrate the utilization of the methodology for computing information relevant to the development of system operating policies and to the consideration of planning alternatives. [ABSTRACT FROM AUTHOR]

The problem of allocating transportation units to alternative trips can be solved by linear programming. However, the linear programming formulation has three shortcomings: (1) the optimal solution obtained does not have an integer number of trips; (2) the optimal solution may have sets of disconnected cycles; and (3) problems of considerable size will be intractable because of the vast number of variables and constraints. In some applications, it has been found that shortcomings 1 and 2 are not serious, but the third one--the size of the problem--presents considerable difficulty. This paper describes an approach--a column generation scheme with out-of-kilter subproblems--that reduces the size of the problem considerably. An algorithm for the method is given, and it is proved that the algorithm solves the problem in a finite number of steps. Computational experience thus far with this method has been limited, but encouraging. [ABSTRACT FROM AUTHOR]

A production and transportation system is considered in which the produced items successively are transported to n different selling places. Transportation to the N places may be ordered in NI different ways and the effects on the system of different orderings among the selling places when servicing them are studied. If the production capacity is K units per unit of time, and if the N places have associated with them times of transport t1,⋯tN and functions fl,⋯,fN expressing the demand as depending on the time of arrival, it is possible to obtain the total sale on the form KgN,{gN-1[A⋯g1(0)⋯]} where the functions gn are defined in terms of K, tn, and fn. Thus the problem to determine the order to serve that maximizes the total sale is reduced to the problem of finding the optimal permutation of gN {gN-1[ ⋯g1(0⋯). When deriving criterions of optimality for the total sale and related measures of effectiveness the following principle is used: Let E(1,⋯, N) be the effectiveness associated with the ordering 1,⋯, N and let kn. be some characteristic of place n. If k1≦⋯≦kn is sufficient (necessary) for E(l,⋯,N)≧E(l,⋯, n-1 , n+l, n, n+2,⋯N) for n=1⋯, N-1 then this condition is also sufficient (necessary) for E(1,⋯,N)≧E (i1, iN) for every permutation i1,⋯ of 1⋯,N. [ABSTRACT FROM AUTHOR]

A linear control algorithm is proposed for the computer operation of a signalized traffic intersection. A theoretical analysis of the algorithm under the assumption of constant vehicular arrival and departure rates shows that the control is stable under unsaturated conditions, and with proper choice of control constants usually gives a rapid convergence to a limit cycle that minimizes the average delay. [ABSTRACT FROM AUTHOR]

Describes an algorithm for computing interzonal transfers using the gravity model. Application of the gravity model to the problem of estimating the number of automobile trips between pairs of points of a highway network given the number of trips that arrive and depart each point.

A linear programming model is set forth for maximizing a vector of final demand deliveries under both regional production constraints and transportation network constraints. The model is essentially designed to study short-run effects, and hence no provision is made for the expansion of either industrial or transportation capacities. Within available capacities, however, the location of production is chosen so as to maximize final demand deliveries. A rough dynamic version of the model is presented as well as an algorithm for reaching an approximation of the optimum solution. [ABSTRACT FROM AUTHOR]

The article discusses the "transportation problem," which is a class of linear programming problems involving the selection of the most economical shipping routes for a commodity from given sources to given destinations. The transportation problem has been typically approached either as a specialized type of linear programming problem or as a method of representation of some combinatorial problems. The author asserts that a third method is possible, which is applicable for the determination of optimum linked paths over a series of points, or "transhipment." The transhipment problem is more complex than shipping an item from one point to another, because points can now be both origins and destinations. The question resembles a combinatorial problem but may be solved by linear programming.