Search

This paper focuses on a generic model for service network design, which includes asset positioning and utilization through constraints on asset availability at terminals. We denote these relations as "design-balance constraints" and focus on the design-balanced capacitated multicommodity network design model, a generalization of the capacitated multicommodity network design model generally used in service network design applications. Both arc- and cycle-based formulations for the new model are presented. The paper also proposes a tabu search metaheuristic framework for the arc-based formulation. Results on a wide range of network design problem instances from the literature indicate the proposed method behaves very well in terms of computational efficiency and solution quality. [ABSTRACT FROM AUTHOR]

The vehicle routing problem with time windows is a hard combinatorial optimization problem that has received considerable attention in the last decades. This paper proposes a two-stage hybrid algorithm for this transportation problem. The algorithm first minimizes the number of vehicles, using simulated annealing. It then minimizes travel cost by using a large neighborhood search that may relocate a large number of customers. Experimental results demonstrate the effectiveness of the algorithm, which has improved 10 (17%) of the 56 best published solutions to the Solomon benchmarks, while matching or improving the best solutions in 46 problems (82%). More important perhaps,the algorithm is shown to be very robust. With a fixed configuration of its parameters, it returns either the best published solutions (or improvements thereof) or solutions very close in quality on all Solomon benchmarks. Very preliminary results on the extended Solomon benchmarks are also given. [ABSTRACT FROM AUTHOR]

This study reviews, in two parts, the formulation, interpretation, and solution methodology of the traffic assignment pro blem with elastic demands, originally described by Beckmann, McGuire and Winsten. This paper (Part I) defines the different possible modes of traffic assignment in a network and identifies the economic rationales of the associated extremism formulations. The accompanying paper (Part II) examines algorithmic approaches for calculating the resulting flow patterns. The assignment pro blem is characterized as an interaction between users and operators of the transportation system, analogous to the interaction between consumers and producers in the marketplace. The notions of "user-optimization" and "system-optimization" thus acquire congruent interpretations, expressed by a systemwide maximization objective. [ABSTRACT FROM AUTHOR]

Unmanned aircraft systems (UASs) are a promising new mode of transportation for cargo delivery. Although control, navigation, and communication technologies are becoming available on individual flight units, system-level motion management for dense UAS traffic remains an open question. This paper presents a motion-planning model based on nonlinear optimization techniques to centrally coordinate paths for all vehicles traversing a shared two-dimensional (2D) space. An exact bound is derived to characterize the discrete-time separation constraints, and a set of new metrics is proposed to measure 2D traffic flow efficiency. The grand goal is to make all vehicles that come under dispatch reach their respective destinations quickly and efficiently while maintaining a safe intervehicle separation at all times. This infinite-horizon operational problem is formulated as a nonlinear nonconvex optimization model that must be solved in a progressive, receding-horizon fashion. To ensure feasibility and overcome path deadlocks attributed to local optima, a series of heuristic measures are developed. By pivoting on artfully coined intermediate feasibility, the algorithm is able to circumvent imminent deadlocks in a predictive manner and progressively construct the solution with guaranteed feasibility. Simulation experiments are performed at various traffic density levels to generate useful insights for airspace regulators and traffic managers. [ABSTRACT FROM AUTHOR]

This paper considers the shortest path problem with waiting costs (SPWC) as an extension to the shortest path problem with time windows. The problem consists of finding the minimum cost path in a network, where cost and time are two independent quantities associated with a path. Path feasibility is constrained by time windows at each node and a linear cost penalty is imposed for each unit of time spent waiting along the path. Starting from a known, nonlinear, integer programming formulation, we propose two alternative formulations for which algorithms already exist. First, we indicate how to transform the SPWC into a shortest path problem with time windows and linear node costs. Second, we prove that the SPWC can also be formulated as a two-resource generalized shortest path problem with resource constraints. Computational results used to compare these alternative formulations are presented. [ABSTRACT FROM AUTHOR]

This paper introduces a strong valid inequality, the 2-path cut, to produce better lower bounds for the vehicle routing problem with time windows. It also develops an effective separation algorithm to find such inequalities. We next incorporate them as needed in the master problem of a Dantzig-Wolfe decomposition approach. In this enhanced optimization algorithm, the coupling constraints require that each customer be serviced. The subproblem is a shortest path problem with time window and capacity constraints. We apply branch and bound to obtain integer solutions. We first branch on the number of vehicles if this is fractional, and then on the flow variables. The algorithm has been implemented and tested on problems of up to 100 customers from the Solomon datasets. It has succeeded in solving to optimality several previously unsolved problems and a new 150-customer problem. In addition, the algorithm proved faster than algorithms previously considered in the literature. These computational results indicate the effectiveness of the valid inequalities we have developed. [ABSTRACT FROM AUTHOR]

This paper presents a constraint logic programming model for the traveling salesman problem with time windows which yields an exact branch-and-bound optimization algorithm without any restrictive assumption on the time windows. Unlike dynamic programming approaches whose performance relies heavily on the degree of discretization applied to the data, our algorithm does not suffer from such space-complexity issues. The data-driven mechanism at its core more fully exploits pruning rules developed in operations research by using them not only a priori but also dynamically during the search. Computational results are reported and comparisons are made with both exact and heuristic algorithms. On Solomon's well-known test bed, our algorithm is instrumental in achieving new best solutions for some of the problems in set RC2 and strengthens the presumption of optimality for the best known solutions to the problems in set C2. [ABSTRACT FROM AUTHOR]

This paper presents a theory of traffic equilibrium which involves responsive signal control policies; in this theory drivers' route choices and the control policy's choice of green times are treated in a symmetrical manner. The central theme of the paper is the iterative optimization assignment algorithm. This algorithm may be considered as a means of calculating equilibria which are consistent with a given responsive control policy. But it may also be regarded as a highly idealized model of the day to day dynamics of drivers' route choices when a responsive signal setting policy is employed; on "day" 1 the signals are held fixed and drivers settle down to an equilibrium flow pattern, on "day 2" the flow pattern is held fixed and the signals are updated according to the control policy for the fixed flow pattern, on "day" 3 the signals are held fixed and drivers settle down to an equilibrium flow pattern.... We state natural but strong conditions on the responsive control policy which guarantee that this algorithm is bound to converge to a convex set of (flow, control) pairs such that (i) the flow is a user equilibrium and (ii) the control parameters satisfy the responsive control policy; and we give a proof of convergence under these conditions--we do not seek to minimize total travel cost. Our conditions involve the delay or cost formula used; with the BPR cost formula, modified in a natural way to allow for green times, the traditional policy of choosing control parameters which minimize delay for the observed traffic pattern does satisfy these conditions in full. However, with Webster's delay formula traditional control policies are a long way... [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 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]

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]

For applications of realistic size, both the discrete and continuous versions of the equilibrium network design problem are too computationally intensive to be solved exactly with the algorithms proposed to date. This intractibility owes to Braess' paradox which makes it necessary to constrain the flow pattern to be a noncooperative Nash or user equilibrium. This paper suggests a new heuristic for finding an approximate solution to the continuous equilibrium network design problem. Numerical tests are reported which indicate that, for networks with significant congestion, the heuristic is markedly more efficient than the Hooke-Jeeves algorithm which has been employed previously. The efficiency of the heuristic results from decomposition of the original problem into a set of interacting optimization subproblems. This decomposition is such that, at each iteration of the algorithm, only one user equilibrium needs to be calculated in order to update the improvement variables of all arcs of the network. This contrasts sharply with the Hooke-Jeeves algorithm which can require that a new user equilibrium be calculated each time an individual arc improvement variable is updated. For applications of realistic size, both the discrete and continuous versions of the equilibrium network design problem are too computationally intensive to be solved exactly with the algorithms proposed to date. This intractibility owes to Braess' paradox which makes it necessary to constrain the flow pattern to be a noncooperative Nash or user equilibrium. This paper suggests a new heuristic for finding an approximate solution to the continuous equilibrium network design problem. Numerical tests are reported which indicate that, for networks with significant congestion, the heuristic is markedly more efficient than the Hooke-Jeeves algorithm which has been employed previously. The efficiency of the heuristic results from decomposition of the original problem into a set of interacting optimization subproblems. This decomposition is such that, at each iteration of the algorithm, only one user equilibrium needs to be calculated in order to update the improvement variables of all arcs of the network. This contrasts sharply with the Hooke-Jeeves algorithm which can require that a new user equilibrium be calculated each time an individual arc improvement variable is updated. [ABSTRACT FROM AUTHOR]

This paper focuses on the problem of finding the optimal travel path of a single service unit to nonemergency destinations. Such destinations result from events other than service calls, e.g., repositioning or relocation operations, returning from the scene of the service call to the "home location," preventive patrol, etc. The analysis is performed on a network model of the urban environment. The time period of interest begins when the service unit starts its travel to a nonemergency destination and ends when the new call for service arrives. The paper contains two models each of which is suitable for a different application. For the two models two different algorithms are presented; one of which is a dynamic programming. These algorithms take into considerations the probabilistic nature of the demand for service. Illustrative examples are also included. [ABSTRACT FROM AUTHOR]

Many transportation applications, including applications in intelligent transportation systems, require the solution of a series of shortest path problems in which only the travel time along a set of arcs of the network change from one problem instance to the next. One could use an existing path algorithm to solve each problem instance independently as it arises. However, significant savings in computation time can often be achieved through the use of a reoptimization algorithm that would begin from the prior solution in determining the updated optimal solution for the given arc travel-time changes. Such quick solution is critical for providing routing instructions to travelers in real time as travel-time information is retrieved from the traffic network. Numerous works have presented reoptimization techniques for use in updating shortest path trees in deterministic and static networks; however, it appears that no reoptimization technique exists in the literature for updating paths where future travel times in time-varying networks change. In this paper, such procedures are proposed. The proposed techniques can provide updated solutions given simultaneous and arbitrary changes (increasing and decreasing in value) in any number of network arcs. Further, this technique can be extended for use in stochastic networks. [ABSTRACT FROM AUTHOR]

Many real-world vehicle routing problems are dynamic optimization problems, with customer requests arriving over time, requiring a repeated reoptimization. In this paper, we consider a dynamic vehicle routing problem where one additional customer arrives at a beforehand unknown location when the vehicles are already under way. Our objective is to maximize the probability that the additional customer can be integrated into one of the otherwise fixed tours without violating time constraints. This is achieved by letting the vehicles wait at suitable locations during their tours, thus influencing the position of the vehicles at the time when the new customer arrives. For the cases of one and two vehicles, we derive theoretical results about the best waiting strategies. The general problem is shown to be NP-complete. Several deterministic waiting strategies and an evolutionary algorithm to optimize the waiting strategy are proposed and compared empirically. I is demonstrated that a proper waiting strategy can significantly increase the probability of being able to service the additional customer, at the same time reducing the average detour to serve that customer. [ABSTRACT FROM AUTHOR]

We present a best-first heuristic search approach for determining an optimal policy for stochastic shortest path problem. A vehicle is to travel from an origin, starting at time t[sub 0], to a destination, where once the destination is reached a terminal cost is accrued. The terminal cost depends on the time of arrival. Travel time along each arc in the network is modeled as a random variable with a distribution dependent on the time that travel along the arc is begun. The objective is to determine a routing policy that minimizes expected total cost. A routing policy is a rule that assigns the next arc to traverse, given the current node and time. The heuristic search algorithm that we specialize to this stochastic problem is AO[sub *]. We demonstrate the significant computational advantages of AO[sub *], relative to dynamic programming, on the basis of run time and storage, using a 131-intersection network of the major roads in Cleveland, Ohio. Further computational experience is based on grid networks that were randomly generated to have characteristics similar to transportation networks, and on randomly generated unstructured networks. [ABSTRACT FROM AUTHOR]

This paper examines whether there is a substantial additional payoff to be derived from using mathematical optimization techniques to globally define a set of mini-clusters. Specifically, we present a new approximate method to mini-clustering that involves solving a multi-vehicle pick-up and delivery problem with time windows by column generation. To solve this problem we have enhanced an existing optimal algorithm in several ways. First, we present an original network design based on lists of neighboring transportation requests. Second, we have developed a specialized initialization procedure which reduces the processing time by nearly 40%. Third, the algorithm was easily generalized to multi-dimensional capacity. Finally, we have also developed a heuristic to reduce the size of the network, while incurring only small losses in solution quality. This allows the application of our approach to much larger problems. To be able to compare the results of optimization-based and local heuristic mini-clustering, we also present a parallel insertion approach to mini-clustering. Our computational results highlight the success of our approach. On test problems with up to 250 requests, our optimization-based method reduced the travel time within the mini-clusters by an average of 10% over the parallel insertion approach. Furthermore, for an actual problem with 2545 requests, a substantial 5.9% improvement in total traveling time was achieved over the heuristic. [ABSTRACT FROM AUTHOR]

State-of-the-art decision-making models in the area of infrastructure maintenance and rehabilitation (which are based on the Markov Decision Process) do not take into account the uncertainty in the measurement of facility condition. This paper presents a methodology, the Latent Markov Decision Process (LMDP), which explicitly recognizes the presence of random errors in the measurement of the condition of infrastructure facilities. Two versions of the LMDP are presented. In the first version, the inspection schedule is fixed, which is the usual assumption made in state-of-the-art models. The second version of the LMDP minimizes the sum of inspection and M & R costs. An empirical comparison of the two versions of the LMDP and the traditional MDP illustrates the importance of incorporating measurement uncertainty in decision-making and of optimizing the inspection schedule. [ABSTRACT FROM AUTHOR]

This paper is concerned with some variational calculus/optimization problems involving the determination of constrained optimal path functions or routes of a single moving facility, which traverses a region encompassing a set of existing facilities. Situations of this type may involve a reconnaisance plane maintaining a surveillance of certain locations, a patrol car traveling in radio contact with several stations with the possibility of being dispatched to answer service calls originating over several designated regions, or an aircraft determining a flight plan over a region containing enemy missile sites. We formulate the general problem of maximizing total benefits, or maximizing the benefits per unit travel time, subject to constraints on the travel path function. The specific problems analyzed involve a direct distance related benefit (or cost) function, employing rectilinear or squared-Euclidean distance measures, and they constrain the paths to be straight lines between parallel boundaries or across rectangular regions, with both ends free or with one end fixed, or to be general paths between fixed end-points. In each case, the problem is reduced to a finite dimensional optimization problem. Illustrative examples and computational results on a personal computer are provided, and several extensions are proposed for future research. [ABSTRACT FROM AUTHOR]

The equilibrium network design problem can be formulated as a mathematical program with variational inequality constraints. We know this problem is nonconvex; hence, it is difficult to solve for a globally optimal solution. In this paper we propose a simulated annealing algorithm for the equilibrium network design problem. We demonstrate the ability of this algorithm to determine a globally optimal solution for two different networks. One of these describes an actual city in the midwestern United States. [ABSTRACT FROM AUTHOR]

This paper deals with the location of service facilities on a transportation network where the closest (in distance, time or cost) facility is known not to service some significant portion of demand. The concept of vector assignment of demand nodes to facilities is introduced to account for non closest facility service. A generalized formulation of the p-median problem incorporating vector assignment is presented. It is shown that an optimal solution to this vector assignment p-median problem exists which consists entirely of nodes of the graph; however, there may be more than one facility per node. Three different solution procedures are discussed for the vector assignment p-median problem. Computational experiments for three different moderately sized data sets give encouraging results. A locational example is included which gives a comparison of an optimal p-median solution and an optimal p-median solution with vector assignment. [ABSTRACT FROM AUTHOR]

This paper examines the problems of routing freight traffic, scheduling train services and allocating classification work between yards on a rail network. It describes a general optimization model which takes into account the interactions between these activities and develops global strategies for their management over a medium term planning horizon. A heuristic algorithm developed to solve this nonlinear, mixed-integer multicommodity flow problem is also presented with some computational results based on an example at the Canadian National Railroads. [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]

In this paper we consider two network optimization problems which have the following characteristics: control parameters vary continuously and network users behave according to War-drop's first principle of traffic equilibrium ("user-optimization"). For each problem, we study an exact algorithm based on constraint accumulation and a heuristic algorithm previously proposed in the literature. [ABSTRACT FROM AUTHOR]

The combined distribution and assignment problem has been studied by many authors. The problems examined have been of different types. Some authors focus their attention on the user optimized combined distribution and assignment problem whereas others study a system optimized version. Apart from this difference there is also a difference in the way the distribution part and the assignment part are incorporated into the models. In this paper we study a combined distribution and assignment problem with entropy objective and cost constraints and give an algorithm based on Benders decomposition for its solution. The resulting solution method will be a "dual" method. [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 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.

The dial-a-ride problem (DARP) involves the dispatching of a fleet of vehicles to transport customers requesting service and is one of the most challenging tasks of combinatorial optimization. We study the DARP as a constraint satisfaction problem, where the goal is to find a feasible solution with respect to the time, capacity, and precedence constraints, or to prove infeasibility. The main contribution of our work is a new robust method for this problem formulation. The algorithm is based on a dynamic subroutine that finds for any set of customers a maximum cluster, that is, a maximal set of customers that can be served by a single vehicle. The performance of the algorithm is analyzed and evaluated by means of computational experiments, justifying the efficiency of the solution method. [ABSTRACT FROM AUTHOR]

We consider an aggregated version of a large-scale driver scheduling problem, derived from an application in less-than-truckload trucking, as a dynamic resource allocation problem. Drivers are aggregated into groups characterized by an attribute vector which capture the important attributes required to incorporate the work rules. The problem is very large: over 5,000 drivers and 30,000 loads in a four-day planning horizon. We formulate a problem that we call the heterogeneous resource allocation problem, which is more general than a classical multicommodity flow problem. Since the tasks have one-sided time windows, the problem is too large to even solve an LP relaxation. We formulate the problem as a multistage dynamic program and solve it using adaptive dynamic programming techniques. Since our problem is too large to solve using commercial solvers, we propose three independent benchmarks and demonstrate that our technique appears to be providing high-quality solutions in a reasonable amount of time. [ABSTRACT FROM AUTHOR]

This article proposes an optimization model for simultaneous estimation of an origin-destination (O-D) matrix and a travel-cost coefficient for congested networks in a logit-based stochastic user equilibrium (SUE). The model is formulated in the form of a standard differentiable, nonlinear optimization problem with analytical stochastic user equilibrium constraints. Explicit expressions of the derivatives of the stochastic user equilibrium constraints with respect to origin-destination demand, link flow, and travel-cost coefficient are derived and computed efficiently through a stochastic network-loading approach. A successive quadratic-programming algorithm using the derivative information is applied to solve the simultaneous estimation model. This algorithm converges to a Karusch-Kuhn-Tucker point of the problem under certain conditions. The proposed model and algorithm are illustrated with a numerical example. [ABSTRACT FROM AUTHOR]

We consider the problem in which a fleet of vehicles located at a central depot is to be optimally used to serve a set of customers partitioned into two subsets of linehaul and backhaul customers. Each route starts and ends at the depot and the backhaul customers must be visited after the linehaul customers. A new (0-1) integer programming formulation of this problem is presented. We describe a procedure that computes a valid lower bound to the optimal solution cost by combining different heuristic methods for solving the dual of the LP-relaxation of the exact formulation. An algorithm for the exact solution of the problem is presented. Computational tests on problems proposed in the literature show the effectiveness of the proposed algorithms in solving problems up to 100 customers. [ABSTRACT FROM AUTHOR]

This article focuses on a study that describes an optimization-based heuristic for vehicle routing and scheduling with soft time window constraints in traffic. The problem of vehicle routing (VRP) with time window constraints arises in a variety of applications, including retail distribution, mail and newspaper delivery, municipal waste collection, fuel oil delivery, school bus routing, airline and railroad scheduling, trucking and bargeline fleet scheduling, demand responsive bus systems, and more. The article discusses a new methodological approach for the time constrained VRP, based on the generalized assignment heuristic proposed by researchers M. Fisher and R. Jaikumar. A significant change from the original generalized assignment heuristic is its iterative application where approximate clustering costs are successively improved. Loose capacity constraints are very desirable for local insertion and improvement heuristics, since they allow more flexibility to perform local operations, such as insertion of a customer in an existing tour or pair-wise switches between tours.

This article formulates a simple plant location problem (SPLP) in transportation as the minimization of a pseudo-Boolean function is transformed into a set covering problem and into a weighted vertex packing problem on a graph. These formulations of the SPLP are compared to similar formulations that have appeared in the literature. For the special case of a simple plant location problem derived from a tree network, the plant location graph is shown to be weakly-triangulated, for which there exist polynomial-time algorithms for finding a maximum weighted vertex packing. In case of a customer's demand if it is different from one unit, it is scaled to one and the transport costs are scaled accordingly. Assume further that the capacity for each opened plant is sufficient to meet the demand of all customers. The SPLP is then to choose a subset of locations from the index set of potential locations for plants at which plants are opened and to specify the transportation between opened plants and all customers so as to meet customer demand and to minimize the total fixed cost plus the total transportation cost.

The section presents abstracts of several dissertations in transportation science. Probabilistic Combinatorial Optimization Problems by Dimitris J. Bertsimas. An Optimization Based Heuristic for Vehicle Routing and Scheduling With Time Window Constraints by Yiannis A. Koskosidis. Local Search Algorithms for Vehicle Routing and Other Combinatorial Problems by Paul M. Thompson. Time Dependent Vehicle Routing Problems: Formulations, Solution Algorithms and Computational Experiments by Chryssi Malandraki. A Network-Based Primal-Dual Solution Methodology for the Multi-Commodity Network Flow Problem by Cynthia Barnhart.

Part I of this study reviewed the formulation of the traffic assignment problem (TAP) in a network and identified its underlying rationale. This part examines algorithmic approaches for calculating the flow patterns resulting from the different modes of assignment. An efficient methodology for solving the elastic-demand TAP is based on remodeling it as an equivalent assignment problem in an expanded network. The variable-demand TAP is then tranformed into a fixed- demand TAP, with a trip table consisting of the potential demands, and can be solved fry available fixed-demand assignment algorithms. Three alternative transformations are described. [ABSTRACT FROM AUTHOR]

An investigation of the single-vehicle, many-to-many, immediate-request dial-a-ride problem is developed in two parts (I and II). Part I focuses on the "static" case of the problem. In this case, intermediate requests that may appear during the execution of the route are not considered. A generalized objective function is examined, the minimization of a weighted combination of the time to service all customers and of the total degree of "dissatisfaction" experienced by them while waiting for service. This dissatisfaction is assumed to be a linear function of the waiting and riding times of each customer. Vehicle capacity constraints and special priority rules are part of the problem. A Dynamic Programming approach is developed. The algorithm exhibits a computational effort which, although an exponential function of the size of the problem, is asymptotically lower than the corresponding effort of the classical Dynamic Programming algorithm applied to a Traveling Salesman Problem of the same size. Part II extends this approach to solving the equivalent "dynamic" case. In this case, new customer requests are automatically eligible for consideration at the time they occur. The procedure is an open-ended sequence of updates, each following every new customer request. The algorithm optimizes only over known inputs and does not anticipate future customer requests. Indefinite deferment of a customer's request is prevented by the priority rules introduced in Part L Examples in both "static" and "dynamic" cases are presented. [ABSTRACT FROM AUTHOR]