A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions

In this paper, we consider a periodic vehicle routing problem that includes, in addition to the classical constraints, the possibility of a vehicle doing more than one route per day, as long as the maximum daily operation time for the vehicle is not exceeded. In addition, some constraints relating to accessibility of the vehicles to the customers, in the sense that not every vehicle can visit every customer, must be observed. We refer to the problem we consider here as the site-dependent multi-trip periodic vehicle routing problem. An algorithm based on tabu search is presented for the problem and computational results presented on randomly generated test problems that are made publicly available. Our algorithm is also tested on a number of routing problems from the literature that constitute particular cases of the proposed problem. Specifically we consider the periodic vehicle routing problem; the site-dependent vehicle routing problem; the multi-trip vehicle routing problem; and the classical vehicle routing problem. Computational results for our tabu search algorithm on test problems taken from the literature for all of these problems are presented.     

The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains challenging. In this work we provide an explanation to such challenge, by proving that when demands are given as a finite set of scenarios, solving the LP relaxation of such formulation is strongly NP-Hard. We also prove a hardness result for the case of independent normal demands.     

A time-based pheromone approach for the ant system

The ant system (AS) is a metaheuristic approach originally developed for solving the traveling salesman problem. AS has been successfully applied to various hard combinatorial optimization problems and different variants have been proposed in the literature. In this paper, we introduce a time-based pheromone approach for AS (TbAS). Due to this nature TbAS is applicable to routing problems involving time-windows. The novelty in TbAS is the multi-layer pheromone network structure which implicitly utilizes the service time information associated with the customers as a heuristic information. To investigate the performance of TbAS, we use the well-known vehicle routing problem with time-windows as our testbed and we conduct an extensive computational study using the Solomon (Algorithms for the vehicle routing and scheduling problems with time window constraints 35:254?C265, 1987) instances. Our results reveal that the proposed time-based pheromone approach is effective in obtaining good quality solutions.     

A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem

The heterogeneous fleet vehicle routing problem is investigated using some adaptations of the variable neighborhood search (VNS). The initial solution is obtained by Dijkstra’s algorithm based on a cost network constructed by the sweep algorithm and the 2-opt. Our VNS algorithm uses several neighborhoods which are adapted for this problem. In addition, a number of local search methods together with a diversification procedure are used. Two VNS variants, which differ in the order the diversification and Dijkstra’s algorithm are used, are implemented. Both variants appear to be competitive and produce new best results when tested on the data sets from the literature. We also constructed larger data sets for which benchmarking results are provided for future comparison.     

Designing WDM Optical Networks Using Branch-and-Price

In this paper, we present an exact solution procedure for the design of two-layer wavelength division multiplexing (WDM) optical networks with wavelength changers and bifurcated flows. This design problem closely resembles the traditional multicommodity flow problem, except that in the case of WDM optical networks, we are concerned with the routing of multiple commodities in two network layers. Consequently, the corresponding optimization models have to deal with two types of multicommodity variables defined for each of the network layers. The proposed procedure represents one of the first branch-and-price algorithms for a general WDM optical network setting with no assumptions on the number of logical links that can be established between nodes in the network. We apply our procedure in a computational study with four different network configurations. Our results show that for the three tested network configurations our branch-and-price algorithm provides solutions that are on average less than 5 % from optimality. We also provide a comparison of our branch-and-price algorithm with two simple variants of the upper bounding heuristic procedure HLDA that is commonly used for WDM optical network design.     

New exact method for large asymmetric distance-constrained vehicle routing problem

In this paper we revise and modify an old branch-and-bound method for solving the asymmetric distance–constrained vehicle routing problem suggested by Laporte et al. in 1987. Our modification is based on reformulating distance–constrained vehicle routing problem into a travelling salesman problem, and on using assignment problem as a lower bounding procedure. In addition, our algorithm uses the best-first strategy and new tolerance based branching rules. Since our method is fast but memory consuming, it could stop before optimality is proven. Therefore, we introduce the randomness, in case of ties, in choosing the node of the search tree. If an optimal solution is not found, we restart our procedure. As far as we know, the instances that we have solved exactly (up to 1000 customers) are much larger than the instances considered for other vehicle routing problem models from the recent literature. So, despite of its simplicity, this proposed algorithm is capable of solving the largest instances ever solved in the literature. Moreover, this approach is general and may be used for solving other types of vehicle routing problems.     

Transshipment games with identical newsvendors and cooperation costs

In a transshipment game, supply chain agents cooperate to transship surplus products. Although the game has been well studied in the OR literature, the fundamental question whether the agents can afford cooperation costs to set up and maintain the game in the first place has not been addressed thus far. This paper addresses this question for the cooperative transshipment games with identical agents having normally distributed independent demands. We provide characterization of equal allocations which are in the core of symmetric games, and prove that not all transshipment games are convex. In particular, we prove that though individual allocations grow with the coalition size, the growth diminishes according to two rules of diminishing individual allocations. These results are the basis for studying the games with cooperation costs. We model the cooperation costs by the cooperation network topology and the cooperation cost per network link. We consider two network topologies, the clique and the hub, and prove bounds for the cost per link that render coalitions stable. These bounds always limit coalition size for cliques. However, the opposite is shown for hubs, namely newsvendors can afford cooperation costs only if their coalition is sufficiently large.     

Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model

In this paper, we address a variant of the vehicle routing problem called the vehicle routing problem with time windows and multiple routes. It considers that a given vehicle can be assigned to more than one route per planning period. We propose a new exact algorithm for this problem. Our algorithm is iterative and it relies on a pseudo-polynomial network flow model whose nodes represent time instants, and whose arcs represent feasible vehicle routes. This algorithm was tested on a set of benchmark instances from the literature. The computational results show that our method is able to solve more instances than the only other exact method described so far in the literature, and it clearly outperforms this method in terms of computing time.     

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.     

Network hub location problems: The state of the art

Hubs are special facilities that serve as switching, transshipment and sorting points in many-to-many distribution systems. The hub location problem is concerned with locating hub facilities and allocating demand nodes to hubs in order to route the traffic between origin–destination pairs. In this paper we classify and survey network hub location models. We also include some recent trends on hub location and provide a synthesis of the literature.     

Deterministic Routing With Bounded Buffers: Turning Offline Into Online Protocols

In this paper we present a deterministic protocol for routing arbitrary permutations in arbitrary networks. The protocol is analyzed in terms of the size of the network and the routing number of the network. Given a network H of n nodes, the routing number of H is defined as the maximum over all permutations on {1, ..., n} of the minimal number of steps to route offline in H. We show that for any network H of size n with routing number R our protocol needs time to route any permutation in H using only constant size edge buffers. This significantly improves all previously known results on deterministic routing. In particular, our result yields optimal deterministic routing protocols for arbitrary networks with diameter or bisection width , constant. Furthermore we can extend our result to deterministic compact routing. This yields, e.g., a deterministic routing protocol with runtime O(R logn) for arbitrary bounded degree networks if only O(logn) bits are available at each node for storing routing information. Our protocol is a combination of a generalized ``routing via simulation' technique with an new deterministic protocol for routing h-relations in an extended version of a multibutterfly network. This protocol improves upon all previous routing protocols known for variants of the multibutterfly network. The ``routing via simulation' technique used here extends a method previously introduced by the authors for designing compact routing protocols. Received July 18, 1997     

Routing vehicles to minimize fuel consumption

We consider a generalization of the capacitated vehicle routing problem known as the cumulative vehicle routing problem in the literature. Cumulative VRPs are known to be a simple model for fuel consumption in VRPs. We examine four variants of the problem, and give constant factor approximation algorithms. Our results are based on a well-known heuristic of partitioning the traveling salesman tours and the use of the averaging argument.     

A customer-centric routing problem with multiple trips of a single vehicle

In this study, we introduce a routing problem with multiple uses of a single vehicle and service time in demand points, minimizing the sum of clients’ waiting time to receive service. This problem is relevant in the distribution of aid in disaster-stricken communities, in the recollection and/or delivery of perishable goods and personnel transportation, among other situations, where reaching clients to perform service, fast and fair, is a priority. We consider vehicle capacity and travel distance constraints, forcing multiple use of the vehicle during the planning horizon. This paper presents two mixed integer formulations for this problem, based on a multi-level network, as well as a metaheuristic algorithm. The proposed models can solve to optimality instances with up to 30 clients. The proposed metaheuristic algorithm obtains high-quality solutions in short computational times.     

Vehicle routing problems with alternative paths: An application to on-demand transportation

The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin–destination connection. Several attributes can be defined for one arc (travel time, travel cost, etc.), but the shortest route modeled by this arc is computed according to a single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. We propose to consider these alternative routes and to evaluate their impact on solution algorithms and solution values through a multigraph representation of the road network. We point out the difficulties brought by this representation for general vehicle routing problems, which drives us to introduce the so-called fixed sequence arc selection problem (FSASP). We propose a dynamic programming solution method for this problem. In the context of an on-demand transportation (ODT) problem, we then propose a simple insertion algorithm based on iterative FSASP solving and a branch-and-price exact method. Computational experiments on modified instances from the literature and on realistic data issued from an ODT system in the French Doubs Central area underline the cost savings brought by the proposed methods using the multigraph model.     

Implicit depot assignments and rotations in vehicle routing heuristics

Vehicle routing variants with multiple depots and mixed fleet present intricate combinatorial aspects related to sequencing choices, vehicle type choices, depot choices, and depots positioning. This paper introduces a dynamic programming methodology for efficiently evaluating compound neighborhoods combining sequence-based moves with an optimal choice of vehicle and depot, and an optimal determination of the first customer to be visited in the route, called rotation. The assignment choices, making the richness of the problem, are thus no more addressed in the solution structure, but implicitly determined during each move evaluation. Two meta-heuristics relying on these concepts, an iterated local search and a hybrid genetic algorithm, are presented. Extensive computational experiments demonstrate the remarkable performance of these methods on classic benchmark instances for multi-depot vehicle routing problems with and without fleet mix, as well as the notable contribution of the implicit depot choice and positioning methods to the search performance. New state-of-the-art results are obtained for multi-depot vehicle routing problems (MDVRP), and multi-depot vehicle fleet mix problems (MDVFMP) with unconstrained fleet size. The proposed concepts are fairly general, and widely applicable to many other vehicle routing variants.     

A column generation-based heuristic algorithm for an inventory routing problem with perishable goods

An inventory routing problem is a variation of the vehicle routing problem in which inventory and routing decisions are determined simultaneously over a given time horizon. The objective is to minimize the sum of transportation and inventory costs. In this paper, we study a specific inventory routing problem in which goods are perishable (PIRP). We develop a mathematical model for PIRP and exploit its structure to develop a column generation-based solution approach. Cutting planes are added to improve the formulation. We present computational experiments to demonstrate that our methodology is effective, and that the integration of routing and inventory can yield significant cost savings.     

Less-Than-Truckload carrier collaboration problem: modeling framework and solution approach

Less-Than-Truckload (LTL) carriers generally serve geographical regions that are more localized than the inter-city line-hauls served by truckload carriers. That localization can lead to urban freight transportation routes that overlap. If trucks are traveling with less than full loads, there typically exist opportunities for carriers to collaborate over such routes. We introduce a two stage framework for LTL carrier collaboration. Our first stage involves collaboration between multiple carriers at the entrance to the city and can be formulated as a vehicle routing problem with time windows (VRPTW). We employ guided local search for solving this VRPTW. The second stage involves collaboration between carriers at transshipment facilities while executing their routes identified in phase one. For solving the second stage problem, we develop novel local search heuristics, one of which leverages integer programming to efficiently explore the union of neighborhoods defined by new problem-specific move operators. Our computational results indicate that integrating integer programming with local search results in at least an order of magnitude speed up in the second stage problem. We also perform sensitivity analysis to assess the benefits from collaboration. Our results indicate that distance savings of 7–15 % can be achieved by collaborating at the entrance to the city. Carriers involved in intra-city collaboration can further save 3–15 % in total distance traveled, and also reduce their overall route times.     

Polyhedral results for the edge capacity polytope

Network loading problems occur in the design of telecommunication networks, in many different settings. For instance, bifurcated or non-bifurcated routing (also called splittable and unsplittable) can be considered. In most settings, the same polyhedral structures return. A better understanding of these structures therefore can have a major impact on the tractability of polyhedral-guided solution methods. In this paper, we investigate the polytopes of the problem restricted to one arc/edge of the network (the undirected/directed edge capacity problem) for the non-bifurcated routing case.?As an example, one of the basic variants of network loading is described, including an integer linear programming formulation. As the edge capacity problems are relaxations of this network loading problem, their polytopes are intimately related. We give conditions under which the inequalities of the edge capacity polytopes define facets of the network loading polytope. We describe classes of strong valid inequalities for the edge capacity polytopes, and we derive conditions under which these constraints define facets. For the diverse classes the complexity of lifting projected variables is stated.?The derived inequalities are tested on (i) the edge capacity problem itself and (ii) the described variant of the network loading problem. The results show that the inequalities substantially reduce the number of nodes needed in a branch-and-cut approach. Moreover, they show the importance of the edge subproblem for solving network loading problems. Received: September 2000 / Accepted: October 2001?Published online March 27, 2002     

A new mixed integer linear model for a rich vehicle routing problem with docking constraints

In this paper we address a rich vehicle routing problem that arises in real-life applications. Among other aspects we consider time windows, simultaneous delivery and pick-up at customer locations and multiple use of vehicles. To guarantee a coordinated material flow at the depot, we include the timed allocation of vehicles to loading bays at which the loading and unloading activities can occur. The resulting vehicle routing problem is formulated as a two-index vehicle-flow model which integrates the routing under real-life conditions and the assignment of vehicles to loading bays at the depot. We use CPLEX 11.0 to solve medium-sized instances that are derived from the extended Solomon test set. The selective implementation of preprocessing techniques and cutting planes improves the solver performance significantly.     

Managing pharmaceuticals delivery service using a hybrid particle swarm intelligence approach

Medicines or drugs have unique characteristics of short life cycle, small size, light weight, restrictive distribution time and the need of temperature and humidity control (selected items only). Thus, logistics companies often use different types of vehicles with different carrying capacities, and considering fixed and variable costs in service delivery, which make the vehicle assignment and route optimization more complicated. In this study, we formulate the problem to a multi-type vehicle assignment and mixed integer programming route optimization model with fixed fleet size under the constraints of distribution time and carrying capacity. Given non-deterministic polynomial hard and optimal algorithm can only be used to solve small-size problem, a hybrid particle swarm intelligence (PSI) heuristic approach, which adopts the crossover and mutation operators from genetic algorithm and 2-opt local search strategy, is proposed to solve the problem. We also adapt a principle based on cost network and Dijkstra’s algorithm for vehicle scheduling to balance the distribution time limit and the high loading rate. We verify the relative performance of the proposed method against several known optimal or heuristic solutions using a standard data set for heterogeneous fleet vehicle routing problem. Additionally, we compare the relative performance of our proposed Hybrid PSI algorithm with two intelligent-based algorithms, Hybrid Population Heuristic algorithm and Improved Genetic Algorithm, using a real-world data set to illustrate the practical and validity of the model and algorithm.