共查询到20条相似文献,搜索用时 125 毫秒
1.
2.
Public transport assignment models have increased in complexity in order to describe passengers' route choices as detailed
and correctly as possible. Important trends in the development are (1) timetable-based assignment, (2) inclusion of feeder
modes, (3) use of stochastic components to describe differences in passengers' preferences within and between purposes and
classes (random coefficients), as well as to describe non-explained variation within a utility theory framework, and (4) consideration
of capacity problems at coach level, system level and terminal level. In the Copenhagen-Ringsted Model (CRM), such a large-scale
transit assignment model was developed and estimated. The Stochastic User Equilibrium problem was solved by the Method of
Successive Averages (MSA). However, the model suffered from very large calculation times. The paper focuses on how to optimise
transit assignment models based on MSA combined with a generalised utility function. Comparable tests are carried out on a
large-scale network. The conclusion is that there is potential of optimising MSA-based methods. Examples of different approaches
for this is presented, tested and discussed in the paper. 相似文献
3.
Pritibhushan Sinha 《Annals of Operations Research》2009,172(1):447-457
We consider some variant models, having changeover cost, of the assignment problem. In these models, multiple assignments
to an operator are allowed. In addition to assignment costs, a changeover cost is incurred if an operator does one job after
another is completed. Two different types of changeover costs and related two models are considered. Mathematical programming
formulations are given for the models. When changeover costs are dependent on the operator but independent of the jobs and
are non-negative, a linear programming model is obtained. For the case when changeover costs are dependent on the jobs, a
linear integer programming formulation is obtained. We also show that, this problem is strongly NP-hard. A heuristic solution
method is suggested for it. Numerical findings on the performance of the method are given. 相似文献
4.
This paper deals with the transit passenger origin-destination (O-D) estimation problem by using updated passenger counts
in congested transit networks and outdated prior O-D matrix. A bilevel programming approach is extended for the transit passenger
O-D updating problem where the upper-level problem seeks to minimize the sum of error measurements in passenger counts and
O-D matrices, while the lower level is the stochastic user equilibrium assignment problem for congested transit networks.
The transit assignment framework is based on a frequency-adaptive transit network model in this paper, which can help determine
transit line frequencies and the network flow pattern simultaneously in congested transit networks. A heuristic solution algorithm
is adapted for solving the transit passenger O-D estimation problem. Finally, a numerical example is used to illustrate the
applications of the proposed model and solution algorithm.
The work described in this paper was mainly supported by two research grants from the Research Grants Council of the Hong
Kong Special Administrative Region (Project No. PolyU 5143/03E and PolyU 5040/02E). 相似文献
5.
William H. K. Lam Z. X. Wu K. S. Chan 《Journal of Mathematical Modelling and Algorithms》2003,2(4):329-348
This paper investigates the transit passenger origin–destination (O–D) estimation problem in congested transit networks where
updated passenger counts and outdated O–D matrices are available. The bi-level programming approach is used for the transit
passenger O–D estimation problem. The upper level minimizes the sum of error measurements in passenger counts and O–D matrices,
and the lower level is a new frequency-based stochastic user equilibrium (SUE) assignment model that can determine simultaneously
the passenger overload delays and passenger route choices in congested transit network together with the resultant transit
line frequencies. The lower-level problem can be formulated as either a logit-type or probit-type SUE transit assignment problem.
A heuristic solution algorithm is developed for solving the proposed bi-level programming model which is applicable to congested
transit networks. Finally, a case study on a simplified transit network connecting Kowloon urban area and the Hong Kong International
Airport is provided to illustrate the applications of the proposed bi-level programming model and solution algorithm.
This revised version was published online in July 2006 with corrections to the Cover Date. 相似文献
6.
《European Journal of Operational Research》1999,112(1):54-80
Production planning problems frequently involve the assignment of jobs or operations to machines. The simplest model of this problem is the well known assignment problem (AP). However, due to simplifying assumptions this model does not provide implementable solutions for many actual production planning problems. Extensions of the simple assignment model known as the generalized assignment problem (GAP) and the multi-resource generalized assignment problem (MRGAP) have been developed to overcome this difficulty. This paper presents an extension of the (MRGAP) to allow splitting individual batches across multiple machines, while considering the effect of setup times and setup costs. The extension is important for many actual production planning problems, including ones in the injection molding industry and in the metal cutting industry. We formulate models which are logical extensions of previous models which ignored batch splitting for the problem we address. We then give different formulations and suggest adaptations of a genetic algorithm (GA) and simulated annealing (SA). A systematic evaluation of these algorithms, as well as a Lagrangian relaxation (LR) approach, is presented. 相似文献
7.
Linzhong Liu Haibo MuYubo Song Haiyan LuoXiaojing Li Fang Wu 《Applied mathematics and computation》2012,218(11):6526-6535
The well-known generalized assignment problem (GAP) is to minimize the costs of assigning n jobs to m capacity constrained agents (or machines) such that each job is assigned to exactly one agent. This problem is known to be NP-hard and it is hard from a computational point of view as well. In this paper, follows from practical point of view in real systems, the GAP is extended to the equilibrium generalized assignment problem (EGAP) and the equilibrium constrained generalized assignment problem (ECGAP). A heuristic equilibrium strategy based genetic algorithm (GA) is designed for solving the proposed EGAP. Finally, to verify the computational efficiency of the designed GA, some numerical experiments are performed on some known benchmarks. The test results show that the designed GA is very valid for solving EGAP. 相似文献
8.
This paper concerns the problem of finding shortest paths from one node to all other nodes in networks for which arc costs can vary with time, each arc has a transit time, and parking with a corresponding time-varying cost is allowed at the nodes. The transit times can also take negative values. A general labeling method, as well as several implementations, are presented for finding shortest paths and detecting negative cycles under the assumption that arc traversal costs are piecewise linear and node parking costs are piecewise constant. 相似文献
9.
This paper presents two mathematical models representing on surface transit systems with general failure, towing and repair time distributions. The stochastic analysis is performed with the aid of the regeneration point technique. Laplace transforms of the state probabilities are obtained. A number of general formulas are developed for the transit system steady-state availability when one of the system transition rates is described by the Erlangian probability density function. Various plots of transit system steady-state availability are shown. 相似文献
10.
《European Journal of Operational Research》1988,37(2):176-186
This paper develops a graph-theoretic framework for large scale transit networks and provides new insight into the equilibrium traffic assignment methodology. Variational inequality formulations for the equilibrium traffic assignment are developed and algorithms for computing equilibrium flows are discussed. A new shortest hyperpaths problem is defined and computational techniques for shortest hyperpaths suggested. 相似文献
11.
Sudipto Guha Adam Meyerson Kamesh Munagala 《Journal of Algorithms in Cognition, Informatics and Logic》2003,48(2):429-440
We consider a generalization of the classical facility location problem, where we require the solution to be fault-tolerant. In this generalization, every demand point j must be served by rj facilities instead of just one. The facilities other than the closest one are “backup” facilities for that demand, and any such facility will be used only if all closer facilities (or the links to them) fail. Hence, for any demand point, we can assign nonincreasing weights to the routing costs to farther facilities. The cost of assignment for demand j is the weighted linear combination of the assignment costs to its rj closest open facilities. We wish to minimize the sum of the cost of opening the facilities and the assignment cost of each demand j. We obtain a factor 4 approximation to this problem through the application of various rounding techniques to the linear relaxation of an integer program formulation. We further improve the approximation ratio to 3.16 using randomization and to 2.41 using greedy local-search type techniques. 相似文献
12.
A transit equilibrium assignment problem assigns the passenger flows on to a congested transit (public transportation) network with asymmetric cost functions and a fixed origin-destination matrix. This problem which may be formulated in the space of hyperpath flows, is transformed into an equivalent problem in the space of total arc flows and an auxiliary variable. A simplicial decomposition algorithm is developed and its convergence is proved under the usual assumptions on the cost functions. The algorithm requires relatively little memory and its efficiency is demonstrated with computational results. 相似文献
13.
Theoretical inventory models with constant demand rate and two transportation modes are analyzed in this paper. The transportation options are truckloads with fixed costs, a package delivery carrier with a constant cost per unit, or using a combination of both modes simultaneously. Exact algorithms for computing the optimal policies are derived for single stage models over both an infinite and a finite planning horizon. 相似文献
14.
A new algorithm for solving quadratic assignment problems is presented. The algorithm, which employs a sequential search technique, constructs a matrix of lower bounds on the costs of locating facilities at different sites. It then improves the elements of this matrix, one by one, by solving a succession of linear assignment problems. After all the elements of the matrix are improved, a feasible assignment is obtained, which results in an improved value for the objective function of the quadratic assignment problem. The procedure is repeated until the desired accuracy in the objective function value is obtained. 相似文献
15.
16.
In this paper, we consider a single-machine earliness-tardiness scheduling problem with due-date assignment, in which the processing time of a job is a function of its position in a sequence and its resource allocation. The due date assignment methods studied include the common due date, and the slack due date, which reflects equal waiting time allowance for the jobs. For each combination of due date assignment method and processing time function, we provide a polynomial-time algorithm to find the optimal job sequence, due date values, and resource allocations that minimize an integrated objective function, which includes earliness, tardiness, due date assignment, and total resource consumption costs. 相似文献
17.
D Ronen 《The Journal of the Operational Research Society》1997,48(10):973-977
When a shipper may use a variety of trucks to ship less-than-truckload shipments, shipping cost is the relevant criterion for evaluating alternate dispatches. This point is demonstrated by optimally solving 15 dispatching problems from industry in two ways, once minimising distance, and second time minimising costs, when a mixed private fleet and a common carrier are available. The distance minimising dispatches are, on the average, 35% more expensive than the corresponding cost minimising ones, but part of this difference stems from assumptions which are necessary to compare these two criteria. 相似文献
18.
We study a single-machine scheduling and due window assignment problem, in which job processing times are defined by functions of their starting times (deteriorating effect) and positions in the sequence (learning effect). The problem is to determine the optimal due windows and the processing sequence simultaneously to minimize costs for earliness, tardiness, the window location, window size and makespan. We show that the problem remains polynomially solvable under the proposed model for two popular due window assignment methods: The slack due date assignment method (usually referred to as SLK) and the unrestricted due date assignment method (usually referred to as DIF). 相似文献
19.
Sıla Çetinkaya Burcu B Keskin Halit Üster 《The Journal of the Operational Research Society》2014,65(9):1371-1379
We consider a two-stage distribution system, where the first stage consists of potential distribution centres (DCs) and the second stage consists of geographically dispersed existing retailers. Our goal is to determine the set of open DCs and assignment of open DCs to retailers simultaneously with inventory decisions of retailers. In addition to the DC-specific fixed facility location costs, we explicitly model the inventory replenishment and holding costs at the retailers and truckload transportation costs between the DCs and the retailers. The transportation costs are subject to truck/cargo capacity, leading to an integrated location-inventory problem with explicit cargo costs. We develop a mixed-integer nonlinear model and analyse its structural properties leading to exact expressions for the so-called implied facility assignment costs and imputed per-unit per-mile transportation costs. These expressions analytically demonstrate the interplay between strategic location and tactical inventory/transportation decisions in terms of resulting operational costs. Although both the theory and practice of integrated logistics have recognized the fact that strategic and tactical decisions are interrelated, to the best of our knowledge, our paper is the first to offer closed-form results demonstrating the relationship explicitly. We propose an efficient solution approach utilizing the implied facility assignment costs and we demonstrate that significant savings are realizable when the inventory decisions and cargo costs are modelled explicitly for facility location purposes. 相似文献
20.
Temporal dynamics is a crucial feature of network flow problems occurring in many practical applications. Important characteristics of real-world networks such as arc capacities, transit times, transit and storage costs, demands and supplies etc. are subject to fluctuations over time. Consequently, also flow on arcs can change over time which leads to so-called dynamic network flows. While time is a continuous entity by nature, discrete-time models are often used for modeling dynamic network flows as the resulting problems are in general much easier to handle computationally. In this paper, we study a general class of dynamic network flow problems in the continuous-time model, where the input functions are assumed to be piecewise linear or piecewise constant. We give two discrete approximations of the problem by dividing the considered time range into intervals where all parameters are constant or linear. We then present two algorithms that compute, or at least converge to optimum solutions. Finally, we give an empirical analysis of the performance of both algorithms. 相似文献