Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem

In this paper, we develop an extended guided tabu search (EGTS) and a new heuristic packing algorithm for the two-dimensional loading vehicle routing problem (2L-CVRP). The 2L-CVRP is a combination of two well-known NP-hard problems, the capacitated vehicle routing problem, and the two-dimensional bin packing problem. It is very difficult to get a good performance solution in practice for these problems. We propose a meta-heuristic methodology EGTS which incorporates theories of tabu search and extended guided local search (EGLS). It has been proved that tabu search is a very good approach for the CVRP, and the guiding mechanism of the EGLS can help tabu search to escape effectively from local optimum. Furthermore, we have modified a collection of packing heuristics by adding a new packing heuristic to solve the loading constraints in 2L-CVRP, in order to improve the cost function significantly. The effectiveness of the proposed algorithm is tested, and proven by extensive computational experiments on benchmark instances.     

A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem

This paper addresses an extension of the capacitated vehicle routing problem where customer demand is composed of two-dimensional weighted items (2L-CVRP). The objective consists in designing a set of trips minimizing the total transportation cost with a homogenous fleet of vehicles based on a depot node. Items in each vehicle trip must satisfy the two-dimensional orthogonal packing constraints. A GRASP×ELS algorithm is proposed to compute solutions of a simpler problem in which the loading constraints are transformed into resource constrained project scheduling problem (RCPSP) constraints. We denote this relaxed problem RCPSP-CVRP. The optimization framework deals with RCPSP-CVRP and lastly RCPSP-CVRP solutions are transformed into 2L-CVRP solutions by solving a dedicated packing problem. The effectiveness of our approach is demonstrated through computational experiments including both classical CVRP and 2L-CVRP instances. Numerical experiments show that the GRASP×ELS approach outperforms all previously published methods.     

A GRASP×ELS for the vehicle routing problem with basic three-dimensional loading constraints

This paper addresses an extension of the capacitated vehicle routing problem where the client demand consists of three-dimensional weighted items (3L-CVRP). The objective is to design a set of trips for a homogeneous fleet of vehicles based at a depot node which minimizes the total transportation cost. Items in each vehicle trip must satisfy the three-dimensional orthogonal packing constraints. This problem is strongly connected to real-life transportation systems where the packing of items to be delivered by each vehicle can have a significant impact on the routes. We propose a new way to solve the packing sub-problem. It consists of a two-step procedure in which the z-constraints are first relaxed to get a (x,y) positioning of the items. Then, a compatible z-coordinate is computed to get a packing solution. Items can be rotated but additional constraints such as item fragility, support and LIFO are not considered. This method is included in a GRASP×ELS hybrid algorithm dedicated to the computation of VRP routes. The route optimization alternates between two search spaces: the space of VRP routes and the space of giant trips. The projection from one to the other is done by dedicated procedures (namely the Split and the concatenation algorithms). Moreover, a Local Search is defined on each search space. Furthermore, hash tables are used to store the result of the packing checks and thus save a substantial amount of CPU time. The effectiveness of our approach is illustrated by computational experiments on 3L-CVRP instances from the literature. A new set of realistic instances based on the 96 French districts are also proposed. They range from 19 nodes for the small instances to 255 nodes for the large instances and they can be stated as realistic since they are based on true travel distances in kilometers between French cities. The impact of the hash tables is illustrated as well.     

An effective tabu search approach with improved loading algorithms for the 3L-CVRP

In this paper, we consider the Three-Dimensional Loading Capacitated Vehicle Routing Problem(3L-CVRP) which combines the routing of a fleet of vehicles and the loading of three-dimensional shaped goods into the vehicles while minimizing the total travel distance incurred. Apparently, 3L-CVRP is a combination of capacitated vehicle routing and three-dimensional bin packing problem and thus of high complexity. Different from most of previous works, we propose an innovative approach, called improved least waste heuristic for solving the loading subproblem, which is iteratively invoked by a simple tabu search algorithm for the routing. The good performance in terms of the solution quality and computational efficiency of our approach is shown through the numerical experiments on the benchmark instances from literature.     

Heuristics for the multi-period orienteering problem with multiple time windows

We present the multi-period orienteering problem with multiple time windows (MuPOPTW), a new routing problem combining objective and constraints of the orienteering problem (OP) and team orienteering problem (TOP), constraints from standard vehicle routing problems, and original constraints from a real-world application. The problem itself comes from a real industrial case. Specific route duration constraints result in a route feasibility subproblem. We propose an exact algorithm for this subproblem, and we embed it in a variable neighborhood search method to solve the whole routing problem. We then provide experimental results for this method. We compare them to a commercial solver. We also adapt our method to standard benchmark OP and TOP instances, and provide comparative tables with state-of-the-art algorithms.     

A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP

The Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP) addresses practical constraints frequently encountered in the freight transportation industry. In this problem, the task is to serve all customers using a homogeneous fleet of vehicles at minimum traveling cost. The constraints imposed by the three-dimensional shape of the goods, the unloading order, item fragility, and the stability of the loading plan of each vehicle are explicitly considered. We improved two well-known packing heuristics, namely the Deepest-Bottom-Left-Fill heuristic and the Maximum Touching Area heuristic, for the three-dimensional loading sub-problem and provided efficient implementations. Based on these two new heuristics, an effective tabu search algorithm is given to address the overall problem. Computational experiments on publicly available test instances show our new approach outperforms the current best algorithms for 20 out of 27 instances. Our approach is also superior to the existing algorithm on benchmark data for the closely related problem variant M3L-CVRP (which uses a slightly different unloading order constraint compared to 3L-CVRP).     

A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints

The capacitated vehicle routing problem with three-dimensional loading constraints combines capacitated vehicle routing and three-dimensional loading with additional packing constraints concerning, for example, unloading operations. An efficient hybrid algorithm including a tabu search algorithm for routing and a tree search algorithm for loading is introduced. Computational results are presented for all publicly available test instances. Most of the best solutions previously reported in literature have been improved while the computational effort is drastically reduced compared to other methods.     

Heuristics for the strip packing problem with unloading constraints

This article addresses the Strip Packing Problem with Unloading Constraints (SPU). In this problem, we are given a strip of fixed width and unbounded height, and n items of C different classes. As in the well-known two-dimensional Strip Packing problem, we have to pack all items minimizing the used height, but now we have the additional constraint that items of higher classes cannot block the way out of lower classes items. This problem appears as a sub-problem in the Two-Dimensional Loading Capacitated Vehicle Routing Problem (2L-CVRP), where one has to optimize the delivery of goods, demanded by a set of clients, that are transported by a fleet of vehicles of limited capacity based at a central depot. We propose two approximation algorithms and a GRASP heuristic for the SPU problem and provide an extensive computational experiment with these algorithms using well know instances for the 2L-CVRP problem as well as new instances adapted from the Strip Packing problem.     

Variable neighborhood search algorithms for the vehicle routing problem with two‐dimensional loading constraints and mixed linehauls and backhauls

In this paper, we explore a vehicle routing problem with two‐dimensional loading constraints and mixed linehauls and backhauls. The addressed problem belongs to a subclass of general pickup and delivery problems. Two‐dimensional loading constraints are also considered. These constraints arise in many real‐world situations and can improve efficiency since backhaul customers do not need to be delayed in a route when it is possible to load their items earlier and without rearrangements of the items. To tackle this problem, we report extensive computational experiments to assess the performance of different variants of the variable neighborhood search approaches. The initial solution relies on an insertion heuristic. Both shaking and local search phases resort to 10 neighborhood structures. Some of those structures were specially developed for this problem. The feasibility of routes is heuristically obtained with a classical bottom‐left based method to tackle the explicit consideration of loading constraints. All the strategies were implemented and exhaustively tested on instances adapted from the literature. The results of this computational study are discussed at the end of this paper.     

Improved filtering for weighted circuit constraints

We study the weighted circuit constraint in the context of constraint programming. It appears as a substructure in many practical applications, particularly routing problems. We propose a domain filtering algorithm for the weighted circuit constraint that is based on the 1-tree relaxation of Held and Karp. In addition, we study domain filtering based on an additive bounding procedure that combines the 1-tree relaxation with the assignment problem relaxation. Experimental results on Traveling Salesman Problem instances demonstrate that our filtering algorithms can dramatically reduce the problem size. In particular, the search tree size and solving time can be reduced by several orders of magnitude, compared to existing constraint programming approaches. Moreover, for medium-size problem instances, our method is competitive with the state-of-the-art special-purpose TSP solver Concorde.     

A coarse-to-fine quasi-physical optimization method for solving the circle packing problem with equilibrium constraints

This paper addresses an important extension of the circle packing problem (CPP), the circle packing problem with equilibrium constraints (CPPEC). It considers the dense packing of n circular disks in a large circular container at the same time satisfying the equilibrium constraints. Under the industrial background of the layout design on satellite modules, this NP-hard global optimization problem is important in both theory and practice. We introduce two new quasi-physical models for solving CPPEC in this paper. One is to mimic the elastic movement driven by repelling forces from extruded disks, the other is to simulate a whole translation movement of the disks driven by a pulling force from an imaginative elastic rope connecting the centroid of the disks and the center of the container. Then, inspired by the coarse-to-fine control strategy in the manufacture industry, we propose a coarse-to-fine quasi-physical (CFQP) optimization method that adopts the two quasi-physical models for the quasi-physical descent procedure and combines a basin hopping with tabu method for the search procedure. In this way, not only could CFQP take into account the diversity of the search space to facilitate the global search, but it also does fine search to find the corresponding local minimum in a promising local area. Experiments were on two sets of 11 representative test instances. Computational results showed that CFQP achieved new and better results on four instances, at the same time it matched the current best records on the other six (accurate to 0.0001). Moreover, CFQP resulted in smaller equilibrium deviations than that of others published in the literature. In addition, we generated 34 new CPPEC instances basing on the CPP benchmarks, and provided computational results on the two sets of 34 new CPPEC instances, and the container radii obtained are close to the published results on CPP.     

Multiscale production routing in multicommodity supply chains with complex production facilities

In this work, we introduce the multiscale production routing problem (MPRP), which considers the coordination of production, inventory, distribution, and routing decisions in multicommodity supply chains with complex continuous production facilities. We propose an MILP model involving two different time grids. While a detailed mode-based production scheduling model captures all critical operational constraints on the fine time grid, vehicle routing is considered in each time period of the coarse time grid. In order to solve large instances of the MPRP, we propose an iterative MILP-based heuristic approach that solves the MILP model with a restricted set of candidate routes at each iteration and dynamically updates the set of candidate routes for the next iteration. The results of an extensive computational study show that the proposed algorithm finds high-quality solutions in reasonable computation times, and in large instances, it significantly outperforms a standard two-phase heuristic approach and a solution strategy involving a one-time heuristic pre-generation of candidate routes. Similar results are achieved in an industrial case study, which considers a real-world industrial gas supply chain.     

A fast hybrid primal heuristic for multiband robust capacitated network design with multiple time periods

We investigate the Robust Multiperiod Network Design Problem, a generalization of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against traffic volume uncertainty, we propose a Robust Optimization model based on Multiband Robustness (Büsing and D’Andreagiovanni, 2012), a refinement of classical Γ-Robustness by Bertsimas and Sim that uses a system of multiple deviation bands.Since the resulting optimization problem may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps.     

A branch-and-cut approach for the vehicle routing problem with loading constraints

In this paper we describe a branch-and-cut algorithm for the vehicle routing problem with unloading constraints. The problem is to determine a set of routes with minimum total cost, each route leaving a depot, such that all clients are visited exactly once. Each client has a demand, given by a set of items, that are initially stored in a depot. We consider the versions of the problem with two and tri dimensional parallelepiped items. For each route in a solution, we also need to construct a feasible packing for all the items of the clients in this route. As it would be too expensive to rearrange the vehicle cargo when removing the items of a client, it is important to perform this task without moving the other client items. Such packings are said to satisfy unloading constraints.In this paper we describe a branch-and-cut algorithm that uses several techniques to prune the branch-and-cut enumeration tree. The presented algorithm uses several packing routines with different algorithmic approaches, such as branch-and-bound, constraint programming and metaheuristics. The careful combination of these routines showed that the presented algorithm is competitive, and could obtain optimum solutions within significantly smaller computational times for most of the instances presented in the literature.     

New resolution algorithm and pretreatments for the two-dimensional bin-packing problem

The two-dimensional bin-packing (2BP) problem involves packing a given set of rectangles A into a minimum number of larger identical rectangles called bins. In this paper, we introduce the concept of dependent orientation items that have special characteristics, and give the formulation that characterizes these items. Then we propose three pretreatments for the non-oriented version of the problem. These pretreatments allow finding optimal packing of some items subsets of the given instance. They enable increasing the total area of the items and consequently the continuous lower bound. Finally, we propose a new heuristic method based on a best-fit algorithm adapted to the 2BP problem. Numerical experiments show that this method is competitive with the heuristic and metaheuristic algorithms proposed in the literature for the considered problem in respect of both the quality of the solution and the computing time.     

A variable neighborhood search heuristic algorithm for the double vehicle routing problem with multiple stacks

This paper addresses the double vehicle routing problem with multiple stacks (DVRPMS) in which a fleet of vehicles must collect items in a pickup region and then travel to a delivery region where all items are delivered. The load compartment of all vehicles is divided into rows (horizontal stacks) of fixed profundity (horizontal heights), and on each row, the unloading process must respect the last‐in‐first‐out policy. The objective of the DVRPMS is to find optimal routes visiting all pickup and delivery points while ensuring the feasibility of the vehicle loading plans. We propose a new integer linear programming formulation, which was useful to find inconsistencies in the results of exact algorithms proposed in the literature, and a variable neighborhood search based algorithm that was able to find solutions with same or higher quality in shorter computational time for most instances when compared to the methods already present in the literature.     

Cyclic staff scheduling: optimization models for some real-life problems

In this work, we propose a general integer programming model to address the staff scheduling problem, flexible enough to be easily adapted to a wide-range of real-world problems. The model is applied with slight changes to two case studies: a glass plant and a continuous care unit, and also to a collection of benchmark instances available in the literature. The emphasis of our approach is on a novel formulation of sequence constraints and also on workload balance, which is tackled through cyclic scheduling. Models are solved using the CPLEX solver. Computational results indicate that optimal solutions can be achieved within a reasonable amount of time.     

A variable neighborhood search for the multi-depot vehicle routing problem with loading cost

The purpose of this paper is to propose a variable neighbourhood search (VNS) for solving the multi-depot vehicle routing problem with loading cost (MDVRPLC). The MDVRPLC is the combination of multi-depot vehicle routing problem (MDVRP) and vehicle routing problem with loading cost (VRPLC) which are both variations of the vehicle routing problem (VRP) and occur only rarely in the literature. In fact, an extensive literature search failed to find any literature related specifically to the MDVRPLC. The proposed VNS comprises three phases. First, a stochastic method is used for initial solution generation. Second, four operators are randomly selected to search neighbourhood solutions. Third, a criterion similar to simulated annealing (SA) is used for neighbourhood solution acceptance. The proposed VNS has been test on 23 MDVRP benchmark problems. The experimental results show that the proposed method provides an average 23.77% improvement in total transportation cost over the best known results based on minimizing transportation distance. The results show that the proposed method is efficient and effective in solving problems.     

An exact algorithm and a metaheuristic for the generalized vehicle routing problem with flexible fleet size

The generalized vehicle routing problem (GVRP) involves finding a minimum-length set of vehicle routes passing through a set of clusters, where each cluster contains a number of vertices, such that the tour includes exactly one vertex from each cluster and satisfies capacity constraints. We consider a version of the GVRP where the number of vehicles is a decision variable. This paper introduces a new mathematical formulation based on a two-commodity flow model. We solve the problem using a branch-and-cut algorithm and a metaheuristic that is a hybrid of the greedy randomized adaptive search procedure (GRASP) and the evolutionary local search (ELS) proposed in [18]. We perform computational experiments on instances from the literature to demonstrate the performance of our algorithms.     

Mining temporal patterns in popularity of web items

Huge amounts of various web items (e.g., images, keywords, and web pages) are being made available on the Web. The popularity of such web items continuously changes over time, and mining for temporal patterns in the popularity of web items is an important problem that is useful for several Web applications; for example, the temporal patterns in the popularity of web search keywords help web search enterprises predict future popular keywords, thus enabling them to make price decisions when marketing search keywords to advertisers. However, the presence of millions of web items makes it difficult to scale up previous techniques for this problem. This paper proposes an efficient method for mining temporal patterns in the popularity of web items. We treat the popularity of web items as time-series and propose a novel measure, a gap measure, to quantify the dissimilarity between the popularity of two web items. To reduce the computational overhead for this measure, an efficient method using the Discrete Fourier Transform (DFT) is presented. We assume that the popularity of web items is not necessarily periodic. For finding clusters of web items with similar popularity trends, we show the limitations of traditional clustering approaches and propose a scalable, efficient, density-based clustering algorithm using the gap measure. Our experiments using the popularity trends of web search keywords obtained from the Google Trends web site illustrate the scalability and usefulness of the proposed approach in real-world applications.