Simulation-based multi-objective model for supply chains with disruptions in transportation

Unpredictable disruptions (e.g., accidents, traffic conditions, among others) in supply chains (SCs) motivate the development of decision tools that allow designing resilient routing strategies. The transportation problem, for which a model is proposed in this paper, consists of minimizing the stochastic transportation time and the deterministic freight rate. This paper extends a stochastic multi-objective minimum cost flow (SMMCF) model by proposing a novel simulation-based multi-objective optimization (SimMOpt) solution procedure. A real case study, consisting of the road transportation of perishable agricultural products from Mexico to the United States, is presented and solved using the proposed SMMCF-Continuous/SimMOpt solution framework. In this case study, time variability is caused by the inspection of products at the U.S.-Mexico border ports of entry. The results demonstrate that this framework is effective and overcomes the limitations of the multi-objective stochastic minimum cost flow problem (which becomes intractable for large-scale instances).     

A Multi-Trip Split-Delivery Vehicle Routing Problem with Time Windows for Inventory Replenishment Under Stochastic Travel Times

This study considers a multi-trip split-delivery vehicle routing problem with soft time windows for daily inventory replenishment under stochastic travel times. Considering uncertainty in travel times for vehicle routing problems is beneficial because more robust schedules can be generated and unanticipated consequences can be reduced when schedules are implemented in reality. However, uncertainties in model parameters have rarely been addressed for the problems in this category mainly due to the high problem complexity. In this study, an innovative and practical approach is proposed to consider stochastic travel times in the planning process. In the planning model, the possible outcomes of vehicle arrivals and product delivery at retailers are systematically categorized and their associated penalty and reward are estimated. Thus, unanticipated costs for every scheduling decision can be incorporated into the planning model to generate vehicle routing schedules that are more robust facing uncertain traffic conditions. To solve the model that is characterized as an NP-hard problem in a reasonable amount of time, a two-stage heuristic solution algorithm is proposed. Finally, the stochastic model is compared with the deterministic model in both planning and simulated operation stages using the data of a supply chain in Taiwan. The result confirms that the schedule generated by the stochastic model is more robust than the one created with the deterministic model because undesired outcomes such as unfulfilled demands are greatly reduced.     

Logistical support scheduling under stochastic travel times given an emergency repair work schedule

Stochastic factors during the operational stage could have a significant influence on the planning results of logistical support scheduling for emergency roadway repair work. An optimal plan might therefore lose its optimality when applied in real world operations where stochastic disturbances occur. In this study we employ network flow techniques to construct a logistical support scheduling model under stochastic travel times. The concept of time inconsistency is also proposed for precisely estimating the impact of stochastic disturbances arising from variations in vehicle trip travel times during the planning stage. The objective of the model is to minimize the total operating cost with an unanticipated penalty cost for logistical support under stochastic traveling times in short term operations, based on an emergency repair work schedule, subject to related operating constraints. This model is formulated as a mixed-integer multiple-commodity network flow problem and is characterized as NP-hard. To solve the problem efficiently, a heuristic algorithm, based on problem decomposition and variable fixing techniques, is proposed. A simulation-based evaluation method is also presented to evaluate the schedules obtained using the manual method, the deterministic model and the stochastic model in the operation stage. Computational tests are performed using data from Taiwan’s 1999 Chi-Chi earthquake. The preliminary test results demonstrate the potential usefulness of the proposed stochastic model and solution algorithm in actual practice.     

Variable neighborhood search for the inventory routing and scheduling problem in a supply chain

The inventory, routing and scheduling decisions are three major driving factors for supply chain performance. Since they are related to one another in a supply chain, they should be determined simultaneously to improve the decision quality. In the past, the inventory policy, vehicle routing and vehicle scheduling are determined sequentially and separately. Hence, the total cost (inventory, routing and vehicle costs) would increase. In this paper, an integrated model for the inventory routing and scheduling problem (IRSP) is proposed. Since searching for the optimal solution for this model is a non-polynomial (NP) problem, a metaheuristic, variable neighborhood search (VNS), is proposed. The proposed method was compared with other existing methods. The experimental results indicate that the proposed method is better than other methods in terms of average cost per day.     

间歇生产调度优化模型的分周期逼近算法

间歇生产调度过程中存在许多不确定因素,其中最重要的是需求不确定.考虑需求不确定的多周期间歇生产调度优化模型采用离散或连续时间表达方式,将调度时间域分割成大量与调度决策相关的时间段,导致模型中存在大量整数变量,给模型求解造成很大困难.本研究对已有求解方法进行了分析,提出分周期逼近算法.将多周期间歇生产调度决策问题分解为第一周期调度决策问题和其余周期调度决策问题,简化结构,加快求解速度.通过方案树聚集将表达需求不确定信息的方案树转化成若干方案文件,针对每个方案文件应用确定性方法获得调度决策,但只保留第一周期调度决策,可以减小最小利益方案对期望利益的影响,提高第一周期调度决策水平;获得若干第一周期候选调度决策后,以时间收缩三阶段方法确定其余周期较优调度决策,同时应用时间收缩策略和补偿策略,提高其余周期调度决策水平;最后用期望利益评估第一周期候选调度决策并确定全部周期调度决策.实例研究证明了本文提出的算法能够提高间歇生产调度决策水平,同时加快求解速度,能够有效求解多周期间歇生产调度优化模型.     

Multi-item inventory model of breakable items with stock-dependent demand under stock and time dependent breakability rate

Items made of glass, ceramic, etc. are normally stored in stacks and get damaged during the storage due to the accumulated stress of heaped stock. These items are known as breakable items. Here a multi-item inventory model of breakable items is developed, where demands of the items are stock dependent, breakability rates increase linearly with stock and nonlinearly with time. Due to non-linearity and complexity of the problem, the model is solved numerically and final decisions are made using Genetic Algorithm (GA). In a particular case, model is solved analytically as well as numerically and results are compared. Models are developed with both crisp and uncertain inventory costs. For uncertain inventory costs both fuzzy and stochastic parameters are considered. A chance constrained approach is followed to deal with simultaneous presence of stochastic and fuzzy parameters. Different numerical examples are used to illustrate the problem for different cases.     

Heavy traffic optimal resource allocation algorithms for cloud computing clusters

Cloud computing is emerging as an important platform for business, personal and mobile computing applications. In this paper, we study a stochastic model of cloud computing, where jobs arrive according to a stochastic process and request resources like CPU, memory and storage space. We consider a model where the resource allocation problem can be separated into a routing or load balancing problem and a scheduling problem. We study the join-the-shortest-queue routing and power-of-two-choices routing algorithms with the MaxWeight scheduling algorithm. It was known that these algorithms are throughput optimal. In this paper, we show that these algorithms are queue length optimal in the heavy traffic limit.     

A planning model and solution algorithm for multi-trip split-delivery vehicle routing and scheduling problems with time windows

This study proposes a daily vehicle routing model for minimizing the total cost of replenishing inventory within a supply chain. The first major contribution of this research is to allow multiple use of vehicles in a split delivery vehicle routing problem with time windows (SDVRPTW), which is more realistic for various real-life applications. The multi-trip SDVRPTW (MTSDVRPTW) is formulated using the time–space network technique, which provides greater flexibility for formulating the complicated interactions between vehicles and products when multi-trip, split delivery, and delivery time windows are simultaneously considered. The resulting formulation of the MTSDVRPTW can be categorized as an integer multi-commodity network flow problem with side constraints. A two-step solution algorithm is proposed to solve this NP-hard problem, which is the second major contribution of this research. Finally, a real-world scale numerical example is performed to demonstrate and to test the methodology. The results indicate that these vehicle routing problems can be solved effectively and efficiently and that the proposed methodology has great potential for inventory replenishment scheduling where split deliveries and multiple trips for a single vehicle are allowed and time window constraints are imposed.     

Multi-objective optimization of the maritime cargo routing and scheduling problem

This paper addresses the multi-objective maritime cargo routing and scheduling problem, in which the delivery of bulk products from pickup to delivery ports is served by a heterogeneous fleet of vessels. A mixed integer linear programming (MILP) model is formulated to simultaneously minimize total operation costs, the scheduling makespan, and delays in selected deliveries. The model accounts for several real features, such as time windows, capacity of the vessel's compartments, and ports requirements. A fuzzy weighted max–min method was applied to solve the problem. Two heuristics were developed to effectively handle the complex generated MILP models during the solution process. Experiments were conducted to evaluate the optimization approach using real-life instances provided by a fertilizer company. Finally, a case study shows that the developed model and algorithmic framework are flexible and effective in coping with real problems, incorporating specific business rules from different companies.     

Multiscale production routing in multicommodity supply chains with complex production facilities

In this work, we introduce the multiscale production routing problem (MPRP), which considers the coordination of production, inventory, distribution, and routing decisions in multicommodity supply chains with complex continuous production facilities. We propose an MILP model involving two different time grids. While a detailed mode-based production scheduling model captures all critical operational constraints on the fine time grid, vehicle routing is considered in each time period of the coarse time grid. In order to solve large instances of the MPRP, we propose an iterative MILP-based heuristic approach that solves the MILP model with a restricted set of candidate routes at each iteration and dynamically updates the set of candidate routes for the next iteration. The results of an extensive computational study show that the proposed algorithm finds high-quality solutions in reasonable computation times, and in large instances, it significantly outperforms a standard two-phase heuristic approach and a solution strategy involving a one-time heuristic pre-generation of candidate routes. Similar results are achieved in an industrial case study, which considers a real-world industrial gas supply chain.     

A variable neighborhood search simheuristic for the multiperiod inventory routing problem with stochastic demands

The inventory routing problem (IRP) combines inventory management and delivery route‐planning decisions. This work presents a simheuristic approach that integrates Monte Carlo simulation within a variable neighborhood search (VNS) framework to solve the multiperiod IRP with stochastic customer demands. In this realistic variant of the problem, our goal is to establish the optimal refill policies for each customer–period combination, that is, those individual refill policies that minimize the total expected cost over the periods. This cost is the aggregation of both expected inventory and routing costs. Our simheuristic algorithm allows to consider the inventory changes between periods generated by the realization of the random demands in each period, which have an impact on the quantities to be delivered in the next period and, therefore, on the associated routing plans. A range of computational experiments are carried out in order to illustrate the potential of our simulation–optimization approach.     

The multi-product,economic lot-sizing problem in flow shops: the powers-of-two heuristic

This paper presents a new and efficient heuristic to solve the multi-product, multi-stage, economic lot-sizing problem. The proposed heuristic, called the powers-of-two method, first determines sequencing decisions then lot sizing and scheduling decisions are determined. This method assumes that cycle times are integer multiples of a basic period and restricts these multiples to the powers of two. Once time multiples are chosen, we determine for each basic period of the global cycle the set of products to be produced and the production sequence to be used. Then a non-linear program is solved to simultaneously determine lot sizes and a feasible production schedule. To evaluate its performance, the powers-of-two method was compared to both the common cycle method and a reinforced version of the job-splitting heuristic. Numerical results show that the powers-of-two method outperforms both of these methods.Scope and purposeThe multi-product, multi-stage, economic lot-sizing problem studied in this paper is the problem of making sequencing, lot-sizing and scheduling decisions for several products manufactured through several stages in a flow shop environment so as to minimize the sum of setup and inventory holding costs while a given demand is fulfilled without backlogging. This problem and similar problems are met in many different industries like the food canning industry, the appliance assembly facilities or in beverage bottling companies. The most commonly used approach to deal with this problem is the common cycle approach where a lot of each product is produced each cycle. A few other approaches are also proposed. In this paper we propose a new and more efficient solution approach that assigns different cycle times to different products.     

A heuristic to solve the synchronized log-truck scheduling problem

We present a synchronized routing and scheduling problem that arises in the forest industry, as a variation of the log-truck scheduling problem. It combines routing and scheduling of trucks with specific constraints related to the Canadian forestry context. This problem includes aspects such as pick-up and delivery, multiple products, inventory stock, multiple supply points and multiple demand points. We developed a decomposition approach to solve the weekly problem in two phases. In the first phase we use a MIP solver to solve a tactical model that determines the destinations of full truckloads from forest areas to woodmills. In the second phase, we make use of two different methods to route and schedule the daily transportation of logs: the first one consists in using a constraint-based local search approach while the second one is a hybrid approach involving a constraint programming based model and a constraint-based local search model. These approaches have been implemented using COMET2.0. The method, was tested on two industrial cases from forest companies in Canada.     

A solution approach for log truck scheduling based on composite pricing and branch and bound

The logging truck scheduling problem is one of the most complex routing problems where both pick‐up and delivery operations are included. It consists in finding one feasible route for each vehicle in order to satisfy the demands of the customers and in such a way that the total transport cost is minimized. We use a mathematical formulation of the log truck scheduling problem where each column represents a feasible route. We generate a large pool of columns based on solving a transportation problem. Then we apply a composite pricing algorithm, which mainly consists of pricing the pool of columns and maintain an active set of these, for solving the LP relaxed model. A branch and price approach is used to obtain integer solutions in which we apply composite pricing to generate new columns. Numerical results from case studies at Swedish forestry companies are presented.     

Direct shipping logistic planning for a hub-and-spoke network with given discrete intershipment times

This paper proposes a heuristic procedure to solve the problem of scheduling and routing shipments in a hybrid hub‐and‐spoke network, when a given set of feasible discrete intershipment times is given. The heuristic procedure may be used to assist in the cooperative operational planning of a physical goods network between shippers and logistics service provider, or to assist shippers in making logistics outsourcing decisions. The objective is to minimise the transportation and inventory holding costs. It is shown through a set of problem instances that this heuristic procedure provides better solutions than existing economic order quantity‐based approaches. Computational results are presented and discussed.     

Adaptive Park-and-ride Choice on Time-dependent Stochastic Multimodal Transportation Network

In transportation networks with stochastic and dynamic travel times, park-and-ride decisions are often made adaptively considering the realized state of traffic. That is, users continue driving towards their destination if the congestion level is low, but may consider taking transit when the congestion level is high. This adaptive behavior determines whether and where people park-and-ride. We propose to use a Markov decision process to model the problem of commuters’ adaptive park-and-ride choice behavior in a transportation network with time-dependent and stochastic link travel times. The model evaluates a routing policy by minimizing the expected cost of travel that leverages the online information about the travel time on outgoing links in making park-and-ride decisions. We provide a case study of park-and-ride facilities located on freeway I-394 in Twin Cities, Minnesota. The results show a significant improvement in the travel time by the use of park-and-ride during congested conditions. It also reveals the time of departure, the state of the traffic, and the location from where park-and-ride becomes an attractive option to the commuters. Finally, we show the benefit of using online routing in comparison to an offline routing algorithm.

     

A heuristic method for the inventory routing and pricing problem in a supply chain

The inventory routing problem (IRP) in a supply chain (SC) is to determine delivery routes from suppliers to some geographically dispersed retailers and inventory policy for retailers. In the past, the pricing and demand decisions seem ignored and assumed known in most IRP researches. Since the pricing decision affects the demand decision and then both inventory and routing decisions, it should be considered in the IRP simultaneously to achieve the objective of maximal profit in the supply chain. In this paper, a mathematical model for the inventory routing and pricing problem (IRPP) is proposed. Since the solution for this model is an NP (non-polynomial) problem, a heuristic method, tabu search adopting different neighborhood search approaches, is used to obtain the optimal solution. The proposed heuristic method was compared with two other methods considering the IRPP separately. The experimental results indicate that the proposed method is better than the two other methods in terms of average profit.     

Dynamic routing strategies for JIT production in hybrid flow shops

In production processes, just-in-time (JIT) completion of jobs helps reduce both the inventory and late delivery of finished products. Previous research which aims to achieve JIT job completion mainly worked on static scheduling problems, in which all jobs are available from time zero or the available time of each job is known beforehand. In contrast, dynamic scheduling problems which involve continual arrival of new jobs are not much researched and dispatching rules remain the most frequently used method for such problems. However, dispatching rules are not high-performing for the JIT objective. This study proposes several routing strategies which can help dispatching rules realize JIT completion for jobs arriving dynamically in hybrid flow shops. The routing strategies are based on distributed computing which makes realtime forecast of completion times of unfinished jobs. The advantages include short computing time, quick response and robustness against disturbance. Computer simulations show that the performance of dispatching rules combined with the proposed routing strategies is significantly higher than that of dispatching rules only and that of dispatching rules combined with the previous routing methods.     

Migrating the fair share algorithm from a distribution to a production planning environment

This paper investigates the ability to migrate the fair share algorithm from a distribution to a production planning environment. In a semi-process-based production system, such as that of the photographic film producer Agfa, the availability of the intermediate product is then the limiting constraint steering the fair share algorithm for the end-product lotsizing decision process. The manufacturing model of Agfa is typically semi-process, where a first stage produces a limited number of intermediate products. The second stage is flow oriented and converts the intermediates into many distinct end-products. The planning method currently implemented within Agfa is a two-level scheduling approach. First, it establishes a cyclical volume plan at the intermediate product level, which is then used as an input constraint for the secondary problem of determining end-product lotsizes. As an alternative to the traditional model, where the end-product lotsizes are determined based on the standard EOQ formula, this investigation suggests the end-product mix decisions to be governed by a tuned fair share algorithm. The paper discusses this algorithm with its parameter settings, the impact on stock values, on service levels, and on set-up and inventory holding costs. The results of both algorithms are compared. This investigation proves that the combination of a cyclical volume plan, at the intermediate product level, combined with fair share mix decisions for the end-product lotsizes, delivers the needed service level with lower inventory levels and reduced operational costs. The main benefit of the model integrating volume planning and mix decisions is its ability to reduce demand amplifications, prohibiting market demand nervousness (amplified by the Forrester effect) from entering into upstream operations. The reduced nervousness allows a major reduction in needed safety stock at the intermediate product level.     

An artificial immune system heuristic for two-stage multi-machine assembly scheduling problem to minimize total completion time

We address the two-stage multi-machine assembly scheduling problem. The first stage consists of m independently working machines where each machine produces its own component. The second stage consists of two independent and identical assembly machines. The objective is to come up with a schedule that minimizes total or mean completion time for all jobs. The problem has been addressed in the scheduling literature and several heuristics have been proposed. In this paper, we propose a new heuristic called artificial immune system (AIS). We conduct experimental analysis for comparing the newly proposed heuristic AIS with the best known heuristic in the literature. Experimental results show that our proposed heuristic AIS performs better than the best known existing heuristic. More specifically, our new heuristic AIS reduces the error of the best known heuristic by 60% while the computational times of both AIS and the best known heuristic are almost the same.