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.     

A tabu search algorithm for the relocation problem in a warehousing system

Relocation of items in a warehousing system is usually used when the handling machines become the bottleneck. This paper addresses the optimization problem of relocation in a warehouse with dynamic operating policy. An integer linear programming formulation is proposed. A two-stage heuristic method is developed to generate an initial solution. A tabu search algorithm is proposed to improve the solution. Two relocation policies are studied and their performances are compared.     

Tabu search for minimizing total tardiness in a job shop

This paper presents a tabu search approach to minimize total tardiness for the job shop scheduling problem. The method uses dispatching rules to obtain an initial solution and searches for new solutions in a neighborhood based on the critical paths of the jobs. Diversification and intensification strategies are suggested. For small problems the solutions’ quality is evaluated against optimal solution values and for large problems the tabu search performance is compared with two heuristics proposed in the literature.     

基于遗传禁忌算法的任务分配与调度的研究

任务分配与调度问题是公认的NP问题,为了合理的对备份任务进行分配与调度,使得最短时间内完成备份任务, 提出了基于遗传禁忌搜索的备份任务调度算法。 重点研究了遗传算法和禁忌搜索算法,并针对二者的不足,提出将其两种算法混合,相互取长补短,仿真实验结果和实例应用表明,笔者提出的算法其搜索效率比单一的遗传算法具有较好的效果。     

Appointment scheduling of outpatient surgical services in a multistage operating room department

This article addresses the appointment scheduling of outpatient surgeries in a multistage operating room (OR) department with stochastic service times serving multiple patient types. We discuss many challenges, such as the limited availability of multiple resources (e.g., staff, operating rooms, surgeons, and recovery beds), and the compatibility of patient and surgeon types. In addition, availability of surgeons is restricted by time window constraints. Three simulation-based optimization methods have been proposed to minimize the patients’ wait time, patients’ completion time, and number of surgery cancellations. The first method is simulation-based tabu search (STS). It combines discrete-event simulation and tabu search to schedule surgery cases. The second and third methods are integer programming enhanced tabu search (IPETS) and binary programming enhanced tabu search (BPETS). IPETS and BPETS improve on STS by incorporating integer programming and binary programming models, respectively. This article includes a case study of an OR department in a major Canadian hospital. We further expand the actual data obtained in the case study to cover a wide range of parameters in sets of test problems, and provide analysis on the efficiency and effectiveness of the proposed methods in comparison with several scheduling rules. Finally, comments on the applications of the proposed methods are provided.     

Modeling and optimization of a container drayage problem with resource constraints

This paper investigates the problem faced by firms that transport containers by truck in an environment with resource constraints. The considered area is export-dominant. As a result, there are three types of container movements as inbound full, outbound full, and inbound empty movements. Both the time windows at the terminal and at the customers’ places and the operation times are considered. Empty containers are also regarded as separate transportation resources besides trucks. The total operating time including waiting time of all the trucks in operation is minimized. The problem is first formulated as a directed graph and then mathematically modeled based on the graph. It falls into a multiple traveling salesman problem with time windows (m-TSPTW) with resource constraints. An algorithm based on reactive tabu search (RTS) is developed to solve the problem. A number of randomly generated examples indicate that the algorithm can be applied to the real world.     

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.     

A tabu search approach for cell scheduling problem with makespan criterion

Scheduling problem in a cellular manufacturing system is treated as the group scheduling problem, assuming that intercellular moves can be eliminated by duplicating machines. However, in a typical CMS, duplicating bottleneck machines may be costly and infeasible. This fact limits the applicability of group scheduling. Scheduling problem in the presence of bottleneck machines is termed as cell scheduling. A mixed-integer linear programming model is proposed for the attempted cell scheduling problem and a nested application of tabu search approach is investigated in this paper to solve the problem heuristically. The effectiveness of the proposed nested tabu search (NTS) algorithm is evaluated on 16 problems selected from the literature. Comparison of the results of NTS with SVS-algorithm reveals the effectiveness and efficiency of the proposed algorithm.     

Pricing Relocation–Redevelopment Projects for City Expansion: The Case in China

A solution to city expansion under limited land availability is relocation of existing habitants, demolition of existing buildings and redevelopment of new buildings. In the case of Chinese cities, however, such strategies have become a channel for municipalities to increase their revenue from sale of land and productivity from increased development, at the expense of low compensation to former occupants and vacant housing after development. We utilize a sequential real options pricing approach to find conditions when relocation/demolition and redevelopment in a finite time horizon are optimal and also to show what factors the governments can influence to delay or speed up redevelopment.     

Interlocking of information systems for international supply and demand chains management

This paper is concerned with coordination aspects of supply chain management and, in particular, investigates setup coordination between two and three stages of a supply chain. The problem arises from a real application in the production chain of a kitchen furniture plant. In different stages of the plant, items are grouped according to different attributes. A setup is required in a stage when the new batch has a different level of attribute from the previous one. Two objectives are considered, i.e., minimizing the total number of setups and minimizing the maximum number of setups of the stages. The problem is to determine a sequence of batches in search for Pareto-optimal solutions with respect to the two objectives. Several metaheuristics, including genetic algorithm, simulated annealing, and iterated local search (ILS) have been proposed for the two-stage problem. In this paper, we develop a constructive heuristic, which combines a least flexibility first principle and a greedy search, for the two- and three-stage problems. Computational results show that the proposed heuristic performs significantly better than the genetic algorithm and simulated annealing. Although the proposed heuristic is inferior to the ILS, which employs two constructive initial solution heuristic, for the two-stage problem, it can be easily extended to the three-stage problem.