Tree based searching approaches for integrated vehicle dispatching and container allocation in a transshipment hub

This study addresses the integration of Vehicle dispatching and container storage location problem with consideration of loading and unloading activities simultaneously. A MIP model is formulated to describe the interrelation between vehicle scheduling, yard crane scheduling and container storage location. A tree structure is used to represent the whole solution space. This representation has a good property as it captures the neighborhood structure and enhances the performance of local search and adaptive searching algorithms. Three variants of tree based searching approaches are developed, namely, the Nested Partitions method (NP), the Beam Search method (BS), and Stochastic Beam Search method (SBS). Extensive experiments show that these proposed methods can find a promising solution in matter of seconds for a practical problem and the Stochastic Beam Search method (SBS) method performs nearly as well as Nested Partitions method (NP) while gaining great computational efficiency. Due to this merit, SBS method is suggested to solve real time integrated vehicle dispatching problem in a relative large scale and may applied in other real time complex system scheduling.     

Static Analysis Method for Detecting Buffer Overflow Vulnerabilities

In this paper, a new static method for automated detection of vulnerabilities that could result in buffer overflows in programs is suggested. The problem of the software defense against threads related to buffer overflows is very important one. Currently, there does not exist satisfactory approaches to its solution. The existing dynamic methods make it possible to avoid incorrect execution for certain classes of programs. The basic disadvantage of these methods is that the procedure of the error detection after the session of tests is very involved. Moreover, they do not guarantee that the results obtained are correct. Static analysis methods are, as a rule, lexical scanners and do not thoroughly analyze the execution of the program, as well as its memory content (e.g., arrays, variables, and the like). The objective of the suggested method is to improve situation in this field and facilitate the audit of a program code by the programmer.__________Translated from Programmirovanie, Vol. 31, No. 4, 2005.Original Russian Text Copyright © 2005 by Puchkov, Shapchenko.     

Exact methods and a heuristic for the optimization of an integrated replenishment-storage planning problem

In this paper we study the coordination of different activities in a supply chain issued from a real case. Multiple suppliers send raw materials (RMs) to a distribution center (DC) that delivers them to a unique plant where the storage of the RMs and the finished goods is not possible. Then, the finished goods are directly shipped to multiple customers having just‐in‐time (JIT) demands. Under these hypotheses, we show that the problem can be reduced to multiple suppliers and one DC. Afterwards, we analyze two cases; in the first, we consider an uncapacitated storage at DC, and in the second, we analyze the capacitated storage case. For the first case, we show that the problem is NP‐hard in the ordinary sense using the Knapsack decision problem. We then propose two exact methods: a mixed integer linear program (MILP) and a pseudopolynomial dynamic program. A classical dynamic program and an improved one using the idea of Shaw and Wagelmans are given. With numerical tests we show that the dynamic program gives the optimal solution in reasonable time for quite large instances compared with the MILP. For the second case, the capacity limitation in DC is assumed, which makes the problem solving more challenging. We propose an MILP and a dynamic programming‐based heuristic that provides solutions close to the optimal solution in very short times.     

Positioning of goods in a cross-docking environment

Cross docking is one of the options to reduce lead times and inventories and to improve customer response time in supply chains. Cross-docking centres are dynamic environments where products arrive, are regrouped, and leave the same day. In this paper we focus on the process of short-term storage of unit-loads in a cross-docking environment. The goal is to determine temporary storage locations for incoming unit loads such that the travel distances of the forklift trucks with these unit loads are minimised. We model this problem as a novel application of the minimum cost flow problem and show the applicability of the model for different types of layouts and priorities. We demonstrate both the efficiency and effectiveness of the method in the operational and design phase at cross-docking environments by applying it to practice-oriented examples. Furthermore, we show that the approach is superior to a commonly used heuristic method.     

Load scheduling for multiple quay cranes in port container terminals

This paper proposes a method to schedule loading operations when multiple yard cranes are operating in the same block. The loading scheduling methods in this paper are based on a genetic algorithm and a simulated annealing method, which consider interferences between adjacent yard cranes. It attempts to minimize the make-span of the yard crane operation. We consider the container handling time, the yard crane travel time, and the waiting time of each yard crane, when evaluating the makespan of the loading operation by yard cranes. An encoding method considering the special properties of the optimal solution of the problem is suggested. Numerical experiment was conducted to compare performances of the algorithms suggested in this study. Received: June 2005 / Accepted: December 2005     

Source/sink inventory control for vehicle rental systems

The problem of operating a vehicle rental system in a two-location environment is investigated. Two interdependent processes are identified as operating simultaneously. Units are rented out, ultimately to be returned to their original location. Secondly, units are rented out from one location but returned to a second location. As a result, the number of units of equipment at each location is constantly changing. In general, these “one-way” flows setup equipment imbalances which require periodic rebalancing of the system.Formulation takes the form of a multi-period dynamic program. Both transient and steady-state cases are investigated. Solution specifies the optimal number of units each location should hold on reserve in each period for “one-way” rentals. Finally, a restocking decision is embedded into the problem, in order to determine the optimal quantity of equipment lo be periodically rebalanced between locations due to “one-way” flows.Limitation of the procedure is explained. The size of the resulting dynamic program makes solution of the general multi-location problem computationally unfeasible. Approximation procedures are suggested to circumvent this limitation.     

响应动态约束条件的多目标货位优化算法研究

针对自动化立库货位决策与优化问题,考虑到优化目标多样、托盘使用状态及可分配货位动态变化等因素,提出了一种响应动态约束条件的多目标货位优化算法。以巷道作业均衡、货架重心稳定及作业路径最短建立多目标优化模型,基于变异系数自适应差分进化算法,使用货位随机数编码,根据实时货位可行域进行个体解码,以响应动态货位约束条件。提出了基于层次分析的Pareto解评价方法,从而获得多批作业货位持续优化的目标权重,为仓储货位决策提供合理方案。多批作业算法实验结果表明:所提算法效果显著优于多目标简单加权算法,能够有效应用于动态货位决策与优化。     

Efficient primal-dual heuristic for a dynamic location problem

In this paper the dynamic location problem with opening, closure and reopening of facilities is formulated and an efficient primal-dual heuristic that computes both upper and lower limits to its optimal solution is described. The problem here studied considers the possibility of reconfiguring any location more than once over the planning horizon. This problem is NP-hard (the simple plant location problem is a special case of the problem studied). A primal-dual heuristic based on the work of Erlenkotter [A dual-based procedure for uncapacitated facility location. Operations Research 1978;26:992–1009] and Van Roy and Erlenkotter [A dual-based procedure for dynamic facility location. Management Science 1982;28:1091–105] was developed and tested over a set of randomly generated test problems. The results obtained are quite good, both in terms of the quality of lower and upper bounds calculated as in terms of the computational time spent by the heuristic. A branch-and-bound procedure that enables to optimize the problem is also described and tested over the same set of randomly generated problems.     

自动化立体仓库货位分配与作业调度集成优化

针对动态提高单载具堆垛机式自动化立体仓库拣选效率的问题,文中提出了一种基于共享货位存储与动态订单拣选策略下的货位分配与作业调度集成优化方法。将动态移库优化扩展到仓库的整个拣选生命周期,建立以双指令循环下堆垛机拣选任务所需的总作业时间最短为评价目标的数学模型,提出了一种基于K-Medoids聚类的粒子群优化(Particle Swarm Optimization,PSO)算法,用K-Medoids算法通过产品与订单的相关性进行初始货位的聚类分析,筛除劣质解的货位范围,并在K-Medoids聚类算法生成的解类簇基础上获得精确解。实验结果表明,考虑动态移库可以使仓库拣选效率提高20%,且该算法与传统PSO算法相比求解时间下降66%左右。     

Input/output lot sizing in single stage batch production systems under constant demand

This paper develops an integrated input/output lot sizing model under deterministic conditions for a single product manufactured within a batch production environment. Our analysis incorporates the effects of work-in-process inventories resulting from multiple input items that are converted to output at finite rates in a single stage process and encompasses, simultaneously, the lot sizing decisions for the end product, as well as the externally procured input items. The resulting model represents a nonlinear mixed integer optimization problem, for which an efficient heuristic solution technique is suggested.