Search

This paper describes an algorithm for a ship scheduling problem, obtained from a Swedish ship-owning company. The algorithm uses the Dantzig-Wolfe decomposition method for linear programming. The subprograms are simple network flow problems that are solved by dynamic programming. The master program in the decomposition algorithm is an LP problem with only zero-one elements in the matrix and the right-hand side. Integer solutions are not guaranteed, but generation and solution of a large number of problems indicates that the frequency of fractional solutions is as small as 1-2 per cent. Problems with about 40 ships and 50 cargoes are solved in about 2.5 minutes on an IBM 7090. In order to resolve the fractional cases, some integer programming experiments have been made. The results will be reported in a forthcoming paper. [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]

In many transit systems, vehicles depart their originating stops at fixed intervals, but headways become increasingly irregular as they move along the line. This paper considers how best to control such randomness through a strategy based on holding individual vehicles at a chosen control stop. An algorithm is presented for constructing an approximate optimal dispatching strategy from the control point, where optimal is defined both in terms of average passenger wait at the control stop and average delay for riders already aboard the vehicle. The algorithm is used on actual operations data from a Boston subway line to propose service improvements. [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]

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]

In this paper the authors find the optimal allocation of servicing periods to a facility servicing N incoming traffic streams. In our model it is assumed that stream flows are deterministic, that there is a fixed amount of lime lost, τi , when the server switches attention from the ith to the i + 1st stream and that the objective is to minimize time average delay. [ABSTRACT FROM AUTHOR]