共查询到20条相似文献,搜索用时 546 毫秒
1.
《European Journal of Operational Research》1997,97(1):87-93
In this paper we address a planar p-facility location problem where, together with a metric induced by a gauge, there exists a series of rapid transit lines, which can be used as alternative transportation system to reduce the total transportation cost. The location problem is reduced to solving a finite number of (multi)-Weber problems, from which localization results are obtained. In particular, it is shown that, if the gauge in use is polyhedral, then the problem is reduced to finding a p-median. 相似文献
2.
将不平衡运输问题转化成网络最短路问题,利用Floyd算法规则,给出了一种既可以解平衡和不平衡运输问题,又可以解平衡和不平衡分配问题的通用迭代算法。与专门用于解运输问题的闭合回路法和专门用于解分配问题的匈牙利法相比,这种算法不但具有通用的优点,而且更便于在计算机上运行。 相似文献
3.
崔春生 《数学的实践与认识》2014,(8)
从目前研究生入学考试中出现的几种新的运筹学运输问题出发,探讨了各种运输问题与传统运输问题的差异。提出以传统运输问题为本,将非传统运输问题转化为传统运输问题借助表上作业法求解的思路。并针对6种不同的非传统运输问题分析了转化的过程和步骤,为运输问题的研究提供了新的内容. 相似文献
4.
Rainer E. Burkard 《Discrete Mathematics》1978,22(3):219-232
In this paper the algebraic transportation problem is introduced which covers besides the Hitchcock and the time transportation problem several other types of transportation problems of practical relevance. To solve this algebraic transportation problem admissible transformations are considered and characterized. Thereupon a transformation algorithm is described which is a generalization of the Hungarian method for the classical transportation problem as well as of a threshold method for time transportation problems. 相似文献
5.
Kenneth R. Rebman 《Linear algebra and its applications》1974,8(1):11-24
Well-known sufficiency conditions for total unimodularity are relaxed to include more general classes of matrices, whose determinants are related to Fibonacci sequences. It is then shown that in order to study determinants of submatrices of the two-commodity transportation problem, one should study precisely these generalized unimodular matrices. (Note that all submatrices of an ordinary transportation problem are unimodular.) This result enables us to establish determinantal values for submatrices of two-commodity transportation problems (in terms of the number of disjoint capacitated routes) and to identify a totally unimodular class of two-commodity transportation problems. 相似文献
6.
Motivated by dead-mileage problem assessed in terms of running empty buses from various depots to starting points, we consider a class of the capacitated transportation problems with bounds on total availabilities at sources and total destination requirements. It is often difficult to solve such problems and the present paper establishes their equivalence with a balanced capacitated transportation problem which can be easily solved by existing methods. Sometimes, total flow in transportation problem is also specified by some external decision maker because of budget/political consideration and optimal solution of such problem is of practical interest to the decision maker and has motivated us to discuss such problem. Various situations arising in unbalanced capacitated transportation problems have been discussed in the present paper as a particular case of original problem. In addition, we have discussed paradoxical situation in a balanced capacitated transportation problem and have obtained the paradoxical solution by solving one of the unbalanced problems. Numerical illustrations are included in support of theory. 相似文献
7.
This paper considers one facility planar location problems using block distance and assuming barriers to travel. Barriers
are defined as generalized convex sets relative to the block distance. The objective function is any convex, nondecreasing
function of distance. Such problems have a non-convex feasible region and a non-convex objective function. The problem is
solved by modifying the barriers to obtain an equivalent problem and by decomposing the feasible region into a polynomial
number of convex subsets on which the objective function is convex. It is shown that solving a planar location problem with
block distance and barriers requires at most a polynomial amount of additional time over solving the same problem without
barriers. 相似文献
8.
G. M. Appa 《The Journal of the Operational Research Society》1973,24(1):79-99
For 54 unimodular linear programming problems it is shown that either (i) the objective function is unbounded, or (ii) the problem is infeasible, or (iii) the problem can be solved by solving a related transportation problem. The related transportation problem is obtained by adding at the most two new constraints to the original problem. 相似文献
9.
The auction algorithm for the transportation problem 总被引:1,自引:0,他引:1
The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. This paper generalizes the auction algorithm to solve linear transportation problems. The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem. Computational results show that this modified version of the auction algorithm is very efficient for certain types of transportation problems. 相似文献
10.
V. M. Kravtsov 《Computational Mathematics and Mathematical Physics》2010,50(9):1615-1626
Theorems about the characterization and exponential growth of the denominators of fractional components of noninteger vertices
of the relaxation polyhedron in the multi-index axial assignment problem are proved. They made it possible to obtain new lower
bounds on the number of noninteger vertices of this polyhedron and to refute the conjecture on the estimate of the ratio of
the number of integer vertices to the number of all vertices of the multi-index axial transportation polyhedron determined
by integer vectors. 相似文献
11.
Takashi Hasuike 《Journal of Global Optimization》2014,60(4):663-678
Solving transportation problems is essential in engineering and supply chain management, where profitability depends on optimal traffic flow. This study proposes risk-control approaches for two bottleneck transportation problems with random variables and preference levels to objective functions with risk parameters. Each proposed model is formulated as a multiobjective programming problem using robust-based optimization derived from stochastic chance constraints. Since it is impossible to obtain a transportation pattern that optimizes all objective functions, our proposed models are numerically solved by introducing an aggregation function for the multiobjective problem. An exact algorithm that performs deterministic equivalent transformations and introduces auxiliary problems is also developed. 相似文献
12.
We give new bounds on the star arboricity and the caterpillar arboricity of planar graphs with given girth. One of them answers an open problem of Gyárfás and West: there exist planar graphs with track number 4. We also provide new NP-complete problems. 相似文献
13.
Javier García José E. Florez Álvaro Torralba Daniel Borrajo Carlos Linares López Ángel García-Olaya Juan Sáenz 《European Journal of Operational Research》2013
When dealing with transportation problems Operational Research (OR), and related areas as Artificial Intelligence (AI), have focused mostly on uni-modal transport problems. Due to the current existence of bigger international logistics companies, transportation problems are becoming increasingly more complex. One of the complexities arises from the use of intermodal transportation. Intermodal transportation reflects the combination of at least two modes of transport in a single transport chain, without a change of container for the goods. In this paper, a new hybrid approach is described which addresses complex intermodal transport problems. It combines OR techniques with AI search methods in order to obtain good quality solutions, by exploiting the benefits of both kinds of techniques. The solution has been applied to a real world problem from one of the largest spanish companies using intermodal transportation, Acciona Transmediterránea Cargo. 相似文献
14.
Stochastic uncapacitated hub location 总被引:1,自引:0,他引:1
Ivan Contreras Jean-François Cordeau Gilbert Laporte 《European Journal of Operational Research》2011,212(3):518-528
We study stochastic uncapacitated hub location problems in which uncertainty is associated to demands and transportation costs. We show that the stochastic problems with uncertain demands or dependent transportation costs are equivalent to their associated deterministic expected value problem (EVP), in which random variables are replaced by their expectations. In the case of uncertain independent transportation costs, the corresponding stochastic problem is not equivalent to its EVP and specific solution methods need to be developed. We describe a Monte-Carlo simulation-based algorithm that integrates a sample average approximation scheme with a Benders decomposition algorithm to solve problems having stochastic independent transportation costs. Numerical results on a set of instances with up to 50 nodes are reported. 相似文献
15.
A typical warehouse or distribution centre ships material to various customer locations across the country, using various modes of transportation. Each mode has different constraints on size of shipment, different cost structures and different transportation times. Typically, for a given warehouse there are certain customer locations that receive frequent shipments of material. It is often possible, therefore, for the warehouse to consolidate different orders for the same customer location into a single shipment. The transportation mode and the day of shipment must be chosen such that the consolidated shipment meets the size constraints and arrives within an agreed-upon ‘delivery window’. In preparing a warehouse distribution plan, a planner seeks to achieve transportation economies of scale (by consolidating two or more orders into fewer shipments) while levelling the workload on warehouse resources and ensuring that material arrives at a customer location during the acceptable delivery window.The problem of deciding what shipments to make daily can be formulated as a set partitioning problem with side constraints. This paper describes a heuristic solution approach for this problem. Computational experiments using actual warehouse select activity indicate that, for moderate-size problems, the heuristic produces solutions with transportation costs that are within a few percent of optimal. Larger problems found in practice are generally too large to be solved by optimal algorithms; the heuristic easily handles such problems. The heuristic has been integrated into the transportation planning system of a leading distributor of telecommunications products. 相似文献
16.
《Mathematical and Computer Modelling》1995,21(4):13-28
In this paper, a transportation model with multiple criteria and multiple constraint levels (MC2) is formulated by using the framework of MC2 linear programming. An algorithm is developed to solve such MC2 transportation problems. In this algorithm, the traditional northwest corner rule is adopted to find an initial basic feasible solution for a given MC2 transportation problem. Then the MC2-simplex method is applied to locate the set of all potential solutions over possible changes of the objective coefficient parameter and the supply and demand parameter for the MC2 transportation problem. A numerical example is illustrated to demonstrate the applicability of the algorithm in solving the MC2 transportation problems. 相似文献
17.
Lars Arge Gerth Stlting Brodal Laura Toma 《Journal of Algorithms in Cognition, Informatics and Logic》2004,53(2):446
Recently external memory graph problems have received considerable attention because massive graphs arise naturally in many applications involving massive data sets. Even though a large number of I/O-efficient graph algorithms have been developed, a number of fundamental problems still remain open.The results in this paper fall in two main classes. First we develop an improved algorithm for the problem of computing a minimum spanning tree (MST) of a general undirected graph. Second we show that on planar undirected graphs the problems of computing a multi-way graph separation and single source shortest paths (SSSP) can be reduced I/O-efficiently to planar breadth-first search (BFS). Since BFS can be trivially reduced to SSSP by assigning all edges weight one, it follows that in external memory planar BFS, SSSP, and multi-way separation are equivalent. That is, if any of these problems can be solved I/O-efficiently, then all of them can be solved I/O-efficiently in the same bound. Our planar graph results have subsequently been used to obtain I/O-efficient algorithms for all fundamental problems on planar undirected graphs. 相似文献
18.
19.
运输问题的退化解及表解中0元的添加 总被引:3,自引:0,他引:3
在运输问题表上作业法中,有时会遇到退化解问题,这样在给调运方案时需要在调运表上添加0元,可是0应添在何处?大多数文献中均未具体给出或给出的结论有误,0元的添加不当有时会导致一系列问题出现,本文将讨论这些问题,且给出一个0元添加的确定的答案. 相似文献