A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure

A phylogeny is a tree that relates taxonomic units, based on their similarity over a set of characters. The phylogeny problem consists in finding a phylogeny with the minimum number of evolutionary steps. We propose a new neighborhood structure for the phylogeny problem. A greedy randomized adaptive search procedure heuristic based on this neighborhood structure and using variable neighborhood descent for local search is described. Computational results on randomly generated and benchmark instances are reported, showing that the new heuristic is quite robust and outperforms the other algorithms in the literature in terms of solution quality and time‐to‐target value.     

Two‐node‐connected star problem

In this study, a two‐node‐connected star problem (2NCSP) is introduced. We are given a simple graph and internal and external costs for each link of the graph. The goal is to find the minimum‐cost spanning subgraph, where the core is two‐node‐connected and the remaining external nodes are connected to the core. First, we show that the 2NCSP belongs to the class of NP‐hard computational problems. Therefore, a greedy randomized adaptive search procedure (GRASP) heuristic is developed, enriched with a variable neighborhood descent (VND). The neighborhood structures include exact integer linear programming models to find the best paths and two‐node‐connected replacements, as well as a shaking operation in order to prevent being trapped in a local minima. The ring star problem (RSP) represents a relevant model in network optimization, where the core is a ring instead of an arbitrary two‐node‐connected graph. We contrast our GRASP/VND methodology with a previous reference work on the RSP in order to highlight the effectiveness of our heuristic. The heuristic is competitive, and the best results produced for several instances so far are under study. In this study, a discussion of the results and trends for future work are provided.     

Heuristics for the capacitated dispersion problem

In this paper, we investigate the adaptation of the greedy randomized adaptive search procedure (GRASP) and variable neighborhood descent (VND) methodologies to the capacitated dispersion problem. Dispersion and diversity problems arise in the placement of undesirable facilities, workforce management, and social media, among others. Maximizing diversity deals with selecting a subset of elements from a given set in such a way that the distance among the selected elements is maximized. We target here a realistic variant with capacity constraints for which a heuristic with a performance guarantee was previously introduced. In particular, we propose a hybridization of GRASP and VND implementing within the strategic oscillation framework. To evaluate the performance of our heuristic, we perform extensive experimentation to first set key search parameters, and then compare the final method with the previous heuristic. Additionally, we propose a mathematical model to obtain optimal solutions for small‐sized instances, and compare our solutions with the well‐known LocalSolver software.     

An extended Akers graphical method with a biased random‐key genetic algorithm for job‐shop scheduling

This paper presents a local search, based on a new neighborhood for the job‐shop scheduling problem, and its application within a biased random‐key genetic algorithm. Schedules are constructed by decoding the chromosome supplied by the genetic algorithm with a procedure that generates active schedules. After an initial schedule is obtained, a local search heuristic, based on an extension of the 1956 graphical method of Akers, is applied to improve the solution. The new heuristic is tested on a set of 205 standard instances taken from the job‐shop scheduling literature and compared with results obtained by other approaches. The new algorithm improved the best‐known solution values for 57 instances.     

Skewed general variable neighborhood search for the location routing scheduling problem

The integrated location routing scheduling problem is a variant of the well-known location routing problem. The location routing problem consists in selecting a set of depots to open and in building a set of routes from these depots, to serve a set of customers at minimum cost. In this variant, a vehicle can perform more than a single route in the planning period. As a consequence, the routes have to be scheduled within the workdays of each vehicle. The problem arises typically when routes are constrained to have a short duration. It happens for example within the boundaries of small geographic areas or in the transportation of perishable goods. In this paper, we propose a skewed general variable neighborhood search based heuristic to solve it. The algorithm is tested extensively and we show that it is efficient and provides the proven optimal solution in a significant number of cases. Moreover, it clearly outperforms a multi-start VND based heuristic that uses the same neighborhood structures.     

An adaptive large neighborhood search heuristic for the share-a-ride problem

The Share-a-Ride Problem (SARP) aims at maximizing the profit of serving a set of passengers and parcels using a set of homogeneous vehicles. We propose an adaptive large neighborhood search (ALNS) heuristic to address the SARP. Furthermore, we study the problem of determining the time slack in a SARP schedule. Our proposed solution approach is tested on three sets of realistic instances. The performance of our heuristic is benchmarked against a mixed integer programming (MIP) solver and the Dial-a-Ride Problem (DARP) test instances. Compared to the MIP solver, our heuristic is superior in both the solution times and the quality of the obtained solutions if the CPU time is limited. We also report new best results for two out of twenty benchmark DARP instances.     

Large neighborhood search for the bike request scheduling problem

This paper introduces an efficient algorithm for the bike request scheduling problem (BRSP). The BRSP is built around the concept of request, defined as the pickup or dropoff of a number of identical items (bikes) at a specific station, within a certain time window, and with a certain priority. The aim of the BRSP is to sequence requests on (and hence determine the routes of) a set of vehicles, in such a way that the sum of the priorities of the executed requests is maximized, all time windows are respected, and the capacity of the vehicles is not exceeded. The generation of the set of requests is explicitly not a part of the problem definition of the BRSP. The primary application of the BRSP, from which it derives its name, is to determine the routes of a set of repositioning vehicles in a bike sharing system, although other applications exist. The algorithm introduced in this paper is based on a set of related greedy randomized adaptive search procedure followed by variable neighborhood descent (GRASP + VND) operators embedded in a large neighborhood search (LNS) framework. Since this paper presents the first heuristic for the BRSP, a computational comparison to existing approaches is not possible. We therefore compare the solutions found by our LNS heuristic to those found by an exact solver (Gurobi). These experiments confirm that the proposed algorithm scales to realistic dimensions and is able to find near‐optimal solutions in seconds.     

A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery

Vehicle routing problem (VRP) is an important and well-known combinatorial optimization problem encountered in many transport logistics and distribution systems. The VRP has several variants depending on tasks performed and on some restrictions, such as time windows, multiple vehicles, backhauls, simultaneous delivery and pick-up, etc. In this paper, we consider vehicle routing problem with simultaneous pickup and delivery (VRPSPD). The VRPSPD deals with optimally integrating goods distribution and collection when there are no precedence restrictions on the order in which the operations must be performed. Since the VRPSPD is an NP-hard problem, we present a heuristic solution approach based on particle swarm optimization (PSO) in which a local search is performed by variable neighborhood descent algorithm (VND). Moreover, it implements an annealing-like strategy to preserve the swarm diversity. The effectiveness of the proposed PSO is investigated by an experiment conducted on benchmark problem instances available in the literature. The computational results indicate that the proposed algorithm competes with the heuristic approaches in the literature and improves several best known solutions.     

Minimizing total tardiness on a single machine with controllable processing times

The concept of time-cost trade-off is commonly considered in PERT/CPM, but it is seldom considered in the scheduling area. Such concept implies that the processing times of jobs are controllable by increasing or decreasing the available resources, such as manpower and equipment. In this paper, we focus on the single machine total tardiness problem with controllable processing times. First, a mixed-integer programming (MIP) model is formulated to find the optimal solution. Then, we propose both a linear programming model and a net benefit of compression (NBC) algorithm to obtain a set of optimal amounts of compression for a given sequence. To solve medium- to large-size problem instances, we develop a heuristic based on the NBC algorithm. To verify the proposed heuristic, the MIP model is used as a comparison for small-size problem instances, whereas for medium- to large-size instances the variable neighborhood search, a useful local search method, is employed. Computational results show that the proposed heuristic has a good performance.     

A comparison of five heuristics for the multiple depot vehicle scheduling problem

Given a set of timetabled tasks, the multi-depot vehicle scheduling problem consists of determining least-cost schedules for vehicles assigned to several depots such that each task is accomplished exactly once by a vehicle. In this paper, we propose to compare the performance of five different heuristics for this well-known problem, namely, a truncated branch-and-cut method, a Lagrangian heuristic, a truncated column generation method, a large neighborhood search heuristic using truncated column generation for neighborhood evaluation, and a tabu search heuristic. The first three methods are adaptations of existing methods, while the last two are new in the context of this problem. Computational results on randomly generated instances show that the column generation heuristic performs the best when enough computational time is available and stability is required, while the large neighborhood search method is the best alternative when looking for good quality solutions in relatively fast computational times.     

A bi‐objective mathematical model for product allocation in block stacking warehouses

Put‐away and picking operations in warehouses play a critical role in determining operating costs and customer response time. While the place where products are put away has an important effect on picking efficiency due to accessibility, it also affects space usage, which is critical for space availability and space costs. Hence, this study focuses on put‐away operations in pallet‐in pallet‐out block stacking warehouses. We develop a unique bi‐objective mathematical model and a constructive heuristic algorithm to allocate products to storage lanes while considering two objectives simultaneously: minimizing total travel distance and maximizing average storage usage. We test our model and heuristic through a real company case study and randomly generated large‐sized problem instances. We show that the model and heuristic offer better storage usage with reduced travel distance than the company's approach when the two objectives have equal weight. We also present a set of nondominated solutions for each problem instance. We present that the heuristic seems beneficial for the warehouse industry due to its short run time and effective solutions.     

Less is more approach: basic variable neighborhood search for the obnoxious p‐median problem

The goal of the less is more approach (LIMA) for solving optimization problems that has recently been proposed in Mladenovi? et al. (2016) is to find the minimum number of search ingredients that make a heuristic more efficient than the currently best. In this paper, LIMA is successfully applied to solve the obnoxious p‐median problem (OpMP). More precisely, we developed a basic variable neighborhood search for solving the OpMP, where the single search ingredient, the interchange neighborhood structure, is used. We also propose a new simple local search strategy for solving facility location problems, within the interchange neighborhood structure, which is in between the usual ones: first improvement and best improvement strategies. We call it facility best improvement local search. On the basis of experiments, it appeared to be more efficient and effective than both first and best improvement. According to the results obtained on the benchmark instances, our heuristic turns out to be highly competitive with the existing ones, establishing new state‐of‐the‐art results. For example, four new best‐known solutions and 133 ties are claimed in testing the set with 144 instances.     

Two-machine flowshop scheduling with flexible operations and controllable processing times

We consider a two-machine flowshop scheduling problem with identical jobs. Each of these jobs has three operations, where the first operation must be performed on the first machine, the second operation must be performed on the second machine, and the third operation (named as flexible operation) can be performed on either machine but cannot be preempted. Highly flexible CNC machines are capable of performing different operations. Furthermore, the processing times on these machines can be changed easily in albeit of higher manufacturing cost by adjusting the machining parameters like the speed and/or feed rate of the machine. The overall problem is to determine the assignment of the flexible operations to the machines and processing times for each operation to minimize the total manufacturing cost and makespan simultaneously. For such a bicriteria problem, there is no unique optimum but a set of nondominated solutions. Using ?-constraint$?\mathrm{-}\mathrm{constraint}$ approach, the problem could be transformed to be minimizing total manufacturing cost for a given upper limit on the makespan. The resulting single criterion problem can be reformulated as a mixed integer nonlinear problem with a set of linear constraints. We use this formulation to optimally solve small instances of the problem while a heuristic procedure is constructed to solve larger instances in a reasonable time.     

A hybrid data mining heuristic to solve the point‐feature cartographic label placement problem

A clean map visualization requires the fewest possible overlaps and depends on how labels are attached to point features. In this paper, we address the cartographic label placement variant problem whose objective is to label a set of points maximizing the number of conflict‐free points. Thus, we propose a hybrid data mining heuristic to solve the point‐feature cartographic label placement problem based on a clustering search (CS) heuristic, a state‐of‐the‐art method for this problem. Although several works have investigated the combination of data mining and multistart metaheuristics, this is the first time data mining has been used to improve CS and simulated annealing based heuristics. Computational experiments showed that the proposed hybrid heuristic was able to reach better cost solutions than the original strategy, with the same time effort. The proposed heuristic also could find almost all known optimal solutions and improved most of the best results for the set of large instances reported so far in the literature.     

An MO‐GVNS algorithm for solving a multiobjective hybrid flow shop scheduling problem

This paper addresses the multiobjective hybrid flow shop (MOHFS) scheduling problem. In the MOHFS problem considered here, we have a set of jobs that must be performed in a set of stages. At each stage, we have a set of unrelated parallel machines. Some jobs may skip stages. The evaluation criteria are the minimizations of makespan, the weighted sum of the tardiness, and the weighted sum of the earliness. For solving it, an algorithm based on the multiobjective general variable neighborhood search (MO‐GVNS) metaheuristic, named adapted MO‐GVNS, is proposed. This work also presents and compares the results obtained by the adapted MO‐GVNS with those of four other algorithms: multiobjective reduced variable neighborhood search, nondominated sorting genetic algorithm II (NSGA‐II), and NSGA‐III, and another MO‐GVNS from the literature. The results were evaluated based on the Hypervolume, Epsilon, and Spacing metrics, and statistically validated by the Levene test and confidence interval charts. The results showed the efficiency of the proposed algorithm for solving the MOHFS problem.     

一种求解多校多车型校车路径问题的元启发算法

针对多种车型可用的多校校车路径问题(SBRP),建立数学模型,并提出了一种迭代局部搜索(ILS)元启发算法进行求解。该算法引入并改进了带时间窗的装卸一体化问题(PDPTW)求解中的点对邻域算子,并使用可变邻域下降搜索(VND)完成局部提升。局部提升过程中,设计一种基于路径段的车型调整策略,尽可能地调整车型,降低成本,并允许接受一定偏差范围内的邻域解以保证搜索的多样性。对于局部提升得到的最好解,使用多点移动方法对其进行扰动,以避免算法过早陷入局部最优。在国际基准测试案例上分别测试多校混载和不混载模式下算法的性能,实验结果验证了设计算法的有效性。进一步使用提出的算法求解单车型多校SBRP问题,并与后启发算法、模拟退火算法和记录更新法等算法进行比较,实验结果表明该算法仍然能够获得较好的优化效果。     

An integration of mixed VND and VNS: the case of the multivehicle covering tour problem

The multivehicle covering tour problem (m‐CTP) is a transportation problem with different kinds of locations, where a set of locations must be visited while another set must be close enough to planned routes. Given two sets of vertices V and W, where V represents the set of vertices that may be visited and W is a set of vertices that must be covered by up to m vehicles, the m‐CTP problem is to minimize vehicle routes on a subset of V including T, which represents the subset of vertices that must be visited through the use of potential locations in V. The variant of m‐CTP without a route‐length constraint is treated in this paper. To tackle this problem, we propose a variable neighborhood search heuristic based on variable neighborhood descent method. Experiments were conducted using the datasets based on traveling salesman problem library instances.     

Heuristics for tactical time slot management: a periodic vehicle routing problem view

In this study, we consider a tactical problem where a time slot schedule for delivery service over a given planning horizon must be selected in each zone of a geographical area. A heuristic search evaluates each schedule selection by constructing a corresponding tactical routing plan of minimum cost based on demand and service time estimates. At the end, the schedule selection leading to the best tactical routing plan is selected. The latter can then be used as a blueprint when addressing the operational problem (i.e., when real customer orders are received and operational routes are constructed). We propose two heuristics to address the tactical problem. The first heuristic is a three‐phase approach: a periodic vehicle routing problem (PVRP) is first solved, followed by a repair phase and a final improvement phase where a vehicle routing problem (VRP) with time windows is solved for each period of the planning horizon. The second heuristic tackles the problem as a whole by directly solving a PVRP with time windows. Computational results compare the two heuristics under various settings, based on instances derived from benchmark instances for the VRP with time windows.     

Generalized mixed integer and VNS heuristic approach to solving the multisize containers drayage problem

This paper addresses the problem of vehicle routing in drayage operations, where vehicles can carry containers of different sizes. The multisize container drayage problem with time windows is modeled as a multiple matching problem and formulated as a mixed integer linear program (MILP) model. The proposed MILP model determines optimal pickup and delivery routes of vehicles and is applicable to any type of vehicles capable of simultaneously transporting any arbitrary number of 20‐ and 40‐ft containers. To solve larger sized problems, we proposed a variable neighborhood search (VNS) heuristic. Both MILP and VNS approaches have been tested on numerous test instances and their performances are reported.     

A tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine

This paper introduces a tabu search heuristic for a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The problem consists in scheduling a set of dependent jobs, where the transition between two jobs comprises an unrestricted setup that can be performed at any time, and a restricted setup that must be performed outside of a given time interval which repeats daily in the same position. The setup time between two jobs is thus a function of the completion time of the first job. The tabu search heuristic relies on shift and swap moves, and a surrogate objective function is used to speed-up the neighborhood evaluation. Computational experiments show that the proposed heuristic consistently finds better solutions in less computation time than a recent branch-and-cut algorithm. Furthermore, on instances where the branch-and-cut algorithm cannot find the optimal solution, the heuristic always identifies a better solution.