Search

In the classic split delivery vehicle routing problem, the demands of customers can be split unconditionally into pieces of any size. However, in the real-world distribution system, the customer demands consist of a set of orders on different quantities of goods. During the distribution, demands can be spitted, but orders cannot. This paper considers the vehicle routing problem with split delivery by order. It formulates the problem as an integer linear programming model, creatively applies the binary to the decimal decoder method to represent the solution, proposes a heuristic order-insertion procedure, and develops a tabu search algorithm. Using the developed algorithm, this paper tests 25 benchmark instances. According to the test results, the algorithm proposed has a small gap with the best-known solutions, but has an advantage in computing time. [ABSTRACT FROM AUTHOR]

We propose an iterated local search based on several classes of local and large neighborhoods for the bin packing problem with conflicts. This problem, which combines the characteristics of both bin packing and vertex coloring, arises in various application contexts such as logistics and transportation, timetabling, and resource allocation for cloud computing. We introduce O(1) evaluation procedures for classical local-search moves, polynomial variants of ejection chains and assignment neighborhoods, an adaptive set covering-based neighborhood, and finally a controlled use of 0-cost moves to further diversify the search. The overall method produces solutions of good quality on the classical benchmark instances and scales very well with an increase of problem size. Extensive computational experiments are conducted to measure the respective contribution of each proposed neighborhood. In particular, the 0-cost moves and the large neighborhood based on set covering contribute very significantly to the search. Several research perspectives are open in relation to possible hybridizations with other state-of-the-art mathematical programming heuristics for this problem. [ABSTRACT FROM AUTHOR]

We introduce a new class of assignment‐based neighborhoods for symmetric and asymmetric traveling salesman problems that exhibits a combinatorial leverage property, by which a tour can be generated in polynomial time that dominates an exponential number of other tours. The ejection chain perspective motivating the new neighborhoods differs from that underlying the most general assignment‐based neighborhoods proposed in the past, giving rise to new tour constructions that encompass and go beyond previous proposals. The resulting neighborhoods provide greater flexibility for generating new tours while simultaneously accounting for sparse traveling salesman graphs that were previously omitted from consideration. Finally, our approaches are applicable for improving the solution of some versions of the vehicle routing problem. [ABSTRACT FROM AUTHOR]

The problem of data representation is fundamental to the efficiency of search algorithms for the traveling salesman problem (TSP). The computational effort required to perform such tour operations as traversal and subpath reversal considerably influence algorithm design and performance. We propose a new data structure-the k-level satellite tree-for representing a TSP tour with a discussion of properties in the framework of general tour operations. The k-level satellite tree representation is shown to be significantly more efficient than its predecessors for large-scale instances. [ABSTRACT FROM AUTHOR]

Ejection chain methods, which include the classical Lin-Kernighan (LK) procedure and the Stem-and-Cycle (S&C) reference structure, have been the source of the currently leading algorithms for large scale symmetric traveling salesman problems (STSP). Although these methods proved highly effective in generating large neighborhoods for symmetric instances, their potential application to the asymmetric setting of the problem (ATSP) introduces new challenges that require special consideration. This article extends our studies on the single-rooted S&C to examine the more advanced doubly-rooted (DR) reference structure. The DR structure, which is allied both to metaheuristics and network optimization, allows more complex network-related (alternating) paths to transition from one tour to another, and offers special advantages for the ATSP. Computational experiments on an extensive testbed exhibits superior performance for the DR neighborhood over its LK counterpart for the ATSP. We additionally show that a straightforward implementation of a DR ejection chain algorithm outperforms the best local search algorithms and obtains solutions comparable to those obtained by the currently most advanced special-purpose algorithms for the ATSP, while requiring dramatically reduced computation time. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(1), 23-33 2016 [ABSTRACT FROM AUTHOR]

This paper introduces polymorphic ejection chains, and applies them to the problem of repairing time assignments in high school timetables while preserving regularity. An ejection chain is a sequence of repairs, each of which removes a defect introduced by the previous repair. Just as the elements of a polymorphic list may have different types, so in a polymorphic ejection chain the individual repairs may have different types. Methods for the efficient realization of these ideas, implemented in the author's KHE framework, are given, and some initial experiments are presented. [ABSTRACT FROM AUTHOR]

Memory allocation has a significant impact on power consumption in embedded systems. We address the dynamic memory allocation problem, in which memory requirements may change at each time interval. This problem has previously been addressed using integer linear programming and iterative approaches which build a solution interval by interval taking into account the requirements of partial time intervals. A GRASP that builds a solution for all time intervals has been proposed as a global approach. Due to the complexity of this problem, the GRASP algorithm solution quality decreases for larger instances. In order to overcome this drawback, we propose a multiple neighborhood search hybridized with a Tabu Search and enhanced by complex ejection chains. The proposed approach outperforms all previously developed methods devised for the dynamic memory allocation problem. [ABSTRACT FROM AUTHOR]

The problem reported in this paper is a variant of the classical vehicle routing problem, where customer requests for a transportation company can be served either by its private fleet of vehicles or assigned to an external common carrier. The latter case occurs if the demand exceeds the total capacity of the private fleet or if it is more economical to do so. Accordingly, the objective is to minimize the variable and fixed costs of the private fleet plus the costs charged by the common carrier. A tabu search heuristic with a neighbourhood structure based on ejection chains is proposed to solve this problem. It is empirically demonstrated that this algorithm outperforms the best approaches reported in the literature on a set of benchmark instances with both homogeneous and heterogeneous fleets. [ABSTRACT FROM AUTHOR]

The design of effective neighborhood structures is fundamentally important for creating better local search and metaheuristic algorithms for combinatorial optimization. Significant efforts have been made to develop larger and more powerful neighborhoods that are able to explore the solution space more effectively while keeping computation complexity within acceptable levels. The most important advances in this domain derive from dynamic and adaptive neighborhood constructions originating in ejection chain methods and a special form of a candidate list design that constitutes the core of the filter-and-fan method. The objective of this paper is to lay out the general framework of the ejection chain and filter-and-fan methods and present applications to a number of important combinatorial optimization problems. The features of the methods that make them effective in these applications are highlighted to provide insights into solving challenging problems in other settings. [ABSTRACT FROM AUTHOR]

This paper describes a Tabu Search heuristic with Ejection chains neighborhood to solve the Vehicle Routing Problem with Private fleet and common Carrier (VRPPC). The VRPPC is a variant of the well-known Vehicle Routing Problem in which a fixed internal fleet (Private fleet) is available at the warehouse in the presence of an external Transporter. Numerical experimentations show that the proposed Tabu Search algorithm provides competitive quality solutions compared to other heuristics proposed in the literature and it provides the best-known solutions to a well-known benchmark problem set. [ABSTRACT FROM AUTHOR]

Abstract: This paper proposes neighborhood search heuristics to optimize the planned routes of vehicles in a context where new requests, with a pick-up and a delivery location, occur in real-time. Within this framework, new solutions are explored through a neighborhood structure based on ejection chains. Numerical results show the benefits of these procedures in a real-time context. The impact of a master–slave parallelization scheme, using an increasing number of processors, is also investigated. [Copyright &y& Elsevier]

We present a Tabu Search (TS) method that employs a simple version of ejection chains for coloring graphs. The procedure is tested on a set of benchmark problems. Empirical results indicate that the proposed TS implementation outperforms other metaheuristic methods, including Simulated Annealing, a previous version of Tabu Search and a recent implementation of a Greedy Randomized Adaptive Search Procedure (GRASP). [ABSTRACT FROM AUTHOR]

Generically, ejection chains are methods conceived to allow solution transformations to be efficiently carried out by modifying a variable number of their components at each step of a local search algorithm. We consider a subpath ejection chain method for the vehicle routing problem (VRP) under capacity and route length restrictions. The method undertakes the identification of a substructure named the flower reference structure which, besides coordinating moves during an ejection chain construction, allows the creation of neighborhood structures with interesting combinatorial characteristics. Specifically, we base the method on a fundamental property of creating alternating paths and cycles during an ejection chain construction. A new algorithm based on a Tabu search framework is proposed, and computational results on a set of academic and real-world problems indicate that the algorithm may be a good alternative to the best heuristic algorithms for the VRP. [ABSTRACT FROM AUTHOR]