ABSTRACT We introduce new matheuristic algorithms for the Inventory Routing Problem with unsplit and split deliveries for both Order‐Up‐to Level and Maximum Level replenishment policies. The first matheuristic is based on the Capacitated Concentrator Location problem. The second is a route‐based approach using routes found in other schemes as input, including the ones found in the first matheuristic. We carry out extensive experiments on benchmark instances to understand their effectiveness. The results show that they are effective and require a relatively short computational time.

Abstract We study the benefit of introducing split deliveries in the inventory routing problem (IRP), both when the order‐up‐to level (OU) and the maximum level replenishment policies are applied. We first propose a mathematical formulation and solve it by implementing a branch‐and‐cut algorithm. Then, we carry out a worst‐case analysis to show the cost increase we have in the worst case by using unsplit deliveries instead of split deliveries, both for the OU and the maximum‐level replenishment policies. Extensive computational results on benchmark instances allow us to evaluate the benefit of introducing split deliveries. Finally, a sensitivity analysis on customer demands, initial inventory levels, maximum inventory levels and distance to the depot allows us to understand the instance features that make split deliveries effective in IRPs.

Abstract For the classical unsplit and split delivery capacitated vehicle routing problems, we carry out a worst‐case analysis for classes of matheuristics and compare their performance on average, on a large set of benchmark instances. The matheuristics are based on the optimal solution of the bin packing problem, the capacitated concentrator location problem, and the unsplit capacitated vehicle routing problem (CVRP). These matheuristics are compared with the classical algorithms having known finite worst‐case performance bound. For the unsplit CVRP, we provide a matheuristic having worst‐case performance bound equal to the one of the classical algorithms, but with an average percent cost increase with respect to the optimal cost equal to 1.13%. For the split delivery case, we provide a matheuristic having worst‐case performance bound 2 and an average percent cost increase with respect to the best‐known cost equal to 0.64%. Moreover, this matheuristic is able to find 22 best‐known solutions, 20 of which are new.

Abstract In the e‐commerce era, vendors have to satisfy a large number of on‐line orders, mainly from private customers, with low weight and volume, reduced delivery time, and overlap of customers' time windows. Production is made available all day long. New strategies and new technologies are emerging for deliveries. The processing time of the orders is reduced. These new features generate interesting challenges in formulating and solving Routing and Inventory Routing problems. After discussing these features and the corresponding challenges, we recall the relevant literature in Routing and Inventory Routing and provide future research directions, mainly related to routing problems with release dates, routing problems with crowdshipping, and inventory routing problems in the e‐commerce era.

We consider a problem in which a supplier must determine the transportation mode for product deliveries to satisfy demand from a set of retailers. Based on combinations of four possible transportation modes, we consider seven different distribution policies on set of instances derived from data from an Italian company. For three demand scenarios (low, moderate, high), we compare the performance of the various distribution policies. Based on demand characteristics, we characterize the optimal distribution policies. We demonstrate the increase in cost resulting from restricting mode choice to a subset of the possibilities.

We consider an inventory routing problem in discrete time where a supplier has to serve a set of customers over a multiperiod horizon. A capacity constraint for the inventory is given for each customer, and the service cannot cause any stockout situation. Two different replenishment policies are considered: the order-up-to-level and the maximum-level policies. A single vehicle with a given capacity is available. The transportation cost is proportional to the distance traveled, whereas the inventory holding cost is proportional to the level of the inventory at the customers and at the supplier. The objective is the minimization of the sum of the inventory and transportation costs. We present a heuristic that combines a tabu search scheme with ad hoc designed mixed-integer programming models. The effectiveness of the heuristic is proved over a set of benchmark instances for which the optimal solution is known.

Abstract In this paper, we study the reoptimization problems which arise when a new node is added to an optimal solution of a traveling salesman problem (TSP) instance or when a node is removed. We show that both reoptimization problems are NP‐hard. Moreover, we show that, while the cheapest insertion heuristic has a tight worst‐case ratio equal to 2 when applied to a TSP instance, it guarantees, in linear time, a tight worst‐case ratio equal to 3/2 when used to add the new node and that also the simplest heuristic to remove a node from the optimal tour guarantees a tight ratio equal to 3/2 in constant time. © 2003 Wiley Periodicals, Inc.