Search

In this paper, we study the quadratic assignment problem with a rank-one cost matrix (QAP-R1). Four integer-programming formulations are introduced of which three are assumed to have partial integer data. Unlike the standard quadratic assignment problem, some of our formulations can solve reasonably large instances of QAP-R1 with impressive running times and are faster than some metaheuristics. Pairwise relative strength of the LP relaxations of these formulations are also analyzed from theoretical and experimental points of view. Finally, we present a new metaheuristic algorithm to solve QAP-R1 along with its computational analysis. Our study offers the first systematic experimental analysis of integer-programming models and heuristics for QAP-R1. The benchmark instances with various characteristics generated for our study are made available to the public for future research work. Some new polynomially solvable special cases are also introduced. Summary of Contribution: This paper aims to advance our knowledge and ability in solving an important special case of the quadratic assignment problem. It shows how to exploit inherent properties of an optimization problem to achieve computational advantages, a strategy that was followed by researchers in model building and algorithm developments for decades. Our computational results attest to this time-tested general philosophy. The paper presents the first systematic computational study of the rank one quadratic assignment problem, along with new mathematical programming models and complexity analysis. We believe the theoretical and computational results of this paper will inspire further research on the topic and will be of significant value to practitioners using rank one quadratic assignment models. [ABSTRACT FROM AUTHOR]

This paper introduces the multiconstraint team orienteering problem with multiple time windows (MC-TOP-MTW). In the MC-TOP-MTW, a set of vertices is given, each with a service time, one or more time windows, and a score. The goal is to maximize the sum of the collected scores, by a fixed number of tours. The tours are limited in length and restricted by the time windows and additional constraints. Next to a mathematical formulation of the MC-TOP-MTW, the main contribution of this paper is a fast and effective algorithm for tackling this problem, by hybridizing iterated local search with a greedy randomized adaptive search procedure. On a large test set, an average run has a score gap of only 5.19% with known high quality solutions, using 1.5 seconds of computational time. For 32% of the test instances, the known high quality solution was found or improved. This solution method also performs well on test instances of the TOPTW, the selective vehicle routing problem with time windows, and the MC-TOP-TW. A sensitivity analysis shows that the performance of the algorithm is insensitive to small changes in the parameter settings. [ABSTRACT FROM AUTHOR]

This paper presents an efficient algorithm for an integrated operating room planning and scheduling problem. It combines the assignment of surgeries to operating rooms and scheduling over a short-term planning horizon. This integration results in more stable planning through consideration of the operational details at the scheduling level, and this increases the chance of successful implementation. We take into account the maximum daily working hours of surgeons, prevent the overlapping of surgeries performed by the same surgeon, allow time for the obligatory cleaning when switching from infectious to noninfectious cases, and respect the surgery deadlines. We formulate the problem using a mathematical programming model and develop a branch-and-price-and-cut algorithm based on a constraint programming model for the subproblem. We also develop dominance rules and a fast infeasibility-detection algorithm based on a multidimensional knapsack problem to improve the efficiency of the constraint programming model. The computational results show that our method has an average optimality gap of 2.81% and significantly outperforms a compact mathematical formulation in the literature. [ABSTRACT FROM AUTHOR]

We present a new computational approach to the problem of placing n identical nonoverlapping disks in the unit square in such a way that their radii are maximized. The problem has been studied in a large number of papers, from both a theoretical and a computational point of view. In this paper, we conjecture that the problem possesses a so-called funneling landscape, a feature that is commonly found in molecular conformation problems. Based on this conjecture, we develop a stochastic search algorithm that displays excellent numerical performance. Thanks to this algorithm, we could improve over previously known putative optima in the range n ≤ 130 in as many as 32 instances, the smallest of which is n=53. [ABSTRACT FROM AUTHOR]

This paper presents the spiral array model and its associated algorithms for tonal induction, approximation, and segmentation. The spiral array is a geometric model for tonality that clusters perceptually similar tonal entities. The model summarizes music information as interior points inside an array of spirals. Distances in the spiral array space are used to quantify tonal similarity. The paper traces the evolution, and presents general forms, of the existing algorithms for key finding, pitch spelling, and segmentation, and proposes a new O(n) algorithm, Argus, for tonal segmentation. The proposed algorithm computes a value that quantifies the discrepancy between the local contexts in the future and past at each point in time. Discrepancy values exceeding control thresholds are shown to mark the segmentation boundaries of the test set that concur with expert analyses. A number of window sizes and threshold settings are investigated. The algorithm is demonstrated using Edward MacDowell's To A Wild Rose and tested on Franz Schubert's Allegretto from Moment Musical D780 No. 6 and Thema from Impromptu D935 No. 4. The algorithm accurately locates tonal boundaries in all three case studies. [ABSTRACT FROM AUTHOR]

Vehicle scheduling is the process of assigning vehicles to a set of predetermined trips with fixed starting and ending times, while minimizing capital and operating costs. This paper considers modeling, algorithmic, and computational aspects of the polynomially solvable case in which there is a single depot and vehicles are identical. A quasiassignment formulation is reviewed and an alternative asymmetric assignment formulation is given. The main contributions of the paper area new two-phase approach which is valid in the case of a special cost structure, an auction algorithm for the quasiassignment problem, a core-oriented approach, and an extensive computational study. New algorithms are compared with the most successful algorithms for the vehicle-scheduling problem, using both randomly generated and real-life data. The new algorithms show a significant performance improvement with respect to computation time. Such improvement can, for example, be very important when this particular vehicle-scheduling problem appears as a subproblem in more complex vehicle- and crew-scheduling problems. [ABSTRACT FROM AUTHOR]

Modeling of transportation systems must invariably balance behavioral richness and computational tractability. In this paper, we develop a transportation equilibrium model and an algorithm for the simultaneous prediction of trip generation, trip distribution, modal split, and trip assignment on large-scale networks. The model achieves a practical compromise between behavioral and computational aspects of modeling the problem. It is formulated as an equivalent convex optimization problem, yet it is behaviorally richer than other models that can be cast as equivalent convex programs. Although the model is not as behaviorally rich as the most general equilibrium models, it has computational advantages. The applications reported in this paper of the model to real systems, i.e., the intercity transport network of Egypt and the urban transportation network of Austin, Texas, illustrate the computational attractiveness of the approach. These results indicate that equivalent optimization formulations are not as restrictive as previously thought, and hence, the equivalent convex programming approach for modeling and predicting equilibrium on transportation systems remains a viable and fruitful avenue for future consideration. [ABSTRACT FROM AUTHOR]

This paper contains linear algorithms for finding the Jordan center, the weighted Jordan center and the path center of a tree. All of these algorithms take advantage of an efficient data structure for representing a tree called a canonical recursive representation. As a result, the first two algorithms are different from and faster than similar algorithms in the literature. This paper also defines a new parameter of a graph called the path center, and shows that the path center of a tree T consists of a unique subpath of T. [ABSTRACT FROM AUTHOR]

The many-to-many stable matching problem (MM), defined in the context of a job market, asks for an assignment of workers to firms satisfying the quota of each agent and being stable, pairwise or setwise, with respect to given preference lists or relations. In this paper, we propose a time-optimal algorithm that identifies all stable worker-firm pairs and all stable assignments under pairwise stability, individual preferences, and the max-min criterion. We revisit the poset graph of rotations to obtain an optimal algorithm for enumerating all solutions to the MM and an improved algorithm finding the minimum-weight one. Furthermore, we establish the applicability of all aforementioned algorithms under more complex preference and stability criteria. In a constraint programming context, we introduce a constraint that models the MM and an encoding of the MM as a constraint satisfaction problem. Finally, we provide a series of computational results, including the case where side constraints are imposed. [ABSTRACT FROM AUTHOR]

In recent years, many algorithms have been proposed to extract process models from process execution logs. The process models describe the ordering relationships between tasks in a process in terms of standard constructs like sequence, parallel, choice, and loop. Most algorithms assume that each trace in a log represents a correct execution sequence based on a model. In practice, logs are often noisy, and algorithms designed for correct logs are not able to handle noisy logs. In this paper we share our key insights from a study of noise in process logs both real and synthetic. We found that all process logs can be explained by a block-structured model with two special self-loop and optional structures, making it trivial to build a fully accurate process model for any given log, even one with inaccurate data or noise present in it. However, such a model suffers from low quality. By controlling the use of self-loop and optional structures of tasks and blocks of tasks, we can balance the quality and accuracy trade-off to derive high-quality process models that explain a given percentage of traces in the log. Finally, new quality metrics and a novel quality-based algorithm for model extraction from noisy logs are described. The results of the experiments with the algorithm on real and synthetic data are reported and analyzed at length. [ABSTRACT FROM AUTHOR]

Route planning in large-scale time-dependent road networks is an important practical application of the shortest-path problem that greatly benefits from speedup techniques. In this paper, we extend a two-level hierarchical approach for point-to-point shortest-path computations to the time-dependent case. This method, also known as core routing in the literature for static graphs, consists of the selection of a small subnetwork where most of the computations can be carried out, thus reducing the search space. We combine this approach with bidirectional goal-directed search to obtain an algorithm capable of finding shortest paths in a matter of milliseconds on continental-sized networks. Moreover, we tackle the dynamic scenario where the piecewise linear functions that we use to model time-dependent arc costs are not fixed but can have their coefficients updated requiring only a small computational effort. [ABSTRACT FROM AUTHOR]

Despite the fact that no polynomial-time algorithm is known for solving mixed-integer programming (MIP) problems, there has been remarkable success in recent years in solving a wide range of difficult MIPs. In this paper, we take a look at some of the hardest problems in the MIPLIB 2003 test set and show how Xpress-MP can be used to solve some of the problems that were previously thought to be intractable. [ABSTRACT FROM AUTHOR]

We consider online versions of the traveling salesman problem (TSP) and traveling repairman problem (TRP) where instances are not known in advance. Cities (points) to be visited are revealed over time, while the server is en route serving previously released requests. These problems are known in the literature as the online TSP (TRP, respectively). The corresponding offline problems are the TSP (TRP) with release dates, problems where each point has to be visited at or after a given release date. In the current literature, the assumption is that a request becomes known at the time of its release date. In this paper we introduce the notion of a request's disclosure date, the time when a city's location and release date are revealed to the server. In a variety of disclosure date scenarios and metric spaces, we give new online algorithms and quantify the value of this advanced information in the form of improved competitive ratios. We also provide a general result on polynomial-time online algorithms for the online TSP. [ABSTRACT FROM AUTHOR]

In this paper we introduce the problem of shunting passenger train units in a railway station. Shunting occurs whenever train units are temporarily not needed to operate a given timetable. We discuss several aspects of this problem and focus on two subproblems. We propose mathematical models for the problem and both subproblems, one of which is solved with a solution method based on column generation. Furthermore, we introduce a new efficient and speedy solution technique for pricing problems in column generation algorithms. Finally, we present computational results based on real-life instances from Netherlands Railways. [ABSTRACT FROM AUTHOR]

In this paper, we develop a unified framework for approximating open and closed queueing networks under any general blocking protocol by extending and generalizing the approximation algorithm for open tandem queues under minimal blocking presented in Di Mascolo et al. (1996). The proposed framework is based on decomposition. We develop decomposition structures and analysis algorithms for any general blocking system using the framework. The proposed algorithms have been extensively tested using simulations as a benchmarking device. The results show that the proposed framework yields robust, reliable, and accurate estimates of system characteristics, such as throughput and Work-In-Process inventory in a wide range of system configurations. The computational load is minimal. The unified framework presents a highly useful set of tools of analysis for queueing-system designers to use in evaluating the performance under numerous design alternatives. Directions for future research are presented, with a focus on critical application areas such as packet-switching-network design and cellular manufacturing. [ABSTRACT FROM AUTHOR]

Placement of inspection stations is a common task in transportation and communication networks. In this paper, two categories of problems involving placement of inspection stations are studied. The first category deals with the selection of inspection stations along a given path from an origin to a destination. The second considers simultaneous selection of both a path and inspection stations along that path. We formulate these problems under a variety of minimization objectives such as the maximum gap between two consecutive inspection stations, the expected penalty cost of failure along the path, and the total inspection cost. Our results include efficient algorithms for many formulations and complexity results as well as fully polynomial approximation schemes for other formulations. When considering cost objectives, we identify a core problem and show that the complexity of many formulations is directly related to the complexity of the core problem. [ABSTRACT FROM AUTHOR]

The aim of this paper is to present a new heuristic method for the Traveling Salesman Problem with Time Windows, based on the solution of an auxiliary problem. The idea is to solve an assignment problem with an ad hoc objective function to obtain a solution close enough to a feasible solution of the original problem. Given this solution, made by a long main tour containing the depot and few small subtours, it is easy to insert all the subtours into the main path using a greedy insertion procedure. The algorithm described applies the proposed constructive scheme and then uses a local search procedure to improve the initial solution. The computational results show the effectiveness of this approach. [ABSTRACT FROM AUTHOR]

The continuous dynamic network loading problem (CDNLP) consists in determining, on a congested network, time-dependent arc volumes, together with arc and path travel times, given the time-varying path flow departue rates over a finite time horizon. This problem constitutes an intrinsic part of the dynamic traffic assignment problem. In this paper, we present a formulation of the CDNLP where travel delays may be nonlinear functions of arc traffic volumes. We prove, under a boundedness condition, that there exists a unique solution to the problem and propose for its solution a finite-step algorithm. Some computational results are reported for a discretized version of the algorithm. [ABSTRACT FROM AUTHOR]

The Fermat location problem is to find a point whose sum of weighted distances from m given points (vertices) is a minimum. The best known method of solution is an iterative scheme devised by Weiszfeld in 1937, which converges to the unique minimum point unless one of the iterates happens to "land" on a nonoptimal vertex. The convergence proof of this scheme depends on two theorems, one of which (descent theorem) states that the objective function strictly decreases at each step. This paper extends the descent theorem by proving: (1) there is a "ball" whose radius and center depend on the Weiszfeld iteration, such that any algorithm whose iterates are "in the ball" or "on its surface" is a descent algorithm; (2) under certain circumstances, one or more of the vertices may be deleted, although the weight(s) are taken into account, and the Weiszfeld algorithm retains its descent property. In general there are several subsets of vertices which may be deleted, and for each subset, a corresponding iterate; (3) the convex hull of these iterates is such that all points within it have the descent property. Examples of the potential application of these extensions are given, including the construction of a modified Weiszfeld algorithm that without exception converges to the optimum. Beyond that, it is hoped the theorems may in time be useful in proving the descent property of yet to be discovered, very fast, nongradient algorithms. [ABSTRACT FROM AUTHOR]

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 this paper, we consider the problem of determining a path that maximizes a multi-attribute, non-order-preserving value function. The motivating application is the determination of a most preferred path for transporting hazardous materials based on transportation cost and risk to population. A sub-path of an optimal path may not be optimal for a non-order-preserving value function, implying that a traditional application of dynamic programming may intentionally or unintentionally produce sub-optimal paths. We consider two approximation procedures for two general cases, the q = 0 case and the q > 0 case, where q is the number of required intermediate stops between origin and destination. The first approximation procedure involves applying dynamic programming as if a sub-path of an optimal path were always optimal. The second approximation procedure involves determining a linear order-preserving criterion that approximates the non-order-preserving value function and then applying dynamic programming. We use the best-first search algorithm BU* to determine optimal routes for both the q = 0 and q > 0 cases. We examine the frequency and magnitude of the resulting sub-optimalities for a multi-attribute value model based on a six-county road network that includes Cleveland, Ohio. Numerical results show that if one of the two approximations is used, significant sub-optimalities can occur over a wide range of decision maker preferences. Both approximations can produce sub-optimality error magnitudes of over 50%. [ABSTRACT FROM AUTHOR]

Many transportation problems can be formulated as a linearly-constrained convex programming problem whose objective function consists of entropy functions and other cost-related terms. In this paper, we propose an unconstrained convex programming dual approach to solving these problems. In particular, we focus on a class of linearly-constrained entropy maximization problem with quadratic cost, study its Lagrangian dual, and provide a globally convergent algorithm with a quadratic rate of convergence. The theory and algorithm can be readily applied to the trip distribution problem with quadratic cost and many other entropy-based formulations, including the conventional trip distribution problem with linear cost, the entropy-based modal split model, and the decomposed problems of the combined problem of trip distribution and assignment. The efficiency and the robustness of this approach are confirmed by our computational experience. [ABSTRACT FROM AUTHOR]

In this paper we consider the optimal location of a single facility with respect to a set of demand points on a tree network. The demands of the points to be served are dynamic and our model takes into account predictable changes in these demands. We study problems with both linear and nonlinear demand functions. We make use of the analytical properties of tree networks and sensitivity analysis, and devise efficient algorithms to construct the optimal trajectory of the parametric location problem. We also give theory that exploits the network topology. [ABSTRACT FROM AUTHOR]

The paper describes a model for the optimal management of periodic deliveries of a given commodity. The goal is to schedule the deliveries according to feasible combinations of delivery days and to determine the scheduling and routing policies of the vehicles in order to minimize over the planning horizon the maximum number of vehicles simultaneously employed, i.e., the fleet size. Heuristic algorithms are proposed and computational experience is reported. [ABSTRACT FROM AUTHOR]

In this paper, a branch and bound algorithm is presented for solving network design problems (NDP). Route selection for the NDP is based on a stochastic incremental traffic assignment approach. Experiments are performed to compare the behaviors of three assignment methods. Numerical examples are presented to illustrate the algorithm for solving the NDP. [ABSTRACT FROM AUTHOR]

In this paper we develop a new heuristic for the hierarchical network design problem. The heuristic is based upon Lagrangian relaxation of a reformulation of the problem. In addition, we develop a branch and bound algorithm to identify the optimal solution for the 5% of the test problems for which the new heuristic failed to do so. This algorithm proved to be very efficient due to the tight bounds generated by the heuristic. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of finding an optimal path of a single service unit that travels toward a "nonservice" destination. Two types of objective functions are examined. One objective function is the minimization of the maximum distance (or weighted distance) between the moving service unit and any demand (node) of the network. The second objective function is the minimization of the total time period that the distance (or weighted distance) between the moving service unit and any node exceeds a response time threshold λ. For these two objective functions, we present algorithms which can be calculated, respectively, in O(n&sup 3;) and O(n&sup 3;log n) elementary operations. [ABSTRACT FROM AUTHOR]

This paper discusses a model for the problem of locating garages in an urban mass transit system and the associated assignment of vehicles to garages for background and peak services of transit lines. The objective of this model is to minimize the sum of fixed site-related costs, variable vehicle costs, and crew relief costs. The model is solved by an iterative procedure involving a location interchange heuristic and a network flow-based algorithm. The implementation of the model is discussed through its various stages, from data preparation to the final policy recommendations. [ABSTRACT FROM AUTHOR]

We consider algorithms proposed for solving the fixed demand user optimized network equilibrium problem with asymmetric user costs. Because the Jacobian matrix for the costs is asymmetric, no known equivalent convex optimization problem exists and alternative solution methods to nonlinear programming techniques must be sought. The purpose of this paper is to compare the performance of several existing methods for determining the equilibrium network flows of a small realistic network model in which intersection controls are incorporated which lead to particularly asymmetric cost functions. [ABSTRACT FROM AUTHOR]

The article focuses on the convergence of equilibrium algorithms with predetermined step sizes. The classical iterative approach to solving minimization programs is to identify a descent direction and choose a step size, which minimizes the objective function along this direction at each iteration. However, the solution of some problems is hampered by the difficulty in evaluating the objective function along the descent direction. The paper focuses on a certain class of traffic assignment problems where the objective function is formulated in terms of paths and thus impractical to compute for large networks.

This paper investigates the accuracy of the pro bit approximation based solution of the spatial aggregation problem of traffic assignment. It tests the normal approximation to uniform intrazonal travel times and the Clark approximation to the solution of the choice probabilities between alternatives characterized by normally distributed travel times. Some guidelines for using the technique are developed. [ABSTRACT FROM AUTHOR]

Recent advances in network equilibrium modeling provide efficient algorithms for solving the urban trip assignment problem. These models can be extended to incorporate the trip distribution problem with two types of variable demand functions. By reinterpreting the zone-to-zone trip variable, these models can be viewed as urban location models. This paper synthesizes these results and shows how several urban location models can be derived from the mathematical framework based on the network equilibrium problem. [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]

The article presents O(N log N) algorithm for the rectilinear round-trip location problem. It refers to papers by authors A.W. Chan and D.W. Hearn, where the problem definition is given and by authors T. Ichimori and T. Nishida, where it is shown that this problem can be solved in O(N log N) time.

This article provides information about the various topics discussed in the May 1, 1994 issue of the journal "Transportation Science." In the classical capacitated plant location problem, the aim is to locate a number of facilities to satisfy customer demand and to minimize the sum of transportation costs between customers and facilities. The problem under consideration in this paper consists of optimally determining the location and size of facilities given that future customer demand is uncertain. Location theory includes a large number of seemingly different problems. Researchers have provided heuristic solution procedures as well as optimal algorithms for special cases of individual problem. This paper introduces a generic multifacility location problem and shows that it subsumes several existing location models or at least restrictions of these models. Some of the problems may require reformulation. By exploiting the underlying structure of the generic multifacility location problem, the authors provide an algorithm for solving it in polynomial time for special cases.