Approximation algorithm for uniform bounded facility location problem

The uniform bounded facility location problem (UBFLP) seeks for the optimal way of locating facilities to minimize total costs (opening costs plus routing costs), while the maximal routing costs of all clients are at most a given bound M. After building a mixed 0–1 integer programming model for UBFLP, we present the first constant-factor approximation algorithm with an approximation guarantee of 6.853+? for UBFLP on plane, which is composed of the algorithm by Dai and Yu (Theor. Comp. Sci. 410:756–765, 2009) and the schema of Xu and Xu (J. Comb. Optim. 17:424–436, 2008). We also provide a heuristic algorithm based on Benders decomposition to solve UBFLP on general graphes, and the computational experience shows that the heuristic works well.     

Minimum power assignment in wireless ad hoc networks with spanner property

Power assignment for wireless ad hoc networks is to assign a power for each wireless node such that the induced communication graph has some required properties. Recently research efforts have focused on finding the minimum power assignment to guarantee the connectivity or fault-tolerance of the network. In this paper, we study a new problem of finding the power assignment such that the induced communication graph is a spanner for the original communication graph when all nodes have the maximum power. Here, a spanner means that the length of the shortest path in the induced communication graph is at most a constant times of the length of the shortest path in the original communication graph. Polynomial time algorithm is given to minimize the maximum assigned power with spanner property. The algorithm also works for any other property that can be tested in polynomial time and is monotone. We then give a polynomial time approximation method to minimize the total transmission radius of all nodes. Finally, we propose two heuristics and conduct extensive simulations to study their performance when we aim to minimize the total assigned power of all nodes. The author is partially supported by NSF CCR-0311174.     

A Genetic Algorithm for the Weight Setting Problem in OSPF Routing

With the growth of the Internet, Internet Service Providers (ISPs) try to meet the increasing traffic demand with new technology and improved utilization of existing resources. Routing of data packets can affect network utilization. Packets are sent along network paths from source to destination following a protocol. Open Shortest Path First (OSPF) is the most commonly used intra-domain Internet routing protocol (IRP). Traffic flow is routed along shortest paths, splitting flow at nodes with several outgoing links on a shortest path to the destination IP address. Link weights are assigned by the network operator. A path length is the sum of the weights of the links in the path. The OSPF weight setting (OSPFWS) problem seeks a set of weights that optimizes network performance. We study the problem of optimizing OSPF weights, given a set of projected demands, with the objective of minimizing network congestion. The weight assignment problem is NP-hard. We present a genetic algorithm (GA) to solve the OSPFWS problem. We compare our results with the best known and commonly used heuristics for OSPF weight setting, as well as with a lower bound of the optimal multi-commodity flow routing, which is a linear programming relaxation of the OSPFWS problem. Computational experiments are made on the AT&T Worldnet backbone with projected demands, and on twelve instances of synthetic networks.     

带工期指派的产品服务系统订单随机调度问题研究

针对由一个制造工厂和多个区域服务中心组成的服务型制造企业，研究了考虑生产时间和服务时间均具有随机性且工期可指派的产品服务系统（PSS）订单调度问题。首先以最小化订单提前、误工和工期指派费用的期望总额为目标构建问题的优化模型，然后分析目标函数近似值的最优性条件，据此提出加权最短平均生产时间排序规则，并结合该规则与插入邻域局部搜索设计了启发式算法对问题进行求解，最后通过数值仿真验证算法的可行性和有效性。研究表明，提前费用偏差对PSS订单调度与工期指派决策的影响很小，因此企业管理者无需准确估计库存费用也能制定出比较有效的PSS订单调度策略；而工期指派费用偏差对决策结果的影响非常大，因此企业管理者在决策时必须谨慎估计该项费用。     

Network Reconfiguration for Increasing Transportation System Resilience Under Extreme Events

Evacuating residents out of affected areas is an important strategy for mitigating the impact of natural disasters. However, the resulting abrupt increase in the travel demand during evacuation causes severe congestions across the transportation system, which thereby interrupts other commuters' regular activities. In this article, a bilevel mathematical optimization model is formulated to address this issue, and our research objective is to maximize the transportation system resilience and restore its performance through two network reconfiguration schemes: contraflow (also referred to as lane reversal) and crossing elimination at intersections. Mathematical models are developed to represent the two reconfiguration schemes and characterize the interactions between traffic operators and passengers. Specifically, traffic operators act as leaders to determine the optimal system reconfiguration to minimize the total travel time for all the users (both evacuees and regular commuters), while passengers act as followers by freely choosing the path with the minimum travel time, which eventually converges to a user equilibrium state. For each given network reconfiguration, the lower‐level problem is formulated as a traffic assignment problem (TAP) where each user tries to minimize his/her own travel time. To tackle the lower‐level optimization problem, a gradient projection method is leveraged to shift the flow from other nonshortest paths to the shortest path between each origin–destination pair, eventually converging to the user equilibrium traffic assignment. The upper‐level problem is formulated as a constrained discrete optimization problem, and a probabilistic solution discovery algorithm is used to obtain the near‐optimal solution. Two numerical examples are used to demonstrate the effectiveness of the proposed method in restoring the traffic system performance.     

Hierarchical Multi‐skill Resource Assignment in the Telecommunications Industry

We formulate a discrete time Markov decision process for a resource assignment problem for multi‐skilled resources with a hierarchical skill structure to minimize the average penalty and waiting costs for jobs with different waiting costs and uncertain service times. In contrast to most queueing models, our application leads to service times that are known before the job is actually served but only after it is accepted and assigned to a server. We formulate the corresponding Markov decision process, which is intractable for problems of realistic size due to the curse of dimensionality. Using an affine approximation of the bias function, we develop a simple linear program that yields a lower bound for the minimum average costs. We suggest how the solution of the linear program can be used in a simple heuristic and illustrate its performance in numerical examples and a case study.     

A Grasp for Aircraft Routing in Response to Groundings and Delays

This paper presents a greedy randomized adaptive search procedure (GRASP) to reconstruct aircraft routings in response to groundings and delays experienced over the course of the day. Whenever the schedule is disrupted, the immediate objective of the airlines is to minimize the cost of reassigning aircraft to flights taking into account available resources and other system constraints. Associated costs are measured by flight delays and cancellations.In the procedure, the neighbors of an incumbent solution are generated and evaluated, and the most desirable are placed on a restricted candidate list. One is selected randomly and becomes the incumbent. The heuristic is polynomial with respect to the number of flights and aircraft. This is reflected in our computational experience with data provided by Continental Airlines. Empirical results demonstrate the ability of the GRASP to quickly explore a wide range of scenarios and, in most cases, to produce an optimal or near-optimal solution.     

The supplier selection problem with quantity discounts and truckload shipping

To minimize procurement expenditures both purchasing and transportation costs need to be considered. We study a procurement setting in which a company needs to purchase a number of products from a set of suppliers to satisfy customer demand. The suppliers offer total quantity discounts and transportation costs are based on truckload shipping rates. The goal is to select a set of suppliers so as to satisfy product demand at minimal total costs. The resulting optimization problem is strongly NP-hard. We develop integer programming based heuristics to solve the problem. Extensive computational experiments demonstrate the efficacy of the proposed heuristics and provide insight into the impact of instance characteristics on effective procurement strategies.     

A memetic differential evolution algorithm for energy-efficient parallel machine scheduling

This paper considers an energy-efficient bi-objective unrelated parallel machine scheduling problem to minimize both makespan and total energy consumption. The parallel machines are speed-scaling. To solve the problem, we propose a memetic differential evolution (MDE) algorithm. Since the problem involves assigning jobs to machines and selecting an appropriate processing speed level for each job, we characterize each individual by two vectors: a job-machine assignment vector and a speed vector. To accelerate the convergence of the algorithm, only the speed vector of each individual evolves and a list scheduling heuristic is applied to derive its job-machine assignment vector based on its speed vector. To further enhance the algorithm, we propose efficient speed adjusting and job-machine swap heuristics and integrate them into the algorithm as a local search approach by an adaptive meta-Lamarckian learning strategy. Computational results reveal that the incorporation of list scheduling heuristic and local search greatly strengthens the algorithm. Computational experiments also show that the proposed MDE algorithm outperforms SPEA-II and NSGA-II significantly.     

Inventory routing problems in a context of vendor-managed inventory system with consignment stock and transshipment

The inventory routing problem involves the integration and the coordination of two components of the logistics value chain: the inventory management and the vehicle routing decisions. In fact, the aim is to jointly decide on the distribution tour, from a distribution centre to a set of locations, and on the inventory policy for each location. Although many research investigations show great interest in policies such as transshipment or dynamic routings on the distribution system performances, these approaches are often criticised in practice as being too restrictive. In this article, we consider the inventory routing framework in a supplier integration context, i.e. a vendor-managed inventory with a consignment stock policy. Under such framework, we show that the transshipment brings more benefits than the classical context. In particular, we consider the case of static routings and we numerically show that transshipment permits to better optimise the distribution tours and to improve the global performance of the supply network.     

Optimization of loss-balanced multicast in all-optical WDM networks

In wavelength-division multiplexing (WDM) optical networks, multicast is implemented by constructing a light-forest, which is a set of light-trees with each light-tree rooted from the multicast source and terminated at a partition subset of the destination nodes. Multicast routing scenario has considerable impact on the quality of optical signal received at each destination. To guarantee the fairness of signal quality at different destinations in a multicast session, it is desirable to construct a loss-balanced light-forest to deliver the multicast traffic. A loss-balanced light-forest is composed of a set of light-trees bounded in size (number of destinations per multicast tree), in size variation (difference in the number of destinations among different multicast trees), and in dimension (maximum source-to-destination distance on each multicast tree). This paper investigates the multicast routing and wavelength assignment (MC-RWA) problem under the loss-balance constraint. The problem is formulated as an optimization model using integer linear programming (ILP). Numerical solutions to the optimization model can supply useful performance benchmarks for loss-balance-constrained optical multicast in WDM networks. This work was supported by the NSF under Grant OCI-0225642 and by the U.S. DoE under Grant DE-FG02–03ER25566.     

Packing trees in communication networks

Given an undirected edge-capacitated graph and given (possibly) different subsets of vertices, we consider the problem of selecting a maximum (weighted) set of Steiner trees, each tree spanning a subset of vertices, without violating the capacity constraints. This problem is motivated by applications in multicast communication networks. We give an integer linear programming (ILP) formulation for the problem, and observe that its linear programming (LP) relaxation is a fractional packing problem with exponentially many variables and a block (sub-)problem that cannot be solved in polynomial time. To this end, we take an r-approximate block solver (a weak block solver) to develop a (1−ε)/r-approximation algorithm for the LP relaxation. The algorithm has a polynomial coordination complexity for any ε∈(0,1). To the best of our knowledge, this is the first approximation result for fractional packing problems with only weak block solvers (with arbitrarily large approximation ratio) and a coordination complexity that is polynomial in the input size. This leads also to an approximation algorithm for the underlying tree packing problem. Finally, we extend our results to an important multicast routing and wavelength assignment problem in optical networks, where each Steiner tree is to be assigned one of a limited set of given wavelengths, so that trees crossing the same fiber are assigned different wavelengths. A preliminary version of this paper appeared in the Proceedings of the 1st Workshop on Internet and Network Economics (WINE 2005), LNCS, vol. 3828, pp. 688–697. Research supported by a MITACS grant for all the authors, an NSERC post doctoral fellowship for the first author, the NSERC Discovery Grant #5-48923 for the second and fourth author, NSERC Discovery Grant #15296 for the third author, the Canada Research Chair Program for the second author, and an NSERC industrial and development fellowship for the fourth author.     

运输网络运量分配问题的模型及算法研究

针对我国在运量分配模型及算法方面研究比较薄弱的现状,本文对此问题进行了系统深人的研究,应用运筹学、计算机科学的新的理论和方法,建立了多目标运量分配优化模型,且在模型中,将一些重要特性考虑成运输流量的函数,从而可使分配结果更符合实际情况。同时为求解该模型,本文研究设计了鲁棒性强、高效、实用的自适应搜索算法。     

越库配送下考虑时空距离的库门分配与车辆调度优化

针对越库配送下考虑时空距离的库门分配与车辆路径问题,建立以车辆派遣成本、运输成本、时间惩罚成本、越库内部操作成本总和最小化为目标的库门分配与车辆路径优化模型。根据问题的特征设计改进的自适应遗传算法,并根据时空距离生成初始解。通过对不同规模的算例进行对比和分析,验证了模型的正确性和算法的有效性,结果表明,所得出的库门分配和车辆调度优化方案可以有效降低越库配送中心的运营成本。研究成果拓展和丰富了越库配送下的车辆路径问题研究,能为物流企业优化配送方案提供理论依据。     

协同运输的路线整合问题研究

本文研究协同运输的路线整合问题(CTRIP):允许所有的O-D流(运输任务)在规定的路线长度内任意采取直通运输、单点中转、两点中转的整合运输路线,整合运输的中枢路段在支付固定成本后可产生运费折扣,如何选择O-D流的整合路线使得总成本最小? CTRIP广泛应用于航空、物流、快递等领域的整合运输实践。论文构造了CTRIP的混合整数规划模型和Benders分解算法,实验显示,算法表现出非常好的计算绩效。最后,我们利用一个具体实例对CTRIP与已有研究展开了比较,结论显示CTRIP更能保证中枢路段的规模优势 。     

Multi-neighborhood based iterated tabu search for routing and wavelength assignment problem

The routing and wavelength assignment problem (RWA) has shown to be NP-hard if the wavelength continuity constraint and the objective of minimizing the number of wavelengths are considered. This paper introduces a multi-neighborhood based iterated tabu search algorithm (MN-ITS), which consists of three neighborhoods with a unified incremental evaluation method, to solve the min-RWA problem. The proposed MN-ITS algorithm is tested on a set of widely studied real world instances as well as a set of challenging random ones in the literature. Comparison with other reference algorithms shows that the MN-ITS algorithm is able to improve five best upper bounds obtained by other competitive reference algorithms in the literature. This paper also presents an analysis to show the significance of the unified incremental evaluation technique and the combination of multiple neighborhoods.     

Job sequencing and component set-up on a surface mount placement machine

In this paper, the problem of sequencing PCB assembly jobs on an automatic SMD placement machine is addressed. The objective is to minimize the makespan. Moreover, both the job arrival times and the precedence constraints for those jobs requiring component placement on the primary and secondary side of the same board must be taken into account. A considerable set-up time occurs when switching from one board type to another, which depends on the number of component feeders to be replaced in the magazine of the assembly machine. The exchange of component feeders is complicated by the fact that each feeder occupies a different number of magazine positions. Theoretically, the minimum makespan required for a given batch of jobs could be derived by solving the order sequencing and the component set-up problems simultaneously. However, optimal solutions are practically unattainable for problems of realistic size. Therefore, efficient heuristic solution procedures are developed which exploit component commonality between PCB types. The numerical results obtained indicate the practicality of the proposed heuristics in an industrial application.     

MINIMIZING TOTAL WEIGHTED COMPLETION TIME ON A SINGLE BATCH PROCESSING MACHINE

We study the problem of scheduling jobs on a single batch processing machine to minimize the total weighted completion time. A batch processing machine is one that can process a number of jobs simultaneously as a batch. The processing time of a batch is given by the processing time of the longest job in the batch. We present a branch and bound algorithm to obtain optimal solutions and develop lower bounds and dominance conditions. We also develop a number of heuristics and evaluate their performance through extensive computational experiments. Results show that two of the heuristics consistently generate high-quality solutions in modest CPU times.     

自动化立体仓库中的储位分配及存取路径优化

储位分配和存取作业路径优化是仓储管理中的两个重要决策问题。本文研究如何在自动化立体仓库中对这两个问题进行同时决策。提出了一个混合整数规划模型对该问题进行优化建模,设计开发了一个基于有向连接图的两阶段优化算法对问题求初始解,并利用禁忌搜索算法对所求得的解进行改进。算法第一阶段解决储位分配问题,在此基础上第二阶段利用Hungarian算法对堆垛机的存取作业路径优化问题进行求解。最后利用实例对算法效率和精度进行分析评价,计算结果验证了算法的有效性。