Search

The paper presents a mathematical investigation into bus scheduling. The passenger arrival rate is supposed to be given; the problem is to determine the bus departure rate as a function of time. The primary objective is to minimize the number of buses that is needed. A secondary criterion is the minimization of the passenger waiting time, for which a calculus of variation technique is used. Although the paper deals mainly with a single busroute, it is also shown how the theory can be extended to the case of a pair of linked busroutes. The practical implications are illustrated by an example. The fleetsize formula that is used here is thought to be applicable to many transportation systems. [ABSTRACT FROM AUTHOR]

The article presents a paper, which shows how to determine the optimal number and routings of containers used to move mail among several cities. This paper extends the above system to more than two cities, with different schedules on different days and with transfer of containers permitted throughout the system. A mathematical formulation is developed that can be readily solved by known linear programming techniques. Critical assumptions are (a) periodic demand patterns and linear transportation costs between each city-pair, and (b) constant fixed cost per container in the system. The optimization problem is transformed into a network flow linear program for which efficient solution methods are known. The researchers have investigated a system where containerized mail would be sent between two cities. The problem solved in reference was that of determining the best number of containers to be sent each day between the two cities, based on (a) the distribution of mail volumes going between the cities each day and (b) the costs for sending containers, full or empty, and for sending mail by other means in case of container shortage. Thus the original convex programming problem has been converted to an especially tractable type of linear program, namely the optimization of a network flow.

In a previous paper, APPELGREN (1969), a decomposition algorithm for a class of vessel scheduling problems was presented. In some problems, the algorithm gives fractional solutions that cannot be interpreted as feasible schedules. This paper treats two integer programming methods that can be used to resolve these cases. The cutting plane method that was first tested was abandoned because it was not able to solve all the test problems. The second method is a branch-and- bound algorithm, where the branching is performed on one of the `essential' fractional variables and where the bounds are obtained by the decomposition algorithm. All fractional problems that have been found by simulation or in regular use of the algorithm have been solved, mostly with one branching only. There are fundamental difficulties in combining these integer programming methods with the DANTZIG-WOLFE decomposition, since the constraints generated in the master program have to be taken into account in the solution of the subprograms. The success in this case is due to the simple structure of the master LP problem. [ABSTRACT FROM AUTHOR]

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 various theoretical analyses that have been made of delay to traffic at a fixed time traffic signal are critically reviewed. The more practicably applicable expressions for the average delay per vehicle, especially those derived by Webster, Miller, and Newell, are examined in some detail, and this paper provides an introduction to numerical comparisons to be reported by Hutchinson in the sequel. [ABSTRACT FROM AUTHOR]

This paper describes an aircraft scheduling model which accounts for indivisibilities in production (airplanes, flights), capacity costs due to peak demand, and consumer preferences regarding the time of day flights are scheduled. Application of the model to real-world routing problems is not intended, as the scope is limited to a system comprised of a single city pair. However, the model does make possible a detailed examination of the economic welfare aspects of various routing criteria and the degree of realism in the assumptions made. Cost functions formulated from CAB data, along with hypothesized characteristics of air travel demand, form a data base for the model. Results are included to show the effect on economic welfare of utilizing a model which fails to incorporate passenger preferences as to the time of day flights are scheduled. [ABSTRACT FROM AUTHOR]

The article focuses on models of fleet routing and scheduling problems for transportation systems, which are formulated as integer linear programs with 0-1 variables. The topics discussed in this paper are concerned with important operational problems confronting the management of the competitive air transportation system. Some of these problems are significant for other transportation systems, including those with public-service rather than profit objectives. The problems are those connected with fleet utilization, fleet size, routing, and scheduling. Work that is related to some of these problems has been carried out by operations researchers and has been limited because, when optimal solutions were sought, computation times were excessive. The principal method of attack has been dynamic programming, which usually involves a very large state space for any real-life transportation system. The basic models are of the discrete-time rather than of the continuous-time variety. This property permits the formulation of the optimization problems as integer linear programs. The aim is to formulate a realistic model and to obtain its optimal solution

The Dantzig and Fulkerson Tanker Scheduling Problem is concerned with the determination of the minimum size and optimal routing of a fleet of homogeneous tankers needed to meet a prescribed schedule of deliveries. This problem has been formulated as a network flow problem. Later formulations consider an existing nonhomogeneous tanker fleet and relax the fixed shipping schedule. These problems are treated as multicommodity minimal cost flow problems. This paper further extends the problem to consider differing carrying capabilities of the vehicles and formulates a mixed integer linear program that permits partially loaded tankers. A branch-and-bound enumerative scheme in conjunction with a decomposed linear program with network sub-problem is presented. [ABSTRACT FROM AUTHOR]

Investigations of motorist delays at the intersection of a major and minor road have involved variations of one or the other of two merging strategies: (i) MILLER'S[8] model that assumes that a minor-road motorist makes consecutive decisions consistently, and (ii) that of WEISS AND MARADUDIN[7] that assumptions that a different, independent decision is made for each headway. In this paper we show that results for both models may be obtained easily, using the results of queuing theory, if certain reasonable assumptions are made. Simple expressions for the Laplace-Stieltjes transforms and means of the delays are derived in the case of independent major-road headways with a common, general distribution. For exponential headways, a numerical study shows the mean Miller delay to increase with the variation in the merge times, while the mean Weiss-Maradudin delay decreases. To illustrate the application of the expressions obtained, we investigate the reduction in the delay achieved by inserting a traffic island between two streams of major-road traffic. [ABSTRACT FROM AUTHOR]

The paper discusses the computer construction of the lists of weeks of work that form the basis of the rotating roster for crews operating buses for a transit system. There are two construction phases; the first consists of making a day-off pattern and the second consists of placing daily shifts in the lists under the constraint of the day-off pattern. Techniques used to attain objectives include integer linear programming and optimal assignment. [ABSTRACT FROM AUTHOR]