Sequential Monte Carlo in reachability heuristics for probabilistic planning

Some of the current best conformant probabilistic planners focus on finding a fixed length plan with maximal probability. While these approaches can find optimal solutions, they often do not scale for large problems or plan lengths. As has been shown in classical planning, heuristic search outperforms bounded length search (especially when an appropriate plan length is not given a priori). The problem with applying heuristic search in probabilistic planning is that effective heuristics are as yet lacking.In this work, we apply heuristic search to conformant probabilistic planning by adapting planning graph heuristics developed for non-deterministic planning. We evaluate a straight-forward application of these planning graph techniques, which amounts to exactly computing a distribution over many relaxed planning graphs (one planning graph for each joint outcome of uncertain actions at each time step). Computing this distribution is costly, so we apply Sequential Monte Carlo (SMC) to approximate it. One important issue that we explore in this work is how to automatically determine the number of samples required for effective heuristic computation. We empirically demonstrate on several domains how our efficient, but sometimes suboptimal, approach enables our planner to solve much larger problems than an existing optimal bounded length probabilistic planner and still find reasonable quality solutions.     

Incorporating lateral transfers of vehicles and inventory into an integrated replenishment and routing plan for a three-echelon supply chain

This paper focuses on developing an integrated replenishment and routing plan that takes into account lateral transfers of both vehicles and inventory for a three-echelon supply chain system including a single plant, multiple distribution centers and multiple retailers. A mixed integer programming model to the overall system is formulated first, and then an optimization-based heuristic consisting of three major components is proposed. The purpose of the first component is to assign retailers to distribution centers, and determine routing schedules for each distribution center. And the remaining two components are corresponding to two smaller optimization models – a variant of the classical transportation problem modeled for determining vehicle transfer between distribution centers, and a variant of the conventional minimum cost network flow problem modeled for determining inventory replenishment and transfer. Experimental results reveal that the proposed algorithm is rather computational effectiveness, and the pooling strategy that considers both vehicles and inventory transfers is a worthy option in designing supply chain operations.     

Lot-sizing heuristics for continuous time-varying demand and shortages

In this paper we propose two heuristic procedures for the inventory lot-sizing problem with continuous time-varying demands and shortages. The first heuristic is an extension of the Silver-Meal solution method to general continuous demands. The key idea of the second heuristic is to balance the sum of the holding and backorder costs over each replenishment cycle with the ordering cost. In the case of linearly time-varying demand, the two heuristics procedures are evaluated according to three measures of cost performance and two measures of computation efficiency over 10000 test problems. The results revealed that the modified least-cost approach is generally more effective than the generalized Silver-Meal. It generated comparable cost performance in problems with shortages and a superior cost advantage in problems with infinite shortage cost. Moreover, both heuristics are faster than the exact procedure in execution.     

A scheduling algorithm based on the singular value decomposition heuristic method in a distributed manufacturing system

Because distributed manufacturing technology is the foundation of modernized production and traditional heuristic methods exhibit problems of high complexity and low efficiency, this paper designs a scheduling algorithm based on the singular value decomposition heuristic (SVDH) method. The algorithm uses the device distribution and the transportation relationship between devices in a distributed manufacturing system. The algorithm takes the sequence relationship between tasks and the distance between devices as the implicit relationship between the task and the device. The algorithm makes use of the implicit relationship to amend the processing time matrix of the task and corrects the processing time matrix that contains the transportation relationship. Singular value decomposition principal component analysis is performed on the corrected processing time to find the most suitable processing device for each process, and an initial solution matrix is established. The heuristic solution is used to optimize the initial solution to find the optimal scheduling result based on the initial solution matrix. The establishment of the initial solution can effectively reduce the computational complexity of the heuristic solution, realize a parallelizing solution, and improve the efficiency of the heuristic solutions. In addition, the SVDH scheduling result has a lower transfer time between devices due to the consideration of the topology of tasks and devices, that is, the transit time. In this paper, the experiments are conducted on the heuristic performance, scheduling results, and transportation time. The experimental results show the advantages of SVDH over general heuristic algorithms in terms of efficiency and transit time.     

Adaptive selection of heuristics for assigning time slots and rooms in exam timetables

This paper presents an iterative adaptive approach which hybridises bin packing heuristics to assign exams to time slots and rooms. The approach combines a graph-colouring heuristic, to select an exam in every iteration, with bin-packing heuristics to automate the process of time slot and room allocation for exam timetabling problems. We start by analysing the quality of the solutions obtained by using one heuristic at a time. Depending on the individual performance of each heuristic, a random iterative hyper-heuristic is used to randomly hybridise the heuristics and produce a collection of heuristic sequences to construct solutions with different quality. Based on these sequences, we analyse the way in which the bin packing heuristics are automatically hybridised. It is observed that the performance of the heuristics used varies depending on the problem. Based on these observations, an iterative hybrid approach is developed to adaptively choose and hybridise the heuristics during solution construction. The overall aim here is to automate the heuristic design process, which draws upon an emerging research theme which is concerned with developing methods to design and adapt heuristics automatically. The approach is tested on the exam timetabling track of the second International Timetabling Competition, to evaluate its ability to generalise on instances with different features. The hyper-heuristic with low-level graph-colouring and bin-packing heuristics approach was found to generalise well over all the problem instances and performed comparably to the state of the art approaches.     

Developing a multi-objective,multi-item inventory model and three algorithms for its solution

We develop a multi-objective model in a multi-product inventory system.The proposed model is a joint replenishment problem(JRP) that has two objective functions.The first one is minimization of total ordering and inventory holding costs,which is the same objective function as the classic JRP.To increase the applicability of the proposed model,we suppose that transportation cost is independent of time,is not a part of holding cost,and is calculated based on the maximum of stored inventory,as is the case in many real inventory problems.Thus,the second objective function is minimization of total transportation cost.To solve this problem three efficient algorithms are proposed.First,the RAND algorithm,called the best heuristic algorithm for solving the JRP,is modified to be applicable for the proposed problem.A multi-objective genetic algorithm(MOGA) is developed as the second algorithm to solve the problem.Finally,the model is solved by a new algorithm that is a combination of the RAND algorithm and MOGA.The performances of these algorithms are then compared with those of the previous approaches and with each other,and the findings imply their ability in finding Pareto optimal solutions to 3200 randomly produced problems.     

Mixed integer programming in production planning with backlogging and setup carryover: modeling and algorithms

This paper proposes a mixed integer programming formulation for modeling the capacitated multi-level lot sizing problem with both backlogging and setup carryover. Based on the model formulation, a progressive time-oriented decomposition heuristic framework is then proposed, where improvement and construction heuristics are effectively combined, therefore efficiently avoiding the weaknesses associated with the one-time decisions made by other classical time-oriented decomposition algorithms. Computational results show that the proposed optimization framework provides competitive solutions within a reasonable time.     

供应链订单分配优化模型及其模拟退火算法

受4M1E(人、机、料、法、环)因素的随机波动影响,产品的制造过程通常是不完美的,从而产生不良产品.针对已有研究多忽略不良产品的特点,建立了更加符合实际需求的订单分配多目标混合整数规划模型,其优化目标为最小化交易成本、采购成本、不良产品数量、产品延迟交付数量,以及最大化供应商信誉评价.考虑到模型求解的复杂度,设计了一种模拟退火算法,并结合启发式规则避免了大量非法初始解与邻点解的出现.实验算例表明所建立的模型能够反映订单分配过程中的产品缺陷现象,其算法能够在允许的运算时间内获得稳定的满意解,并且随着算例规模的增大,其计算时间与优化结果均优于LINGO软件.     

A quadra-directional decomposition heuristic for a two-dimensional,non-equidistant machine-cell location problem

After the development of numerous cell formation techniques, machine-cell location (MCL) problems have been the focus of many researchers in cellular manufacturing systems. With the cost cutting strategy, locating machines within the cell itself has not only been the major concern of management, but also the location of cells with respect to each other on a spatial coordinate system to minimize the transportation cost or job movement costs. For lack of being able to solve a large problem optimally, a number of heuristics have been developed for one-dimensional machine and MCL problems. The problem still exists for locating machine-cells on spatial coordinates, which has been addressed in this research. The location coordinates have been decomposed into four movements, backward, forward, upward and downward; and the MCL problem is formulated as a linear combination of these four decomposed (partitioned) objective functions subject to other boundary conditions. A quadra-directional decomposition heuristic (QDDH) is developed to find a sub-optimal solution to the MCL problem. The decomposition procedure for four objective functions is presented and the performance of the heuristic is tested on a set of well-known data. Empirical tests show that the solution procedure produces efficient, good quality solutions for different sizes of the problem instances.     

A heuristic for the vehicle routing problem with due times

This paper studies the vehicle routing problem with due times. The vehicles are supposed to visit customers within the due times, and a penalty cost is imposed in case the vehicle arrives past the due times. The objective is to minimize the weighted sum of the traveling time of vehicles and the tardiness of the service customers receive. A mixed integer programming formulation and a heuristic based on the tabu search for a practical use are suggested. Route-perturb and route-improvement method for the neighborhood generation is proposed. Performances are compared with other heuristics appeared in the literature using the bench-mark data set modified to be fit to the model. It is shown that the suggested heuristic gives a good solution in a short computation time.     

Improved Tabu search heuristics for the dynamic space allocation problem

The dynamic space allocation problem (DSAP) presented in this paper considers the task of assigning items (resources) to locations during a multi-period planning horizon such that the cost of rearranging the items is minimized. Three tabu search heuristics are presented for this problem. The first heuristic is a simple basic tabu search heuristic. The second heuristic adds diversification and intensification strategies to the first, and the third heuristic is a probabilistic tabu search heuristic. To test the performances of the heuristics, a set of test problems from the literature is used in the analysis. The results show that the tabu search heuristics are efficient techniques for solving the DSAP. More importantly, the proposed tabu search heuristic with diversification/intensification strategies found new best solutions using less computation time for one-half of all the test problems.     

Analysis of the maximum level policy in a production-distribution system

We consider a production-distribution system, where a facility produces one commodity which is distributed to a set of retailers by a fleet of vehicles. Each retailer defines a maximum level of the inventory. The production policy, the retailers replenishment policies and the transportation policy have to be determined so as to minimize the total system cost. The overall cost is composed by fixed and variable production costs at the facility, inventory costs at both facility and retailers and routing costs. We study two different types of replenishment policies. The well-known order-up to level (OU) policy, where the quantity shipped to each retailer is such that the level of its inventory reaches the maximum level, and the maximum level (ML) policy, where the quantity shipped to each retailer is such that the inventory is not greater than the maximum level. We first show that when the transportation is outsourced, the problem with OU policy is NP-hard, whereas there exists a class of instances where the problem with ML policy can be solved in polynomial time. We also show the worst-case performance of the OU policy with respect to the more flexible ML policy. Then, we focus on the ML policy and the design of a hybrid heuristic. We also present an exact algorithm for the solution of the problem with one vehicle. Results of computational experiments carried out on small size instances show that the heuristic can produce high quality solutions in a very short amount of time. Results obtained on a large set of randomly generated problem instances are also shown, aimed at comparing the two policies.     

A sensitivity analysis of solving joint replenishment problems using the RAND method under inaccurate holding cost estimates and demand forecasts

This paper presents a study of solving the joint replenishment problem (JRP) by using the RAND method, a heuristic approach that has been proven to find almost as good as optimal solutions, under uncertain customer demands and inaccurate unit holding cost estimation. The classical JRP deals with the issue of determining a replenishment policy that minimizes the total cost of replenishing multiple products from a single supplier. The total cost considered in the JRP consists of a major ordering cost independent of the number of items in the order, a minor ordering cost depending on the items in the order, and the holding cost. There have been many heuristic approaches proposed for solving the JRP. Most of the research work was done under the assumptions that the demand for each item type and the unit holding cost are known and constant. However, in the real world accurately forecasting customer demands and precisely estimating the unit holding cost are both difficult. Besides, the real values of the demands and the unit holding cost may change over the replenishment horizon. The present study addresses the issue of the uncertain demands and the unit holding cost to the JRP and investigates how misestimates of these demands and holding costs may influence the replenishment policy as determined by the famous JRP heuristic, the RAND method.     

Solution approaches for facility location of medical supplies for large-scale emergencies

In this paper, we propose models and solution approaches for determining the facility locations of medical supplies in response to large-scale emergencies. We address the demand uncertainty and medical supply insufficiency by providing each demand point with services from a multiple quantity of facilities that are located at different quality levels (distances). The problem is formulated as a maximal covering problem with multiple facility quantity-of-coverage and quality-of-coverage requirements. Three heuristics are developed to solve the location problem: a genetic algorithm heuristic, a locate–allocate heuristic, and a Lagrangean relaxation heuristic. We evaluate the performance of the model and the heuristics by using illustrative emergency examples. We show that the model provides an effective method to address uncertainties with little added cost in demand point coverage. We also show that the heuristics are able to generate good facility location solutions in an efficient manner. Moreover, we give suggestions on how to select the most appropriate heuristic to solve different location problem instances.     

Heuristics for tactical time slot management: a periodic vehicle routing problem view

In this study, we consider a tactical problem where a time slot schedule for delivery service over a given planning horizon must be selected in each zone of a geographical area. A heuristic search evaluates each schedule selection by constructing a corresponding tactical routing plan of minimum cost based on demand and service time estimates. At the end, the schedule selection leading to the best tactical routing plan is selected. The latter can then be used as a blueprint when addressing the operational problem (i.e., when real customer orders are received and operational routes are constructed). We propose two heuristics to address the tactical problem. The first heuristic is a three‐phase approach: a periodic vehicle routing problem (PVRP) is first solved, followed by a repair phase and a final improvement phase where a vehicle routing problem (VRP) with time windows is solved for each period of the planning horizon. The second heuristic tackles the problem as a whole by directly solving a PVRP with time windows. Computational results compare the two heuristics under various settings, based on instances derived from benchmark instances for the VRP with time windows.     

轴辐式网络下多重时效要求的车辆调度问题

公路运输在多式联运中发挥着不可替代的重要作用,车辆调度问题日益成为制约公路运输质量和效率的主要因素之一。针对零担快运和快递干线运输的特点,考虑车辆容量限制和节点任务的多重时效性约束,建立了轴辐式网络下的车辆调度模型,设计了基于启发式调度规则的节约算法进行求解。通过中国邮政广州邮区的运营数据进行算例分析,计算结果表明,显著提高了车辆有效使用效率和运营成本,验证了模型和算法的有效性。最后分析了网络辐射范围对运输效率和经济性的影响及车辆有效使用效率与期望工时之间的关系,为公路干线运输车辆调度提供决策支持。     

Solving fuzzy capacitated location routing problem using hybrid variable neighborhood search and evolutionary local search

A fuzzy capacitated location routing problem (FCLRP) is solved by using a heuristic method that combines variable neighborhood search (VNS) and evolutionary local search (ELS). Demands of the customer and travel times between customers and depots are considered as fuzzy and deterministic variables, respectively in FCLRP. Heterogeneous and homogeneous fleet sizes are performed together to reach the least multi-objective cost in a case study. The multi-objective cost consists of transportation cost, additional cost, vehicle waiting cost and delay cost. A fuzzy chance constrained programming model is added by using credibility theory. The proposed method reaches the solution by performing four stages. In the first stage, initial solutions are obtained by using a greedy heuristic method, and then VNS heuristic, which consists of seven different neighborhood structures, is performed to improve the solution quality in the second stage. In the third stage, a perturbation procedure is applied to the improved solution using ELS algorithm, and then VNS heuristic is applied again in the last stage. The combination of VNS and ELS is called VNSxELS algorithm and applied to a case study, which has fifty-seven customers and five distributing points, effectively in a reasonable time.     

Flow shops with WIP and value added costs

A new deterministic flow shop problem is studied where the objective is to minimize the total WIP (work-in-process) cost. Based on a value added model, the unit time WIP cost increases as a job passes through various stages in the production process. The recognition version is unary NP-Complete even for two machines. Several simple and intuitive heuristics are presented. For each heuristic, we determine asymptotically attainable upper bounds on the relative error. Finally, the heuristics are empirically evaluated.     

Determination of the locations and capacities of sugar cane loading stations in Thailand

In this paper, we address the problem of the location of sugar cane loading stations in Thailand. A loading station is a facility for collecting cane from small farmers; the cane is then transported to a sugar mill by a large truck. An improperly located loading station can result in high investment and transportation costs in the sugar industry. A mathematical model and a heuristic algorithm were developed to determine the suitable capacity of existing loading stations, the locations and capacities of new loading stations and the allocations of cane field harvests to each loading station. The model accounted for variations in the cane yield of each field during the harvesting periods and between crop years. The objective function was the minimization of the associated costs, including the investment costs, the transportation costs and the cost of the cane yield loss if the cane is not harvested at an optimal time. The performance of the developed heuristics was assessed under various scenarios. The results were shown to deviate slightly from the solution to the mathematical model. The sensitivities of the solutions under variations of the transportation cost, yield loss cost and investment costs were studied. The model was also applied to an industrial case study. A relevant and accurate solution was obtained.     

Scheduling the vehicles of bus rapid transit systems: a case study

Bus rapid transit (BRT) is a cost-efficient, traffic-free bus-based transportation system competing with subways. There are 205 municipalities around the world that implemented their own BRT systems. Istanbul, having the sixth-most congested traffic in the world, built its own BRT system (Metrobüs), which serves more than 830,000 people (6.45% of all public transportation usage) in a day with 6254 trips covered by its current fleet of 496 vehicles. In this study, we model the vehicle scheduling problem of Metrobüs as a multiple depot vehicle scheduling problem. The model aims to minimize the fleet size and total deadhead kilometers while covering all timetabled trips. We propose a new heuristic, trips merger (TM), to solve the model and show that there exists cost reduction opportunities in terms of both fleet size and deadhead kilometers. The proposed heuristic is a member of the state-space reduction heuristics family, which first reduces the problem size, then solves the reduced problem. Computational study reveals that TM performed better than the existing state-space reduction heuristics for the Metrobüs case.