Self-adaptive large neighborhood search algorithm for parallel machine scheduling problems

A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems＇ another feature lies in oversubscription, namely not all jobs can be scheduled within specified scheduling horizons due to the limited machine capacity. The objective is thus to maximize the overall profits of processed jobs while respecting machine constraints. A first-in- first-out heuristic is applied to find an initial solution, and then a large neighborhood search procedure is employed to relax and re- optimize cumbersome solutions. A machine learning mechanism is also introduced to converge on the most efficient neighborhoods for the problem. Extensive computational results are presented based on data from an application involving the daily observation scheduling of a fleet of earth observing satellites. The method rapidly solves most problem instances to optimal or near optimal and shows a robust performance in sensitive analysis.

An adaptive large neighborhood search for the multi-point dynamic aggregation problem

The multi-point dynamic aggregation(MPDA)problem is a challenging real-world problem.In the MPDA problem,the demands of tasks keep changing with their inherent incremental rates,while a heterogeneous robot fleet is required to travel between these tasks to change the time-varying state of each task.The robots are allowed to collaborate on the same task or work separately until all tasks are completed.It is challenging to generate an effective task execution plan due to the tight coupling between robots abilities and tasks'incremental rates,and the complexity of robot collaboration.For effectiveness consideration,we use the variable length encoding to avoid redundancy in the solution space.We creatively use the adaptive large neighborhood search(ALNS)framework to solve the MPDA problem.In the proposed algorithm,high-quality initial solutions are generated through multiple problem-specific solution construction heuristics.These heuristics are also used to fix the broken solution in the novel integrated decoding-construction repair process of the ALNS framework.The results of statistical analysis by the Wilcoxon rank-sum test demonstrate that the proposed ALNS can obtain better task execution plans than some state-of-the-art algorithms in most MPDA instances.

Joint mission and route planning of unmanned air vehicles via a learning-based heuristic

Unmanned air vehicles(UAVs) have been regularly employed in modern wars to conduct different missions. Instead of addressing mission planning and route planning separately,this study investigates the issue of joint mission and route planning for a fleet of UAVs. The mission planning determines the configuration of weapons in UAVs and the weapons to attack targets, while the route planning determines the UAV’s visiting sequence for the targets. The problem is formulated as an integer linear programming model. Due to the inefficiency of CPLEX on large scale optimization problems, an effective learningbased heuristic, namely, population based adaptive large neighborhood search(P-ALNS), is proposed to solve the model. In P-ALNS, seven neighborhood structures are designed and adaptively utilized in terms of their historical performance. The effectiveness and superiority of the proposed model and algorithm are demonstrated on test instances of small, medium and large sizes. In particular, P-ALNS achieves comparable solutions or as good as those of CPLEX on small-size(20 targets)instances in much shorter time.

Solving vehicle routing problem with time windows using metaheuristic approaches

Purpose-Drugs are strategic products with essential functions in human health.An optimum design of the pharmaceutical supply chain is critical to avoid economic damage and adverse effects on human health.The vehicle-routing problem,focused on finding the lowest-cost routes with available vehicles and constraints,such as time constraints and road length,is an important aspect of this.In this paper,the vehicle routing problem(VRP)for a pharmaceutical company in Turkey is discussed.Design/methodology/approach-A mixed-integer programming(MIP)model based on the vehicle routing problem with time windows(VRPTW)is presented,aiming to minimize the total route cost with certain constraints.As the model provides an optimum solution for small problem sizes with the GUROBI®solver,for large problem sizes,metaheuristic methods that simulate annealing and adaptive large neighborhood search algorithms are proposed.A real dataset was used to analyze the effectiveness of the metaheuristic algorithms.The proposed simulated annealing(SA)and adaptive large neighborhood search(ALNS)were evaluated and compared against GUROBI®and each other through a set of real problem instances.Findings-The model is solved optimally for a small-sized dataset with exact algorithms;for solving a larger dataset,however,metaheuristic algorithms require significantly lesser time.For the problem addressed in this study,while the metaheuristic algorithms obtained the optimum solution in less than one minute,the solution in the GUROBI®solver was limited to one hour and three hours,and no solution could be obtained in this time interval.Originality/value-The VRPTW problem presented in this paper is a real-life problem.The vehicle fleet owned by the factory cannot be transported between certain suppliers,which complicates the solution of the problem.