Simultaneous dock assignment and sequencing of inbound trucks under a fixed outbound truck schedule in multi-door cross docking operations

This paper studies the simultaneous dock assignment and sequencing of inbound trucks for a multi-door cross docking operation with the objective to minimize total weighted tardiness, under a fixed outbound truck departure schedule. The problem is newly formulated and solved by six different metaheuristic algorithms, which include simulated annealing, tabu search, ant colony optimization, differential evolution, and two hybrid differential-evolution algorithms. To evaluate the total weighted tardiness associated with any given inbound-truck sequence and dock assignment, an operational policy is developed. This policy is employed by every metaheuristic algorithm in searching for the optimal dock assignment and sequence. Each metaheuristic algorithm is tested with 40 problems. The major conclusions are: (1) metaheuristic is generally an effective optimization method for the subject problem; (2) population based metaheuristic algorithms are generally more effective than projection based metaheuristic algorithms; (3) proper selection of algorithmic parameters is important and more critical for projection based metaheuristic algorithms than population based algorithms; (4) the two best algorithms are ant colony optimization and hybrid differential evolution 2; among them, ACO takes less time than hybrid 2 and thus can be declared the best among all the six metaheuristic algorithms tested.     

Metaheuristics for drilling operation scheduling in Taiwan PCB industries

Among all types of production environment, identical parallel machines are frequently used to increase the manufacturing capacity of the drilling operation in Taiwan printed circuit board (PCB) industries. Additionally, multiple but conflicting objectives are usually considered when a manager plans the production scheduling. Compared to the single objective problem, the multiple-objective version no longer looks for an individual optimal solution, but a Pareto front consisting of a set of non-dominated solutions will be needed and established. The manager then can select one of the alternatives from the set. This research aims at employing a variable neighborhood search (VNS) algorithm and a multiple ant colony optimization (MACO) algorithm to solve the identical parallel-machine scheduling problem with two conflicting objectives: makespan and total tardiness. In VNS, two neighborhoods are defined—insert a job to a different position or swap two jobs in the sequence. To save the computational expense, one of the neighborhoods is randomly selected for the target solution which is also arbitrarily chosen from the current Pareto front. In MACO, a two-phase construction procedure where three colonies are employed in each phase is proposed. These two algorithms are tested on a set of real data collected from a leading PCB factory in Taiwan and their performances are compared. The computational results show that VNS outperforms all competing algorithms—SPGA, MOGA, NSGA-II, SPEA-II, and MACO in terms of solution quality and computational time.     

Case Study: Solving a Rental Fleet Sizing Model with a Large Time–Space Network

This article addresses a rental fleet sizing problem (RFS) in the context of the truck rental industry, subject to uncertain customer travel time and nonstationary customer demand that is dependent on geographical location, time, and the economic cycle of the industry. We integrate tactical (asset purchases and sales) and operational (empty truck movement and vehicle assignment) decisions, with the explicit incorporation of an asset age factor, to achieve lower cost solutions. Typically, the length of time horizon and number of locations under consideration are quite large, which makes the RFS model computationally challenging to solve. Aggregation procedures are employed for location clustering and end-of-horizon effects are examined through demand scenario-based analyses. For the reduced time–space networks, decision analyses are conducted for the RFS model to provide insights into the truck rental business regarding asset movement decisions and asset procurement/disposal decisions over time and locations.     

Algorithm portfolios for logistics optimization considering stochastic demands and mobility allowance

The vehicle routing problem with stochastic demand (VRPSD) is a well known NP-hard problem. The uncharacteristic behaviour associated with the problem enhances the computational efforts required to obtain a feasible and near-optimal solution. This paper proposes an algorithm portfolio methodology based on evolutionary algorithms, which takes into account the stochastic nature of customer demand to solve this computationally complex problem. These problems are well known to have computationally complex objective functions, which make their solutions hard to find, particularly when problem instances of large dimensions are considered. Of particular importance in such situations is the timeliness of the solution. For example, Apple was forced to delay their shipments of iPads internationally due to unprecedented demand and issues with their delivery systems in Samsung Electronics and Seiko Epson. Such examples illustrate the importance of stochastic customer demands and the timing of delivery. Moreover, most of the evolutionary algorithms, known for providing computationally efficient solutions, are unable to always provide optimal or near optimal solutions to all the VRPSD instances within allocated time interval. This is due to the characteristic variations in the computational time taken by evolutionary algorithms for same or varying size of the VRPSD instances. Therefore, this paper presents portfolios of different evolutionary algorithms to reduce the computational time taken to resolve the VRPSD. Moreover, an innovative concept of the mobility allowance (MA) in landmoves based on the levy’s distribution function has been introduced to cope with real situations existing in vehicle routing problems. The proposed portfolio approach has been evaluated for the varying instances of the VRPSD. Four of the existing metaheuristics including Genetic Algorithm (GA), Simulated Annealing (SA), Artificial Immune System (AIS), TABU Search (TS) along with new neighbourhood search, are incorporated in the portfolios. Experiments have been performed on varying dimensions of the VRPSD instances to validate the different properties of the algorithm portfolio. An illustrative example is presented to show that the set of metaheuristics allocated to certain number of processors (i.e. algorithm portfolio) performed better than their individual metaheuristics.     

Ant colony optimization for the single model U-type assembly line balancing problem

An assembly line is a production line in which units move continuously through a sequence of stations. The assembly line balancing problem is defined as the allocation of tasks to an ordered sequence of stations subject to precedence constraints with the objective of optimizing a performance measure. In this paper, we propose ant colony algorithms to solve the single-model U-type assembly line balancing problem. We conduct an extensive experimental study in which the performance of the proposed algorithm is compared against best known algorithms reported in the literature. The results indicate that the proposed algorithms display very competitive performance against them.     

基于改进的蚁群算法的移动机器人路径规划

针对移动机器人路径规划中的传统蚁群算法收敛精度低、易陷入局部最优等问题,提出一种改进蚁群算法。首先,对算法的转移概率进行改进,加入转向代价,减少不必要的转折,并针对启发函数启发性能不够强,对路径启发信息进行改进;然后,提出一种自适应的参数调整伪随机状态转移策略,动态改变参数值,避免过早陷入搜索停滞,增强搜索的全面性,同时对信息素更新方式进行改进,调整信息素挥发系数,保持蚂蚁发现最优路径的能力;最后,通过Matlab与其他算法进行对比分析。仿真结果表明,改进的蚁群算法收敛速度快,且路径长度和算法迭代次数有明显减少,能得到全局最优路径。改进蚁群算法具有可行性、有效性,在移动机器人路径规划中有一定的应用价值。     

An integrated multi-depot hub-location vehicle routing model for network planning of parcel service

The paper describes why optimal design of depot and hub transportation networks for parcel service providers makes it necessary to develop a generalized hub location and vehicle routing model (VRM). Analogous problems occur for postal, parcel and piece goods service providers. A generalized hub location and VRM is developed which encompasses the determination of the number, locations of hubs and depots and their assigned service areas as well as the routes between the demand points and consolidation points (depots, hubs). Because this task leads to a very complex transport design problem, a heuristic solution concept has to be developed. The applicability to a case study is demonstrated; the case of completely new system configuration for Austria is considered. Management must simultaneously decide the number, location, service areas and routes from demand points to depots and vice versa (the pickup and delivery structure) as well as the number and locations of hubs and the routes of depot–hub and hub–hub transports (the hub location or line haul structure), The developed management support decision model leads for real cases to a tremendous number of some million binary variables as well as continuous variables and million of constraints.     

An integrated distribution routing model in multi-supply center system

A distribution routing problem with time constraint is one of the important problems in distribution and supply center management. This research is concerned with an integrated distribution routing problem for multi-supply centers based on improved genetic algorithm and graphical user interface (GUI)-type programming. In this research, we proposed a method based on a three-step approach: in step 1 a sector clustering model is developed to transfer the multi-supply center problem to single supply center problems which are easier to be solved; in step 2 we developed a vehicle routing model with time constraints and in step 3 we developed a GA-TSP model which can improve the vehicle routing schedules. The objective of the problem is to minimize the logistic cost for a set of customers without being tardy or exceeding the capacity or travel time of the vehicles. For computational purpose, we developed a GUI-type computer program according to the proposed methods and the sample outputs show that the proposed method is very effective on a set of standard test problems, and it could be potentially useful in solving the distribution routing problems.     

An integrated production–distribution model for the dynamic location and allocation problem with safety stock optimization

The design and management of a multi-stage production–distribution system is one of the most critical problems in logistics and in facility management. Companies need to be able to evaluate and design different configurations for their logistic networks as quickly as possible. This means coordinating the entire supply chain effectively in order to minimize costs and simultaneously optimize facilities location, the allocation of customer demand to production/distribution centers, the inbound and outbound transportation activities, the product flows between production and/or warehousing facilities, the reverse logistics activities, etc.Full optimization of supply chain is achieved by integrating strategic, tactical, and operational decision-making in terms of the design, management, and control of activities. The cost-based and mixed-integer programming model presented in this study has been developed to support management in making the following decisions: the number of facilities (e.g. warehousing systems, distribution centers), the choice of their locations and the assignment of customer demand to them, and also incorporate tactical decisions regarding inventory control, production rates, and service-level determination in a stochastic environment. This paper presents an original model for the dynamic location–allocation problem with control of customer service level and safety stock optimization. An experimental analysis identifies the most critical factors affecting the logistics cost, and to finish, an industrial application is illustrated demonstrating the effectiveness of the proposed optimization approach.     

A modified artificial bee colony algorithm for order acceptance in two-machine flow shops

We consider a two-stage make-to-order production system characterized by limited production capacity and tight order due dates. We want to make joint decisions on order acceptance and scheduling to maximize the total net revenue. The problem is computationally intractable. In view of the fact that artificial bee colony algorithm has been shown to be an effective evolutionary algorithm to handle combinatorial optimization problems, we first conduct a pilot study of applying the basic artificial bee colony algorithm to treat our problem. Based on the results of the pilot study and the problem characteristics, we develop a modified artificial bee colony algorithm. The experimental results show that the modified artificial bee colony algorithm is able to generate good solutions for large-scale problem instances.     

Multi-agent-based transport planning in the newspaper industry

In many cases of today's planning tasks, the synchronization of production and distribution is becoming increasingly important in order to minimize costs and to maximize customer satisfaction. This is especially the case if transport schedules are closely connected to production schedules, as it is in the newspaper industry—where perishable goods are distributed immediately after production. In order to achieve the above mentioned competing objectives, a special kind of vehicle routing problem, the vehicle routing problem with time windows and cluster-dependent tour starts (VRPTWCD), has to be solved. Moreover, the varying print and post-processing schedules due to unknown editorial deadlines lead to the need for a dynamic online control of the newspaper production and distribution process. In this contribution, the outlined dynamic transport problem is solved online under consideration of unforeseen changes in production schedules. The solution concept is based on a multi-agent system consisting of, amongst others, several Edition and Vehicle Agents. This system is exemplarily applied to a real life application case of one of the largest German newspaper companies. It is shown that a static (centralized) optimization of the underlying problem would even lead to worse results in comparison to the current situation and that the appliance of the multi-agent system is suitable in the newspaper industry.     

基于PSO的信息熵数据融合非均匀分簇路由算法

针对无线传感器网络分簇算法中能量分布不均衡导致的"热区"和簇头负载过重问题,提出了一种基于PSO算法优化簇头选举的非均匀分簇算法。在候选簇头选举和竞争半径计算过程中综合考虑节点动态能量、节点密度和节点距基站距离,将网络进行非均匀分簇,并引入PSO算法进行最终簇头选举。根据节点能量、节点密度和距基站距离确定簇间单跳多跳结合的路由规则,选取代价函数小的节点作为下一跳节点。基于节点信息熵确定融合阈值,进行簇内数据融合剔除冗余数据。仿真结果表明,改进算法的数据传输量比EEUC算法和UCRA算法分别提高了20%和10%,提升了数据的融合效率,有效延长了网络生命周期,簇头能量消耗得到均衡,减少了网络能量消耗,网络的整体性能显著优于其他对比算法。     

采用蚁群算法模拟机器人寻路的仿真实验

蚁群算法是一种基于蚁群寻找食物这一现象,实现寻路优化的算法。通过在MATLAB中进行程序设计,实现了利用蚁群算法模拟自动寻路的计算,并进一步将程序应用于简易机器人的寻路模块,初步实现机器人的寻路优化功能。     

Constraint-based ACO for a shared resource constrained scheduling problem

We consider a scheduling problem arising in the mining industry. Ore from several mining sites must be transferred to ports to be loaded on ships in a timely manner. In doing so, several constraints must be met which involve transporting the ore and deadlines. These deadlines are two-fold: there is a preferred deadline by which the ships should be loaded and there is a final deadline by which time the ships must be loaded. Corresponding to the two types of deadlines, each task is associated with a soft and hard due time. The objective is to minimize the cumulative tardiness, measured using the soft due times, across all tasks. This problem can be formulated as a resource constrained job scheduling problem where several tasks must be scheduled on multiple machines satisfying precedence and resource constraints and an objective to minimize total weighted tardiness. For this problem we present hybrids of ant colony optimization, Beam search and constraint programming. These algorithms have previously shown to be effective on similar tightly-constrained combinatorial optimization problems. We show that the hybrid involving all three algorithms provides the best solutions, particularly with respect to feasibility. We also investigate alternative estimates for guiding the Beam search component of our algorithms and show that stochastic sampling is the most effective.     

The storage location assignment problem for outbound containers in a maritime terminal

This paper addresses the storage location assignment problem for outbound containers. The problem is decomposed into two stages. The yard bays and the amount of locations in each yard bay, which will be assigned to the containers bounded for different ships, are determined in the first stage. The exact storage location for each container is determined in the second stage. The problem in the first stage is solved by a mixed integer programming model, while a hybrid sequence stacking algorithm is applied to solve the problem in the second stage. Experimental results show that the proposed approach is effective and efficient in solving the storage location assignment problem for outbound containers.     

The selective pickup and delivery problem: Formulation and a memetic algorithm

The pickup and delivery problem addresses the real-world issues in logistic industry and establishes an important category of vehicle routing problems. The problem is to find the shortest route to collect and distribute commodities under the assumption that the total supply and the total demand are in equilibrium. This study presents a novel problem formulation, called the selective pickup and delivery problem (SPDP), by relaxing the constraint that all pickup nodes must be visited. Specifically, the SPDP aims to find the shortest route that can supply delivery nodes with required commodities from some pickup nodes. This problem can substantially reduce the transportation cost and fits real-world logistic scenarios. Furthermore, this study proves that the SPDP is NP-hard and proposes a memetic algorithm (MA) based on genetic algorithm and local search to resolve the problem. A novel representation of candidate solutions is designed for the selection of pickup nodes. The related operators are also devised for the MA; in particular, it adapts the 2-opt operator to the sub-routes of the SPDP for enhancement of visiting order. The experimental results on several SPDP instances validate that the proposed MA can significantly outperform genetic algorithm and tabu search in terms of solution quality and convergence speed. In addition, the reduced route lengths on the test instances and the real-world application to rental bikes distribution demonstrate the benefit of the SPDP in logistics.     

An efficient hybrid genetic algorithm for the multi-product multi-period inventory routing problem

The inventory routing problem (IRP) addressed in this study is a many-to-one distribution network consisting of an assembly plant and many distinct suppliers where each supplies a distinct product. We consider a finite horizon, multi-periods, multi-suppliers and multi-products where a fleet of capacitated homogeneous vehicles, housed at a depot, transport products from the suppliers to meet the demand specified by the assembly plant in each period. The demand for each product is deterministic and time varying. A mathematical formulation of the problem is given and CPLEX 9.1 is run for a finite amount of time to obtain lower and upper bounds. A hybrid genetic algorithm, which is based on the allocation first route second strategy and which considers both the inventory and the transportation costs, is proposed. In addition to a new set of crossover and mutation operators, we also introduce two new chromosome representations. Several medium and small sized problems are also constructed and added to the existing data sets to show the effectiveness of the proposed approach.     

Logistics scheduling to minimize inventory and transport costs

We study a logistics scheduling problem where a manufacturer receives raw materials from a supplier, manufactures products in a factory, and delivers the finished products to a customer. The supplier, factory and customer are located at three different sites. The objective is to minimize the sum of work-in-process inventory cost and transport cost, which includes both supply and delivery costs. For the special case of the problem where all the jobs have identical processing times, we show that the inventory cost function can be unified into a common expression for various batching schemes. Based on this characteristic and other optimal properties, we develop an O(n) algorithm to solve this case. For the general problem, we examine several special cases, identify their optimal properties, and develop polynomial-time algorithms to solve them optimally.     

A strategic-tactical model for the supply chain design in the delocalization context: Mathematical formulation and a case study

In this paper, we propose a mathematical model for the design of supply chains in the delocalization context. Our main objective is to develop a strategic-tactical supply chain design model that integrates all the relevant components that characterize the delocalization problem. We adopt the activity based approach to model the problem and we focus on the logistic decisions of activity location, technology choice, supplier selection, etc., and the financial decisions of transfer pricing, transportation costs allocation, etc. The mathematical formulation is illustrated by a case study from the automotive sector. A comparison between the model solution and the real decisions is used to prove the applicability and the utility of the proposed model.     

Ship routing problem with berthing time clash avoidance constraints

We consider a ship routing problem in which multiple vessels have to perform pickups and deliveries of cargoes at various locations. The loading and unloading time of cargoes at pickup and delivery locations is significant, and at each of these locations we need to assign a time slot to each vessel to perform the loading/unloading task so as to avoid time clashes. This problem is motivated by the operations of feeder vessels and company-owned cargo terminals, where the shipping company wishes to coordinate the routing and the berthing time of its vessels. We develop a heuristic algorithm for the problem using set partitioning formulation and column generation techniques. The effectiveness of the heuristic is tested via extensive computational experiments.