Routing order pickers in a warehouse with a middle aisle

This paper considers a parallel aisle warehouse, where order pickers can change aisles at the ends of every aisle and also at a cross aisle halfway along the aisles. An algorithm is presented that can find shortest order picking tours in this type of warehouses. The algorithm is applicable in warehouse situations with up to three aisle changing possibilities. Average tour length is compared for warehouses with and without a middle aisle. It appears that in many cases the average order picking time can be decreased significantly by adding a middle aisle to the layout.     

基于改进粒子群算法V型非传统布局仓库通道优化设计

V型仓储布局是一种典型的非传统布局方式,针对V型布局主通道设计的问题,将主通道抽象为若干个点连接而成的折线通道,每条拣货通道按物动量大小对仓库进行分区,采用更加符合实际的存取货物作业的概率不相等的非完全随机存储策略,建立最小化平均拣货距离的仓库主通道设计数学优化模型。其次,设计了基于极值扰动算子的改进粒子群优化算法(EDO-PSO)进行算法求解,利用极值扰动算子解决易陷入局部最优问题,采用并行深度搜索策略,提高算法性能,并用Benchmark函数与其他改进PSO算法对比验证算法性能。最后,结合具体实验数据仿真分析,计算结果表明,该方法在相同货位分配策略下,能有效缩短总拣货距离,验证了方法的有效性。     

Using a TSP heuristic for routing order pickers in warehouses

In this paper, we deal with the sequencing and routing problem of order pickers in conventional multi-parallel-aisle warehouse systems. For this NP-hard Steiner travelling salesman problem (TSP), exact algorithms only exist for warehouses with at most three cross aisles, while for other warehouse types literature provides a selection of dedicated construction heuristics. We evaluate to what extent reformulating and solving the problem as a classical TSP leads to performance improvements compared to existing dedicated heuristics. We report average savings in route distance of up to 47% when using the LKH (Lin–Kernighan–Helsgaun) TSP heuristic. Additionally, we examine if combining problem-specific solution concepts from dedicated heuristics with high-quality local search features could be useful. Lastly, we verify whether the sophistication of ‘state-of-the-art’ local search heuristics is necessary for routing order pickers in warehouses, or whether a subset of features suffices to generate high-quality solutions.     

A travel-time model for a person-onboard order picking system

The design of an order picking system in a distribution center depends on several decisions, where a key decision is determining the optimal storage system configuration (the number, length, and height of the storage aisles). To make this decision, a throughput model that considers vertical, as well as horizontal, travel is needed. In this paper we extend prior research that considers horizontal travel for a given number and length of the storage aisles so that we are also able to consider the height of the aisles as well. Such a model will provide a more accurate estimate of the throughput of an order picker and it will also permit an examination of the tradeoff between the length and height of the aisles. The analytical model we develop to estimate throughput is based on probability models and order statistics results assuming random storage. It is intended for person-onboard order picking systems and we consider both Tchebychev and rectilinear travel. We illustrate the use of our travel-time model by incorporating it into a simple, cost-based optimization model to recommend the height of a one-pallet-deep storage system.     

p-Hub approach for the optimal park-and-ride facility location problem

Park and Ride facilities (P&R) are car parks at which users can transfer to public transportation to reach their final destination. We propose a mixed linear programming formulation to determine the location of a fixed number of P&R facilities so that their usage is maximized. The facilities are modeled as hubs. Commuters can use one of the P&R facilities or choose to travel by car to their destinations, and their behavior follows a logit model. We apply a p-hub approach considering that users incur in a known generalized cost of using each P&R facility as input for the logit model. For small instances of the problem, we propose a novel linearization of the logit model, which allows transforming the binary nonlinear programming problem into a mixed linear programming formulation. A modification of the Heuristic Concentration Integer (HCI) procedure is applied to solve larger instances of the problem. Numerical experiments are performed, including a case in Queens, NY. Further research is proposed.     

基于多候选储位的存取路径优化问题研究

针对单储位储存方式可能导致仓库存取通道拥挤和作业效率低的情形,提出了一种基于多候选储位的存取路径优化方法。首先分配了货物的存取储位,然后建立了多候选储位的车辆路径问题(MLVRP)模型,并基于储位优先解码原则设计了遗传算法,最后通过算例证明该方法的有效性和算法的高效性。多候选储位的方法可以为取货任务至少节约18.4%(两个候选储位)和21.8%(三个候选储位)的路程,算法迭代10000次只需要434s。     

A travel time estimation model for a high-level picker-to-part system with class-based storage policies

Most previous related studies on warehouse configurations and operations only investigated single-level storage rack systems where the height of storage racks and the vertical movement of the picking operations are both not considered. However, in order to utilize the space efficiently, high-level storage systems are often used in warehouses in practice. This paper presents a travel time estimation model for a high-level picker-to-part system with the considerations of class-based storage policy and various routing policies. The results indicate that the proposed model appears to be sufficiently accurate for practical purposes. Furthermore, the effects of storage and routing policies on the travel time and the optimal warehouse layout are discussed in the paper.     

Mixed-width aisle configurations for order picking in distribution centers

Space required for the order picking area and labor required to perform the picking activity are two significant costs for a distribution center (DC). Traditionally, DCs employ either entirely wide or entirely narrow aisles in their picking systems. Wide aisles allow pickers to pass each other, which reduces blocking, and requires fewer pickers than their narrow-aisle counterpart for the same throughput. However, the amount of space required for wide-aisle configurations is high. Narrow aisles utilize less space than wide aisles, but are less efficient because of the increased likelihood of congestion experienced by pickers. We propose a variation to the traditional orthogonal aisle designs where both wide and narrow aisles are mixed within the configuration, with a view that mixed-width aisles may provide a compromise between space and labor. To analyze these new mixed-width aisle configurations, we develop analytical models for space and travel time considering randomized storage and traversal routing policies. Through a cost-based optimization model, we identify system parameters for which mixed-width aisle configurations are optimal. Experimental results indicate that annual cost savings of up to $48,000 can be realized over systems with pure wide or narrow aisle configurations.     

Finding efficient solutions for rectilinear distance location problems efficiently

Given n planar existing facility locations, a planar new facility location X is called efficient if there is no other location Y for which the rectilinear distance between Y and each existing facility is at least as small as between X and each existing facility, and strictly less for at least one existing facility. Rectilinear distances are typically used to measure travel distances between points via rectilinear aisles or street networks. We first present a simple arrow algorithm, based entirely on geometrical analysis, that constructs all efficient locations. We then present a row algorithm which is of order n(log n) that constructs all efficient locations, and establish that no alternative algorithm can be of a lower order.     

Location with acceleration–deceleration distance

In this paper we investigate a model where travel time is not necessarily proportional to the distance. Every trip starts at speed zero, then the vehicle accelerates to a cruising speed, stays at the cruising speed for a portion of the trip and then decelerates back to a speed of zero. We define a time equivalent distance which is equal to the travel time multiplied by the cruising speed. This time equivalent distance is referred to as the acceleration–deceleration (A–D) distance. We prove that every demand point is a local minimum for the Weber problem defined by travel time rather than distance. We propose a heuristic approach employing the generalized Weiszfeld algorithm and an optimal approach applying the Big Triangle Small Triangle global optimization method. These two approaches are very efficient and problems of 10,000 demand points are solved in about 0.015 seconds by the generalized Weiszfeld algorithm and in about 1 minute by the BTST technique. When the generalized Weiszfeld algorithm was repeated 1000 times, the optimal solution was found at least once for all test problems.     

The option value of advanced R & D

Existing tools for making R&D investment decisions cannot properly capture the option value in R&D. Since many new products are identified as failures during the R&D stages, the possibility of refraining from market introduction may add a significant value to the NPV of the R&D project. This paper presents new theoretical insight by developing a stochastic jump amplitude model in a real setting. The option value of the proposed model depends on the expected number of jumps and the expected size of the jumps in a particular business. The model is verified with empirical knowledge of current research in the field of multimedia at Philips Corporate Research. This way, the gap between real option theory and the practice of decision making with respect to investments in R&D is diminished.     

A hierarchical location-allocation model with travel based on expected referral distances

The hierarchical p-median location-allocation model assumes that patrons always travel to the closest facility of appropriate level and that their interests are best served when the distances they must travel to do this are minimized. This assumption about travel behavior is unrealistic, patrons in the real world are known, for instance, to bypass lower level facilities that can serve their needs to attend higher level facilities. We introduce the concept of “expected distance under referral” to deal with such irrationality and incorporate it into a location-allocation model that minimizes the negative effects of such irrational behavior. We demonstrate the model with several types of non-optimal travel behavior.     

Optimization of Poincaré sections for discriminating between stochastic and deterministic behavior of dynamical systems

This paper studies the problem of finding optimal parameters for a Poincaré section used for determining the type of behavior of a time series: a deterministic or stochastic one. To reach that goal optimization algorithms are coupled with the Poincaré & Higuchi (P&H) method, which calculates the Higuchi dimension using points obtained by performing a Poincaré section of a certain attractor. The P&H method generates distinctive patterns that can be used for determining if a given attractor is produced by a deterministic or a stochastic system, but this method is sensitive to the parameters of the Poincaré section. Patterns generated by the P&H method can be characterized using numerical measures which in turn can be used for finding such parameters for the Poincaré section for which the patterns produced by the P&H method are the most prominent. This paper studies several approaches to parameterization of the Poincaré section. Proposed approaches are tested on twelve time series, six produced by deterministic chaotic systems and six generated randomly. The obtained results show, that finding good parameters of the Poincaré section is important for determining the type of behavior of a time series. Among the tested methods the evolutionary algorithm was able to find the best Poincaré sections for use with the P&H method.     

基于弹性区带架构的多目标设施布局问题研究

为解决设施面积不等的连续型设施布局问题,建立了基于弹性区带架构布置形式,以物料搬运成本最小、邻近关系最大、距离要求满足度最大的多目标设施布局模型。模型中考虑了区域内的横向、纵向过道,对设施的长宽比进行了限制,使得结果更符合实际情况。为克服传统多目标单一化方法需要人为设置子目标函数权重、主观性过强的缺陷,采用基于带有精英保留策略的非支配排序遗传算法(NSGA Ⅱ)的多目标优化算法求解模型,设计了相应的编码方式、交叉算子、变异算子、罚函数。最后通过某物流园区的实例分析证明了模型与方法的有效性。     

A model of R&D valuation and the design of research incentives

We develop a real options model of R&D valuation that takes into account the uncertainty in the quality (or efficacy) of the research output, the time and cost to completion, and the market demand for the R&D output. The model is then applied to study the problem of pharmaceutical under-investment in R&D for vaccines to treat diseases affecting the developing regions of the world. To address this issue, world organizations and private foundations are willing to sponsor vaccine R&D, but there is no consensus on how to administer the sponsorship effectively. Different research incentive contracts are examined using our valuation model. Their effectiveness is measured in the following five dimensions: expected cost to the sponsor, probability of development success, consumer surplus generated, expected number of successful vaccinations and expected cost per person successfully vaccinated. We find that, in general, purchase commitment plans (pull subsidies) are more effective than cost subsidy plans (push subsidies). Moreover, we find that a hybrid subsidy plan constructed from a purchase commitment combined with a sponsor research cost-sharing subsidy is the most effective.     

A model of R&D valuation and the design of research incentives

We develop a real options model of R&D valuation that takes into account the uncertainty in the quality (or efficacy) of the research output, the time and cost to completion, and the market demand for the R&D output. The model is then applied to study the problem of pharmaceutical under-investment in R&D for vaccines to treat diseases affecting the developing regions of the world. To address this issue, world organizations and private foundations are willing to sponsor vaccine R&D, but there is no consensus on how to administer the sponsorship effectively. Different research incentive contracts are examined using our valuation model. Their effectiveness is measured in the following five dimensions: expected cost to the sponsor, probability of development success, consumer surplus generated, expected number of successful vaccinations and expected cost per person successfully vaccinated. We find that, in general, purchase commitment plans (pull subsidies) are more effective than cost subsidy plans (push subsidies). Moreover, we find that a hybrid subsidy plan constructed from a purchase commitment combined with a sponsor research cost-sharing subsidy is the most effective.     

Travel time models for automated warehouses with aisle transferring storage and retrieval machine

This paper presents analytical travel time models for the computation of travel time for automated warehouses with the aisle transferring S/R machine (in continuation multi-aisle AS/RS). These models consider the operating characteristics of the storage and retrieval machine such as acceleration and deceleration and the maximum velocity. Assuming uniform distributed storage rack locations and pick aisles and using the probability theory, the expressions of the cumulative distribution functions with which the mean travel time is calculated, have been determined. The computational models enable the calculation of the mean travel time for the single and dual command cycles, from which the performance of multi-aisle AS/RS can be evaluated. A simulation model of multi-aisle AS/RS has been developed to compare the performances of the proposed analytical travel time models. The analyses show that regarding all examined types of multi-aisle AS/RS, the results of proposed analytical travel time models correlate with the results of simulation models of multi-aisle AS/RS.     

A fast simulated annealing method for batching precedence-constrained customer orders in a warehouse

Batching customer orders in a warehouse can result in considerable savings in order pickers’ travel distances. Many picker-to-parts warehouses have precedence constraints in picking a customer order. In this paper a joint order-batching and picker routing method is introduced to solve this combined precedence-constrained routing and order-batching problem. It consists of two sub-algorithms: an optimal A^∗-algorithm for the routing; and a simulated annealing algorithm for the batching which estimates the savings gained from batching more than two customer orders to avoid unnecessary routing. For batches of three customer orders, the introduced algorithm produces results with an error of less than 1.2% compared to the optimal solution. It also compares well to other heuristics from literature. A data set from a large Finnish order picking warehouse is rerouted and rebatched resulting in savings of over 5000 kilometres or 16% in travel distance in 3 months compared to the current method.     

Facility placement with sub-aisle design in an existing layout

In this paper, we consider the integration of facility placement in an existing layout and the configuration of one or two connecting sub-aisles. This is relevant, for example, when placing a new machine/department on a shop floor with existing machines/departments and an existing aisle structure. Our work is motivated by the work of Savas et al. [Savas, S., Batta, R., Nagi, R., 2002. Finite-size facility placement in the presence of barriers to rectilinear travel. Operations Research 50 (6), 1018–1031], that considered the optimal planar placement of a finite-size facility in the presence of existing facilities. Our work differs from theirs in that we consider material handling to be restricted to the aisle structure. We do not allow the newly placed facility to overlap with existing facilities or with the aisle structure. Facilities are rectangular and travel is limited to new or existing aisles. We show that there are a finite number of candidate placements for the new facility. Algorithms are developed to find the optimal placement and the corresponding configurations for the sub-aisles. Complexity of the solution method is analyzed. Also, a numerical example is provided to explore the impact of the number of sub-aisles added.     

Comparative evaluation of performance of national R&D programs with heterogeneous objectives: A DEA approach

The strategic importance of performance evaluation of national R&D programs is highlighted as the resource allocation draws more attention in R&D policy agenda. Due to the heterogeneity of national R&D programs’ objectives, however, it is intractably difficult to relatively evaluate multiple programs and, consequently, few studies have been conducted on the performance comparison of the R&D programs. This study measures and compares the performance of national R&D programs using data envelopment analysis (DEA). Since DEA allows each DMU to choose the optimal weights of inputs and outputs which maximize its efficiency, it can mirror R&D programs’ unique characteristics by assigning relatively high weights to the variables in which each program has strength. Every project in every R&D program is evaluated together based on the DEA model for comparison of efficiency among different systems. Kruskal–Wallis test with a post hoc Mann–Whitney U test is then run to compare performance of R&D programs. Two alternative approaches to incorporating the importance of variables, the AR model and output integration, are also introduced. The results are expected to provide policy implications for effectively formulating and implementing national R&D programs.