A tabu search heuristic for redesigning a multi-echelon supply chain network over a planning horizon

This paper addresses the problem of redesigning a supply chain network with multiple echelons and commodities. The problem belongs to a comprehensive class of network redesign problems previously introduced in the literature. Redesign decisions comprise the relocation of existing facilities to new sites under an available budget over a finite time horizon, the supply of commodities by upstream facilities, the inventory levels at storage facilities, and the flow of commodities through the network. The problem is modeled as a large-scale mixed-integer linear program. Feasible solutions are obtained by using a tabu search procedure that explores the space of the facility location variables. The latter prescribe the time periods in which changes in the network configuration occur. They are triggered by the setup of new facilities, which operate with capacity transferred from the existing facilities, and by closing the latter upon their entire relocation. As the problem is highly constrained, infeasible solutions with excess budget are allowed during the course of the search process. However, such solutions are penalized for their infeasibility. Computational experiments on realistically sized randomly generated instances indicate that this strategic oscillation scheme used in conjunction with tabu search performs very well.     

Algorithm portfolios for logistics optimization considering stochastic demands and mobility allowance

The vehicle routing problem with stochastic demand (VRPSD) is a well known NP-hard problem. The uncharacteristic behaviour associated with the problem enhances the computational efforts required to obtain a feasible and near-optimal solution. This paper proposes an algorithm portfolio methodology based on evolutionary algorithms, which takes into account the stochastic nature of customer demand to solve this computationally complex problem. These problems are well known to have computationally complex objective functions, which make their solutions hard to find, particularly when problem instances of large dimensions are considered. Of particular importance in such situations is the timeliness of the solution. For example, Apple was forced to delay their shipments of iPads internationally due to unprecedented demand and issues with their delivery systems in Samsung Electronics and Seiko Epson. Such examples illustrate the importance of stochastic customer demands and the timing of delivery. Moreover, most of the evolutionary algorithms, known for providing computationally efficient solutions, are unable to always provide optimal or near optimal solutions to all the VRPSD instances within allocated time interval. This is due to the characteristic variations in the computational time taken by evolutionary algorithms for same or varying size of the VRPSD instances. Therefore, this paper presents portfolios of different evolutionary algorithms to reduce the computational time taken to resolve the VRPSD. Moreover, an innovative concept of the mobility allowance (MA) in landmoves based on the levy’s distribution function has been introduced to cope with real situations existing in vehicle routing problems. The proposed portfolio approach has been evaluated for the varying instances of the VRPSD. Four of the existing metaheuristics including Genetic Algorithm (GA), Simulated Annealing (SA), Artificial Immune System (AIS), TABU Search (TS) along with new neighbourhood search, are incorporated in the portfolios. Experiments have been performed on varying dimensions of the VRPSD instances to validate the different properties of the algorithm portfolio. An illustrative example is presented to show that the set of metaheuristics allocated to certain number of processors (i.e. algorithm portfolio) performed better than their individual metaheuristics.     

Economic lot and delivery scheduling problem for multi-stage supply chains

The economic lot and delivery scheduling problem for a multi-stage supply chain comprising multiple items is studied in this paper. It is required to develop a synchronized replenishment strategy, and specify the sequence of production and the replenishment cycle time that achieves synchronization through the supply chain at minimum cost. The problem is presented in a novel formulation based on the quadratic assignment representation. The common cycle time and the integer multipliers policies are adopted to accomplish the desired synchronization. The two policies are represented by nonlinear models handled through a hybrid algorithm. The algorithm combines linearization, outer approximation and Benders decomposition techniques. Results of the two policies demonstrate that a cost reduction up to16.3% can be attained by employing the integer multipliers policy instead of the common cycle time. Computational experiments show the efficiency of the new formulation and solution algorithm by reaching the optimal solution for large problem instances in short time.     

A coevolutionary algorithm for the flexible delivery and pickup problem with time windows

This paper addresses a flexible delivery and pickup problem with time windows (FDPPTW) and formulates the problem into a mixed binary integer programming model in order to minimize the number of vehicles and to minimize the total traveling distance. This problem is shown to be NP-hard. In this study, therefore, a coevolutionary algorithm incorporated with a variant of the cheapest insertion method is developed to speed up the solution procedure. The FDPPTW scheme overcomes the shortcomings of the existing schemes for the delivery and pickup problems. By testing with some revised Solomon's benchmark problems, the computational results have shown the efficiency and the effectiveness of the developed algorithm.     

Interlocking of information systems for international supply and demand chains management

This paper is concerned with coordination aspects of supply chain management and, in particular, investigates setup coordination between two and three stages of a supply chain. The problem arises from a real application in the production chain of a kitchen furniture plant. In different stages of the plant, items are grouped according to different attributes. A setup is required in a stage when the new batch has a different level of attribute from the previous one. Two objectives are considered, i.e., minimizing the total number of setups and minimizing the maximum number of setups of the stages. The problem is to determine a sequence of batches in search for Pareto-optimal solutions with respect to the two objectives. Several metaheuristics, including genetic algorithm, simulated annealing, and iterated local search (ILS) have been proposed for the two-stage problem. In this paper, we develop a constructive heuristic, which combines a least flexibility first principle and a greedy search, for the two- and three-stage problems. Computational results show that the proposed heuristic performs significantly better than the genetic algorithm and simulated annealing. Although the proposed heuristic is inferior to the ILS, which employs two constructive initial solution heuristic, for the two-stage problem, it can be easily extended to the three-stage problem.     

A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling

This paper addresses the multiobjective flexible job shop scheduling problem (MOFJSP) regarding minimizing the makespan, total workload, and maximum workload. The problem is solved in a Pareto manner, whose goal is to seek for the set of Pareto optimal solutions. We propose a multiobjective evolutionary algorithm, which utilizes effective genetic operators and maintains population diversity carefully. A main feature of the proposed algorithm is its simplicity—it needs only two parameters. Performance of our algorithm is compared with seven state-of-the-art algorithms on fifteen popular benchmark instances. Only our algorithm can find 70% or more non-dominated solutions for every instance.     

基于遗传禁忌算法的任务分配与调度的研究

任务分配与调度问题是公认的NP问题,为了合理的对备份任务进行分配与调度,使得最短时间内完成备份任务, 提出了基于遗传禁忌搜索的备份任务调度算法。 重点研究了遗传算法和禁忌搜索算法,并针对二者的不足,提出将其两种算法混合,相互取长补短,仿真实验结果和实例应用表明,笔者提出的算法其搜索效率比单一的遗传算法具有较好的效果。     

基于变邻域搜索算法的物流配送系统集成优化研究

本文针对物流配送系统集成优化问题,考虑取货和送货两种业务的配送情形下仓库和车辆的容量上限约束,构建包括仓库的开放成本、配送成本以及容量溢出成本的非线性混合整数优化模型,设计变邻域搜索启发式算法对模型进行求解。算法通过泰森多边形确定位置上的初始订单分配,再通过扫描半径及消费者数据结构标识实现邻域搜索,改进算法对解决方案进行迭代更新,完成优化求解。最后通过对辽宁宅急送取／送一体化物流配送案例进行数值分析,验证算法可行性和有效性。     

Ship routing problem with berthing time clash avoidance constraints

We consider a ship routing problem in which multiple vessels have to perform pickups and deliveries of cargoes at various locations. The loading and unloading time of cargoes at pickup and delivery locations is significant, and at each of these locations we need to assign a time slot to each vessel to perform the loading/unloading task so as to avoid time clashes. This problem is motivated by the operations of feeder vessels and company-owned cargo terminals, where the shipping company wishes to coordinate the routing and the berthing time of its vessels. We develop a heuristic algorithm for the problem using set partitioning formulation and column generation techniques. The effectiveness of the heuristic is tested via extensive computational experiments.     

An integrated distribution routing model in multi-supply center system

A distribution routing problem with time constraint is one of the important problems in distribution and supply center management. This research is concerned with an integrated distribution routing problem for multi-supply centers based on improved genetic algorithm and graphical user interface (GUI)-type programming. In this research, we proposed a method based on a three-step approach: in step 1 a sector clustering model is developed to transfer the multi-supply center problem to single supply center problems which are easier to be solved; in step 2 we developed a vehicle routing model with time constraints and in step 3 we developed a GA-TSP model which can improve the vehicle routing schedules. The objective of the problem is to minimize the logistic cost for a set of customers without being tardy or exceeding the capacity or travel time of the vehicles. For computational purpose, we developed a GUI-type computer program according to the proposed methods and the sample outputs show that the proposed method is very effective on a set of standard test problems, and it could be potentially useful in solving the distribution routing problems.     

An improved algorithm and solution on an integrated production-inventory model in a three-layer supply chain

Ben-Daya et al. (2010) established a joint economic lot-sizing problem (JELP) for a three-layer supply chain with one supplier, one manufacturer, and multiple retailers, and then proposed a heuristic algorithm to obtain the integral values of four discrete variables in the JELP. In this paper, we first complement some shortcomings in Ben-Daya et al. (2010), and then propose a simpler improved alternative algorithm to obtain the four integral decision variables. The proposed algorithm provides not only less CPU time but also less total cost to operate than the algorithm by Ben-Daya et al. (2010). Furthermore, our proposed algorithm can solve certain problems, which cannot be solved by theirs. Finally, the solution obtained by the proposed algorithm is indeed a global optimal solution in each of all instances tested.     

基于改进遗传算法的模具零件孔群加工路径优化

为提高孔群模具的加工效率,提出了一种最近邻、遗传算法和禁忌搜索相融合的改进遗传算法。采用最近邻算法选取一系列好的初始种群,同时将禁忌搜索中"禁忌"的思想引入到遗传算法中,并在进化过程中随机引入部分新个体,进行迭代搜索。根据孔群加工特点建立了类似旅行商问题的数学模型,并用改进算法求解最短加工路径,在分布复杂的孔类模具上进行数值实验。轮胎实例应用结果表明,改进算法优化后路径长度比CAM系统算法优化后路径长度缩短5.31%,比X向路径法缩短77.88%,比Y向路径法缩短77.63%,比最近邻算法缩短4.52%;当实验参数相同时,改进算法路径长度比遗传算法缩短14.65%,且运行时间平均缩短了63.60%。改进算法的路径长度明显缩短,有效提高了孔群的数控加工效率。其通用性较好,在提升数控系统孔群加工效率方面具有参考价值。     

Multi-objective ant colony optimisation: A meta-heuristic approach to supply chain design

This paper proposes a new approach to determining the Supply Chain (SC) design for a family of products comprising complex hierarchies of subassemblies and components. For a supply chain, there may be multiple suppliers that could supply the same components as well as optional manufacturing plants that could assemble the subassemblies and the products. Each of these options is differentiated by a lead-time and cost. Given all the possible options, the supply chain design problem is to select the options that minimise the total supply chain cost while keeping the total lead-times within required delivery due dates. This work proposes an algorithm based on Pareto Ant Colony Optimisation as an effective meta-heuristic method for solving multi-objective supply chain design problems. An experimental example and a number of variations of the example are used to test the algorithm and the results reported using a number of comparative metrics. Parameters affecting the performance of the algorithm are investigated.     

GAN-MP hybrid heuristic algorithm for non-convex portfolio optimization problem

Abstract

During recent decades, the traditional Markowitz model has been extended for asset cardinality, active share, and tracking-error constraints, which were introduced to overcome the drawbacks of the original Markowitz model. The resulting optimization problems, however, are often very difficult to solve, whereas those of the original Markowitz model are easily solvable. In order to resolve the portfolio optimization problem for the new extensions, we developed a novel heuristic algorithm that combines GAN (Generative Adversarial Networks) with mathematical programming: the GAN-MP hybrid heuristic algorithm. To the best of our knowledge, this is the first attempt to bridge neural networks (NN) and mathematical programming to tackle a real-world portfolio optimization problem. Computational experiments with real-life stock data show that our algorithm significantly outperforms the existing non-linear optimization solvers.     

Inventory service-level optimization within distribution network design problem

We propose a sequential heuristic approach to optimize inventory service levels in a two-stage supply chain. The proposed approach deals with service level and inventory decisions, simultaneously with network design decisions, and incorporating unfulfilled demand costs in a previous inventory-location model. A two-step formulation is considered, where the first step optimizes service level and the second step addresses location and inventory decisions. Each algorithm iteration solves an inventory-location model for a fixed service level, and then the service level is updated in order to reach an equilibrium condition between operating system and unfulfilled demand costs. The algorithm converged in three iterations for a set of sample instances, obtaining the same outcome in comparison with a more intuitive, exact, but more time-consuming search procedure.     

Stochastic single-source capacitated facility location model with service level requirements

A stochastic version of single-source capacitated facility location problem is considered. A set of capacitated facilities is to be selected to provide service to demand points with stochastic demand at the minimal total cost. The facilities have service level requirements modeled by chance constraints. For Poisson demand, the problem is proved equivalent to a known solvable deterministic problem. For Normally distributed demand, it is equivalent to a deterministic mixed integer non-linear programming problem. A hybrid heuristic of Lagrangean relaxation with a single-customer-multi-exchange heuristic is embedded within a branch-and-bound framework to find upper and lower bounds for this problem. From test instances created from benchmark problems (10–20 facilities and 50 demand nodes) and real-life data on the deterministic problem, the gap between the bounds is within 6.5% with an average of 2.5%.     

Order acceptance and scheduling in a two-machine flowshop

We study the order acceptance and scheduling problem in a two-machine flowshop. The firm receives a pool of orders before a planning period, each of which is characterized by revenue, processing times on machines 1 and 2, a due date, and a tardiness penalty. The firm seeks to decide on the orders to accept and schedule the accepted orders so as to maximize the total net revenue. We formulate the problem as mixed-integer linear programming models, and develop a heuristic and a branch-and-bound (B&B) algorithm based on some derived dominance rules and relaxation techniques. We assess the performance of the B&B algorithm and the heuristic via computational experiments. The computational results show that the B&B algorithm can solve problem instances with up to 20 jobs within a reasonable time while the heuristic is efficient in approximately solving large instances of the problem.     

Heuristics for operational fixed job scheduling problems with working and spread time constraints

Operational fixed job scheduling problems select a set of jobs having fixed ready and processing times and schedule the selected jobs on parallel machines so as to maximize the total weight. In this study, we consider working time and spread time constrained versions of the operational fixed job scheduling problems. The working time constraints limit the total processing load on each machine. The spread time constraints limit the time between the start of the first job and the finish of the last job on each machine. For the working time constrained problem, we present a filtered beam search algorithm that evaluates the promising nodes of the branch and bound tree. For the spread time constrained problem we propose a two phase algorithm that defines the promising sets for the first jobs and finds a solution for each promising set. The results of our computational tests reveal that our heuristic algorithms perform very well in terms of both solution quality and time.     

Supply chain scheduling and coordination with dual delivery modes and inventory storage cost

We study a two-echelon supply chain scheduling problem in which a manufacturer acquires supplies from an upstream supplier and processes orders from the downstream retailers. The supply chain sells a single short-life product in a single season. We consider the scenario where the manufacturer can only accept some of the orders from the retailers due to its supplier's common production time window and its own two common production and delivery time windows. The upstream supplier processes materials and delivers the semi-finished products to the manufacturer within its time window. Then the manufacturer further processes these products to produce finished products and delivers them to the retailers within its two time windows, where one window is for production and normal delivery, and the other is for production and express delivery. Having to store the materials before processing them, the supplier incurs a storage cost, which depends on the order size and storage time. The manufacturer pays the transportation cost for delivering the finished products to the retailers. Due to double marginalization, the performance of the supply chain is sub-optimal. We model the supply chain problem as a flow shop scheduling problem with multiple common time windows. We derive some dominance properties and establish some theorems that help solve the sequencing problems for the orders and eliminate the idle time among the orders. Based on these results, we develop fast pseudo-polynomial dynamic algorithms to optimally solve the problem. We prove that the problem is NP-hard in the ordinary sense only. We develop two practically relevant and robust methods for the supply chain to achieve optimal profit-making performance through channel coordination.     

Firm‐Level Monopsony and the Gender Pay Gap

This study uses linked employer–employee data to estimate firm‐by‐gender specific labor supply elasticities. Using a dynamic model of labor supply, I find evidence that females face a greater degree of search frictions than males. However, the majority of the gender gap in labor supply elasticities is driven by across‐firm sorting rather than within‐firm differences. I find that males face a labor supply elasticity 0.15 points higher than females, which leads to 3.3 percent lower earnings for women. Sixty percent of the elasticity differential can be explained by marriage and child penalties faced by women but not men.