Fine-tuning a parametric Clarke and Wright heuristic by means of EAGH (empirically adjusted greedy heuristics)

Alt?nel and Öncan (2005) (A new enhancement of the Clarke and Wrightsavings heuristic for the capacitated vehicle routing problem) proposed aparametric Clarke and Wright heuristic to solve the capacitated vehicle routingproblem (CVRP). The performance of this parametric heuristic is sensitive tofine-tuning. Antinel and Öncan used an enumerative parameter-settingapproach and improved on the results obtained with the original Clarke andWright heuristic, but their approach requires much more computation time tosolve an instance. Battarra et al (2008) (Tuning a parametricClarke–Wright heuristic through a genetic algorithm) proposed a geneticalgorithm to set the parameter values. They succeeded in reducing the timeneeded to solve an instance, but the quality of the solution was slightly worse.In this paper, we propose to use the EAGH (empirically adjusted greedyheuristics) procedure to set the parameter values. A computational experimentshows the efficiency of EAGH; in an even shorter time, we improve on the bestresults obtained with any parametric Clarke and Wright heuristic method proposedin the literature.     

A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem

In this work we are concerned with the Clarke–Wright savings method for the classical capacitated vehicle routing problem. This is an NP-hard problem and numerous heuristic solution methods have been proposed. They can be classified as the classical ones and metaheuristics. Recent developments have shown that classical heuristics do not compare with the best metaheuristic implementations. However, some of them are very fast and simple to implement. This explains the popularity of the Clarke–Wright savings method in practice and the motivation behind its enhancements. We follow this line of research and propose a new enhancement which differs from the previous ones in its saving criterion: Customer demands are considered in addition to distances. Based on the extensive computational experiments we can say that the new method is not only very fast but also very accurate.     

Single vehicle routing problems with a predefined customer sequence, compartmentalized load and stochastic demands

We consider the problem of finding the optimal routing of a single vehicle that delivers K different products to N customers according to a particular customer order. The demands of the customers for each product are assumed to be random variables with known distributions. Each product type is stored in its dedicated compartment in the vehicle. Using a suitable dynamic programming algorithm we find the policy that satisfies the demands of the customers with the minimum total expected cost. We also prove that this policy has a specific threshold-type structure. Furthermore, we investigate a corresponding infinite-time horizon problem in which the service of the customers does not stop when the last customer has been serviced but it continues indefinitely with the same customer order. It is assumed that the demands of the customers at different tours have the same distributions. It is shown that the discounted-cost optimal policy and the average-cost optimal policy have the same threshold-type structure as the optimal policy in the original problem. The theoretical results are illustrated by numerical examples.     

Exact algorithms for the chance-constrained vehicle routing problem

We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle’s capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing exact methods for the VRP with stochastic demands require independent demands. We first study an edge-based formulation for the CCVRP, in particular addressing the challenge of how to determine a lower bound on the number of vehicles required to serve a subset of customers. We then investigate the use of a branch-and-cut-and-price (BCP) algorithm. While BCP algorithms have been considered the state of the art in solving the deterministic VRP, few attempts have been made to extend this framework to the VRP with stochastic demands. In contrast to the deterministic VRP, we find that the pricing problem for the CCVRP problem is strongly \(\mathcal {NP}\)-hard, even when the routes being priced are allowed to have cycles. We therefore propose a further relaxation of the routes that enables pricing via dynamic programming. We also demonstrate how our proposed methodologies can be adapted to solve a distributionally robust CCVRP problem. Numerical results indicate that the proposed methods can solve instances of CCVRP having up to 55 vertices.     

Research on the vehicle routing problem with interval demands

In this paper, a vehicle routing problem with interval demands is investigated based on the motivation of dispatching vehicles to deliver perishable products in practice. A nonlinear interval-based programming method is used to build a model for the vehicle routing problem with interval demands, which assumes that demands of customers are uncertain but fall in given intervals and actual demand of a customer becomes known only when the vehicle visited the customer. A vehicle-coordinated strategy was designed to solve the service failure problem. A hybrid algorithm based on the artificial immune system is also proposed to solve the model for vehicle routing problem with interval demands. The validity of methods and sensitivity analysis are illustrated by conducting some numerical examples. We find that the tolerant possibility degree of interval number has significant impacts on the distances. The planned distance strictly increased, while the additional distance strictly decreased and the total distance after coordinated transport has a U-typed relationship with the tolerant possibility degree of interval number.     

Heuristics for the lexicographic max-ordering vehicle routing problem

In this paper, we propose fast heuristics for the vehicle routing problem (VRP) with lexicographic max-order objective. A fixed number of vehicles, which are based at a depot, are to serve customers with known demands. The lexicographic max-order objective is introduced by asking to minimize lexicographically the sorted route lengths. Based on a model for this problem, several approaches are studied and new heuristic solution procedures are discussed resulting in the development of a sequential insertion heuristic and a modified savings algorithm in several variants. Comparisons between the algorithms are performed on instances of the VRP library VRPLIB. Finally, based on the results from the computational experiments, conclusions about the applicability and efficiency of the presented algorithms are drawn.     

An improvement in the Gavish-Shlifer algorithm for a class of transportation scheduling problems

In [2] Gavish and Shlifer present an algorithm for solving a class of transportation scheduling problems which includes the delivery problem, the school bus problem, and others. Their algorithm is based on the ‘savings method’ of Clarke and Wright. By solving a sequence of assignment problems, upper bounds may be generated for the original problem and the optimal solution determined through a branch and bound procedure. However, for certain problems the CPU time becomes excessive. In this paper we show that the bounds may be improved by solving a related maximum matching problem instead of the assignment problem. The result is that fewer branches need to be investigated. Computational results are presented indicating that considerably less CPU time is needed to solve problems using this approach than with the approach of Gavish and Shlifer.     

Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking

As shown in recent researches, the costs in distribution systems may be excessive if routes are ignored when locating depots. The location routing problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions. This paper presents a new metaheuristic to solve the LRP with capacitated routes and depots. A first phase executes a GRASP, based on an extended and randomized version of Clarke and Wright algorithm. This phase is implemented with a learning process on the choice of depots. In a second phase, new solutions are generated by a post-optimization using a path relinking. The method is evaluated on sets of randomly generated instances, and compared to other heuristics and a lower bound. Solutions are obtained in a reasonable amount of time for such a strategic problem. Furthermore, the algorithm is competitive with a metaheuristic published for the case of uncapacitated depots.     

An approximation algorithm for the pickup and delivery vehicle routing problem on trees

This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand. Customers are located on nodes of the tree, and each customer has a positive demand of pickup and/or delivery.Demands of customers are served by a fleet of identical vehicles with unit capacity. Each vehicle can serve pickup and delivery demands. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. In each tour, a vehicle begins at the depot with certain amount of goods for delivery, visits a subset of the customers in order to deliver and pick up goods and returns to the depot. At any time during the tour, a vehicle must always satisfy the capacity constraint, i.e., at any time the sum of goods to be delivered and that of goods that have been picked up is not allowed to exceed the vehicle capacity. We propose a 2-approximation algorithm for the problem.     

A new exact algorithm for the vehicle routing problem based onq-paths andk-shortest paths relaxations

We consider the basic Vehicle Routing Problem (VRP) in which a fleet ofM identical vehicles stationed at a central depot is to be optimally routed to supply customers with known demands subject only to vehicle capacity constraints. In this paper, we present an exact algorithm for solving the VRP that uses lower bounds obtained from a combination of two relaxations of the original problem which are based on the computation ofq-paths andk-shortest paths. A set of reduction tests derived from the computation of these bounds is applied to reduce the size of the problem and to improve the quality of the bounds. The resulting lower bounds are then embedded into a tree-search procedure to solve the problem optimally. Computational results are presented for a number of problems taken from the literature. The results demonstrate the effectiveness of the proposed method in solving problems involving up to about 50 customers and in providing tight lower bounds for problems up to about 150 customers.     

Capacitated location allocation problem with stochastic location and fuzzy demand: A hybrid algorithm

In this article, a capacitated location allocation problem is considered in which the demands and the locations of the customers are uncertain. The demands are assumed fuzzy, the locations follow a normal probability distribution, and the distances between the locations and the customers are taken Euclidean and squared Euclidean. The fuzzy expected cost programming, the fuzzy β-cost minimization model, and the credibility maximization model are three types of fuzzy programming that are developed to model the problem. Moreover, two closed-form Euclidean and squared Euclidean expressions are used to evaluate the expected distance between customers and facilities. In order to solve the problem at hand, a hybrid intelligent algorithm is applied in which the simplex algorithm, fuzzy simulation, and a modified genetic algorithm are integrated. Finally, in order to illustrate the efficiency of the proposed hybrid algorithm, some numerical examples are presented.     

Optimised crossover genetic algorithm for capacitated vehicle routing problem

This paper presents a genetic algorithm for solving capacitated vehicle routing problem, which is mainly characterised by using vehicles of the same capacity based at a central depot that will be optimally routed to supply customers with known demands. The proposed algorithm uses an optimised crossover operator designed by a complete undirected bipartite graph to find an optimal set of delivery routes satisfying the requirements and giving minimal total cost. We tested our algorithm with benchmark instances and compared it with some other heuristics in the literature. Computational results showed that the proposed algorithm is competitive in terms of the quality of the solutions found.     

Economic lot sizes and vehicle scheduling

In this paper a relationship between the vehicle scheduling problem and the dynamic lot size problem is considered. For the latter problem we assume that order quantities for different products can be determined separately. Demand is known over our n-period production planning horizon. For a certain product our task is to decide for each period if it should be produced or not. If it is produced, what is its economic lot size? Our aim here is to minimize the combined set-up and inventory holding costs. The optimal solution of this problem is given by the well-known Wagner-Whitin dynamic lot size algorithm. Also many heuristics for solving this problem have been presented. In this article we point out the analogy of the dynamic lot size problem to a certain vehicle scheduling problem. For solving vehicle scheduling problems the heuristic algorithm developed by Clark and Wright in very often used. Applying this algorithm to the equivalent vehicle scheduling problem we obtain by analogy a simple heuristic algorithm for the dynamic lot size problem. Numerical results indicate that computation time is reduced by about 50% compared to the Wagner-Whitin algorithm. The average cost appears to be approximately 0.8% higher than optimum.     

DVRP: a hard dynamic combinatorial optimisation problem tackled by an evolutionary hyper-heuristic

In this paper we propose and evaluate an evolutionary-based hyper-heuristic approach, called EH-DVRP, for solving hard instances of the dynamic vehicle routing problem. A hyper-heuristic is a high-level algorithm, which generates or chooses a set of low-level heuristics in a common framework, to solve the problem at hand. In our collaborative framework, we have included three different types of low-level heuristics: constructive, perturbative, and noise heuristics. Basically, the hyper-heuristic manages and evolves a sophisticated sequence of combinations of these low-level heuristics, which are sequentially applied in order to construct and improve partial solutions, i.e., partial routes. In presenting some design considerations, we have taken into account the allowance of a proper cooperation and communication among low-level heuristics, and as a result, find the most promising sequence to tackle partial states of the (dynamic) problem. Our approach has been evaluated using the Kilby’s benchmarks, which comprise a large number of instances with different topologies and degrees of dynamism, and we have compared it with some well-known methods proposed in the literature. The experimental results have shown that, due to the dynamic nature of the hyper-heuristic, our proposed approach is able to adapt to dynamic scenarios more naturally than low-level heuristics. Furthermore, the hyper-heuristic can obtain high-quality solutions when compared with other (meta) heuristic-based methods. Therefore, the findings of this contribution justify the employment of hyper-heuristic techniques in such changing environments, and we believe that further contributions could be successfully proposed in related dynamic problems.     

The \alpha -cost minimization model for capacitated facility location-allocation problem with uncertain demands

Facility location-allocation problem aims at determining the locations of some facilities to serve a set of spatially distributed customers and the allocation of each customer to the facilities such that the total transportation cost is minimized. In real life, the facility location-allocation problem often comes with uncertainty for lack of the information about the customers’ demands. Within the framework of uncertainty theory, this paper proposes an uncertain facility location-allocation model by means of chance-constraints, in which the customers’ demands are assumed to be uncertain variables. An equivalent crisp model is obtained via the \(\alpha \) -optimistic criterion of the total transportation cost. Besides, a hybrid intelligent algorithm is designed to solve the uncertain facility location-allocation problem, and its viability and effectiveness are illustrated by a numerical example.     

A multi-space sampling heuristic for the vehicle routing problem with stochastic demands

The vehicle routing problem with stochastic demands consists in designing transportation routes of minimal expected cost to satisfy a set of customers with random demands of known probability distributions. This paper proposes a simple yet effective heuristic approach that uses randomized heuristics for the traveling salesman problem, a tour partitioning procedure, and a set partitioning formulation to sample the solution space and find high-quality solutions for the problem. Computational experiments on benchmark instances from the literature show that the proposed approach is competitive with the state-of-the-art algorithm for the problem in terms of both accuracy and efficiency. In experiments conducted on a set of 40 instances, the proposed approach unveiled four new best-known solutions (BKSs) and matched another 24. For the remaining 12 instances, the heuristic reported average gaps with respect to the BKS ranging from 0.69 to 0.15 % depending on its configuration.     

An Improved Version of Cuckoo Hashing: Average Case Analysis of Construction Cost and Search Operations

Cuckoo hashing is a hash table data structure introduced by Pagh and Rodler, that offers constant worst case search time. As a major contribution of this paper, we analyze modified versions of this algorithm with improved performance. Further, we provide an asymptotic analysis of the search costs of all these variants of cuckoo hashing and compare these results with the well known properties of double hashing and linear probing. The analysis is supported by numerical results. Finally, our analysis shows, that the expected number of steps of search operations can be reduced by using a modified version of cuckoo hashing instead of standard algorithms based on open addressing.     

Bases for Vehicle Fleet Scheduling

In this paper bases for the allocation of customers to routes are discussed. Five possibilities are considered and applied to six cases. The outcome is that no basis is superior to the others in all cases and that the suggestion of Clarke and Wright is a reasonable one to use. One other method is found to be at least as good. Full details are given.     

A hybrid evolutionary algorithm for the periodic location-routing problem

The well-known vehicle routing problem (VRP) has been studied in depth over the last decades. Nowadays, generalizations of VRP have been developed for tactical or strategic decision levels of companies but not both. The tactical extension or periodic VRP (PVRP) plans a set of trips over a multiperiod horizon, subject to frequency constraints. The strategic extension is motivated by interdependent depot location and routing decisions in most distribution systems. Low-quality solutions are obtained if depots are located first, regardless of the future routes. In the location-routing problem (LRP), location and routing decisions are tackled simultaneously. Here for the first time, except for some conference papers, the goal is to combine the PVRP and LRP into an even more realistic problem covering all decision levels: the periodic LRP or PLRP. A hybrid evolutionary algorithm is proposed to solve large size instances of the PLRP. First, an individual representing an assignment of customers to combinations of visit days is randomly generated. The evolution operates through an Evolutionary Local Search (ELS) on visit day assignments. The algorithm is hybridized with a heuristic based on the Randomized Extended Clarke and Wright Algorithm (RECWA) to create feasible solutions and stops when a given number of iterations is reached. The method is evaluated over three sets of instances, and solutions are compared to the literature on particular cases such as one-day horizon (LRP) or one depot (PVRP). This metaheuristic outperforms the previous methods for the PLRP.     

The multi-trip vehicle routing problem

The basic vehicle routing problem is concerned with the design of a set of routes to serve a given number of customers, minimising the total distance travelled. In that problem, each vehicle is assumed to be used only once during a planning period, which is typically a day, and therefore is unrepresentative of many practical situations, where a vehicle makes several journeys during a day. The present authors have previously published an algorithm which outperformed an experienced load planner working on the complex, real-life problems of Burton's Biscuits, where vehicles make more than one trip each day. This present paper uses a simplified version of that general algorithm, in order to compare it with a recently published heuristic specially designed for the theoretical multi-trip vehicle routing problem.