Simultaneous evacuation and entrance planning in complex building based on dynamic network flows

This paper presents mathematical models and a heuristic algorithm that address a simultaneous evacuation and entrance planning. For the simultaneous evacuation and entrance planning, four types of mathematical models based on the discrete time dynamic network flow model are developed to provide the optimal routes for evacuees and responders within a critical timeframe. The optimal routes obtained by the mathematical models can minimize the densification of evacuees and responders into specific areas. However, the mathematical model has a weakness in terms of long computation time for the large-size problem. To overcome the limitation, we developed a heuristic algorithm. We also analyzed the characteristics of each model and the heuristic algorithm by conducting case studies. This study pioneers area related to evacuation planning by developing and analyzing four types of mathematical models and a heuristic algorithm which take into account simultaneous evacuation and entrance planning.     

Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.     

Experiments in mixed-integer linear programming using pseudo-costs

This paper discusses heuristic branch and bound methods for solving mixed integer linear programming problems. The research presented on here is the follow on to that recorded in [3].After a resumé of the concept of pseudo-costs and estimations, new heuristic rules for generating a tree which make use of pseudo-costs and estimations are presented. Experiments have shown that models having a low percentage of integer variables behave in a radically different way from models with a high percentage of integer variables. The new heuristic rules seem to apply generally to the first type of model.Later, other heuristic rules are presented that are used with models having a high percentage of integer variables and with models having a special structure (models including special ordered sets.)The rules introduced here have been implemented in the IBM Mathematical Programming System Extended/370. They are used to solve large mixed integer linear programming models.Numerical results that permit comparisons to be made among the different rules are provided and discussed.     

Experimental investigation of real-time scheduling in flexible manufacturing systems

This paper presents a new two-phase (TP) approximate method for real-time scheduling in a flexible manufacturing system (FMS). This method combines a reduced enumeration schedule generation algorithm with a 0–1 optimization algorithm. In order to make the combined algorithm practicable, heuristic rules are introduced for the selection of jobs to be scheduled. The relative performance of the TP method vis-a-vis conventional heuristic dispatching rules such as SPT, LPT, FCFS, MWKR, and LWKR is investigated using combined process-interaction/discrete-event simulation models. An efficient experimental procedure is designed and implemented using these models, and the statistical analysis of the results is presented. For the particular case investigated, the conclusions are very encouraging. In terms of mean flow time, the TP method performs significantly better than any other tested heuristic dispatching rules. Also, the experimental results show that using global information significantly improves the FMS performance.     

A note on “Location of hubs in a competitive environment”

This note suggests modifications to two models for locating hubs in a competitive environment introduced by Marianov et al. [European Journal of Operational Research 114 (1999) 363–371]. They make it possible to provide optimal solutions much faster. It is also shown that the implementation of the heuristic proposed by Marianov et al. contains a flaw. Yet the heuristic itself is correct.     

Multiple Container Packing: A Case Study of Pipe Packing

While the problem of packing single containers and pallets has been thoroughly investigated very little attention has been given to the efficient packing of multiple container loads. Normally in practice a multiple container load is packed by a single container algorithm used in a greedy fashion. This paper introduces the issues involved in multiple container loading. It lays out three different strategies for solving the problem: sequential packing using a single container heuristic, pre-allocating items to the containers and choosing container loads using simultaneous packing models. The principal simultaneous models are pattern selection IP models. We present an application of packing pipes in shipping containers using two pattern selection IP models, a pattern selection heuristic, a sequential greedy algorithm and a pre-allocation method. The experimental results use randomly generated data sets. We discuss several useful insights into the methods and show that for this application the pattern selection methods perform best.     

An index heuristic for transshipment decisions in multi-location inventory systems based on a pairwise decomposition

In multi-location inventory systems, transshipments are often used to improve customer service and reduce cost. Determining optimal transshipment policies for such systems involves a complex optimisation problem that is only tractable for systems with few locations. Consequently simple heuristic transshipment policies are often applied in practice. This paper develops an approximate solution method which applies decomposition to reduce a Markov decision process model of a multi-location inventory system into a number of models involving only two locations. The value functions from the subproblems are used to estimate the fair charge for the inventory provided in a transshipment. This estimate of the fair charge is used as the decision criterion in a heuristic transshipment policy for the multi-location system. A numerical study shows that the proposed heuristic can deliver considerable cost savings compared to the simple heuristics often used in practice.     

Increasing the operational efficiency of container terminals in Australia

This paper discusses the major factors influencing the transfer efficiency of rail container terminals, as measured by the throughput time of containers. An analytically based simulation model is designed to describe container progress in the system. Cyclic heuristic rules for equipment assignment are applied and a new heuristic rule is developed to dispatch trains to tracks. The simulation model combined with the heuristic rules is used to address a number of specific objectives of the study. Different performance measures are applied and the impact that the train-to-track despatching and the handling equipment assignment can have on the measures is established. Validation and testing of models make use of data from Acacia Ridge Terminal, Brisbane, Australia.     

Dynamic scheduling to minimize lost sales subject to set-up costs

We consider scheduling a shared server in a two-class, make-to-stock, closed queueing network. We include server switching costs and lost sales costs (equivalently, server starvation penalties) for lost jobs. If the switching costs are zero, the optimal policy has a monotonic threshold type of switching curve provided that the service times are identical. For completely symmetric systems without set-ups, it is optimal to serve the longer queue. Using simple analytical models as approximations, we derive a heuristic scheduling policy. Numerical results demonstrate the effectiveness of our heuristic, which is typically within 10% of optimal. We also develop and test a heuristic policy for a model in which the shared resource is part of a series network under a CONWIP release policy. This revised version was published online in June 2006 with corrections to the Cover Date.     

基于双重视角的MPPSP及其禁忌搜索启发式算法

首先界定研究假设条件并定义文中所使用的符号;随后从业主及承包商双重视角构建MPPSP的整数规划优化模型;针对问题的强NP-hard属性,设计禁忌搜索启发式算法;在随机生成的标准算例集合上对算法进行测试;最后用一个算例对研究结果进行说明。结论如下:本文所开发的禁忌搜索启发式算法可以有效地求解MPPSP;关于给定项目的支付进度安排,承包商和业主的偏好存在显著差异;随着支付次数与支付比例的增加,承包商收益提高,业主收益下降,而双方收益均随折现率的上升而下降。     

A new model and solution method for product line design with pricing

Existing customer preference based product design models do not consider product prices and consumer budgets. These models assume that a purchase is based only on the satisfaction obtained from the product, irrespective of the product price and customer budget. However, when products are expensive relative to buyers' budgets, the effect of prices and budgets must be considered in addition to customer satisfaction. Most current models, moreover, assume that a low preference for one product characteristic is compensated by high preference for another, which may not hold for unacceptable levels of characteristics. For such products, we incorporate prices, budget constraints, and minimum acceptable thresholds in our model. To solve the model we develop a highly accurate, robust and efficient Beam Search (BS) based heuristic that identifies optimal or near optimal product lines. The heuristic is tested on 300 simulated problems and an application. It is also compared to a Genetic Algorithms (GA) based heuristic. We found that our heuristic worked better than the GA heuristic in identifying optimal and near optimal solutions quickly. We also give detailed examples that illustrate the heuristic and demonstrate a pricing analysis application of the model.     

Optimal Web site reorganization considering information overload and search depth

Adaptive Web sites have been extensively studied as the Internet and Web sites continuously grow. Based on Web usage mining, most of these studies focus on providing assistance to users instead of optimizing the Web site itself. This study proposes 0–1 programming models for reorganizing Web sites based on the cohesion between Web pages obtained by Web usage mining. Additionally, the proposed models reduce the information overload and search depth for users surfing in the Web site. Additionally, a heuristic approach was proposed to reduce the required computation time. The proposed models were verified and extensively tested with numerical examples.     

Strategic timetable scheduling for last trains in urban railway transit networks

Well-designed timetables, with appropriate coordination between the last feeder trains and the last connecting trains so that passengers can enjoy “smooth” transfers, are desired by passengers and are a major service goal of metro corporations. This paper addresses the strategically last train scheduling problem in urban railway transit networks. First, two practical optimization models for last trains are proposed to minimize the standard deviation of transfer redundant times and to balance the last train transfers in subway networks. Second, we design a new heuristic algorithm to solve the developed models. Finally, the models and the heuristic are applied to the Beijing subway network. The results show that the last train timetables for the Beijing subway network have been improved by increasing the average travelling speed and the average technical speed by 9.9% and 8.42%, respectively. This means that the last train passengers can save 97.4 min in total in the Beijing subway network when riding last trains.     

A branch-and-bound based solution approach for the mixed-model assembly line-balancing problem for minimizing stations and task duplication costs

A common assumption in the literature on mixed-model assembly line balancing is that a task that is common to multiple models must be assigned to a single station. In this paper, we relax this restriction, and allow a common task to be assigned to different stations for different models. We seek to minimize the sum of costs of the stations and the task duplication. We develop an optimal solution procedure based on a backtracking branch-and-bound algorithm and evaluate its performance via a large set of experiments. A branch-and-bound based heuristic is then developed for solving large-scale problems. The heuristic solutions are compared with a lower bound and experiments show that the heuristic provides much better solutions than those obtained by traditional approaches.     

A bi-criteria heuristic for the vehicle routing problem with time windows

This paper describes a heuristic for the Vehicle Routing and Scheduling Problem with Time Windows (VRSPTW). Unique to this problem are the so-called time windows, i.e. time slots during which the vehicle must arrive at the customer to deliver the goods. The heuristic builds on the well-known Clarke and Wright Savings method with an additional criterion that models an intuitive view of time influence on route building. Experiments show that this added criterion yields significantly better solutions to the VRSPTW than pure routing heuristics, and also compares favorably to other new heuristics, developed specifically for the VRSPTW.     

Replenishment Schedule for Deteriorating Items with Time-Proportional Demand

In this paper a heuristic model is presented for determining the ordering schedule when an inventoried item is subject to deterioration and demand changes linearly over time. While the optimizing model developed by researchers fixes the ordering interval and varies the ordering size, the heuristic permits variation in both replenishment-cycle length and the size of the order. As a result, the heuristic produces a better solution than optimizing models in the study presented here.     

Modelling replenishment and transshipment decisions in periodic review multilocation inventory systems

Effective models of key operational decisions in multilocation inventory systems are important for a successful retail sector. This paper argues that much of the existing research in this area is not applicable to a highly competitive retail environment, particularly if periodic review replenishment policies are used. The paper develops a model of a periodic review multilocation inventory system that is suitable for this environment and investigates the characteristics of optimal replenishment and transshipment decisions. This motivates the development of three simple heuristic transshipment policies that are practical for systems with many locations. The results of a numerical study involving systems with five locations suggest that the performance of these heuristic policies is often close to optimal and can be considerably better than the performance of commonly used policies.     

The deterministic multi-item dynamic lot size problem with joint business volume discount

This paper considers the multi-item dynamic lot size model where joint business volume discount is applied for all items purchased whenever the total dollar value of an order reaches a certain level. Multi-item discounts are prevalent in practical applications, yet the literature has only considered limited instances of single-item models. We establish the mathematical formulation and design an effective dynamic programming based heuristic. Computational results disclose our approach obtains high quality solutions that dominate the best known heuristic for the simplified one-item case, and that proves vastly superior to the state-of-the-art CPLEX MIP code for the multi-item case (for which no alternative heuristics have been devised). We obtained significantly better solutions than CPLEX for the more complex problems, while running from 4800 to over 100,000 times faster. Enhanced variants of our method improve these outcomes further. This revised version was published online in June 2006 with corrections to the Cover Date.     

Proximity Benders: a decomposition heuristic for stochastic programs

In this paper we present a heuristic approach to two-stage mixed-integer linear stochastic programming models with continuous second stage variables. A common solution approach for these models is Benders decomposition, in which a sequence of (possibly infeasible) solutions is generated, until an optimal solution is eventually found and the method terminates. As convergence may require a large amount of computing time for hard instances, the method may be unsatisfactory from a heuristic point of view. Proximity search is a recently-proposed heuristic paradigm in which the problem at hand is modified and iteratively solved with the aim of producing a sequence of improving feasible solutions. As such, proximity search and Benders decomposition naturally complement each other, in particular when the emphasis is on seeking high-quality, but not necessarily optimal, solutions. In this paper, we investigate the use of proximity search as a tactical tool to drive Benders decomposition, and computationally evaluate its performance as a heuristic on instances of different stochastic programming problems.     

Using combined forecasts with changing weights for electricity demand profiling

Day-ahead half-hourly demand forecasts are required for scheduling and for calculating the daily electricity pool price. One approach predicts turning points on the demand curve and then produces half-hourly forecasts by a heuristic procedure, called profiling, which is based on a past demand curve. This paper investigates possible profiling improvements. Using a cubic smoothing spline in the heuristic leads to a slight improvement. Often, several past curves could reasonably be used in the profiling method. Consequently, there are often several demand curve forecasts available. Switching and smooth transition forecast combination models are considered. These models enable the combining weights to vary across the 48 half-hours, which is appealing as different forecasts may be more suitable for different periods. Several criteria are used to control the changing weights, including weather, and the methodology is extended to the case of more than two forecasts. Empirical analysis gives encouraging results.