Search

In power delivery systems, the use of dispersed generation and security control to improve network utilization requires the optimal use of system control devices. The installation of loop controller allows the distribution system to operate in a loop configuration, achieving effective management of voltage and power flow. In the investment planning process, it is important to identify the optimal location and installed capacity of the equipment such that all operational constraints are satisfied. This paper presents a method for identifying the optimal location and capacity with the minimum installation cost. Our novel approach uses an economic model that considers the fixed costs. A slope scaling procedure is presented, and its efficiency is demonstrated using numerical experiments.

To cope with growing passenger demand and to provide better services, increasing the number of trains is desired for certain lines. Maximum possible throughput of a line is often limited due to the limited number of platforms at the terminal, which was the case with two bullet-train lines originating from Tokyo. In these lines, there exists an intermediate station in the close vicinity of the terminal. This paper proposes a network-based optimization model to analyze the throughput of a line when turn-backs at the adjacent station are introduced to increase the line capacity.

We consider the allocation of a running time supplement to a railway timetable. Previously, Vekas et al. developed a stochastic programming model. In this paper, their optimization model is improved by adding bound constraints on the supplements. It is shown that the probability of delays decreases when using the proposed model. In addition, an effective L-shaped algorithm is presented.

Optimization of vehicle routes with delivery and pickup for a rental industry is considered. The company delivers to or pickups from customers rented products. Several types of products exist, and customers rent the specified number of products of the specific type. Time windows exist for delivery and pickup. There exist two sizes of vehicles, and their trips start from and end at depot and vehicles can make several trips during a day. Delivery must precede pickup on any trip of a vehicle. Capacity of vehicles depends on product type and also on how products are loaded on vehicles. Depending on demand quantity, split deliveries/pickups may be necessary. The company wants to minimize the total transportation cost. Based on the fact that the total number of distinct trips is rather small due to limited capacity of the vehicles, our solution strategy first enumerates all possible trips. Routes (i.e., collection of trips) are obtained by assigning trips to vehicles so that the total cost is minimized subject to constraints on demand, an upper limit on the number of trips per vehicle, and time compatibility of trips assigned to each vehicle. Since there exist many time compatibility constraints, the problem is first solved without them, we then check the compatibility and if necessary add compatibility constraints, and the problem is solved again until all routes become time compatible. Computational performance of the proposed solution approach is evaluated.

It is necessary for railway companies to construct daily schedules of assigning rolling stocks to utilization paths. A utilization path consists of a series of trains that a particular rolling stock performs in a day. A mixed integer programming model based on Lai et al. [1] is presented and is shown that straightforward applications of the model result in too much computational time and also inappropriate assignment schedules due to end effects. We show that the model can be modified to alleviate these difficulties, and also show that the repeated applications of the optimization model in the rolling horizon allow to generate a feasible assignment schedule for a longer period of time thus indicating the feasibility of the optimization approach.

The unit commitment problem is to determine the schedule of power generating units and the generating level of each unit. The decisions involve which units to commit at each time period and at what level to generate power to meet the electricity demand. We consider the heuristic column generation algorithm to solve this problem. Previous methods used the approach in which each column corresponds to the start–stop schedule and output level. Since power output is a continuous quantity, it takes time to generate the required columns efficiently. In our proposed approach, the problem to be solved is not a simple set partitioning problem, because the columns generated contain only a schedule specified by 0–1 value. It is shown that the proposed heuristic approach is effective to solve the problem.

In recent years, it has been difficult for manufactures and suppliers to forecast demand from a market for a given product precisely. Therefore, it has become important for them to cope with fluctuations in demand. From this viewpoint, the problem of planning or scheduling in production systems can be regarded as a mathematical problem with stochastic elements. However, in many previous studies, such problems are formulated without stochastic factors, treating stochastic elements as deterministic variables or parameters. Stochastic programming incorporates such factors into the mathematical formulation. In the present paper, we consider a multi-product, discrete, lotsizing and scheduling problem on parallel machines with stochastic demands. Under certain assumptions, this problem can be formulated as a stochastic integer programming problem. We attempt to solve this problem by a scenario aggregation method proposed by Rockafellar and Wets. The results from computational experiments suggest that our approach is able to solve large-scale problems, and that, under the condition of uncertainty, incorporating stochastic elements into the model gives better results than formulating the problem as a deterministic model.

So many scheduling problems arise in railway industries. One of the typical scheduling problems is Crew Scheduling Problem. Much attention has been paid to this problem by a lot of researchers, but many studies have not been done to the problems in railway industries in Japan. In this paper, we consider a railway crew scheduling problem in Japan. The problem can be formulated into Set Covering Problem (SCP). In SCP, a row corresponds to a trip representing a minimal task and a column corresponds to a pairing representing a sequence of trips performed by a certain crew. Many algorithms have been developed and proposed for it. On the other hand, in practical use, it is important to investigate how these algorithms behave and work on a certain problem. Therefore, we focus on Wedelin's algorithm, which is based on Lagrange relaxation and is known as one of the high performance algorithms for SCP, and mainly examine the basic idea of this algorithm. Furthermore, we show effectiveness of this procedure through computational experiments on instances from Japanese railway.

In this paper, we introduce a class of stochastic programming problem with fixed charge recourse in which a fixed cost is imposed if the value of the continuous recourse variable is strictly positive. The algorithm of a branch-and-cut method to solve the problem is developed by using the property of the expected recourse function. Then, the problem is applied to a power generating system. The numerical experiments show that the proposed algorithm is quite efficient. The mathematical programming model defined in this paper is quite useful for a variety of design and operational problems.

Daily route generation of home care staff is considered and a column generation heuristic is developed. Constraints considered include staff working hours, time window for each visit, means of transportation (bicycle/car), maximum allowable idle time between visits, patient/staff compatibility, among others. Since it is desired to generate compact routes in the geographically scattered area, the minimization of total travel time is used. Computational results based on real data will be presented. To further reduce CPU time, pre-processing of input data is performed to reduce the solution space by narrowing the time window of visits and by limiting candidate staff members who could be assigned to a specific visit. The pre-processing is performed by solving two small 0–1 programs. It is shown how the pre-processing cuts down the CPU time of the column generation algorithm.

Score orienteering is a variant of the orienteering game where competitors start at a specified control point, visit as many control points as possible and thereby collect prizes, and return to the starting point within a prescribed amount of time. The competitor with the highest amount of prizes wins the game. In this paper, we propose the minimum directed 1-subtree problem as a new relaxation to this problem and develop two methods to improve its lower bound. We describe a cut and dual simplex method and a Lagrangian relaxation method, and construct an algorithm that combines these two methods in an appropriate way. Computational experiments are carried out to analyse the behavior of the proposed relaxation with respect to the characteristics of the test problems. Especially for large-scale instances, we find that the proposed relaxation is superior to the ordinary assignment relaxation.

We consider the allocation of a running time supplement to a railway timetable. Previously, Vekas et al. examined the optimal way to allocate the running time supplement. The uncertain disturbances in a railway were modeled using random variables. In their model, it was assumed that there was an upper limit to the total supplement, but its allocation was not restricted. In this paper, we suggest an improvement to the previous model and present a new stochastic programming model in which there is a constraint on the running time supplement allocated to each trip to minimize the expected delay. Then a solution algorithm to solve the problem is developed. In the previous model, allocation of the running time supplement was biased because it was not allocated to all trips. We balance the amounts of supplements for trips by adding upper and lower bounds. The fluctuations of the supplements for trips become small, and the probability of a delay decreases using our new model. Then the calculation times using the L-shaped algorithm and the former method solving a deterministic equivalent of large-scale problems are compared. It is shown that the large-scale problems can be solved effectively by using the L-shaped method.

It is commonly believed that the use of the assignment problem works well when one selects a relaxation problem within the framework of a branch and bound algorithm to solve an asymmetric traveling salesman problem (TS P) optimally. In this paper, we present asymmetric TSP instances found in real-life setting, and show that t.he above common belief is not necessarily appropriate. Based on the real-life example, a family of asymmetric TSP instances called SLOPE is considered, which are generated by deforming arc lengths of standard two-dimensional TSPs on a plane in a, specific manner. For this type of instances, we show that the assignmellt relaxation yields poor performance, and propose a minimum 1-arborescence relaxation similar to the minimum i-tree relaxation that has been successfullv applied to the symmetric TSPs. In order to make the algorithm more efficient, the propel' selection of Cc ro;t node and the detenninat,ion of Lagrange multipliers to increase the lower bounds are explored. Computational experiments with instances SLOPE and also with t.he real-life instance show that the proposed algorithm gives better computational performance than the algorithm with the assignment relax­ ation.

Two or more multiplicative congruential random-number generators with prime modulus combined by means of a method proposed by Wichmann and Hill (1982) yield a random-number generator equivalent to a multiplicative congruential random-number generator with modulus equal to the product of the moduli of the component multiplicative congruential generators. The period of a random-number sequence obtained by the Wichmann-Hill method is equal to the least common multiple of the periods of the combined sequences. One of the two purposes of this paper is to present a necessary and sufficient set of efficiently verifiable conditions for the period to be equal to its maximum, which is the maximum of the least common multiple. Each of the conditions is always satisfied or is more easily verifiable when the modulus of each of the component generators is a safe prime. The other purpose of this paper is to derive an efficiently evaluatable formula for serial correlations of the maximum-period sequences by the Wichmann-Hill method. The authors recommend (i) to make the modulus of each of the component generators a safe prime, and (ii) to chose the multipliers of the components so as to (a) maximize the period and (b) make the serial correlations small in absolute value.

Previous research on inventory distributions between local warehouses or retailers (bases) has focused separately on either of two types of stock transshipment policies: preventive lateral transshipments or emergency lateral transshipments. Each of these has its advantages and disadvantages, and combining these policies may well enable merchandisers to achieve higher service levels. Thus, the combined use of these policies is the focus of the present study. A stochastic programming problem is formulated with demand as a stochastic variable, and the policy of using both preventive and emergency lateral transshipment is examined for its effectiveness while solution methods are examined for their efficiency.

This paper presents a simulation-optimization approach to find an appropriate dispatching priority. The study is based on a detailed simulator for a module-type commercial FMS. Specifically, after presenting the basic configuration and fundamental control logic of the system together with its main characteristics as a special type of a job shop, an algorithm is presented which combines simulated annealing and simulation to explore a dispatching priority of operations that minimizes the total tardiness. Computational performance of the algorithm is presented which shows that good solutions can be obtained mostly after 300 iterations or so. The paper also compares the performance of the optimal" or near optimal dispatching priority generated by the proposed algorithm with those generated by standard dispatching rules. The results show that standard dispatching rules such as EDD and SLACK which take due dates into considerations perform moderately, but not extremely well. The results also show that some of the workload-based dispatching rules such as SPT work consistently well.

Described in this paper is an application of a discrete-event simulation model for the Mazatrol FMS system manufactured by Yamazaki Mazak, one of the leading machine tool companies in the world, to analyze various causes of machine idle times. The Mazatrol FMS is a module-type FMS which consists of the maximum of 8 horizontal machining centers, 1 to 4 load/unload stations, a stacker crane, pallet stockers among others. Presentation of a conceptual framework for the machine idle times and their causes is followed by detailed simulation results. Simulation indicates that the utilization of machining centers during the normal operating period is at least 92.7% and is reasonably high, under the conditions of enough work load for each machine and no equipment failure. It is also shown that the main causes of the machine idle times differ depending on the periods in which they occur during the entire makespan. The increase of routing flexibility, which is known to be an important factor for the reduction of the makespan, is found to give little effect on the machine utilization. On the other hand, the results show that the number of pallets is an important factor for high machine utilization. The simulation results are expected to provide useful information for efficient operation of FMSs in general, and of the Mazatrol FMS in particular. Suggestions are given on how simulation results could be used to improve the system utilization on the medium-range as well as the short-term planning of FMSs.