Heuristics for a multiperiod inventory routing problem with production decisions

Manufacturers who resupply a large number of retailers on a periodic basis continually struggle with the question of how to formulate a replenishment strategy. This paper presents a comparative analysis of a series of heuristics for an inventory routing problem (IRP) that arises in a manufacturing supply chain. The IRP is formulated as a mixed integer program with the objective of maximizing the net benefits associated with making deliveries in a specific time period to a widely dispersed set of customers. It is assumed that inventory can accumulate at the customer sites, but that all demand must be met without backlogging. Because optimal solutions were not within reach of exact methods, a two-step procedure was developed that first estimates daily delivery quantities and then solves a vehicle routing problem for each day of the planning horizon. As part of the methodology, a linear program is used to determine which days it is necessary to make at least some deliveries to avoid stockouts.The IRP is investigated in the context of an integrated production–inventory–distribution–routing problem (PIDRP). The full model takes into account production decisions and inventory flow balance in each period. For the computations, a previously developed branch-and-price algorithm is used that requires the solution of multiple IRPs (one in each period) to generate columns for the master problem. Testing showed that PIDRP instances with up to eight time periods and 50 customers can be solved within 1 h. This level of performance could not be matched by either CPLEX or an exact version of the branch-and-price algorithm.     

Multi-period Vehicle Routing Problem with Due dates

In this paper we study the Multi-period Vehicle Routing Problem with Due dates (MVRPD), where customers have to be served between a release and a due date. Customers with due dates exceeding the planning period may be postponed at a cost. A fleet of capacitated vehicles is available to perform the distribution in each day of the planning period. The objective of the problem is to find vehicle routes for each day such that the overall cost of the distribution, including transportation costs, inventory costs and penalty costs for postponed service, is minimized. We present alternative formulations for the MVRPD and enhance the formulations with valid inequalities. The formulations are solved with a branch-and-cut algorithm and computationally compared. Furthermore, we present a computational analysis aimed at highlighting managerial insights. We study the potential benefit that can be achieved by incorporating flexibility in the due dates and the number of vehicles. Finally, we highlight the effect of reducing vehicle capacity.     

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 multistart adaptive memory-based tabu search algorithm for the heterogeneous fixed fleet open vehicle routing problem

This paper addressed the heterogeneous fixed fleet open vehicle routing problem (HFFOVRP), in which the demands of customers are fulfilled by a fleet of fixed number of vehicles with various capacities and related costs. Moreover, the vehicles start at the depot and terminate at one of the customers. This problem is an important variant of the classical vehicle routing problem and can cover more practical situations in transportation and logistics. We propose a multistart adaptive memory programming metaheuristic with modified tabu search algorithm to solve this new vehicle routing problem. The algorithmic efficiency and effectiveness are experimentally evaluated on a set of generated instances.     

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 genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries

The vehicle routing problem with simultaneous pick-up and deliveries, which considers simultaneous distribution and collection of goods to/from customers, is an extension of the capacitated vehicle routing problem. There are various real cases, where fleet of vehicles originated in a depot serves customers with pick-up and deliveries from/to their locations. Increasing importance of reverse logistics activities make it necessary to determine efficient and effective vehicle routes for simultaneous pick-up and delivery activities. The vehicle routing problem with simultaneous pick-up and deliveries is also NP-hard as a capacitated vehicle routing problem and this study proposes a genetic algorithm based approach to this problem. Computational example is presented with parameter settings in order to illustrate the proposed approach. Moreover, performance of the proposed approach is evaluated by solving several test problems.     

Solving a new bi-objective location-routing-inventory problem in a distribution network by meta-heuristics

This paper presents a novel bi-objective location-routing-inventory (LRI) model that considers a multi-period and multi-product system. The model considers the probabilistic travelling time among customers. This model also considers stochastic demands representing the customers’ requirement. Location and inventory-routing decisions are made in strategic and tactical levels, respectively. The customers’ uncertain demand follows a normal distribution. Each vehicle can carry all kind of products to meet the customer’s demand, and each distribution center holds a certain amount of safety stock. In addition, shortage is not allowed. The considered two objectives aim to minimize the total cost and the maximum mean time for delivering commodities to customers. Because of NP-hardness of the given problem, we apply four multi-objective meta-heuristic algorithms, namely multi-objective imperialist competitive algorithm (MOICA), multi-objective parallel simulated annealing (MOPSA), non-dominated sorting genetic algorithm II (NSGA-II) and Pareto archived evolution strategy (PAES). A comparative study of the forgoing algorithms demonstrates the effectiveness of the proposed MOICA with respect to four existing performance measures for numerous test problems.     

Robustness of inventory replenishment and customer selection policies for the dynamic and stochastic inventory-routing problem

When inventory management, distribution and routing decisions are determined simultaneously, implementing a vendor-managed inventory strategy, a difficult combinatorial optimization problem must be solved to determine which customers to visit, how much to replenish, and how to route the vehicles around them. This is known as the inventory-routing problem. We analyze a distribution system with one depot, one vehicle and many customers under the most commonly used inventory policy, namely the (s,S), for different values of s. In this paper we propose three different customer selection methods: big orders first, lowest storage first, and equal quantity discount. Each of these policies will select a different subset of customers to be replenished in each period. The selected customers must then be visited by a vehicle in order to deliver a commodity to satisfy the customers' demands. The system was analyzed using public benchmark instances of different sizes regarding the number of customers involved. We compare the quality and the robustness of our algorithms and detailed computational experiments show that our methods can significantly improve upon existing solutions from the literature.     

Arc routing in a node routing environment

We describe a special variant of the vehicle routing problem (VRP), where there are many customers per road segment. This class of VRPs arises in, e.g. mail delivery, and is a borderline case where both arc routing and node routing techniques may be applied for modeling and solving. In a real-world setting, the problem should be modeled so as to incorporate all important constraining factors. We use a simplified node routing model and aggregate customers into supernodes to reduce problem size. A tabu search metaheuristic for the standard node routing-based VRP is then applied to the aggregated version of the problem. Our method is tested both on test instances from the literature as well as on a portfolio of new test instances especially made to fit the problem at hand. Experimental results are reported, showing that aggregation of customers can lead to substantial improvements both in solution time and solution quality in this setting, especially for larger instances.     

一种求解两级车辆路径问题的Memetic 算法

两级车辆路径问题是指物资必须先由中心仓库配送至中转站(第1级),再由中转站配送至客户(第2级)的一种车辆路径问题。针对该NP难问题提出一种Memetic算法通过自底向上的方式进行求解。首先利用改进的最优切割算法MDVRP-Split将客户合理分配至中转站;然后采用局部搜索解决第1级问题,交叉产生的精英个体通过局部搜索改进。标准算例的测试结果表明,所提出算法更注重求解质量与求解效率的平衡,性能优于其他现有的两种算法。     

A tabu search procedure for coordinating production,inventory and distribution routing problems

This paper addresses the problem of optimally coordinating a production‐distribution system over a multi‐period finite horizon, where a facility production produces several items that are distributed to a set of customers by a fleet of homogeneous vehicles. The demand for each item at each customer is known over the horizon. The production planning determines how much to produce of each item in every period, while the distribution planning defines when customers should be visited, the amount of each item that should be delivered to customers and the vehicle routes. The objective is to minimize the sum of production and inventory costs at the facility, inventory costs at the customers and distribution costs. We also consider a related problem of inventory routing, where a supplier receives or produces known quantities of items in each period and has to solve the distribution problem. We propose a tabu search procedure for solving such problems, and this approach is compared with vendor managed policies proposed in the literature, in which the facility knows the inventory levels of the customers and determines the replenishment policies.     

A two-level self-adaptive variable neighborhood search algorithm for the prize-collecting vehicle routing problem

This paper investigates the prize-collecting vehicle routing problem (PCVRP), which has a strong background in practical industries. In the PCVRP, the capacities of all available vehicles are not sufficient to satisfy the demands of all customers. Consequently it is not a compulsory requirement that all customers should be visited. However, a prize can be collected once a customer is visited. In addition, it is required that the total demands of visited customers should reach a pre-specified value at least. The objective is to establish a schedule of vehicle routes so as to minimize the total transportation cost and at the same time maximize the prize collected by all vehicles. The total transportation cost consists of the total distance of vehicle routes and the sum of vehicles used in the schedule. To solve the PCVRP, a two-level self-adaptive variable neighborhood search (TLSAVNS) algorithm is developed according to the two levels of decisions in the PCVRP, namely the selection of customers to visit and the visiting sequence of selected customers in each vehicle route. The proposed TLSAVNS algorithm is self-adaptive because the neighborhoods and their search sequence are determined automatically by the algorithm itself based on the analysis of its search history. In addition, a graph extension method is adopted to obtain the lower bound for PCVRP by transforming the proposed mixed integer programming model of PCVRP into an equivalent traveling salesman problem (TSP) model, and the obtained lower bound is used to evaluate the proposed TLSAVNS algorithm. Computational results on benchmark problems show that the proposed TLSAVNS algorithm is efficient for PCVRP.     

基于两阶段求解算法的动态车辆调度问题研究

在分析需求动态变化的基础上,根据需求信息的提出顺序,将动态配送问题转换成不同时刻的静态车辆调度问题,建立基于时间轴的动态车辆调度模型;利用量子理论改进遗传算法,设计量子遗传算法;针对动态车辆调度问题实时性强的特点,设计＂初始优化阶段＋实时优化阶段＂的两阶段求解策略,通过信息更新插入动态需求客户,并对已产生的计划路径进行局部优化调整.通过仿真计算,验证了模型和算法的有效性.     

A new mathematical model for a competitive vehicle routing problem with time windows solved by simulated annealing

This paper presents an extension of a competitive vehicle routing problem with time windows (VRPTW) to find short routes with the minimum travel cost and maximum sale by providing good services to customers before delivering the products by other rival distributors. In distribution of the products with short life time that customers need special device for keeping them, reaching time to customers influences on the sales amount which the classical VRPs are unable to handle these kinds of assumptions. Hence, a new mathematical model is developed for the proposed problem and for solving the problem, a simulated annealing (SA) approach is used. Then some small test problems are solved by the SA and the results are compared with obtained results from Lingo 8.0. For large-scale problems, the, Solomon's benchmark instances with additional assumption are used. The results show that the proposed SA algorithm can find good solutions in reasonable time.     

Truck and trailer routing—Problems,heuristics and computational experience

In the truck and trailer routing problem (TTRP) the vehicle fleet consists of truck units and trailer units with some customers only accessible by truck. For that purpose trailers can be uncoupled en-route at customers where truck sub-tours are built. We discuss several variants of this specific rich vehicle routing problem (RVRP): the TTRP with and without the option of load transfer between truck and trailer as well as the requirement of time windows for delivery. We present computational experience with a simple and flexible hybrid approach which is based on local search and large neighborhood search as well as standard metaheuristic control strategies. This approach which has shown to be rather effective on several other RVRP-classes before can compete with complex state-of-the-art approaches with respect to speed and accuracy on the TTRP too.     

An evolutionary approach for multi-objective vehicle routing problems with backhauls

The vehicle routing problem (VRP) is an important aspect of transportation logistics with many variants. This paper studies the VRP with backhauls (VRPB) in which the set of customers is partitioned into two subsets: linehaul customers requiring a quantity of product to be delivered, and backhaul customers with a quantity to be picked up. The basic VRPB involves finding a collection of routes with minimum cost, such that all linehaul and backhaul customers are serviced. A common variant is the VRP with selective backhauls (VRPSB), where the collection from backhaul customers is optional. For most real world applications, the number of vehicles, the total travel cost, and the uncollected backhauls are all important objectives to be minimized, so the VRPB needs to be tackled as a multi-objective problem. In this paper, a similarity-based selection evolutionary algorithm approach is proposed for finding improved multi-objective solutions for VRPB, VRPSB, and two further generalizations of them, with fully multi-objective performance evaluation.     

The integrated production–inventory–distribution–routing problem

The integration of production and distribution decisions presents a challenging problem for manufacturers trying to optimize their supply chain. At the planning level, the immediate goal is to coordinate production, inventory, and delivery to meet customer demand so that the corresponding costs are minimized. Achieving this goal provides the foundations for streamlining the logistics network and for integrating other operational and financial components of the system. In this paper, a model is presented that includes a single production facility, a set of customers with time varying demand, a finite planning horizon, and a fleet of vehicles for making the deliveries. Demand can be satisfied from either inventory held at the customer sites or from daily product distribution. In the most restrictive case, a vehicle routing problem must be solved for each time period. The decision to visit a customer on a particular day could be to restock inventory, meet that day’s demand or both. In a less restrictive case, the routing component of the model is replaced with an allocation component only. A procedure centering on reactive tabu search is developed for solving the full problem. After a solution is found, path relinking is applied to improve the results. A novel feature of the methodology is the use of an allocation model in the form of a mixed integer program to find good feasible solutions that serve as starting points for the tabu search. Lower bounds on the optimum are obtained by solving a modified version of the allocation model. Computational testing on a set of 90 benchmark instances with up to 200 customers and 20 time periods demonstrates the effectiveness of the approach. In all cases, improvements ranging from 10–20% were realized when compared to those obtained from an existing greedy randomized adaptive search procedure (GRASP). This often came at a three- to five-fold increase in runtime, however.     

需求可拆分车辆路径问题的聚类求解算法

针对传统的车辆路径问题通常假设客户的需求不能拆分,即客户的需求由一辆车满足,而实际上通过需求的拆分可使需要的车辆数更少,从而降低配送成本的问题,分析了需求可拆分的车辆路径问题的解的特征,证明了客户需求不宜拆分应满足的条件,设计了符合解的特征的聚类算法,并对其求解.通过实验仿真,将所提出的聚类算法与蚁群算法和禁忌搜索算法进行比较,所得结果表明了所提出的算法可以更有效地求得需求可拆分车辆路径问题的优化解,是解决需求可拆分车辆路径问题的有效方法.     

A genetic algorithm for vehicle routing with backhauling

In this paper, a greedy route construction heuristic for a vehicle routing problem with backhauling is described. This heuristic inserts customers one by one into the routes using a fixed a priori ordering of customers. Then, a genetic algorithm is used to identify an ordering that produces good routes. Numerical comparisons are provided with an exact algorithm and with other heuristic approaches.     

Heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem in a carrier

In this paper, we present heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem arising in a real-world situation. In this problem, customers make requests of goods, which are packed in a sortment of boxes. The objective is to find minimum cost delivery routes for a set of identical vehicles that, departing from a depot, visit all customers only once and return to the depot. Apart of the usual 3D container loading constraints which ensure that the boxes are packed completely inside the vehicles and that the boxes do not overlap each other in each vehicle, the problem also takes into account constraints related to the vertical stability of the cargo and multi-drop situations. The algorithms are based on the combination of classical heuristics from both vehicle routing and container loading literatures, as well as two metaheuristic strategies, and their use in more elaborate procedures. Although these approaches cannot assure optimal solutions for the respective problems, they are relatively simple, fast enough to solve real instances, flexible enough to include other practical considerations, and normally assure relatively good solutions in acceptable computational times in practice. The approaches are also sufficiently generic to be embedded with algorithms other than those considered in this study, as well as they can be easily adapted to consider other practical constraints, such as the load bearing strength of the boxes, time windows and pickups and deliveries. Computational tests were performed with these methods considering instances based on the vehicle routing literature and actual customers’ orders, as well as instances based on a real-world situation of a Brazilian carrier. The results show that the heuristics are able to produce relatively good solutions for real instances with hundreds of customers and thousands of boxes.