An ant colony optimization routing algorithm for two order pickers with congestion consideration

This paper develops a routing method to control the picker congestion that challenges the traditional assumption regarding the narrow-aisle order picking system. We proposes a new routing algorithm based on Ant Colony Optimization (ACO) for two order pickers (A-TOP) with congestion consideration. Using two extended dedicated heuristics with congestion consideration as reference group, a comprehensive simulation study is conducted to evaluate the effectiveness of A-TOP. The simulation proves that A-TOP achieves the shortest total picking time in most instances and performs well in dealing with the congestion. The impacts of warehouse layout, order size, and pick:walk-time ratio on A-TOP and system performance are analyzed as well. A-TOP can adapt to different warehouse configurations, meanwhile, it can be easily extended to the situation with more than two order pickers.     

Throughput analysis for order picking system with multiple pickers and aisle congestion considerations

Most of previous studies in picker-to-parts warehousing systems investigated only single-picker operations and are therefore adequate to evaluate order picking efficiency by travel distance as aisle congestion never takes place in such systems. In real world applications, the congestion inevitably occurs when a system has multiple pickers working together within the same region. This paper presents an approximation method based on a GI/G/1 closed queueing network by using self-correcting approximation technique algorithm to evaluate the throughput time of an order picking system with multiple pickers and aisle congestion considerations for different routing policies. The results generated by the proposed method are compared and validated via simulation model using eM-plant simulator for different sizes of warehouses. The results indicate that the approximation method appears to be sufficiently accurate for practical purposes. The sensitivity analysis of the throughput time with respect to order sizes, number of pickers and number of aisles are conducted and the performance of different item storage policies are also evaluated using the proposed approximation model.     

CCIPCA-OPCSC: An online method for detecting shared congestion paths

It is very useful to detect network paths sharing the same bottleneck for improving efficiency and fairness of network resource usage. Existing techniques have been designed to detect shared congestion between a pair of paths with a common source or destination point. And they are poor in scalability and not applicable to online detection. To cope with these problems, a novel method called CCIPCA-based Online Path Clustering by Shared Congestion (CCIPCA-OPCSC) is proposed to detect shared congestion paths, whose essence lies in the use of a novel eigenvector projection analysis (EPA). First, the delay measurement data of each path are mapped into a point in a new, low-dimensional space based on the correlation among paths reflected by the eigenvectors and eigenvalues in the process of PCA. In this new space, points are close to each other if the corresponding paths share congestion. CCIPCA is also introduced to compute the eigenvectors and eigenvalues incrementally. Second, the clustering analysis is applied on these points so as to identify shared congestion paths accurately. CCIPCA-OPCSC has low computational complexity and can fulfill the requirement of online detection. This method is evaluated by NS2 simulations and experiments on the PlanetLab testbed over the Internet. The results demonstrate that this novel method is feasible and effective.     

An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen

The vehicle routing problem with time windows and multiple deliverymen (VRPTWMD) is a variant of the vehicle routing problem with time windows in which service times at customers depend on the number of deliverymen assigned to the route that serves them. In particular, a larger number of deliverymen in a route leads to shorter service times. Hence, in addition to the usual routing and scheduling decisions, the crew size for each route is also an endogenous decision. This problem is commonly faced by companies that deliver goods to customers located in busy urban areas, a situation that requires nearby customers to be grouped in advance so that the deliverymen can serve all customers in a group during one vehicle stop. Consequently, service times can be relatively long compared to travel times, which complicates serving all scheduled customers during regular work hours. In this paper, we propose a hybrid method for the VRPTWMD, combining a branch-price-and-cut (BPC) algorithm with two metaheuristic approaches. We present a wide variety of computational results showing that the proposed hybrid approach outperforms the BPC algorithm used as standalone method in terms of both solution quality and running time, in some classes of problem instances from the literature. These results indicate the advantages of using specific algorithms to generate good feasible solutions within an exact method.     

An ACO-based hyperheuristic with dynamic decision blocks for intercell scheduling

In real production of equipment manufacturing industry, coordination between cells is needed. Intercell scheduling therefore comes into being. In this paper, a limited intercell transportation capacity constraint is taken into consideration, a hyperheuristic is proposed, which employs ant colony optimization to select appropriate heuristic rules for production scheduling and transportation scheduling. Moreover, dynamic decision blocks are introduced to the hyperheuristic to make a better balance between optimization performance and computation efficiency. Computational results show that, as compared with other approaches, the proposed approach performs much better with respect to minimizing total weighted tardiness while retaining low computational costs, and it is especially suitable for the problems with large sizes.     

Algorithms for on-line order batching in an order picking warehouse

In manual order picking systems, order pickers walk or ride through a distribution warehouse in order to collect items required by (internal or external) customers. Order batching consists of combining these – indivisible – customer orders into picking orders. With respect to order batching, two problem types can be distinguished: in off-line (static) batching, all customer orders are known in advance; in on-line (dynamic) batching, customer orders become available dynamically over time. This paper considers an on-line order batching problem in which the maximum completion time of the customer orders arriving within a certain time period has to be minimized. The author shows how heuristic approaches for off-line order batching can be modified in order to deal with the on-line situation. In a competitive analysis, lower and upper bounds for the competitive ratios of the proposed algorithms are presented. The proposed algorithms are evaluated in a series of extensive numerical experiments. It is demonstrated that the choice of an appropriate batching method can lead to a substantial reduction of the maximum completion time.     

An efficient checkpointing method for multicomputers with wormhole routing

Efficient checkpointing and resumption of multicomputer applications is essential if multicomputers are to support time-sharing and the automatic resumption of jobs after a system failure. We present a checkpointing scheme that is transparent, imposes overhead only during checkpoints, requires minimal message logging, and allows for quick resumption of execution from a checkpointed image. Furthermore, the checkpointing algorithm allows each processorp to continue running the application being checkpointed except during the time thatp is actively taking a local snapshot, and requires no global stop or freeze of the multicomputer. Since checkpointing multicomputer applications poses requirements different from those posed by checkpointing general distributed systems, existing distributed checkpointing schemes are inadequate for multicomputer checkpointing. Our checkpointing scheme makes use of special properties of wormhole routing networks to satisfy this new set of requirements.     

An evolutionary algorithm for order splitting with multiple transport alternatives

In this paper, a new methodology is suggested for determining the optimal mix of transport alternatives to minimize total logistics costs when goods are shipped from a supplier to a receiver. The total logistics costs comprise order costs, transportation costs and inventory costs.It is assumed that only a limited number of transport alternatives are capable of shipping the goods from the supplier to the receiver. Moreover, if a certain transport alternative is selected to ship the goods, then its entire capacity is used. These assumptions imply that the number of possible order quantities is finite and that the problem can be formulated as a combinatorial optimization problem. In a first step to explore the use of metaheuristics for optimization problems like these, an Evolutionary Algorithm is developed in this paper. The heuristic is tested on real-life problem instances.     

A branch-and-price-and-check model for the vehicle routing problem with location congestion

This paper considers a vehicle routing problem with pickup and delivery, time windows and location congestion. Locations provide a number of cumulative resources that are utilized by vehicles either during service (e.g., forklifts) or for the entirety of their visit (e.g., parking bays). Locations can become congested if insufficient resources are available, upon which vehicles must wait until a resource becomes available before proceeding. The problem is challenging from a computational standpoint since it incorporates the vehicle routing problem and the resource-constrained project scheduling problem. The main contribution of this paper is a branch-and-price-and-check model that uses a branch-and-price algorithm that solves the underlying vehicle routing problem, and a constraint programming subproblem that checks the feasibility of the location resource constraints, and then adds combinatorial nogood cuts to the master problem if the resource constraints are violated. Experimental results show the benefits of the branch-and-price-and-check approach.     

基于遗传算法的双区型仓库拣货路径优化研究

拣货作业成本是物流成本的重要组成部分。根据物流配送中心传统双区型仓库拣货路径问题的特点,建立了数学模型,并设计了相应的遗传算法来求解该问题。在算例中,通过与传统穿越策略、S形启发式算法和动态规划方法的比较,结果表明以遗传算法优化拣货路径问题,可以明显减少拣货路径的距离及拣货作业时间,具有良好的实用性。     

An ACO-based intercell scheduling approach for job shop cells with multiple single processing machines and one batch processing machine

Intercell transfers are inevitable for the manufacturing of complicated products, which disrupts the philosophy of cellular manufacturing and leads new challenges to the field of production scheduling. The issue of intercell scheduling is analyzed in the context of a cellular manufacturing system consisting of multiple single-processing machines and one batch-processing machine, which is derived from the actual manufacturing of complicated assemblies in the equipment manufacturing industry. Since the two types of machines are different from, even contrary to, each other in some constraint conditions, a combinational ant colony optimization (CACO) approach is developed in this paper, which designs two structures for the single-processing machines and the batch-processing machine, respectively. By updating pheromone trails integratedly and scheduling the single-processing operations and the batch-processing operations simultaneously, cooperative optimization for the two types of machines is achieved in the CACO. Minimizing the maximum completion time is taken as the scheduling objectives. Computational results show that the CACO has significant advantages comparing with other approaches and the CPLEX, and is especially suitable for the large dimension problems.     

An efficient and easily deployable QoS-based routing scheme for online Internet multicasting

With the advent of multimedia applications, the support of online multicasting with quality of service guarantees has gained considerable attention in the field of communication networks and distributed systems. Online multicasting requires the support of online join and leave operations. In this paper, a new Simple and Efficient Low-cost Delay-bounded Online Multicasting (SELDOM) heuristic is proposed. SELDOM is particularly tailored to networks in which group membership changes frequently. SELDOM supports two modes of operations: non-rearrangeable and rearrangeable. The scheme handles join requests dynamically by determining the least-cost path which satisfies the required delay-bounds to which the new group member is to be attached. To handle a leave request, the scheme seeks to limit the number of rearrangements required in order to reduce the disturbance such a request may cause to current group members. The worst case time complexity of SELDOM is O(n²). An important research contribution of this work shows that if any non-rearrangeable multicast heuristic uses a path other than the least-delay path to add a node to the multicast tree, then the resulting multicast tree can have cycles or nodes with two incoming paths. A simulation-based comparison between non-rearrangeable and rearrangeable online multicast trees is also presented.     

随机需求车辆路径问题的价值逼近在线决策

随着高效实时物流的发展,不确定车辆路径问题面临着兼顾决策精度和实时响应能力的新挑战.本文以应用最为广泛的随机需求车辆路径问题为例,研究提出一种有效的在线决策方法.首先,考虑多车辆同时在线,以总旅行成本最小化为目标,建立马尔科夫决策模型,并引入可信度约束和邻域半径减少策略缩小行动空间,提高求解效率.其次,设计强化学习中的...     

An integrated solution for QoS provision and congestion management in high-performance interconnection networks using deterministic source-based routing

A key element in any system based on several interconnected computing and/or storage nodes is the interconnection network. Currently, one of the main concerns of high-speed interconnection network designers is how to improve network performance while using the minimum number of network resources. In that sense, in this paper we describe an efficient switch architecture suitable for any interconnect technology implementing deterministic source-based routing. This switch architecture uses the same network resources to provide two issues that improve network performance: Congestion Management and QoS support. We also present results to compare the effectiveness of this architecture to those of other proposals typically used to provide these issues in this context. These results have been obtained for synthetic traffic and for traces from parallel benchmarks and video frames. From the results, we can conclude that in any traffic scenario, our proposal is as effective as the previous ones, while requiring fewer resources and thus being much more cost-effective.     

An ACO-based multi-objective optimization for cooperating VM placement in cloud data center

The Journal of Supercomputing - High-performance computing requires numerous virtual machines (VMs) to meet the demand for services of the end-users. Such computation generates high intra-network...     

A higher order method for multiple zeros of nonlinear functions

A method of order three for finding multiple zeros of nonlinear functions is developed. The method requires two evaluations of the function and one evaluation of the derivative per step.     

自动化仓库巷道网络AGV货区遍历优化——设计基于优先权遗传算法实现

针对自动化仓库、自动化车间及自动化码头等自动化局部物流存储系统仓库巷道网络中AGV（自动化导引车）对仓库货区遍历作业的路径优化问题,以搜索遍历所有货区的最短路径为目标,建立混合整数线性规划模型,并设计基于优先权的遗传算法求解。通过Matlab仿真实验分析比较算子性能,验证算法的有效性。     

An instrumental variable method for model order identification

The paper describes a simple instrumental variable method for identifying the structure of a wide class of time-series models. The method is aimed at providing a parametrically efficient (parsimonious) model structure which will lead to a combination of low residual error variance, i.e. a good explanation of the data, and low parametric estimation error variance (as measured by some norm associated with the covariance matrix of the estimation errors). It can be applied to single input-single output and multivariable systems using either discrete or continuous-time series models. It can also function as a recursive (on-line) test for reduction in model order.     

An effective early fraud detection method for online auctions

While online auctions continue to increase, so does the incidence of online auction fraud. To avoid discovery, fraudsters often disguise themselves as honest members by imitating normal trading behaviors. Therefore, maintaining vigilance is not sufficient to prevent fraud. Participants in online auctions need a more proactive approach to protect their profits, such as an early fraud detection system. In practice, both accuracy and timeliness are equally important when designing an effective detection system. An instant but incorrect message to the users is not acceptable. However, a lengthy detection procedure is also unsatisfactory in assisting traders to place timely bids. The detection result would be more helpful if it can report potential fraudsters as early as possible. This study proposes a new early fraud detection method that considers accuracy and timeliness simultaneously. To determine the most appropriate attributes that distinguish between normal traders and fraudsters, a modified wrapper procedure is developed to select a subset of attributes from a large candidate attribute pool. Using these attributes, a complement phased modeling procedure is then proposed to extract the features of the latest part of traders’ transaction histories, reducing the time and resources needed for modeling and data collection. An early fraud detection model can be obtained by constructing decision trees or by instance-based learning. Our experimental results show that the performance of the selected attributes is superior to other attribute sets, while the hybrid complement phased models markedly improve the accuracy of fraud detection.     

给出属性优先序的模糊多属性决策方法

研究属性值为模糊变量,已知属性优先序信息的模糊多属性决策问题。基于模糊变量的期望值、模糊变量之间的距离等概念,建立以极大化属性值的离差为目标的模糊期望值模型来确定各属性的权重;基于期望值算子,计算出各方案的期望效用值,从而获得各方案的排序;通过数值算例说明所提出方法的有效性。