ABSTRACT. This paper presents a breakout local search (BLS) heuristic algorithm for solving the heaviest k-subgraph problem - a combinatorial optimization graph problem with various practical applications. BLS explores the search space by alternating iteratively between local search phase and dedicated perturbation strategies. Focusing on the perturbation phase, the algorithm determines its jump magnitude and perturbation type according to the search history to obtain the most appropriate degree of diversification. Computational experiments are performed on a number of large random graphs. The experimental evaluations show that the results obtained by BLS are comparable to, and in most cases superior to, those of the current state-of-the-art approaches.

ABSTRACT. A heuristic approach is presented to solve a problem of planning maintenance work on the electrical network. The objective function to be minimized is non-convex, which makes the problem very difficult. The approach combines mathematical programming and local search. The initial solution is obtained by solving a simple mixed integer program that minimizes the linear part of the objective function. The solution is then improved by an iterative procedure based on solving mixed integer programs with modified objective function coefficients. Finally, the solution is further improved by a local search heuristic. This approach won the first prize in the senior category of the EURO/ROADEF 2020 challenge. Experimental results are presented which demonstrate the effectiveness of our approach on large instances provided by RTE (the French electricity transmission network).

ABSTRACT. This paper introduces an extended version of the min-Knapsack problem with compactness constraints (mKPC). The idea is to define penalty values for certain items when they are not selected in the knapsack. In addition to cost, weight, and compactness constraints in the mKPC, which require selected items to remain within close proximity, the min-Knapsack problem with compactness constraints and penalty values (mKPCP) incorporates penalty values for excluding certain items. The method outlined in this study leverages the learning mechanism of a metaheuristic approach, Fixed Set Search, integrating it with integer programming to address partial solutions throughout the process. To enhance the learning mechanism process, the initial population of solutions is generated through an algorithm that randomly creates solutions considering the compactness constraint and the item sequences, with the aim of enhancing diversity. The experiments were conducted also with zero-penalty values, transforming the mKPCP into the mKPC. The experiments indicate the proposed method yields promising outcomes across a diverse set of instances. The proposed approach does not rely heavily on any unique characteristics of the problem and could be adapted to other binary problems, including the minimum vertex cover problem and the facility location problem, with small adjustments.

ABSTRACT. If DSATUR heuristic was proven efficient for many instances of the vertex coloring problem, this article extends DSATUR with matheuristic operators to have better solutions, and also to understand better the inefficiency causes of DSATUR heuristic. Using an Integer Linear Programming formulation allows to have larger local greedy optimization. Matheuristics allow also to initialize DSATUR heuristics and matheuristics with cliques or a partial optimal coloring. Dual bounds are also obtained for large size instances, improving clique lower bounds given as input. Computational analyses are provided, highlighting the strengths and weaknesses of DATUR heuristic and matheuristics.

ABSTRACT. Hexaly Optimizer, previously known as LocalSolver, is a global solver relying on three components: a high-level modeling formalism, exact methods to obtain optimality proofs and a local search heuristic to find good solutions on large instances. The modeling formalism has been recently extended beyond the classical MILP and MINLP formalism by introducing set-based decisions. A list is decision variable that can be used to model an ordered sequence of clients in a routing model or tasks to perform on a resource in a scheduling model. Expressions built upon the list contents can represent the overall travel time in routing models or non-overlap constraints in disjunctive scheduling without having to create a quadratic number of expressions or constraints. The local search benefits from this high-level model by applying all the classical neighborhoods from the literature directly on the lists (insertion, removal, swap, k-opt, etc.). Finally, tighter bounds are obtained using dedicated reformulations that exploits the high-level information contained in the model. This talk will present this modeling formalism on routing and scheduling problems and gives performance results on standard benchmarks.

ABSTRACT. Many real-life manufacturing scenarios are concerned with the flexible assembly production problem in environments where the assembly operations are executed in multiple stages derived from the bills of materials of the final assemblies and can be executed on different eligible machines to produce batches of components. In this paper, we report the results of analyzing the differences between the behavior of trajectory and population-based metaheuristics when they are applied to the flexible assembly scheduling problem with batch splitting. We relied on the usage of two problem encodings and two perturbation operators, as well as on three metaheuristics: Simulated Annealing (SA), Tabu Search (TS), and an Evolutionary Algorithm (EA). We conducted an extended experimental analysis on several benchmarks corresponding to Flexible Jobshop Scheduling, 2 Stage Assembly Scheduling, and Flexible Assembly Scheduling. Our analysis reveals that the search pattern influences the performance of the scheduler, as significant differences have been observed between SA, TS, and EA, particularly when the run-time budget is limited.

ABSTRACT. Efficient management of berth allocation (BAP), quay crane allocation and transshipment operations is crucial for the optimization of container terminals. Though, to the most of our knowledge, there exist only a few papers that have focused on (BAP) in the specific area of ship-to-ship transshipment. This paper includes significant differences with the existing literature which lie: (1) in a dynamic approach for the problem by a relative positions formulation, and (2) by introducing constraints to address synchronization, simultaneous arrival. Considering the information about the pairs of transshipment relations as well as the characteristics of each vessel, the proposed Mixed-Integer Programming (MIP) problem determines the berthing position of each vessel, the berthing time and decides the most suitable method. We add some assumptions that allow to model the proposed problems where the number of moored ships in a certain planning horizon and the number of available quay cranes, are given. We used CPLEX to validate the novel MIP that we approximately solved, later, by the mean of NSGA-III. Finally, we conducted a sensitivity analysis and a comparative study assessing various parameters for their best settings, and we used a statistical analysis for crossover operators to decide for their best choice.

ABSTRACT. We consider a Job Shop Scheduling Problem with transport (JSPT) which consists in jointly scheduling machines and robots. In contrast with the literature, we assume that a transport operation may involve several robots simultaneously, which requires resource synchronization over time. We formulate this problem as a Mixed Integer Linear Programming (MILP) formulation. Then we propose a GRASP-ELS meta-heuristic and a local search procedure where we use a Bierwith’s sequence approach to evaluate a solution. In a numerical study, we have adapted instances from the literature to our problem. The meta-heuristic competes with the exact resolution providing high quality solution in reduced computation time, which lead us to consider that both the modeling and local search are accurate.

ABSTRACT. The S-labeling problem is a graph layout problem that assigns numeric labels to the vertices of a graph. It aims to minimize the sum of the minimum numeric label assigned to each pair of adjacent vertices. In this preliminary work, we propose the use of the Variable Neighborhood Search (VNS) framework to test different Shake procedures and Local Search methods for the problem. We compare our VNS variants with the state-of-the-art Population-based Iterated Greedy algorithm on a set of benchmark instances. The results show that our VNS methods can obtain competitive solutions with a low deviation, but they are not able to improve the best-known values. We discuss the strengths and weaknesses of our proposal and suggest some future research directions. This work lays the groundwork for future research into the S-Labeling problem using Variable Neighborhood Search.

ABSTRACT. The Weighted Total Domination Problem (WTDP) belongs to the family of dominating set problems. Given a weighted graph, the WTDP consists in selecting a total domination set D such that the sum of vertices and edges weights of the subgraph induced by D plus, for each vertex not in D, the minimum weight of its edge to a vertex in D is minimized. A total domination set D is a subset of vertices such that every vertex, is at least adjacent to one vertex in D. This problem arises in many real-life applications closely related to covering and independent set problems, however it remains computationally challenging due to its NP-hardness. This work presents a Variable Neighborhood Search procedure to tackle the WTDP. In addition, we develop a Biased Greedy Randomized Adaptive Search Procedure that keeps adding elements once a feasible solution is found in order to produce high-quality initial solutions. We perform extensive numerical analysis to look into the influence of the algorithmic components and to disclose the contribution of the elements and strategies of our method. Finally, the empirical analysis shows that our proposal outperforms the state-of-art results, supported by an statistical analysis.

ABSTRACT. This paper studies the relationship between three linear layout problems: minimum linear arrangement, cutwidth minimization, and bandwidth minimization. Our research suggests that, given their correlation, optimizing one problem could optimize the others. The Variable Neighborhood Search metaheuristic can take advantage of this, especially by switching problem formulations during the search process. The paper presents experiments analyzing different strategies and provides insights about their effectiveness. Our findings indicate that the proposed variant of Variable Neighborhood Search outperforms traditional single-process optimization methods in terms of both solution quality and computational efficiency.

ABSTRACT. For a given undirected graph G = (V, E) with a non-negative weight function w : E → R+ and subsets {G1, . . . , Gk} of V , the group Steiner tree (GST) problem consists of constructing a tree T = (VT , ET ) with minimal cost, where VT ⊆ V , ET ⊆ E, and T spans at least one node from each of the groups. We develop a VNS-based mathuristic approach for solving the GST problem. Our main contribution is that we propose a new problem-specific node release strategy that mimic the steps of a VNS-based heuristic. Instead of exploring different neighborhoods by combinatorially enumerating neighboring solutions, as in classical local search, we use a provably good integer linear programming formulation to solve a sequence of subproblems of the original problem. Our approach leads to an improvement over the state-of-the-art Gurobi solver both in terms of quality and runtime of the instances available in the literature.

ABSTRACT. In this talk we present a novel path relinking approach, called reactive path relinking (RPR), which hybridizes two of the most extended path relinking variants: interior path relinking and exterior path relinking. The RPR decides which of the two variants should use, depending of if solutions are similar or different, in order to diversity or intensify in the search space.

To apply this methodology an interesting facility location problem known as the bi-objective p-Median and p-Dispersion problem (BpMD problem). The BpMD problem seeks to locate p facilities to service a set of n demand points, and the goal is to minimize the total distance between facilities and demand points and, simultaneously, maximize the minimum distance between all pairs of hosted facilities.

Additionally, this new algorithm proposal is adapted to a multi-objective perspective since the considered problem is bi-objective. The task is to find a good approximation of the Pareto front. Computational results prove the superiority of the proposed algorithm over the best procedures found in the literature.

ABSTRACT. Arc Routing Problems typically deal with traversing a set of connecting edges or arcs in a network at the minimum possible cost. In this paper, we target the close enough model in which clients can be served from relatively close arcs, addressing some practical situations, such as inventory management or automated meter reading. We propose a heuristic to maximize the sum of profits of the clients served (penalized with the distance traveled). Our solving procedure, based on the VNS methodology, incorporates efficient search strategies to obtain high-quality solutions in short computational times, as required in practical applications. We study its improvement by coupling the method with Path Relinking as a post-processing. Our experimentation over a benchmark of previously reported instances shows the good performance of the heuristics as compared with a previous GRASP.

ABSTRACT. This talk offers an in-depth exploration of the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic and its integration with Path Relinking (PR) since its inception in 1999. GRASP with PR has emerged as a widely adopted approach for addressing challenging optimization problems. The talk covers the historical development of GRASP with PR, its underlying theoretical foundation, and recent advancements in the field. Additionally, it offers a critical assessment of various PR variants, including memory-based and randomized designs. We complement our theoretical descriptions with a practical analysis from the experimentation on two well known optimization problems: the linear ordering and the max-cut. By delivering valuable insights, this presentation empowers researchers and practitioners with the knowledge necessary to effectively take advantage of GRASP with PR in solving optimization problems. Attendees will gain a comprehensive understanding of the principles and applications of GRASP with PR, enabling them to make informed decisions in their optimization problems.

ABSTRACT. A metaheuristic algorithm for solving Capacitated Vehicle Routing Problem (CVRP) that is composed of neighborhood search and path relinking is proposed. Path relinking is a method to integrate intensification and diversification into the neighborhood search. We test several mechanisms of integration between neighborhood search and path relinking. Several variants of the mechanism give a significant improvement to the baseline algorithm. Furthermore, the best hybridization mechanism is found by performing a post-hoc analysis.

ABSTRACT. We have already mathematically formulated a CoveringSalesman Problem with Nodes and Segments (CSPNS). In CSPNS, a node distribution is given. In CSPNS, some nodes are selected from the given set, and a tour is constructed that visits these nodes. An objective of CSPNS is to identify the shortest tour that covers all given nodes by segments and nodes in the tour. In this study, to find good near-optimal solutions within a reasonable time frame, we propose a heuristic method using tabu search.

ABSTRACT. Hybridizing learning and optimization often improves existing algorithms in single-objective optimization. Indeed, high-quality solutions often contain relevant knowledge that can be used to guide the heuristic towards promising areas. Learning from the structure of solutions is challenging in combinatorial problems. Most of the time, local optima are considered for this task since they tend to contain more relevant structural information. If local optima generally contain more interesting information than other solutions, producing them requires a time-consuming process. In this paper, we investigate the interest of learning on local optima during the execution of a multi-objective algorithm. To this end, we consider a hybridized MOEA/D (a multi-objective genetic algorithm) with a knowledge discovery mechanism adapted to the problem solved and we conduct experiments on a bi-objective vehicle routing problem with time windows. The knowledge discovery mechanism extracts sequences of customers from solutions. The results show the benefit of using different strategies for the components of the knowledge discovery mechanism and the efficacy of extracting patterns from local optima for larger instances. An analysis of speed-up performance gives deeper conclusions about the use of local optima.

ABSTRACT. The vehicle routing problem with simultaneous pickup and delivery with time windows (VRPSPDTW) is an important variant of the vehicle routing problem which has received considerable attention among researchers in the last decade. The vast majority of solution methodologies for the VRPSPDTW have been applied to synthetic problem instances that bear little resemblance to routing problems found in the real world. Recently, 20 large-scale VRPSPDTW instances based on real customer data from the transportation company known as JD Logistics became publicly available as a new benchmark VRPSPDTW problem set.

In this paper, a memetic algorithm (MA), referred to as MA-BCRCD, is proposed for use on these real-world instances. The MA prioritizes efficient search and utilizes a crossover method which is shown to be more effective than that of the previous MA approach (known as MATE) applied to this set. MA-BCRCD finds new best known solutions for all 20 instances. It also performs better on average for all instances in comparison to the performance of MATE. The results and analysis provided in this study suggest that further improvements on this problem set are possible both in terms of solution quality and search efficiency.

ABSTRACT. Over the last years, hybrid genetic search (HGS) algorithms for the VRP and its variants have demonstrated encouraging results in particular with the use of a route-first-cluster-second heuristic. As an individual is represented by a “giant tour” (TSP Solution) in this method, the advantages are an easiness regarding the population management and crossover operators combined with an optimal split method for the transition from an individual to a VRP solution. In parallel progress in optimization using deep learning model have been significants, especially for the vehicle routing problem (VRP). The goal is to improve the efficiency of HGS by taking advantage of deep learning methods to evaluate cost directly on an individual, thus avoiding the need to switch search space and saving computational time. To this end, a reverse split method is used to switch freely between population and solution space to train the deep learning model using cost evaluation and feature extraction.

ABSTRACT. Event-interval sequences are defined as multivariate series of events that occur over time. The classification of event-interval sequences has gained increasing attention among researchers in the field of time series analysis due to their broad applicability, as for instance in healthcare and weather forecasting. This paper focuses on the optimized extraction of interpretable features from event-interval sequences to construct supervised classifiers. The current state-of-the-art is represented by e-lets, which are randomly sampled subsequences of event-intervals. We propose a new approach to interpretable classification of event-interval sequences based on sparse-lets, a novel generalization of e-lets. Our approach relies on genetic algorithms to learn sparse-lets, generating optimized and interpretable features. We evaluate the performance of our method through experiments conducted on benchmark datasets, and compare it against the state-of-the-art. Computational results show that our method is a viable competitor in terms of classification accuracy. Moreover, we show that our method generates simpler features than competing approaches, retaining only the most important information.

ABSTRACT. Time series analysis plays a critical role in data analytics, an effective modeling of nonlinear trends is essential for obtaining actionable results, notably for forecasting and missing values imputation. The segmentation of time series and the corresponding detection of change points stand out for their practical implications. This paper presents preliminary results of a study on the applicability of mathematical programming, and in particular matheuristics, to time series segmentation.

ABSTRACT. The Vehicle Routing Problem with Time Windows (VRPTW) is a widely recognized combinatorial optimization problem. Hosino et al. have reported that a Chaotic Search (CS) method, which uses the chaotic neurodynamics to escape from local minima, effective solves for the VRPTW. To enhance the solution search performance of the CS method, a Chaos Search method with Adaptive Penalty Coefficient (CS-APC) was proposed, and found to be effective for VRPTW. CS-APC improves the search performance by using the APC to broaden the solution search space, thus exploring diverse solutions. However, CS- APC had an issue with over-expanding the solution search space, even during the final stages of the search. To address this issue, we propose a new CS method that uses an Adaptive Penalty Coefficient with Temperature annealing (CS-APCT). CS-APCT gradually narrows down the solution search space and enhances the quality of the solution. Numerical experiments show that the proposed method offers up to a 22.45% improvement in an objective function value compared to the recent ant colony-based solution method. Additionally, it provides a solution that approximates the PSO-based solution method.

ABSTRACT. In recent years, Quantum Computing has been a source of tremendous excitement and innovation. The Quadratic Unconstrained Binary Optimization (QUBO) model is at the center of the excitement and innovation. In this paper, we aim to introduce a new quantum-inspired metaheuristic algorithm known as AdaptQUBO. This novel algorithm represents a fusion of diverse heuristic concepts, including tabu search, scatter search, and path-relinking. In particular, the adaptive search of the tabu tenure which is achieved in combination with different heuristics components enables AdaptQUBO to tackle different kinds of QUBO problem instances. Additionally, AdaptQUBO boasts parallelism which enables it to make good use of powerful and extended multi-thread abilities. To evaluate the performance of AdaptQUBO, we conducted extensive assessments on 122 large problem instances from benchmarks, including widely used QUBO and Max-Cut instances and less investigated random graph instances with different structures. We compare the results with the leading metaheuristic QUBO solver that reimplements various types of state-of-the-art heuristics and uses machine learning to select the best heuristic based on the characteristics of each problem. The computational results demonstrate that AdaptQUBO is very successful in solving large-scale QUBO problems and highly competitive in terms of both solution quality and computational efficiency.

ABSTRACT. We suggest employing graph sparsification as a pre-processing step for max cut programs using the QUBO solver. Quantum(-inspired) algorithms are recognized for their potential efficiency in handling quadratic unconstrained binary optimization (QUBO). Various meta-heuristic approaches, including those based on the Quantum Approximate Optimization Algorithm, have been suggested for addressing QUBO challenges in this context. Given that max cut is an NP-hard problem and can be readily expressed using QUBO, it stands out as an exemplary case to demonstrate the effectiveness of quantum(-inspired) QUBO approaches. Here, the non-zero count in the QUBO matrix corresponds to the graph's edge count. Given that many quantum(-inspired) solvers operate through cloud services, transmitting data for dense graphs can be costly. By introducing the graph sparsification method, we aim to mitigate these communication costs. Experimental results on classical and quantum-inspired solvers indicate that this approach substantially reduces communication overheads and yields an objective value close to the optimal solution.

ABSTRACT. From a metaheuristic viewpoint, Quantum Annealing can be seen as similar to simulated annealing but using the phenomenon of quantum tunnelling to escape local minima. In the Quantum Annealing paradigm, combinatorial optimization problems can be formulated as QUBO (Quadratic Unconstrained Binary Optimization), and QUBO has become the standard input language for all quantum and quantum-inspired annealing hardware and software solvers.

Complex constrained optimization problems are sometimes difficult to formulate in QUBO as two things have to be taken care of: the encoding of integers by Boolean variables and the representation of constraints in QUBO. It is therefore important to compare the performance of different QUBO models of the same problem, in order to investigate the path towards the most efficient QUBO formulation.

We propose in this paper to consider the well-known Travelling Salesman Problem (TSP) and to compare the performance of two different QUBO formulations for this problem. We experimented with several TSP instances from TSPLIB, and we present and compare in this paper the results for one-hot and domain-wall models that have been implemented on two quantum-inspired annealing QUBO solvers based on clusters of GPUs: the Fixstars Amplify Annealer Engine and the ABS QUBO solver.

ABSTRACT. Decision-making software is used to automatically make informed decisions by leveraging large amounts of data. Advances in machine learning have extended the implementation of these systems to processes that have a significant impact on the lives of people, such as credit scoring, employment applications, or insurance rates. Due to their impact, these systems must guarantee fairness from social and legal points of view, operating in a non-discriminatory manner. Several methods have been studied in the literature to improve the fairness of these systems, but often at the cost of accuracy. In this work, we propose two methods based on the Variable Neighborhood Search scheme to optimize the fairness of machine learning models after the training phase. In particular, we apply the proposed approaches to optimize Linear Regression models, which are frequently used in decision-making software. The proposed methods are competitive with a state-of-the-art Hill Climbing algorithm, using a set of publicly available instances.

ABSTRACT. This paper studies the influence of combining exact algorithms with heuristic procedures for the optimization of the Order Batching Problem. The problem looks to minimize the time that an operator needs to pick all items from a set of orders within a warehouse, when all orders are known before starting the picking process. It involves solving different tasks, such as batching the orders in groups or routing the picker through the warehouse. In this proposal a previous General Variable Neighborhood Search proposal for the batching task has been integrated with exact algorithms for the routing task. Several experiments have been designed to test the performance of the constructed algorithms

ABSTRACT. The p-center problem, which is NP-hard, aims to select p centers from a set of candidates to serve all clients while minimizing the maximum distance between each client and its assigned center. To solve this challenging optimization problem, we transform the p-center problem into a series of decision subproblems, and propose a vertex weighting-based double-tabu search (VWDT) algorithm. It integrates a vertex weighting strategy and a double-tabu search which combines both solution-based and attribute-based tabu strategies to help the search to escape from the local optima trap. Computational experiments on totally 510 public instances in the literature show that VWDT is highly competitive comparing to the state-of-the-art algorithms. Specifically, VWDT improves the previous best known results for 84 large instances and matches the best results for all the remaining ones. Apart from the improvements in solution quality, VWDT is much faster than other state-of-the-art algorithms in the literature, especially on some large instances. Furthermore, we perform additional experiments to analyze the impact of the key components to VWDT, such as the vertex weighting and the double-tabu search strategy.

ABSTRACT. Metaheuristics, such as tabu search, simulated annealing, and ant colony optimization, have demonstrated remarkable success in solving combinatorial optimization problems across diverse domains. Despite their efficacy, the lack of understanding of why these metaheuristics work well has sparked criticism, emphasizing the need for a deeper exploration of their components.

This paper focuses on the tabu list component within tabu search, aiming to unravel its relative importance in influencing overall algorithmic performance. We employ a white-box framework to investigate various methods for handling the tabu list, including short-term and long-term strategies. We conduct experiments to compare the performance of different tabu list strategies using a well-known benchmark problem, the Permutation Flow Shop Scheduling Problem. The results show that the tabu list component does not provide significant differences in the final result. Nevertheless, the strategies exhibit diverse search trajectories related with distinct prohibition structures.

ABSTRACT. We investigate a new collaborative operating room scheduling problem (CORS) with consideration of the downstream recovery beds. For solving this challenging problem, we develop an effective multi-operator driven iterated tabu search (MOITS) algorithm to achieve a good search balance between intensification and diversification. The greedy initial solution construction procedure employs a priority scoring rule to sequence patients to obtain a high-quality initial schedule. The multi-operator driven tabu search procedure employs four move operators to manipulate surgeries in different OR time blocks, two move operators to change recovery hospitals of the scheduled surgeries, and one move operator to change specialties of the OR time blocks. New evaluation functions are designed for the recovery beds related move operators to allow capacity violations during the search. The elite set guided adaptive perturbation procedure uses historical information from a pool of best found solutions to adjust the OR time blocks assigned to each specialty. Experimental results indicate that our proposed MOITS algorithm is capable of finding much better solutions with an order-of-magnitude time reduction than Gurobi across problems of different sizes. Additional analysis are performed to shed light on the merits of the proposed strategies.

ABSTRACT. The advances in information and communication technology are changing the way people move. Companies that offer demand-responsive transportation services have the opportunity to reduce their costs and increase their revenues through collaboration, while at the same time reducing the environmental impact of their operations. We consider the case of companies, offering a shared taxi service, that are involved in horizontal collaboration, and present mixed integer programming models for the optimization of their routes that embed constraints aimed at controlling the workload exchange of each company with others. These constraints bound the workload exchange in terms of traveled time and/or served customers to be less than thresholds agreed in advance by the companies. As models are too difficult to solve for realistic size instances, an efficient Adaptive Large Neighborhood Search heuristic is presented for their solution. Computational results show the effectiveness of the ALNS algorithm and the benefits of the collaboration. The ALNS heuristic has an excellent performance, with an average error of 0.3%. Moreover, the optimization models allow a saving, with respect to a non-collaboration setting, of up to 30%, very close to the upper bound on the possible savings that is obtained in the unconstrained setting.

ABSTRACT. This paper investigates a specific instance of the static repositioning problem within station-based bike-sharing systems. Our study incorporates operational and damaged bikes, a heterogeneous fleet, and multiple visits between stations and the depot. The objective is to minimize the weighted sum of the deviation from the target number of bikes for each station, the number of damaged bikes not removed, and the total time used by vehicles. To solve this problem, we propose a matheuristic approach based on a randomized multi-start algorithm integrated with an integer programming model for optimizing the number of operatives and damaged bikes that will be moved between stations and/or the depot (loading instructions). The algorithm's effectiveness was assessed using instances derived from real-world data, yielding encouraging results. Furthermore, we adapted our algorithm to a simpler problem studied in the literature, achieving competitive outcomes compared to other existing methods. The experimental results in both scenarios demonstrate that this algorithm can generate high-quality solutions within a short computational time.

ABSTRACT. Municipalities all around the globe struggle to cope with over-utilized street networks due to the ongoing trend of urbanization. In this context, mobility-on-demand systems offer flexible ride-sharing options with the goal of reducing the inefficient use of private cars. Due to the scale of operations, the problem of serving customer requests given a fleet of ride-sharing vehicles is often considered from a dynamic, short-term viewpoint. To study the large-scale system optimum, we tackle the issue of scaling in our research and consider a longer-term deterministic setting with up to 21 thousand requests and one thousand vehicles. We develop an efficient metaheuristic comprising state-of-the-art components in a decomposition-based approach, focusing on optimizing service level and operational costs. Our core search loop starts by decomposing our problem based on a complete solution. These partitions are then searched and improved in parallel using a ruin-and-recreate approach. Recombination is performed by extracting pooling decisions based on the decisions from the partial solutions and solving a k-disjoint shortest path problem. We generate and conduct experiments on the well-known New York taxi data set and show the efficacy of our approach for large instances of the related pickup and delivery problem with time windows.

ABSTRACT. The use of drones in last-mile delivery services has attained significant interest due to the need for fast delivery. In addition, drones have the potential to reduce the cost associated with last-mile deliveries. However, restrictions such as payload capacity, range limits, and legal regulations have restricted the effective operational range of drones. To assist in alleviating these operational limitations, integrating a conventional delivery truck with drones to form a truck-drone delivery system, has received significant attention in the literature. This paper presents a scenario in which a single drone works in tandem with a single truck to serve customers. The drone can perform multiple deliveries in a single route, and the objective is to minimize the total traveling costs of both vehicles. An integer linear programming (ILP) model is developed and solved to optimality for small instances using the exact solution method. Considering the complexity of the ILP model, a variable neighborhood search (VNS) algorithm is introduced and assessed using small and large instances. In addition, a modified VNS involving a new neighborhood selection strategy is proposed and compared to the basic VNS. Both algorithms generate solutions in a short computational time for instances with up to 100 customer nodes.