无人仓系统储位分配问题的优化模型与算法

考虑到无人仓系统补货阶段货架上只有部分空余储位的特点，研究了补货商品储位分配问题的优化模型与算法。以同一货架上存放的商品之间关联度之和最大化为目标建立了混合整数规划模型；结合贪婪算法和邻域搜索算法设计了求解模型的两阶段方法。第一阶段利用贪婪算法求初始可行解；第二阶段利用邻域搜索算法对初始可行解进行优化。利用一个具体算例验证了邻域搜索算法的优化效果，结果显示，通过邻域搜索算法对初始可行解的优化，可以使目标函数值至少提升27%。进一步利用多个小规模算例分析了两阶段算法的近似比和求解速度，验证了算法的快速有效性。本文的研究结果不仅解决了货架初始状态非空情况下的储位分配问题，同样适合解决货架初始状态为空的情况，因此更加符合实际场景，可以作为无人仓管理信息系统的核心模型和算法。     

Managing Production and Distribution for Supply Chains in the Processed Food Industry

We develop and evaluate a modeling approach for making periodic review production and distribution decisions for a supply chain in the processed food industry. The supply chain faces several factors, including multiple products, multiple warehouses, production constraints, high transportation costs, and limited storage at the production facility. This problem is motivated by the supply chain structure at Amy's Kitchen, one of the leading producers of natural and organic foods in the United States. We develop an enhanced myopic two‐stage approach for this problem. The first stage determines the production plan and uses a heuristic, and the second stage determines the warehouse allocation plan and uses a non‐linear optimization model. This two‐stage approach is repeated every period and incorporates look‐ahead features to improve its performance in future periods. We validate our model using actual data from one factory at Amy's Kitchen and compare the performance of our model to that of the actual operation. We find that our model significantly reduces both inventory levels and stockouts relative to those of the actual operation. In addition, we identify a lower bound on the total costs for all feasible solutions to the problem and measure the effectiveness of our model against this lower bound. We perform sensitivity analysis on some key parameters and assumptions of our modeling approach.     

A harmony search-based memetic optimization model for integrated production and transportation scheduling in MTO manufacturing

This paper investigates an integrated production and transportation scheduling problem in an MTO supply chain. A harmony search-based memetic optimization model is developed to handle this problem, in which certain heuristic procedures are proposed to convert the investigated problem into an order assignment problem. A novel improvisation process is also proposed to improve the optimum-seeking performance. The effectiveness of the proposed model is validated by numerical experiments. The experimental results show that (1) the proposed model can solve the investigated problem effectively and that (2) the proposed memetic optimization process exhibits better optimum-seeking performance than genetic algorithm-based and traditional memetic optimization processes.     

A variable neighborhood search algorithm for human resource selection and optimization problem in the home appliance manufacturing industry

The increase in human resource cost puts forward higher requirements for the optimization of home appliance manufacturing processes. This paper studied an integrated human resource optimization problem considering the human resource selection, learning effect, skills degradation effect, and parallel production lines. There are multiple different manufacturing tasks with different normal processing times. Human resources have different abilities and costs. The actual processing time of a task is determined by its normal processing time, position, and ability of the human resource. The objective is to minimize production time and the labor cost. To solve the studied problem, we first consider the case where the human resources have been selected and assigned to the production lines. Then, some structural properties are proposed and a heuristic is developed to arrange tasks on every single production line. Also, we derive a lower bound for the problem. Since the investigated problem is NP-hard, a Variable Neighborhood Search is designed to solve the problem in a reasonable time. Finally, computational experiments are conducted and the experimental results validate the performance of the proposed methods.

     

大规模客运专线网络运营优化模型与求解算法

本文在分析铁路运营优化模型的研究进展的基础上,提出了一个适合大规模客运专线网络运营的优化模型,并提出了求解此模型的列生成算法和启发式快速算法。目的是将客运专线网路的开行方案优化与动态收益优化问题结合起来,解决更大、更复杂的客运网络运营优化问题。模型以列车运营总收益最大化为目标。用随机生成数据进行的模型试验表明,模型及算法可以在较短的时间内求解较大规模的收益管理优化问题。     

Coordinated scheduling of production and delivery stages with stage-dependent inventory holding costs

This paper considers a problem of integrated decision-making for job scheduling and delivery batching wherein different inventory holding costs between production and delivery stages are allowed. In the problem, jobs are processed on a facility at a production stage and then delivered at the subsequent delivery stage by a capacitated vehicle. The objective is to find the coordinated schedule of production and delivery that minimizes the total cost of the associated WIP inventory, finished product inventory and delivery, where both the inventory costs are characterized in terms of the weighted flow-time and the delivery cost is proportional to the required number of delivery batches. It is proved that the problem is NP-hard in the strong sense. Thereupon, three heuristic algorithms are derived. Some restricted cases are also characterized as being solvable in polynomial time. Numerical experiments are conducted to evaluate the performance of the derived heuristic algorithms.     

B2C电子商务环境下订单拣选与配送联合调度优化

如何在顾客下单后协调好拣选和配送环节,在最短的时间、以较低的成本将商品从货架上拣出、打包后配送到顾客手中,已成为B2C电子商务物流管理中亟待解决的问题。本文尝试以最小化订单履行时间为目标,构建非线性拣选与配送联合调度模型,以解决订单拣选顺序、拣选作业方式、车辆行驶线路等联合决策。为求解此NP难问题,设计了三阶段启发式算法：首先采用“聚类-路径优化”思想,依据顾客位置进行配送方案确认;然后采用基于相似度聚类的订单分批规则对每条配送线路的订单进行分批合并;最后调整拣选任务与配送线路顺序。通过数据实验对模型进行验证,并与传统拣选与配送分开优化的结果进行对比。结果表明,三阶段算法能够有效缩短订单完成时间、降低配送车辆等待时间、改善配送资源利用率。     

下料问题与运输问题联合优化建模

本文研究了考虑子材运输的标准一维下料问题。建立了由生产商负责运输时,标准一维下料与运输协调优化整数规划模型,最小化母材使用成本,子材库存成本及子材运输成本。采用拉格朗日松弛技术对有关约束进行松弛和模型分解,设计基于序列规则和FFD规则的混合启发式算法求解模型。该算法由两部分组成,分别用于求解标准一维下料子问题和卖方运输子问题。通过随机产生的1800个算例,验证模型合理性与算法的有效性。与基于列生成法的两阶段算法解进行比较,平均总成本降低了17.57%,表明集成算法优于两阶段算法。     

LOT-SIZING IN CAPACITATED MULTI-STAGE SERIAL SYSTEMS

The lot-sizing problem in capacitated multi-stage systems with a serial product structure is addressed. This is a complex optimization problem that is part of the decision set in material requirements planning (MRP) systems. The mathematical model that describes the problem uses the concept of echelon stock and includes lead times. Setup times are taken into account, which implies that the problem of finding a feasible solution is NP-Complete. This paper proposes a heuristic method that provides a production plan in order to minimize inventory, production, and setup costs. The heuristic starts from a solution for the uncapacitated problem, which is given by the sequential application of the Wagner-Whitin algorithm. Feasibility is then attempted by shifting production amounts between periods. Computational tests conducted in 1,800 instances with up to 40 components and 18 periods have shown that feasible solutions were obtained in 83.7% of the instances. For the infeasible instances, on average, the heuristic is able to find solutions with very low capacity excess. The solutions' quality is evaluated through a lower bound provided by Lagrangean relaxation and on average the gap is less than 10%.     

A shelf-space optimization model when demand is stochastic and space-elastic

The more customer demand is impulse-driven, the more it is space-dependent and the more it is subject to variation. We investigate the corresponding problem of retail shelf-space planning when demand is stochastic and sensitive to the number and position of facings. We develop a model to maximize a retailer׳s profit by selecting the number of facings and their shelf position under the assumption of limited space. The model is particularly applicable to promotional or temporary products.We develop the first optimization model and solution approach that takes stochastic demand into account, since the current literature applies deterministic models for shelf-space planning. By the means of an innovative modeling approach for the case with space- and positioning effects and the conversion of our problem into a mixed-integer problem, we obtain optimal results within very short run times for large-scale instances relevant in practice. Furthermore, we develop a solution approach to account for cross-space elasticity, and solve it using an own heuristic, which efficiently yields near-optimal results. We demonstrate that correctly considering space elasticity and demand variation is essential. The corresponding impacts on profits and solution structures become even more significant when space elasticity and stochastic demand interact, resulting in up to 5% higher profits and up to 80% differences in solution structures, if both effects are correctly accounted for. We develop an efficient modeling approach, compare the model results with approaches applied in practice and derive rules-of-thumb for planners.     

Decentralised bilevel model for shared inventory management

In this study, we consider the case of a large corporation that owns a warehouse and two concurrent chains. The company opted for shared inventory policy. The warehouse is looking into minimising its inventory cost and at the same time reducing the fluctuation of the personnel. The chains, independently, are trying to minimise their inventory costs. The warehouse plays the role of a leader in optimising its objectives and, as followers, the two chains try to satisfy their objectives. The problem is formulated into a decentralised nonlinear bilevel programming problem. We also consider the fuzziness of some parameters due to the imprecise available information. We propose the mathematical model and we solve it for our specific case.     

“货到人”拣选系统中AGV路径规划与调度研究

本文在电商行业快速发展及人工智能不断成熟的背景下,对智能仓库中采用“货到人”拣选系统的AGV(Automated Guided Vehicle)调度优化问题进行研究,此问题需同时考虑单AGV的路径规划及多AGV间的碰撞避免。基于此,本文提出了两阶段优化算法,首先分别采用数学模型求解和基于货架优先级的任务分配算法得到AGV的货架搬运任务序列,并根据AGV行驶规则生成初始路径。然后设计碰撞检测及避免算法对可能发生冲突的路径交叉点进行主动避撞调度。当发生突发情况时(如设备故障),采取实时重调度措施进行被动路径调整以获得全局AGV无碰路径。最后基于两阶段算法分析了两种AGV搬运任务分配策略的适用情况,并给出了最优的AGV数量配置建议。实验结果表明,本文算法能够调度100台AGV在配备有2015个货架、10个作业平台的仓库中完成100个订单的拣选作业。本研究可为企业采用“货到人”拣选系统实现多AGV的协同调度提供理论依据和实践指导。     

A mixed integer programming and heuristic algorithm for a warehouses location problem

A warehouses location problem is treated using a mixed integer programming and a heuristic algorithm. A simplification of freight rates schedules, based upon shipments consolidation and a linear regression of rates vs distances was made. Warehousing costs were divided according to fixed and variable and related to the throughput of the warehouses. Consideration was given in the analysis to the choice between owning and leasing each warehouse. In the case studied, the analysis demonstrated that a possible saving of approximately 22 per cent in annual distribution costs could be realized under the optimized warehouse location network.     

Scheduling aerial resource operations for the extinction of large-scale wildfires

The significant increase in large-scale wildfire events in recent decades, caused primarily by climate change, has resulted in a growing number of aerial resources being used in suppression efforts. Present-day management lacks efficient and scalable algorithms for complex aerial resource allocation and scheduling for the extinction of such fires, which is crucial to ensuring safety while maximizing the efficiency of operations. In this work, we present a Mixed Integer Linear Programming (MILP) optimization model tailored to large-scale wildfires for the daily scheduling of aerial operations. The main objective is to achieve a prioritized target water flow over all areas of operation and all time periods. Minimal target completion across individual areas and time periods and total water output are also maximized as secondary and ternary objectives, respectively. An efficient and scalable multi-start heuristic, combining a randomized greedy approach with simulated annealing employing large neighborhood search techniques, is proposed for larger instances. A diverse set of problem instances is generated with varying sizes and extinction strategies to test the approaches. Results indicate that the heuristic can achieve (near)-optimal solutions for smaller instances solvable by the MILP, and gives solutions approaching target water flows for larger problem sizes. The algorithm is parallelizable and has been shown to give promising results in a small number of iterations, making it applicable for both night-before planning and, more time-sensitive, early-morning scheduling.     

ANALYZING GEOGRAPHICALLY DISCRETE WAREHOUSING NETWORKS BY COMPUTER SIMULATION*

This paper describes a comprehensive simulation modeling approach to the problem of locating warehousing facilities in a fashion that minimizes the cost associated with operating a multi-product, multi-source, multi-destination distribution system. The digital simulation model presented in the study is derived within an “industrial dynamics” framework, utilizes input from an existing management information system, and employs a number of relatively simple heuristic procedures to analyze various alternative warehousing networks. Simulation results, in terms of the distribution costs associated with various warehouse locations, are presented for cases involving the effect of provision of a 100% service level, the effect of constraining product availability and/or inventory capacities at various warehouses, and the effect of deleting various warehouses from the existing warehouse network.     

Single cycle policies for the one-warehouse N-retailer inventory/distribution system

We address a multi-echelon inventory system with one-warehouse and N  -retailers. The demand at each retailer is assumed to be known and satisfied by the warehouse. Shortages are not allowed and lead times are negligible. Costs at each facility consist of a fixed charge per order and a holding cost. The goal is to determine single-cycle policies which minimize the average cost per unit time, that is, the sum of the average holding and setup costs per unit time at the retailers and at the warehouse. We propose a O(NlogN)$\mathrm{O}(N\log N)$ heuristic procedure to compute efficient single-cycle policies. This heuristic is compared with other approaches proposed by Schwarz, Graves and Schwarz and Muckstadt and Roundy. We carry out a computational study to test the effectiveness of the heuristic and to compare the performance of the different procedures. From the computational results, it is shown that the new heuristic provides, on average, better single-cycle policies than those given by the Muckstadt and Roundy method.     

考虑人车混采的道路信息采集的路径规划研究

本文考虑了道路信息外业采集的任务要求,人车混采的采集方式以及路网特性等方面,为道路信息采集人员的路径规划建立了满足人车混采约束的整数规划模型;提出了分阶段的转化算法,将其逐步转化为有限时间容量限制的弧路径问题(TCARP)。TCARP问题是一种NP-hard问题,精确求解算法无法在合理时间内得到问题的最优解,因此本文设计了求解TCARP问题的两种快速启发式算法TPS和TUH及其随机化版本;考虑到实际采集问题的大规模特性,在两种快速启发式算法的基础上构造GRASP-PA寻优算法。最后分别结合不同规模的基准算例和实际采集算例证明了本文所构造的算法的有效性。     

A Model for Resource Constrained Production and Inventory Management

We present a general model for multi-item production and inventory management problems that include a resource restriction. The decision variables in the model can take on a variety of interpretations, but will typically represent cycle times, production batch sizes, number of production runs, or order quantities for each item. We consider environments where item demand rates are approximately constant and performing an activity such as producing a batch of a product or placing an order results in the consumption of a scarceresource that is shared among the items. Some examples of shared resources include limited machine capacity, a restriction on the amount of money that can be tied up in stock, orlimited storage capacity. We focus on the case where the decision variables must be integer valued or selected from a discrete set of choices, such as when an integer number of production runs is desired for each item, or in order quantity problems where the items come in pack sizes containing more than one unit and, therefore, the order quantities must be an integer multiple of the pack sizes. We develop a heuristic and a branch and bound algorithm for solving the problem. The branch and bound algorithm includes reoptimization procedures and the heuristic to improve its performance. Computational testing indicates that the algorithms are effective for solving the general model.     

Multi-time scale Markov decision process approach to strategic network growth of reverse supply chains

This paper addresses a complex set of decisions that surround the growth over time of reverse supply chain networks that collect used products for reuse, refurbishment, and/or recycling by processors. The collection network growth problem is decomposed into strategic, tactical and operational problems. This paper focuses on the strategic problem which is to determine how to allocate capital budget resource effectively to grow the network to meet long term collection targets and collection cost constraints. We model the strategic problem as a Markov decision process which can also be posed as multi-time scale Markov decision problem. The recruitment problem in a tactical level appears as a sub-problem for the strategic model. Using dynamic programming, linear programming and Q-Learning approaches, an heuristic is implemented to solve realistically sized problems. A numerical study demonstrates that the heuristic can obtain a good solution for the large-scale problem in reasonable time which is not possible when trying to obtain the optimal solution with the exact DP approach.     

A Heuristic Algorithm for the Capacitated Multiple Supplier Inventory Grouping Problem

This paper presents and solves a model for the multiple supplier inventory grouping problem, which involves the minimization of logistics costs for a firm that has multiple suppliers with capacity limitations. The costs included in the model are purchasing, transportation, ordering, and inventory holding, while the firm's objective is to determine the optimal flows and groups of commodities from each supplier. We present an algorithm, which combines subgradient optimization and a primal heuristic, to quickly solve the multiple supplier inventory grouping problem. Our algorithm is tested extensively on problems of various sizes and structures, and its performance is compared to that of OSL, a state-of-the-art integer programming code. The computational results indicate that our approach is extremely efficient for solving the multiple supplier inventory grouping problem.