A GRASP metaheuristic for humanitarian aid distribution

Large scale disasters, natural or human-made, have huge consequences on people and infrastructures. After a disaster strikes, the distribution of humanitarian aid to the population affected is one of the main operations to be carried out, and several crucial decisions must be made in a short time. This paper addresses a last-mile distribution problem in disaster relief operations, under insecure and uncertain conditions. A model is presented that takes into account the cost and time of operation, the security and reliability of the routes, and the equity of aid handed out. The output of the model consists of a detailed set of itineraries that can be used to build an implementable distribution plan. Given its high complexity, the resulting problem is solved using a multi-criteria metaheuristic approach. In particular, a constructive algorithm and a GRASP based metaheuristic are developed, which are tested in a case study based on the 2010 Haiti earthquake.     

A GRASP + ILP-based metaheuristic for the capacitated location-routing problem

In this paper we present a three-phase heuristic for the Capacitated Location-Routing Problem. In the first stage, we apply a GRASP followed by local search procedures to construct a bundle of solutions. In the second stage, an integer-linear program (ILP) is solved taking as input the different routes belonging to the solutions of the bundle, with the objective of constructing a new solution as a combination of these routes. In the third and final stage, the same ILP is iteratively solved by column generation to improve the solutions found during the first two stages. The last two stages are based on a new model, the location-reallocation model, which generalizes the capacitated facility location problem and the reallocation model by simultaneously locating facilities and reallocating customers to routes assigned to these facilities. Extensive computational experiments show that our method is competitive with the other heuristics found in the literature, yielding the tightest average gaps on several sets of instances and being able to improve the best known feasible solutions for some of them.     

A metaheuristic approach to the urban transit routing problem

The urban transit routing problem (UTRP) is NP-Hard and involves devising routes for public transport systems. It is a highly complex multi-constrained problem and the evaluation of candidate route sets can prove both time consuming and challenging, with many potential solutions rejected on the grounds of infeasibility. Due to the problem difficulty, metaheuristic algorithms are highly suitable, yet the success of such methods depend heavily on: (1) the quality of the chosen representation, (2) the effectiveness of the initialization procedures and (3) the suitability of the chosen neighbourhood moves. Our paper focuses on these three issues, and presents a framework which can be used as a starting point for solving this problem. We devise a simple model of the UTRP to evaluate candidate route sets. Finally, our approach is validated using simple hill-climbing and simulated annealing algorithms. Our simple method improves upon published results for Mandl’s benchmark problems. In addition, the potential for solving larger problem instances has been explored.     

A route-neighborhood-based metaheuristic for vehicle routing problem with time windows

In this paper, a two-stage metaheuristic based on a new neighborhood structure is proposed to solve the vehicle routing problem with time windows (VRPTW). Our neighborhood construction focuses on the relationship between route(s) and node(s). Unlike the conventional methods for parallel route construction, we construct routes in a nested parallel manner to obtain higher solution quality. Valuable information extracted from the previous parallel construction runs is used to enhance the performance of parallel construction. In addition, when there are only a few unrouted customers left, we design a special procedure for handling them. Computational results for 60 benchmark problems are reported. The results indicate that our approach is highly competitive with all existing heuristics, and in particular very promising for solving problems of large size.     

A metaheuristic for the school bus routing problem with bus stop selection

Existing literature on routing of school buses has focused mainly on building intricate models that attempt to capture as many real-life constraints and objectives as possible. In contrast, the focus of this paper is on understanding the joint problem of bus route generation and bus stop selection – two important sub-problems – in its most basic form. To this end, this paper defines the school bus routing problem (SBRP) as a variant of the vehicle routing problem in which three simultaneous decisions have to be made: (1) determine the set of stops to visit, (2) determine for each student which stop (s)he should walk to, and (3) determine routes that lie along the chosen stops, so that the total traveled distance is minimized. An MIP model of this basic problem is developed.     

A two-phase hybrid metaheuristic for the vehicle routing problem with time windows

The subject of this paper is a two-phase hybrid metaheuristic for the vehicle routing problem with time windows and a central depot (VRPTW). The objective function of the VRPTW considered here combines the minimization of the number of vehicles (primary criterion) and the total travel distance (secondary criterion). The aim of the first phase is the minimization of the number of vehicles by means of a (μ,λ)-evolution strategy, whereas in the second phase the total distance is minimized using a tabu search algorithm. The two-phase hybrid metaheuristic was subjected to a comparative test on the basis of 356 problems from the literature with sizes varying from 100 to 1000 customers. The derived results show that the proposed two-phase approach is very competitive.     

A hybrid metaheuristic for the vehicle routing problem with stochastic demand and duration constraints

The vehicle routing problem with stochastic demands (VRPSD) consists in designing optimal routes to serve a set of customers with random demands following known probability distributions. Because of demand uncertainty, a vehicle may arrive at a customer without enough capacity to satisfy its demand and may need to apply a recourse to recover the route’s feasibility. Although travel times are assumed to be deterministic, because of eventual recourses the total duration of a route is a random variable. We present two strategies to deal with route-duration constraints in the VRPSD. In the first, the duration constraints are handled as chance constraints, meaning that for each route, the probability of exceeding the maximum duration must be lower than a given threshold. In the second, violations to the duration constraint are penalized in the objective function. To solve the resulting problem, we propose a greedy randomized adaptive search procedure (GRASP) enhanced with heuristic concentration (HC). The GRASP component uses a set of randomized route-first, cluster-second heuristics to generate starting solutions and a variable-neighborhood descent procedure for the local search phase. The HC component assembles the final solution from the set of all routes found in the local optima reached by the GRASP. For each strategy, we discuss extensive computational experiments that analyze the impact of route-duration constraints on the VRPSD. In addition, we report state-of-the-art solutions for a established set of benchmarks for the classical VRPSD.     

A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers

The purpose of this article is to propose a perturbation metaheuristic for the vehicle routing problem with private fleet and common carrier (VRPPC). This problem consists of serving all customers in such a way that (1) each customer is served exactly once either by a private fleet vehicle or by a common carrier vehicle, (2) all routes associated with the private fleet start and end at the depot, (3) each private fleet vehicle performs only one route, (4) the total demand of any route does not exceed the capacity of the vehicle assigned to it, and (5) the total cost is minimized. This article describes a new metaheuristic for the VRPPC, which uses a perturbation procedure in the construction and improvement phases and also performs exchanges between the sets of customers served by the private fleet and the common carrier. Extensive computational results show the superiority of the proposed metaheuristic over previous methods.     

GRASP algorithms for the robust railway network design problem

This paper analyzes the solvability of a railway network design problem and its robust version. These problems are modeled as integer linear programming problems with binary variables, and their solutions provide topological railway networks maximizing the trip coverage in the presence of a competing mode, both assuming that the network works fine and that links can fail, respectively. Since these problems are computationally intractable for realistic sizes, GRASP heuristics are proposed for finding good feasible solutions. The results obtained in a computational experience indicate that our GRASP algorithms are suitable for railway network design problems.     

A list based threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem

In real life situations most companies that deliver or collect goods own a heterogeneous fleet of vehicles. Their goal is to find a set of vehicle routes, each starting and ending at a depot, making the best possible use of the given vehicle fleet such that total cost is minimized. The specific problem can be formulated as the Heterogeneous Fixed Fleet Vehicle Routing Problem (HFFVRP), which is a variant of the classical Vehicle Routing Problem. This paper describes a variant of the threshold accepting heuristic for the HFFVRP. The proposed metaheuristic has a remarkably simple structure, it is lean and parsimonious and it produces high quality solutions over a set of published benchmark instances. Improvement over several of previous best solutions also demonstrates the capabilities of the method and is encouraging for further research.     

Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking

The two-echelon location-routing problem (LRP-2E) arises from recent transportation applications like city logistics. In this problem, still seldom studied, first-level trips serve from a main depot a set of satellite depots, which must be located, while second-level trips visit customers from these satellites. After a literature review on the LRP-2E, we present four constructive heuristics and a hybrid metaheuristic: A greedy randomized adaptive search procedure (GRASP) complemented by a learning process (LP) and path relinking (PR). The GRASP and learning process involve three greedy randomized heuristics to generate trial solutions and two variable neighbourhood descent (VND) procedures to improve them. The optional path relinking adds a memory mechanism by combining intensification strategy and post-optimization. Numerical tests show that the GRASP with LP and PR outperforms the simple heuristics and an adaptation of a matheuristic initially published for a particular case, the capacitated location-routing problem (CLRP). Additional tests on the CLRP indicate that the best GRASP competes with the best metaheuristics published.     

A comparison of routing sets for robust network design

Designing a network able to route a set of non-simultaneous demand vectors is an important problem arising in telecommunications. In this paper, we compare the optimal capacity allocation costs for six routing sets: affine routing, volume routing and its two simplifications, the routing based on an unrestricted 2-cover of the uncertainty set, and the routing based on a cover delimited by a hyperplane.     

A metaheuristic based on a pool of routes for the vehicle routing problem with multiple trips and time windows

This paper studies the vehicle routing problem with multiple trips and time windows, in which vehicles are allowed to perform multiple trips during a scheduling period and each customer must be served within a given time interval. The problem is of particular importance for planning fleets of hired vehicles in common practices, such as e-grocery distributions, but this problem has received little attention in the literature. As a result of the multi-layered structure characteristic of the problem solution, we propose a pool-based metaheuristic in which various routes are first constructed to fill a pool, following which some of the routes are selected and combined to form vehicle working schedules. Finally, we conduct a series of experiments over a set of benchmark instances to evaluate and demonstrate the effectiveness of the proposed metaheuristic.     

A meta-model for multiobjective routing in MPLS networks

MPLS (Multiprotocol Label Switching) enables the utilisation of explicit routes and other advanced routing mechanisms in multiservice packet networks, capable of dealing with multiple and heterogeneous QoS (Quality of Service) parameters. Firstly the paper presents a discussion of conceptual and methodological issues raised by multiobjective routing optimisation models for MPLS networks. The major contribution is the proposal of a multiobjective routing optimisation framework for MPLS networks. The major features of this modelling framework are: the formulation of a three-level hierarchical routing optimisation problem including network and service performance objectives, the inclusion of fairness objectives in the different levels of optimisation and a two-level stochastic representation of the traffic in the network (traffic flow and packet stream levels). A variant of the general model for two classes of traffic flows, QoS traffic and Best Effort traffic, is also presented. Finally a stochastic teletraffic modelling approach, underlying the optimisation model, is fully described. Work partially supported by programme POSI of the III EC programme cosponsored by FEDER and national funds.     

Heuristics for vehicle routing on tree-like networks

This paper presents two new heuristics for the vehicle routing problem on tree-like road networks. These networks occur, for example, in rural road systems where the supply (or delivery) nodes are located on rural roads leading off from a few highways which form the ‘trunks’ of a tree-like network. The heuristics have the conventional objective of minimising the total distance travelled by the vehicles. The development of the heuristics takes advantage of the tree-like structure of the network. These two new heuristics and two other heuristics from the published literature are applied to some test problems and computational results are presented. The computational experience indicates that one of the new heuristics provides superior solutions to the existing heuristics and in reasonable computing time. It therefore appears suitable for large-scale practical routing problems.     

Efficient and fair routing for mesh networks

Inspired by the One Laptop Per Child project, we consider mesh networks that connect devices that cannot recharge their batteries easily. We study how the mesh should retransmit information to make use of the energy stored in each of the nodes effectively. The solution that minimizes the total energy spent by the whole network may be very unfair to some nodes because they bear a disproportionate burden of the traffic. A Nash equilibrium—achieved when nodes minimize the energy they spend—does not model the situation well because, as retransmissions consume battery without increasing the node’s utility, it predicts that nodes refuse to participate. Actually, there are wireless communication protocols, peer-to-peer networks and other systems that provide incentives or impose penalties to encourage nodes to be active and to participate. We explicitly aim at the solution that minimizes the total energy spent by nodes among those that satisfy a fairness constraint. Although this does not guarantee that the solution is at equilibrium, nodes do not have a big incentive to deviate from the proposed solution since they do not view the situation as extremely unfair to them. This is consistent with the recommendation of Beccaria and Bolelli (Proceedings of the 3rd IEEE Vehicle Navigation & Information Systems Conference, pp. 117–126, Oslo, 1992) who proposed to optimize social welfare keeping user needs as constraints. We propose a distributed and online routing algorithm and compare it to an offline, centralized approach. The centralized approach, besides being unrealistic in terms of information requirements, is also NP-hard to solve. For both reasons, we focus on the former and evaluate it by conducting an extensive set of computational experiments that evaluate the efficiency and fairness achieved by our algorithm.     

Cognitive and self-selective routing for sensor networks

New approaches to Quality-of-Service (QoS) routing in wireless sensor networks which use different forms of learning are the subject of this paper. The Cognitive Packet Network (CPN) algorithm uses smart packets for path discovery, together with reinforcement learning and neural networks, while Self-Selective Routing (SSR) is based on the “Ant Colony” paradigm which emulates the pheromone-based technique which ants use to mark paths and communicate information about paths between different insects of the same colony (Koenig et al. in Ann Math Artif Intell 31(1–4): 41–76, 2001). In this paper, we present first experimental results on a network test-bed to evaluate CPN’s ability to discover paths having the shortest delay, or shortest length. Then, we present small test-bed experiments and large-scale network simulations to evaluate the effectiveness of the SSR algorithm. Finally, the two approaches are compared with respect to their ability to adapt as network conditions change over time.     

A GRASP for the biquadratic assignment problem

The biquadratic assignment problem (BiQAP) is a generalization of the quadratic assignment problem (QAP). It is a nonlinear integer programming problem where the objective function is a fourth degree multivariable polynomial and the feasible domain is the assignment polytope. BiQAP problems appear in VLSI synthesis. Due to the difficulty of this problem, only heuristic solution approaches have been proposed. In this paper, we propose a new heuristic for the BiQAP, a greedy randomized adaptive search procedure (GRASP). Computational results on instances described in the literature indicate that this procedure consistently finds better solutions than previously described algorithms.     

A bundle-type algorithm for routing in telecommunication data networks

To optimize the quality of service through a telecommunication network, we propose an algorithm based on Lagrangian relaxation. The bundle-type dual algorithm is adapted to the present situation, where the dual function is the sum of a polyhedral function (coming from shortest path problems) and of a smooth function (coming from the congestion function).     

Algorithms for partitioning of large routing networks

Partitioning of large networks is vital for decentralized management and control.This paper presents two algorithms called ‘Hierarchical Recursive Progression-1’ (HRP-1) and ‘Hierarchical Recursive Progression-2’ (HRP-2) for partitioning of large networks into subnetworks of limited size with very few interconnections between them. In other words, we are trying to maximize the internal nodes and minimize the external connections of the subnetworks. The restriction on the size and the external connections is obtained by comparison against a user-defined value for the size of the subnetwork and for external connections via a term called density. The density of a subnetwork is defined as the ratio of the number of external connections and the size of the subnetwork. The two algorithms presented in the paper are based on the principle of subnetwork clustering. At the start of the algorithms,the number of subnetworks is equal to the total number of nodes of the network with each subnetwork containing a single node. Later, subnetworks are merged at various runs of the algorithm to form new subnetworks using connectivity,density and size criteria. The algorithms terminate when all the subnetworks satisfy a user-defined size and density limit. The difference between the algorithms HRP-1 and HRP-2 lies in the definition of density of subnetworks and the way through which the subnetworks are grouped at consecutive iterations of the algorithm. Note that the number of nodes inside the subnetworks never violates the size limit, thereby ensuring even distribution of load on the partitions obtained. Finally, the two algorithms are compared and tested on randomly generated graphs and a part of Paris road Network.