Ant colony optimization algorithm to solve for the transportation problem of cross-docking network

This paper addresses the transportation problem of cross-docking network where the loads are transferred from origins (suppliers) to destinations (retailers) through cross-docking facilities, without storing them in a distribution center (DC). We work on minimizing the transportation cost in a network by loading trucks in the supplier locations and then route them either directly to the customers or indirectly to cross-docking facilities so the loads can be consolidated. For generating a truck operating plan in this type of distribution network, the problem was formulated using an integer programming (IP) model and solved using a novel ant colony optimization (ACO) algorithm. We solved several numerical examples for verification and demonstrative purposes and found that our proposed approach finds solutions that significantly reduce the shipping cost in the network of cross-docks and considerably outperform Branch-and-Bound algorithm especially for large problems.     

Coupling a memetic algorithm to simulation models for promising multi-period asset allocations

The use of simulation models to manage and regulate property–liability insurers has gained in popularity over the last decade. This paper introduces a hybridized search optimization algorithm, also known as a Memetic Algorithm, for use with these insurer simulation models. The proposed algorithm combines the merits of both local and global search optimization techniques, and provides an efficient and robust approach for insurance model application. Our research investigated whether this enhanced optimization algorithm could further improve the results of a simulation model. As part of this investigation, a company-wide simulation model of a property–liability insurer was coupled with the proposed hybrid algorithm to tackle a typical multi-period asset allocation problem. The resulting asset allocations obtained by the proposed memetic algorithm coupled with the simulation model demonstrated better results than currently available investment strategies. The significant and robust improvements put forth in the present research demonstrate the great potential of our multi-phase hybrid algorithm in enhancing simulation model capabilities.     

Multistart Iterated Tabu Search for Bandwidth Coloring Problem

This paper presents a Multistart Iterated Tabu Search (MITS) algorithm for solving Bandwidth Coloring Problem (BCP) and Bandwidth MultiColoring Problem (BMCP). The proposed MITS algorithm exhibits several distinguishing features, such as integrating an Iterated Tabu Search (ITS) algorithm with a multistart method and a problem specific perturbation operator. Tested on two sets of 66 public benchmark instances widely used in the literature, the MITS algorithm achieves highly competitive results compared with the best performing algorithms, improving the previous best known results for 22 instances while matching the previous best known results for 39 ones. Furthermore, two important features of the proposed algorithm are analyzed.     

Minimising maximum response time

The minmax response time problem (mRTP) is a scheduling problem that has recently appeared in the literature and can be considered as a fair sequencing problem. This kind of problems appears in a wide range of real-world applications in mixed-model assembly lines, computer systems, periodic maintenance and others. The mRTP arises whenever products, clients or jobs need to be sequenced in such a way that the maximum time between the points at which they receive the necessary resources is minimised. The mRTP has been solved in the literature with a greedy heuristic. The objective of this paper is to improve the solution of this problem by means of exact and heuristic methods. We propose one mixed integer linear programming model, nine local search procedures and five metaheuristic algorithms. Extensive computational experiments are carried out to test them.     

Iterative approaches for solving a multi-objective 2-dimensional vector packing problem

In this paper, we address a bi-objective 2-dimensional vector packing problem (Mo2-DBPP) that calls for packing a set of items, each having two sizes in two independent dimensions, say, a weight and a height, into the minimum number of bins. The weight corresponds to a “hard” constraint that cannot be violated while the height is a “soft” constraint. The objective is to find a trade-off between the number of bins and the maximum height of a bin. This problem has various real-world applications (computer science, production planning and logistics). Based on the special structure of its Pareto front, we propose two iterative resolution approaches for solving the Mo2-DBPP. In each approach, we use several lower bounds, heuristics and metaheuristics. Computational experiments are performed on benchmarks inspired from the literature to compare the effectiveness of the two approaches.     

Enhancing data parallelism for Ant Colony Optimization on GPUs

Graphics Processing Units (GPUs) have evolved into highly parallel and fully programmable architecture over the past five years, and the advent of CUDA has facilitated their application to many real-world applications. In this paper, we deal with a GPU implementation of Ant Colony Optimization (ACO), a population-based optimization method which comprises two major stages: tour construction and pheromone update. Because of its inherently parallel nature, ACO is well-suited to GPU implementation, but it also poses significant challenges due to irregular memory access patterns. Our contribution within this context is threefold: (1) a data parallelism scheme for tour construction tailored to GPUs, (2) novel GPU programming strategies for the pheromone update stage, and (3) a new mechanism called I-Roulette to replicate the classic roulette wheel while improving GPU parallelism. Our implementation leads to factor gains exceeding 20x for any of the two stages of the ACO algorithm as applied to the TSP when compared to its sequential counterpart version running on a similar single-threaded high-end CPU. Moreover, an extensive discussion focused on different implementation paths on GPUs shows the way to deal with parallel graph connected components. This, in turn, suggests a broader area of inquiry, where algorithm designers may learn to adapt similar optimization methods to GPU architecture.     

A general heuristic for vehicle routing problems

We present a unified heuristic which is able to solve five different variants of the vehicle routing problem: the vehicle routing problem with time windows (VRPTW), the capacitated vehicle routing problem (CVRP), the multi-depot vehicle routing problem (MDVRP), the site-dependent vehicle routing problem (SDVRP) and the open vehicle routing problem (OVRP).     

A GRASP approach for the extended car sequencing problem

This paper presents a solution procedure for a new variant of the Car Sequencing Problem (CSP) based on the GRASP metaheuristic. In this variant, called xCSP (extended CSP), the aim is to satisfy the hard constraints of the CSP while scheduling the maximum possible number of cars with specific options at specific times of the day in order to satisfy other production requirements. Additional constraint ratios are likewise considered that force at least a minimum specific number of consecutive options. An extension of the CSP is formalized in this paper and computational results are presented using available on-line instances that verify the good performance of a GRASP procedure defined for the xCSP.     

Variable neighborhood search for the Vertex Separation Problem

The Vertex Separation Problem belongs to a family of optimization problems in which the objective is to find the best separator of vertices or edges in a generic graph. This optimization problem is strongly related to other well-known graph problems; such as the Path-Width, the Node Search Number or the Interval Thickness, among others. All of these optimization problems are NP-hard and have practical applications in VLSI (Very Large Scale Integration), computer language compiler design or graph drawing. Up to know, they have been generally tackled with exact approaches, presenting polynomial-time algorithms to obtain the optimal solution for specific types of graphs. However, in spite of their practical applications, these problems have been ignored from a heuristic perspective, as far as we know. In this paper we propose a pure 0-1 optimization model and a metaheuristic algorithm based on the variable neighborhood search methodology for the Vertex Separation Problem on general graphs. Computational results show that small instances can be optimally solved with this optimization model and the proposed metaheuristic is able to find high-quality solutions with a moderate computing time for large-scale instances.