Search

The golf director problem is a sports management problem that aims to find an allocation of golf players into fair teams for certain golf club competitions. The motivation for fairness as the objective is that club golf competitions are recreational events for which the golf director needs to form teams that are competitive even though they consist of players with different skill levels measured by their USGA (http://www.usga.org) or R&A (http://www.randa.org) handicaps. We formalize the concept of “fairness" of allocation of players into teams playing 18-hole golf games and argue that finding an optimal assignment of players to teams is intractable for even the fastest computers. Instead, we provide an efficient simulation and optimization-based procedure that finds a near-optimal fair team allocation. Computational tests show the approach to be better than standard methods. A computer implementation of the solution method is publicly available and located at http://www.fairgolfteams.com. The website provides a golf director with a variety of controls to manage and run club golf competitions in a fair way. This is described in the appendix.

In this paper, we extend the toll pricing framework previously developed for vehicular traffic networks to ones with the potential to include many modes of transportation such as walking, driving, and using public conveyance (e.g., buses, subways, and trains). To determine tolls, we construct a user equilibrium and system optimal model. In both models, we assume that users adopt strategies or hyperpaths to travel between each origin-destination pair and the demand between each pair is fixed. However, the choice between driving and using public transportation is determined by a binomial logit function. As in the case of vehicular traffic networks, the set of valid tolls can be obtained from the solution to the system problem and the equilibrium conditions for the user problem. Then, secondary objective functions similar to those for traffic networks can be used to select a toll vector for, e.g., implementation. We provide a numerical example to illustrate our approach.

In this paper, we present a toll pricing framework for a general variable demand traffic assignment problem with side constraints, where the demand between an origin destination pair is a function of the least total travel cost for making the trip. This general demand model unifies earlier toll pricing treatments of the variable demand models including elastic demand traffic assignment problems and combined distribution assignment problems. All of these models have the constant toll revenue property. Given that users experience the side constraints, we show that when they are charged by a toll vector in the first best toll set, the system optimal flows and demands are achieved. We then present a toll pricing framework by which a traffic planner might find the most appropriate toll vector given certain restrictions and objectives on the network. Finally, we derive the toll sets and illustrate the toll pricing framework for specific instances of the general variable demand models.

Club golf competitions are regular events arranged by golf directors (or professionals) for club members. Player skill levels are measured by their USGA or R&A handicaps and it is the job of the director to use the handicaps to organize teams that are, in some sense, fair. The handicap system is limited in that it does not take the variance of players’ scores into account. In this paper we propose two optimization models that employ the handicap distributions from a prior study [1]. The first model directly computes team probabilities to win a single hole, and the second derives team probabilities to win from those of the players. The computational complexity of both models grows exponentially with the number of players. Using scenario optimization, with approximations, the second model is shown to give very good results for up to \(40\) players in reasonable computer time. Also, the solution of a real problem shows that common assumptions about the structure of fair teams are not necessarily correct.

We propose a new algorithm for dynamic lot size models (LSM) in which production and inventory cost functions are only assumed to be piecewise linear. In particular, there are no assumptions of convexity, concavity or monotonicity. Arbitrary capacities on both production and inventory may occur, and backlogging is allowed. Thus the algorithm addresses most variants of the LSM appearing in the literature. Computational experience shows it to be very effective on NP-hard versions of the problem. For example, 48 period capacitated problems with production costs defined by eight linear segments are solvable in less than 2.5 minutes of Vax 8600 cpu time.

We develop a new dynamic programming method for the single item capacitated dynamic lot size model with non-negative demands and no backlogging. This approach builds the Optimal value function in piecewise linear segments. It works very well on the test problems, requiring less than 0.3 seconds to solve problems with 48 periods on a VAX 8600. Problems with the time horizon up to 768 periods are solved. Empirically, the computing effort increases only at a quadratic rate relative to the number of periods in the time horizon.

The golf handicap system is designed to be fair in single player games. The same system is also applied to team games with two or more players per team. In this study the fairness of the particular team golf game known as fourball match play was analyzed as well as measures to improve it. By using historical player data, software was produced to simulate games. The level of fairness was estimated given the handicaps of the players. It was determined that

SYNOPTIC ABSTRACTThis paper presents a variation of the restricted simplicial decomposition (RSD) algorithm especially designed for solving nonlinear network problems with unrestricted arc flows and an objective function that is separable, strictly convex and symmetric with respect to the origin. These problems have the drawback that the standard linear subproblem of RSD is unbounded. However, their optimal solution is in the convex hull of a set of spanning tree solutions. The proposed algorithm uses a new linearized subproblem with nonnegative arc costs in a directed network, thereby avoiding negative cycles and guaranteeing the generation of a spanning tree at each iteration. Computational results are presented for some large-scale electrical networks and water distribution problems.

The formulation of static traffic assignment models, with variable and fixed demand, based on Wardrop's first principle, are presented for deterministic and stochastic models. The main algorithms used to obtain solutions for these network equilibrium models are given for each class of assignment problems. Calibration and validation issues are considered.

The partitioning technique of J.F. Benders, which was generalized to nonlinear programming by Geoffrion, is further generalized to linearly constrained variational inequality problems. The conditions under which such a generalization is possible and appropriate are examined. An important area of application is the asymmetric traffic assignment problem for which the decomposition assumes a simple and effective form. A computational example demonstrates the algorithm.

Congestion or toll pricing problems in [HeR98] require a solution to the system problem (the traffic assignment problem that minimizes the total travel delay) to define the set of all valid tolls or the toll set. For practical problems, it may not be possible to obtain an exact solution to the system problem and the inaccuracy in an approximate system solution may render the toll set empty. When this occurs, this paper offers alternative toll sets based on relaxed optimality conditions. With carefully chosen parameters, tolls from the relaxed toll sets are shown theoretically and empirically (using four transportation networks in the literature) to induce route choices that are nearly system optimal.

Traffic equilibrium models are commonly in use for the prediction of traffic patterns on transportation networks that are subject to congestion phenomena. Even though their application in various transportation planning contexts has increased dramatically over the past twenty five years, due to the development of efficient solution algorithms and the increasing power of various computing platforms, they are based on concepts that have been stated more than seventy years ago. The idea of traffic equilibrium originated as early as 1924, when Knight gave a simple and an intuitive description of a postulate of traffic behavior under congested conditions, as follows: Suppose that between two points there are two highways, one of which is broad enough to accommodate without crowding all the traffic which may care to use it, but is poorly graded and surfaced, while the other is a much better road, but narrow and quite limited in capacity. If a large number of trucks operate between the two termini and are free to choose either of the two routes, they will tend to distribute themselves between the roads in such proportions that the cost per unit of transportation, or effective returns per unit of investment, will be the same for every truck on both routes. As more trucks use the narrower and better road, congestion develops, until a certain point it becomes equally profitable to use the broader but poorer highway.

Although transportation economists have advocated the tolling of urban streets as a mechanism for controlling congestion and managing travel demands for over 50 years, it is only recently that this idea has become practical. When compared to the alternative of building more roads, congestion pricing - in particular via electronic tolling - is attractive and has been adopted in countries around the world. Recent implementations in London, Singapore, and various cities in Norway, as well as a number of projects in the United States, have been judged successful. This book presents rigorous treatments of issues related to congestion pricing. The chapters describe recent advances in areas such as mathematical and computational models for predicting traffic congestion, determining when, where, and how much to levy tolls, and analyzing the impact of tolls on transporation systems. The analyses and methodologies developed in this book provide: - Mechanisms that aid in determining and comparing congestion pricing schemes - Methodologies for evaluating the efficiency of existing and proposed congestion pricing schemes - A means to predict the impact of pricing on urban transporation systems - Information essential to the financial and political success of congestion pricing programs.

The generalized linear programming family of methods (Dantzig-Wolfe decomposition, dual cutting plane, etc.) can be accelerated by the addition of (inexact) line searches in the dual space. Convergence results for this method are given, and a summary of computational experience is presented. The results of solving two sets of problems, namely, linear and quadratic integer programs, are summarized. >

In earlier work a toll pricing framework for congestion pricing has been developed for both fixed and elastic demand traffic assignment models as an alternative to traditional marginal social cost pricing. Within the framework it is possible to define alternative objectives such as minimizing toll costs, minimizing the number of toll booths, etc. This paper will report the results of recent computational experiments on methods designed for various toll pricing objectives.

This paper extends the notion of toll pricing and the toll pricing framework previously developed for fixed demand traffic assignment (Bergendorff, Hearn and Ramana, 1997; Hearn and Ramana, 1998) to the problem with elastic demand. The system problem maximizes net benefit to the network users (Gartner, 1980; Yang and Huang, 1998) and the user problem is the usual one of finding equilibrium with elastic demand. We define and characterize T, the set of all tolls for the user problem that achieve the system optimal solution. When solutions to the two problems are unique, T is a polyhedron defined by the optimal solution of the system problem, similar to the case in (Bergendorff, Hearn and Ramana, 1997; Hearn and Ramana, 1998). The Toll Pricing Framework in (Hearn and Ramana, 1998) is also extended to allow optimization of secondary criteria over T. Examples include minimizing the number of toll booths and minimizing the maximum toll on any link. A numerical example illustrates the results.

Congestion toll pricing addresses the classic traffic assignment problem for which Wardrop enunciated two principles of traffic flow: user-optimal behavioral hypothesis and the notion and system-optimality. (See Florian and Hearn, 1995, for a recent review of the traffic assignment problem and Johnson and Mattson, 1992 for a recent volume of papers on road pricing.) The traditional objective of congestion pricing has been to determine link tolls which will cause the solution of the tolled user-optimal problem to be optimal for the untolled system problem (Arnott and Small, 1994). In most of the literature, the one choice given has been the vector of marginal social cost pricing tolls.

This paper concerns tolling methodologies for traffic networks which ensure that the resultant equilibrium flows are system optimal. A nonnegative vector β is defined to be a valid toll vector, if the set of tolled user equilibrium solutions is a subset of the set of untolled system optimal solutions. The problem of characterizing the toll set τ, which is the set of all valid toll vectors, is studied. Descriptions and characterizations of τ are given for the cases when either the cost map is strictly monotonic or is affine monotonic. In the latter case, the cost map is of the form Qυ + c, where Q is a not necessarily symmetric matrix and Q + Q T is positive semidefinite. The results are illustrated with several examples.

Publisher Summary This chapter introduces the formulation, analysis and solution of the network equilibrium model (NEM). In the sequel, the terminology used will be that associated with the movement of vehicles over a network of streets, such as in an urban traffic network, since this context is a very familiar one. Nevertheless, the use of the model for problems arising in different physical contexts will be outlined, once the model formulation, analysis of its properties, and solution algorithms has been presented. The general version of the network equilibrium problem is formulated and its mathematical structure is analyzed, in order to characterize the existence and uniqueness of solutions. Then, solution algorithms for versions of the network equilibrium problem which may be formulated as nonlinear cost network optimization problems are presented. This is followed by solution algorithms for network equilibrium problems which are formulated as variational inequality problems with an embedded network structure. Then, a relatively short presentation of stochastic network equilibrium models is given. The applicability of the network equilibrium problem in other physical contexts is outlined.

A dual decomposition algorithm is developed for large-scale traffic assignment problems. In contrast to standard methods, this algorithm does not require that the system or user optimal objective function be differentiable and it allows bounds on the arc flows. Iterates alternate between dual ascent steps and calculations of shortest paths as in the Frank-Wolfe method. Although a dual method, it produces feasible flow patterns at each iteration. Convergence of the method is proven and a computational example is given.

Recently introduced optimization formulations of the asymmetric traffic assignment problem are developed. The duality of two formulations is shown, and conditions for convexity and differentiability of the objective functions are given. Convexity conditions are also given for the family of formulations recently introduced by Smith (1983). When the travel cost vector is affine and monotone, all of the formulations are shown to be convex programming problems. Algorithmic implications of the results are discussed.

The problem of determining the effective resistance of a network of resistors is modeled as a quadratic min-cost network flow problem. Using duality theory, it can be reformulated as an unconstrained quadratic program. Based on computational comparison with standard primal methods such as the Frank-Wolfe algorithm, the unconstrained version can be solved for more efficiently by the conjugate gradient technique. Computational results are presented for five large-scale problems from physicists' studies of conducting fibers (sticks) embedded in an insulatng polymer.

In this paper, generalized linear programming (GLP) is treated as a generator of feasible directions for the associated Lagrangian dual problem. In particular, we examine the ascent property of d"G"L"P which is defined to be the difference of two successive dual iterates generated by GLP. It is shown that d"G"L"P always ascends the dual function, L, at the points where L is differentiable. At nondifferentiable points, the choice of column entering the master problem is not unique and an arbitrary choice can produce a nonascent direction. However by appropriate choice of entering column(s), d"G"L"P will be an ascent direction. Computational results on random problems indicate that adding line searches along d"G"L"P directions can improve the performance of GLP.

A finite algorithm is given for finding the smallest sphere enclosing a convex polyhedron in En described by a given system of linear equalities or inequalities. Extreme points of the polyhedron, and minimum spheres enclosing them, are generated in a systematic manner until the optimum is attained.

Unconstrained planar minimax location problems are typically convex but not everywhere differentiable, thus precluding their solution by gradient techniques. We employ subgradients, which always exist, to the solution of some planar minimax location problems. A heuristic subgradient algorithm is presented for the solution of minimax location problems involving Euclidean and rectilinear distances. An attractive feature of the method is the ease of implementation on any size computer. We give a computational comparison of the algorithm with existing methods.

The problem considered is that of finding the location of a facility in the plane so that the maximum weighted rectilinear round-trip distance between the facility and N pairs of existing facilities is minimized. The round-trip distance is the total distance traveled starting from the new facility via a pair of existing facilities and back to the new facility. An efficient one-pass solution procedure is developed for finding all the optimal locations to the problem, and is compared computationally with the simplex method. Two special cases are investigated, namely, when the existing facilities lie on a line, and when all the weights are equal.

The problem considered is that of locating N new facilities among M existing facilities with the objective of minimizing the maximum weighed Euclidean distance among all facilities. The application of nonlinear duality theory shows this problem can always be solved by maximizing a continuously differentiable concave objective subject to a small number of linear constraints. This leads to a solution procedure which produces very good numerical results. Computational experience is reported.