In this paper, we introduce a clustering and scheduling problem on a production line modeled as a single machine. A set of jobs (some of them being urgent) must be partitioned into clusters, and a robust (with respect to a min–max criterion) cyclic sequencing of the clusters must be determined (i.e., the product-wheel paradigm is employed). Each cluster has to satisfy two constraints: the setup constraint (i.e., only jobs with small setup times between them are allowed in the cluster) and the capacity constraint (i.e., the setup and processing times in the cluster cannot exceed a given shift duration). Three objective functions are minimized in a lexicographic fashion: (1) the number of urgent clusters (i.e., containing at least one urgent job); (2) the total number of clusters; (3) a worst-case scenario with respect to the setup among clusters. In other words, makespan and setup penalties are considered. Graph-coloring models and methods are designed for (1) and (2), whereas traveling-salesman approaches are introduced for (3). The considered problem was proposed by a micro-machining company located in Switzerland, named DIXI polytool. In order to cover their industrial needs, the company imposed very strict computing-time limitations (a few minutes only), and was able to provide realistic instances with different characteristics. Three methods are compared in our experiments: an integer linear model (with CPLEX), a constructive heuristic that represents a current-practice rule, and a metaheuristic relying on various tabu-search procedures. Results show the efficiency (with respect to quality and speed) of our metaheuristic, and managerial insights are provided.

Abstract We propose a model for solving a parcel delivery problem with a fleet of trucks embedded with drones. When appropriate, drones are loaded with a parcel, launched directly from the truck, and sent to a client. Afterward, the drones autonomously return to the truck to be replenished and recharged. Inspired by the case of a large European logistics provider, the proposed modeling framework confronts realistic delivery problems involving time windows, limited drone autonomy, and the eligibility of clients to be served by drones. The considered global cost function includes fixed daily vehicle fares, driver wages, and the fuel and electricity consumption to power trucks and drones. To solve the problems at hand, we propose a mixed‐integer linear programming formulation and an adaptive large neighborhood search. Moreover, we introduce an efficient modeling framework to manage the numerous synchronization constraints induced by the simultaneous use of trucks and drones. We analyze the benefits of this new transportation concept for delivery problems involving up to 100 parcels. Results show that truck‐and‐drone solutions can reduce costs up to 34% compared to traditional truck‐only delivery. From a managerial perspective, we show that a certain percentage of client locations must be reachable by drone to make truck‐and‐drone solutions competitive (i.e., if the fixed costs of the drones are compensated for by the savings on truck routes) and compare the cost structures of truck‐and‐drone versus truck‐only solutions.

Given a fleet of identical vehicles and a set of n clients to be served from a single depot, the well-known vehicle routing problem (VRP) consists in serving each client (with a deterministic demand) once with a unique vehicle, with the aim of minimizing the total traveled distance. In this work, the basic VRP is extended within a medical environment, leading to MVRP (for medical VRP). Indeed, the depot is typically a laboratory for blood analysis, and a client is assumed to be a medical location at which blood samples should be picked up by a vehicle. In order to have efficient tests at the laboratory, at most 90 minutes should elapse between the release time of the blood sample and the delivery time at the laboratory. In addition, only a proportion of the demand is known in advance and the travel times depend on the traffic conditions. A fleet of non-identical vehicle is considered (with different speeds and capacities), and each location has to be visited anytime a blood sample is available. Finally, medical items should be daily delivered from the laboratory to some medical locations. A transportation cost function with three components has to be minimized. Solution methods are proposed, which are able to account for all the specific features of the problem. The experiments highlight the benefit of considering diversion opportunities (which consists in diverting a vehicle away from its planned destinations).

We study a new multiobjective job scheduling problem on nonidentical machines with applications in the car industry, inspired by the problem proposed by the car manufacturer Renault in the ROADEF 2005 Challenge. Makespan, smoothing costs and setup costs are minimized following a lexicographic order, where smoothing costs are used to balance resource utilization. We first describe a mixed integer linear programming (MILP) formulation and a network interpretation as a variant of the well‐known vehicle routing problem. We then propose and compare several solution methods, ranging from greedy procedures to a tabu search and an adaptive memory algorithm. For small instances (with up to 40 jobs) whose MILP formulation can be solved to optimality, tabu search provides remarkably good solutions. The adaptive memory algorithm, using tabu search as an intensification procedure, turns out to yield the best results for large instances. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(3), 246–261 2016

Ant algorithms are well-known metaheuristics which have been widely studied and used since two decades. Generally, an ant is a constructive heuristic able to build a solution from scratch. However, other types of ant algorithms have recently emerged: the discussion is thus not limited by the common framework of the constructive ant algorithms. The goal of this paper is on the one hand to classify and benchmark the ant algorithms, and on the other hand to put forward the successful elements of these methods. Moreover, the performance of the different types of ant algorithms is evaluated according to several criteria, and not only according to the quality of the obtained solutions.

We propose a new heuristic for nonlinear global optimization combining a variable neighborhood search framework with a modified trust-region algorithm as local search. The proposed method presents the capability to prematurely interrupt the local search if the iterates are converging to a local minimum that has already been visited or if they are reaching an area where no significant improvement can be expected. The neighborhoods, as well as the neighbors selection procedure, are exploiting the curvature of the objective function. Numerical tests are performed on a set of unconstrained nonlinear problems from the literature. Results illustrate that the new method significantly outperforms existing heuristics from the literature in terms of success rate, CPU time, and number of function evaluations.