A construction and improvement heuristic for a liquefied natural gas inventory routing problem

We present a large scale ship routing and inventory management problem for a producer and distributor of liquefied natural gas (LNG). The problem contains multiple products, inventory and berth capacity at the loading port and a heterogeneous fleet of ships. The goal is to create an annual delivery program to fulfill the producer’s long-term contracts at minimum cost, while maximizing the revenue from selling LNG in the spot market. To solve this problem we have developed a construction and improvement heuristic (CIH).The CIH is a multi-start local search heuristic that constructs a set of solutions using a greedy insertion procedure. The solutions are then improved using either a first-descent neighborhood search, branch-and-bound on a mathematical formulation, or both. Tests on real-life instances show that the CIH provides good solutions in a short amount of time.     

Heuristic approaches for the inventory-routing problem with backlogging

We study an inventory-routing problem in which multiperiod inventory holding, backlogging, and vehicle routing decisions are to be taken for a set of customers who receive units of a single item from a depot with infinite supply. We consider a case in which the demand at each customer is deterministic and relatively small compared to the vehicle capacity, and the customers are located closely such that a consolidated shipping strategy is appropriate. We develop constructive and improvement heuristics to obtain an approximate solution for this NP-hard problem and demonstrate their effectiveness through computational experiments.     

模糊需求下物流系统CLRIP 问题研究

从物流系统集成的角度出发．考虑到客户需求的模糊性，建立了多仓库单级物流配送系统中的设施选址、车辆运输路线安排、库存控制的集成优化模型．用来解决在给定的多个潜在设施点中选出一系列设施的位置．并确定巡回运输路线．同时基于客户所采用的单时期模糊需求存贮策略确定其最佳订货量，并给出了求解该模型的启发式算法．最后通过实例计算证明了上述模型和算法的有效性．     

Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery

The vehicle routing problem with simultaneous pick-up and delivery is the problem of optimally integrating goods distribution and waste collection, when no precedence constraints are imposed on the order in which the operations must be performed. The purpose of this paper is to present heuristic algorithms to solve this problem approximately in a small amount of computing time. We present and compare constructive algorithms, local search algorithms and tabu search algorithms, reporting on our computational experience with all of them. In particular we address the issue of applying the tabu search paradigm to algorithms based on complex and variable neighborhoods. For this purpose we combine arc-exchange-based and node-exchange-based neighborhoods, employing different and interacting tabu lists. All the algorithms presented in this paper are applicable to problems in which each customer may have either a pick-up demand or a delivery demand as well as to problems in which each customer may require both kinds of operation.     

An improved heuristic for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is an important and practical problem in the OR literature. In short, the problem is to identify routes to service (e.g., pickup or deliver) demand located along the edges of a network such that the total cost of the routes is minimized. In general, a single route cannot satisfy the entire demand due to capacity constraints on the vehicles. CARP belongs to the set of NP-hard problems; consequently numerous heuristic and metaheuristic solution approaches have been developed to solve it. In this paper an “ellipse rule” based heuristic is proposed for the CARP. This approach is based on the path-scanning heuristic, one of the mostly used greedy-add heuristics for this problem. The innovation consists basically of selecting edges only inside ellipses when the vehicle is near the end of each route. This new approach was implemented and tested on three standard datasets and the solutions are compared against: (i) the original path-scanning heuristic; (ii) two other path-scanning heuristics and (iii) the three best known metaheuristics. The results indicate that the “ellipse rule” approach lead to improvements over the three path-scanning heuristics, reducing the average distance to the lower bound in the test problems by about 44%.     

Vehicle routing problem with a heterogeneous fleet and time windows

In this paper, a problem variant of the vehicle routing problem with time windows is introduced to consider vehicle routing with a heterogeneous fleet, a limited number of vehicles and time windows. A method that extends an existing tabu search procedure to solve the problem is then proposed. To evaluate the performance of the proposed method, experiments are conducted on a large set of test cases, which comprises several benchmark problems from numerous problem variants of the vehicle routing problem with a heterogeneous fleet. It is observed that the proposed method can be used to give reasonably good results for these problem variants. In addition, some ideas are presented to advance the research in heuristics, such as fair reporting standards, publication of benchmark problems and executable routines developed for algorithmic comparison.     

An improved model for vehicle routing problem with time constraint based on genetic algorithm

A vehicle routing problem (VRP) with time constraint is one of the important problems in distribution and transportation. Thus the generic VRP and its practical extensions are discussed in great detail in the literatures. In the VRP, the service of a customer must start and finish within a given time interval. The objective of this problem is to minimize the cost of servicing the set of customers without being tardy or exceeding the capacity or travel time of the vehicles. In this research we concentrated on developing a GA–TSP model by improving the genetic algorithm (GA) operators and the initial population. For the computational purpose, we developed a GUI (graphic user interface)-type computer program according to the proposed method. The computational results show that the proposed method is very effective on a set of standard test problems and it can be potentially useful in solving the VRPs.     

An optimization algorithm for the inventory routing problem with continuous moves

The typical inventory routing problem deals with the repeated distribution of a single product from a single facility with an unlimited supply to a set of customers that can all be reached with out-and-back trips. Unfortunately, this is not always the reality. We focus on the inventory routing problem with continuous moves, which incorporates two important real-life complexities: limited product availabilities at facilities and customers that cannot be served using out-and-back tours. We need to design delivery tours spanning several days, covering huge geographic areas, and involving product pickups at different facilities. We develop an integer programming based optimization algorithm capable of solving small to medium size instances. This optimization algorithm is embedded in local search procedure to improve solutions produced by a randomized greedy heuristic. We demonstrate the effectiveness of this approach in an extensive computational study.     

A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem

In the heterogeneous fleet vehicle routing problem (HVRP), several different types of vehicles can be used to service the customers. The types of vehicles differ with respect to capacity, fixed cost, and variable cost. We assume that the number of vehicles of each type is fixed and equal to a constant. We must decide how to make the best use of the fixed fleet of heterogeneous vehicles.     

The production routing problem: A review of formulations and solution algorithms

The production routing problem (PRP) combines the lot-sizing problem and the vehicle routing problem, two classical problems that have been extensively studied for more than half a century. The PRP is solved in an attempt to jointly optimize production, inventory, distribution and routing decisions and is thus a generalization of the inventory routing problem (IRP). Although the PRP has a complicated structure, there has been a growing interest in this problem during the past decade in both academia and industry. This article provides a comprehensive review of various solution techniques that have been proposed to solve the PRP. We attempt to provide an in-depth summary and discussion of different formulation schemes and of algorithmic and computational issues. Finally, we point out interesting research directions for further developments in production routing.     

A local search method for periodic inventory routing problem

Inventory routing problem considers inventory allocation and routing problems simultaneously, in which the replenishment policies and routing arrangement are determined by the supplier under the vendor managed inventory mode. What we consider here is a periodic inventory routing problem that once the delivery time, quantity and routing are determined, they will remain the same in the following periods. The problem is modeled concisely, and then it is decomposed into two subproblems, inventory problem and vehicle routing problem. The inventory problem is solved by proposing a local search method, which is achieved by four operators on delivery quantity and retailer’s demand. Insertion operator aims to insert a new replenishment point of a retailer while removal operator is to remove a replenishment point. Besides, addition operator is adopted as an assistant tool, and crossover operator is proposed for some special cases. We also propose a tabu search method to solve the routing problem. Finally, the computational results show that the method is efficient and stable.     

An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem

One of the most important problems in combinatorial optimization is the well-known vehicle routing problem (VRP), which calls for the determination of the optimal routes to be performed by a fleet of vehicles to serve a given set of customers. Recently, there has been an increasing interest towards extensions of VRP arising from real-world applications. In this paper we consider a variant in which time windows for service at the customers are given, and vehicles may perform more than one route within a working shift. We call the resulting problem the minimum multiple trip VRP (MMTVRP), where a “multiple trip” is a sequence of routes corresponding to a working shift for a vehicle. The problem objective is to minimize the overall number of the multiple trips (hence the size of the required fleet), breaking ties in favor of the minimum routing cost.     

A variable neighborhood search simheuristic for the multiperiod inventory routing problem with stochastic demands

The inventory routing problem (IRP) combines inventory management and delivery route‐planning decisions. This work presents a simheuristic approach that integrates Monte Carlo simulation within a variable neighborhood search (VNS) framework to solve the multiperiod IRP with stochastic customer demands. In this realistic variant of the problem, our goal is to establish the optimal refill policies for each customer–period combination, that is, those individual refill policies that minimize the total expected cost over the periods. This cost is the aggregation of both expected inventory and routing costs. Our simheuristic algorithm allows to consider the inventory changes between periods generated by the realization of the random demands in each period, which have an impact on the quantities to be delivered in the next period and, therefore, on the associated routing plans. A range of computational experiments are carried out in order to illustrate the potential of our simulation–optimization approach.     

A heuristic method for the vehicle routing problem with backhauls and inventory

The purpose of this paper is to determine the route of the vehicle routing problem with backhauls (VRPB), delivering new items and picking up the reused items or wastes, and resolve the inventory control decision problem simultaneously since the regular VRPB does not. Both the vehicle routing decision for delivery and pickup, and the inventory control decision affect each other and must be considered together. Hence, a mathematical model of vehicle routing problem with backhauls and inventory (VRPBI) is proposed. Since finding the optimal solution(s) for VRPBI is a NP-hard problem, this paper proposes a heuristic method, variable neighborhood tabu search (VNTS), adopting six neighborhood searching approaches to obtain the optimal solution. Moreover, this paper compares the proposed heuristic method with two other existing heuristic methods. The experimental results indicate that the proposed method is better than the two other methods in terms of average logistic cost (transportation cost and inventory cost).     

Heuristics for the mixed swapping problem

In the swapping problem, to each vertex of a complete directed graph are associated at most two object types representing its supply and demand. It is assumed that for each object type the total supply equals the total demand. A vehicle of unit capacity, starting and ending its route at an arbitrary vertex, is available to carry the objects along the arcs of the graph. The aim is to determine a minimum cost route such that each supply and demand is satisfied. When some of the object types are allowed to be temporarily unloaded at some intermediate vertices before being carried to their final destination, the problem is called the mixed swapping problem. In this paper we describe constructive and improvement heuristics which were successfully applied to randomly generated instances with up to 10,000 vertices, with an average optimality gap not exceeding 1%.     

The dynamic multiperiod vehicle routing problem with probabilistic information

This paper introduces the Dynamic Multiperiod Vehicle Routing Problem with Probabilistic Information, an extension of the Dynamic Multiperiod Vehicle Routing Problem in which, at each time period, the set of customers requiring a service in later time periods is unknown, but its probability distribution is available. Requests for service must be satisfied within a given time window that comprises several time periods of the planning horizon. We propose an adaptive service policy that aims at estimating the best time period to serve each request within its associated time window in order to reduce distribution costs. The effectiveness of this policy is compared with that of two alternative basic policies through a series of computational experiments.     

A branch-and-price approach for a multi-period vehicle routing problem

In this paper, we consider tactical planning for a class of multi-period vehicle routing problems (MPVRP). This problem involves optimizing daily product collections from several production locations over a given planning horizon. In this context, a single routing plan for the whole horizon must be prepared, and the seasonal variations in the producers’ supplies must be taken into account. Production variations over the horizon are approximated using a sequence of periods, each corresponding to a production season, while the intra-period variations are neglected. We propose a mathematical model that is based on the two-stage a priori optimization paradigm. The first stage corresponds to the design of a plan which, in the second stage, takes the different periods into account. The proposed set partitioning-based formulation is solved using a branch-and-price approach. The subproblem is a multi-period elementary shortest path problem with resource constraints (MPESPPRC), for which we propose an adaptation of the dynamic-programming-based label-correcting algorithm. Computational results show that this approach is able to solve instances with up to 60 producers and five periods.     

A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem

In the heterogeneous fixed fleet vehicle routing problem there are different types of vehicles and a given number of vehicles of each type. The resolution of this problem consists of assigning the customers to the existing vehicles and, in relation to each vehicle, defining the order of visiting each customer for the delivery or collection of goods. The objective is to minimize the total costs, satisfying customers’ requirements and visiting each customer exactly once. In this paper a tabu search algorithm is proposed and tested on several benchmark problems. The computational experiments show that the proposed algorithm produces high quality solutions within an acceptable computation time. Four new best solutions are reported for a set of test problems used in the literature.     

A convex optimization approach for solving the single-vehicle cyclic inventory routing problem

This paper investigates the mathematical structure of the Single-Vehicle Cyclic Inventory Routing Problem (SV-CIRP). The SV-CIRP is an optimization problem consisting of finding a recurring distribution plan, from a single depot to a selected subset of retailers, that maximizes the collected rewards from the visited retailers while minimizing transportation and inventory costs. It appears as fundamental building block for all variants of the cyclic inventory routing problem (CIRP). One of the main complications in developing solution methods for the SV-CIRP using the current formulations is the non-convexity of the objective function. We demonstrate how the problem can be reformulated so that its continuous relaxation is a convex optimization problem. We further examine its mathematical properties and compare our findings with statements previously done in literature. Based of these findings we propose an algorithm that solves the SV-CIRP more effectively. We present experimental results on well-known benchmark instances, for which we are able to find optimal solutions for 22 out of 50 instances and obtained new best known solutions to 23 other instances.