A stochastic fleet composition problem

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.     

An evolutionary implicit enumeration procedure for solving the resource‐constrained project scheduling problem

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.     

A two-stage robust optimization approach for the mobile facility fleet sizing and routing problem under uncertainty

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.     

A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem

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.     

A multistart adaptive memory-based tabu search algorithm for the heterogeneous fixed fleet open vehicle routing problem

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.     

Algorithms for solving the single-sink fixed-charge transportation problem

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.     

A simulated annealing approach for the multi-periodic rail-car fleet sizing problem

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.     

An improved algorithm for the maximum agreement subtree problem

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(kn³)-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(kn²+n²logk−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(n²lognloglogn)-time.     

求解度约束最小生成树问题的新算法

针对网络设计和组合优化中的度约束最小生成树问题,基于第k最小生成树的求解算法,提出了一种求解网络G关于指定节点的最小k度生成树的新算法。该算法通过对网络G的最小生成树作最优可行变换,逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树,最终得到了网络G关于指定节点的最小k度生成树。给出了算法实施的具体步骤,并证明了算法的正确性。最后通过仿真结果和一个运输实例,表明了该算法在解决度约束最小生成树问题中的有效性。     

An algorithm for solving the system-level problem in multilevel optimization

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.     

A faster off-line algorithm for the TCP acknowledgement problem

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(n²) 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).     

A new heuristic algorithm for the operating room scheduling problem

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.     

用于求解井下最短逃生路径问题的离散萤火虫算法

针对煤矿井下避灾路线最短路径求解问题,提出了一种新的离散萤火虫算法。该算法通过采用转移概率方法初始化萤火虫个体,并提出一种新的有效编码和解码方式,重新定义萤火虫的空间距离、最大荧光亮度和相对荧光亮度等,使得萤火虫个体的状态可表示为一条从起点到目标点的有效路径。为增加解的多样性及防止计算结果陷入局部最优解,以一定概率对萤火虫代表的路径执行扰动操作,经过多次迭代计算后,可得到所要求解的最短路径。实验结果表明,该算法在种群规模较小、迭代次数较少的情况下可以收敛到最优解,具有较强的收敛性和灵活性,可用于求解任何实际的最短路径问题。     

动态搜索算法求解时间依赖型旅行商问题研究

时间依赖型旅行商问题(TDTSP)是旅行商问题(TSP)的延伸.在该问题中,任意两节点间的旅行时间(成本)不仅取决于节点间的距离,还依赖于一天中具体时段或节点在哈密顿圈中所处的具体位置.对基于节点所处哈密顿圈中具体位置的TDTSP问题建立相应的数学模型,并提出求解该问题的动态搜索算法.通过实验仿真,验证了动态搜索算法优于目前在邻域搜索领域求解该问题最有效的动态规划启发式算法.     

An FPT algorithm in polynomial space for the Directed Steiner Tree problem with Limited number of Diffusing nodes

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^?$T^{?}$ of minimum cost ω(T^?)$\omega (T^{?})$ rooted at r and spanning X.     

An efficient column-generation-based algorithm for solving a pickup-and-delivery problem

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.     

求解最小费用最大流问题的信念传播算法

最小费用最大流问题是一种组合优化问题,在经济、工业等领域具有重要研究意义和应用价值.针对部分最小费用最大流问题求解算法效率较低的情况,依据最小费用最大流问题的线性规划方程,将问题模型映射为对应因子图模型,改进描述函数,给出迭代方程,设计了求解最小费用最大流问题的信念传播算法.利用迭代方程优先对最大可行流特征值进行收敛计算,得到最大流,设置最大流阈值,在此基础上进行最小费用计算,从而求得问题最优解.最后选取若干带权有向图模型进行数值实验,验证了算法的可行性及有效性,且算法在求解效率上优于部分算法.