共查询到20条相似文献,搜索用时 0 毫秒
1.
In this paper, we consider the problem of forming a new vehicle fleet, consisting of multiple vehicle types, to cater for uncertain future requirements. The problem is to choose the number of vehicles of each type to purchase so that the total expected cost of operating the fleet is minimized. The total expected cost includes fixed and variable costs associated with the fleet, as well as hiring costs that are incurred whenever vehicle requirements exceed fleet capacity. We develop a novel algorithm, which combines dynamic programming and the golden section method, for determining the optimal fleet composition. Numerical results show that this algorithm is highly effective, and takes just seconds to solve large-scale problems involving hundreds of different vehicle types. 相似文献
2.
An evolutionary implicit enumeration procedure for solving the resource‐constrained project scheduling problem
下载免费PDF全文
![点击此处可从《International Transactions in Operational Research》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Reza Zamani 《International Transactions in Operational Research》2017,24(6):1525-1547
This paper presents a procedure for solving the resource‐constrained project scheduling problem. It consists of an implicit enumeration module and a genetic algorithm. If the procedure is provided access to all of its required computational resources of the problem at hand, it guarantees the optimality of the produced solution. In contrast, and in the case of limited access to computational resources, the procedure gradually moves the root of the search‐tree downward, and consequently prunes part of the search space, trading speed with precision effectively. In the cases where speed has been traded with precision, and the guarantee of optimality has been lost, the final schedule created by the implicit enumeration module is used as a template whose modified instances fill an initial pool of a genetic algorithm to improve the proposed solution. The procedure has been applied to 2040 benchmark instances. The results are promising; whereas for all small‐ and some medium‐sized instances, the procedure has found and guaranteed optimal solutions, for other instances, whose optimal solutions cannot be guaranteed within the limit of computational resources, it has produced high‐quality solutions. 相似文献
3.
We propose a two-stage robust optimization model for the mobile facility fleet sizing and routing problem with demand uncertainty. A two-level cutting plane based method is developed, which includes an algorithm to generate problem-specific lower bound inequalities in the outer level, and a hybrid algorithm in the inner level that combines heuristic and exact methods to solve the recourse problem. Numerical tests show that the design and operation from the proposed method outperforms other solution approaches. The efficiency of the proposed solution algorithm in identifying the optimal solution is quantified and the robustness of the proposed model is demonstrated for varying degrees of uncertainty in demand. 相似文献
4.
In the heterogeneous fleet vehicle routing problem (HVRP), several different types of vehicles can be used to service the customers. The types of vehicles differ with respect to capacity, fixed cost, and variable cost. We assume that the number of vehicles of each type is fixed and equal to a constant. We must decide how to make the best use of the fixed fleet of heterogeneous vehicles. 相似文献
5.
This paper addressed the heterogeneous fixed fleet open vehicle routing problem (HFFOVRP), in which the demands of customers are fulfilled by a fleet of fixed number of vehicles with various capacities and related costs. Moreover, the vehicles start at the depot and terminate at one of the customers. This problem is an important variant of the classical vehicle routing problem and can cover more practical situations in transportation and logistics. We propose a multistart adaptive memory programming metaheuristic with modified tabu search algorithm to solve this new vehicle routing problem. The algorithmic efficiency and effectiveness are experimentally evaluated on a set of generated instances. 相似文献
6.
7.
The single-sink fixed-charge transportation problem is an important subproblem of the fixed-charge transportation problem. Just a few methods have been proposed in the literature to solve this problem. In this paper, solution approaches based on dynamic programming and implicit enumeration are revisited. It is shown how the problem size as well as the search space of a recently published dynamic programming method can be reduced by exploiting reduced cost information. Additionally, a further implicit enumeration approach relying on solution concepts for the binary knapsack problem is introduced. The performance of the various solution methods is compared in a series of computational experiments. 相似文献
8.
In this paper, we proposed a new formulation and a solution procedure for optimizing the fleet size and freight car allocation wherein car demands and travel times are assumed to be deterministic and unmet demands are backordered. We assume that unmet demands become zero at the end of the planning horizon, i.e., the car demands are totally satisfied through the horizon. There are important interactions between decisions on sizing a rail car fleet and utilizing that fleet. Consequently, the optimum use of rail-cars for demands response in the length of the time periods is one of the main advantages of the proposed model. The model also provides rail network information such as yard capacity, unmet demands, and number of loaded and empty rail-car at any given time and location. Computational tests showed that small-size instances can be solved by the exact approach in a fair amount of CPU time, but it is not feasible for medium and large-size instances. To tackle this problem, a Simulated Annealing (SA) algorithm is proposed to solve the model. The algorithm works efficiently on a neighborhood search within solution space, acceptance probability, and inferior solutions to escape from trap (i.e., local optimal solution). Numerical examples are solved to check for the efficiency and validity of the SA algorithm. 相似文献
9.
In this paper, we solve the maximum agreement subtree problem for a set T of k rooted leaf-labeled evolutionary trees on n leaves where T contains a binary tree. We show that the O(kn3)-time dynamic-programming algorithm proposed by Bryant [Building trees, hunting for trees, and comparing trees: theory and methods in phylogenetic analysis, Ph.D. thesis, Dept. Math., University of Canterbury, 1997, pp. 174-182] can be implemented in O(kn2+n2logk−2nloglogn) and O(kn3−1/(k−1)) time by using multidimensional range search related data structures proposed by Gabow et al. [Scaling and related techniques for geometry problems, in: Proc. 16th Annual ACM Symp. on Theory of Computing, 1984, pp. 135-143] and Bentley [Multidimensional binary search trees in database applications, IEEE Trans. Softw. Eng. SE-5 (4) (1979) 333-340], respectively. When k<2+(logn−logloglogn)/(loglogn), the first implementation will be significantly faster than Bryant's algorithm. For k=3, it yields the best known algorithm which runs in O(n2lognloglogn)-time. 相似文献
10.
针对网络设计和组合优化中的度约束最小生成树问题,基于第k最小生成树的求解算法,提出了一种求解网络G关于指定节点的最小k度生成树的新算法。该算法通过对网络G的最小生成树作最优可行变换,逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树,最终得到了网络G关于指定节点的最小k度生成树。给出了算法实施的具体步骤,并证明了算法的正确性。最后通过仿真结果和一个运输实例,表明了该算法在解决度约束最小生成树问题中的有效性。 相似文献
11.
R. J. Balling J. Sobieszczanski-Sobieski 《Structural and Multidisciplinary Optimization》1995,9(3-4):168-177
A multilevel optimization approach applicable to nonhierarchic coupled systems is presented. The approach includes a general treatment of design (or behaviour) constraints and coupling constraints at the discipline level through the use of norms. Three different types of norms are examined - the max norm, the Kreisselmeier-Steinhauser (KS) norm, and the
p
norm. The max norm is recommended. The approach is demonstrated on a class of hub frame structures that simulate multidisciplinary systems. The max norm is shown to produce system-level constraint functions which are nonsmooth. A cutting-plane algorithm is presented, which adequately deals with the resulting corners in the constraint functions. The algorithm is tested on hub frames with an increasing number of members (which simulate disciplines), and the results are summarized. 相似文献
12.
John Noga 《Information Processing Letters》2002,81(2):71-73
In a recent paper [Proceedings of STOC'98, 1998, pp. 389-398], Dooly, Goldman and Scott study a problem that is motivated by the networking problem of dynamically adjusting delays of acknowledgements in the Transmission Control Protocol (TCP). Among other results, they give an O(n2) off-line algorithm for computing the optimal way of acknowledging n packet arrivals and departures.In this brief note, we observe that there is a faster off-line algorithm for this problem with time complexity O(n). 相似文献
13.
14.
Due to the great importance of operating rooms in hospitals, this paper studies an operating room scheduling problem with open scheduling strategy. According to this strategy, no time slot is reserved for a particular surgeon. The surgeons can use all available time slots. Based on Fei et al.’s model which is considered to be close to reality, we develop a heuristic algorithm to solve it. The idea of this heuristic algorithm is from dynamic programming by aggregating states to avoid the explosion of the number of states. The objective of this paper is to design an operating program to maximize the operating rooms’ use efficiency and minimize the overtime cost. Computational results show that our algorithm is efficient, especially for large size instances where our algorithm always finds feasible solutions while the algorithm of Fei et al. does not. 相似文献
15.
16.
17.
18.
Dimitri Watel Marc-Antoine Weisser Cédric Bentz Dominique Barth 《Information Processing Letters》2015
Given a directed graph with n nodes, a root r, a set X of k nodes called terminals and non-negative weights ω over the arcs, the Directed Steiner Tree problem (DST) asks for a directed tree T? of minimum cost ω(T?) rooted at r and spanning X. 相似文献
19.
We introduce a new variation of the pickup-and-delivery problem. Current methods for solving this problem rely on column-generation subroutines embedded in a branch-and-bound tree. Yet, when applied to our problem, these techniques suffer from significant combinatorial explosion in the number of routes generated by the column-generation subroutine and the number of nodes explored in the branch-and-bound tree. In this paper, by exploiting the problem structure, we develop a specialized column-generation subroutine that reduces the combinatorial explosion significantly leading to a more efficient procedure to solve the problem. 相似文献
20.
最小费用最大流问题是一种组合优化问题,在经济、工业等领域具有重要研究意义和应用价值.针对部分最小费用最大流问题求解算法效率较低的情况,依据最小费用最大流问题的线性规划方程,将问题模型映射为对应因子图模型,改进描述函数,给出迭代方程,设计了求解最小费用最大流问题的信念传播算法.利用迭代方程优先对最大可行流特征值进行收敛计算,得到最大流,设置最大流阈值,在此基础上进行最小费用计算,从而求得问题最优解.最后选取若干带权有向图模型进行数值实验,验证了算法的可行性及有效性,且算法在求解效率上优于部分算法. 相似文献