1 Introduction and Problem Statement

Facility location problems, vehicle routing problems and inventory management are key problem areas in supply chain management [11]. The bi-objective IRP incorporates decisions on a tactical as well as on an operational planning level, such as the combination of inventory management with a Capacitated Vehicle Routing Problem (CVRP). For a detailed IRP literature review we refer to the work of [3, 4]. Furthermore, it seems promising to include a strategic planning level in the IRP to analyze the tradeoff between the two proposed objectives. Without the integration of the depot decision, previous studies show that the two objectives are clearly in conflict to each other: the simultaneously minimization of the total sum of all inventory levels at each customer at the end of each period and the total sum of all distances traveled by the vehicles in each period. While small delivery quantities lead to low inventory levels over time, large delivery quantities allow a minimization of the routing costs [5, 8]. The surveys of [6, 7, 9] investigate the combined location routing and inventory problem. Choosing depots from several potential locations and determining routes to meet customers’ demands is the aim of these works [9].

We propose a single-item IRP with repeated deliveries in a distribution network with one depot and a geographically dispersed set of n customers over a finite planning horizon. Inventory costs and capacities are considered at the customers, but not at the depot. Also, the number of vehicles is unconstrained and capacitated vehicles are used [5]. A deterministic IRP is assumed where the consumption for each customer and each period is known beforehand. When the current inventory is insufficient to satisfy the forthcoming demands \(d_{it}\) of a customer i at each period t, an action (delivery) of the supplier is needed. For satisfying the demand at the customers, we consider the strategy that the inventory currently held at the customers is either able to fully cover the customers demands at period t or the inventory is zero. Following this idea, our replenishment strategy is to avoid stockout situations by shipping enough goods in advance or just in time. With respect to the data, the customers demand can vary from period to period, resulting in changing delivery quantities over the time horizon T (dynamic IRP [8]).

This IRP model description must deal with the following decisions: (1) the depot location must be selected for the whole planning horizon, (2) delivery quantities \(q_{it}\) for each customer i, \(i = 1,\ldots ,n\) and each period \(t \in T\) must be determined, and (3) the VRP must be solved for each period t, \(t = 1,\ldots ,T\) including the delivery quantities \(q_{it}\) into tours for the involved vehicles with the already selected depot.

Two objectives are considered for the IRP: The total sum of inventory levels \(f_{1}=\sum _{t=1}^{T}\sum _{i=1}^{n} L_{i}^{t}\) is minimized, where \(L_{i}^{t}\) is the inventory level for customer i for period t. This objective function \(f_{2}= \sum _{t=1}^{T} \text {VRP}_{t}(q_{it},\ldots ,q_{nT})\) expresses the minimization of the total sum of the routing costs [5]. An overview of models with different objectives is described in [2].

2 Solution Method

Our solution method separates the problem into two decision levels: (1) the determination of delivery volumes and (2) the subsequent computation of the routing for each period which takes into account the previous calculated delivery quantities. In terms of the delivery strategy, alternatives are encoded by a n-dimensional vector \(\pi = (\pi _{1}, \ldots , \pi _{n})\) of integers. Each element \(\pi _{i}\) corresponds to a customer i and reflects for how many periods the demand of customer \(i, i = 1, \ldots , n\) is covered (delivery period). A delivery takes place when the demand cannot be satisfied with the inventory level at the customer.

We define an initial solution by identical periods for all customers, starting with 1 and increasing them by steps of 1 until the alternative cannot be added to the archive of non-dominated solutions. This is e.g. due to the fact that capacity constraints of the vehicles and at the customers must be met. For example, when the delivery period is defined as \(\pi _{i} = 4\), then the exact demand of customer i is satisfied for the next four consecutive periods. When the ‘delivery period’ is set to four for every customer, it is called ‘identical delivery periods’.

Based on this delivery strategy, the supplier ensures that the customer does not run out of products. Also, a growing demand over the time horizon results in higher delivery quantities. This is a rather direct idea of representing delivery policies. Alternatively, a ‘constant-delivery-quantity-approach’ could be applied, which leads to changing delivery periods. A more general solution is provided in [1], where customers are synchronized.

To improve the initial solutions, a run of the local search is performed on the n-dimensional vector \(\pi \) which represents the delivery periods. Particularly, an algorithm is used to change every value within \(\pi \) by \(\pm 1\). Values \(<1\) are avoided since we assume 1 as the smallest measurement of a period and a customer cannot be delivered twice a day. Throughout the search, an unbounded archive is kept which deletes solutions by dominance comparisons. Previous results indicate that the memory of a typical computer is sufficient to store these solutions [8].

3 Computational Experiments

Experiments are carried out to investigate the performance of the integration of depot decisions. In particular, two research questions are raised: (1) To which extent does the choice of the depot influence the long-term consequences of the subsequent vehicle routing and the inventory management? (2) Can we, even in rather straight-forward experiments, find improved depot locations and if so, what is the magnitude of the improvement?

The instances are proposed by [10] and usually the depot is positioned in the ‘center’ of the network so-called ‘original depot’. Here, the x-coordinate is 30 and the y-coordinate is 40. To get an idea of the graph, the x-coordinates range from a minimal value of 5 to a maximum value of 63 and the y-coordinates lie in the range from 6 to 69.

From a strategic planning level viewpoint, it might be beneficial to relocate the depot at some future time. Thus, we compare the ‘original depot’ with other depot locations. We assume that the possible depot location is at the customer’s site. For example, when an instance has 50 customers, 50 different depot locations can be analyzed. Since previous studies achieved similar results for different instances [8], we here restrict the presentation on GS-b-01 with 30 periods and 50 customers. Demand data of the customers increase over time. With respect to every period, the demand values can vary by \(\pm 25\)% around the average demand. In order to verify a similar behaviour of the algorithm, further test runs for different data sets must be performed. Note that all experiments are executed on a single core of an Intel Core i7-6600U CPU 2.60 GHz with 8 GB RAM. Also, the maximal number of evaluations is set to 300,000. Note that it takes 177 min to compute the approximation of the Pareto front for the ‘original depot’ (GS-b-01). In each evaluation, 30 vehicle routing problems have to be solved, so the computation time is considerably higher in comparison to what we commonly find in the literature. However, an earlier termination is possible when the local search has already investigated all alternatives in the archive. It is also possible that some alternatives in the archive are not yet explored by the local search.

Fig. 1
figure 1

Comparison of the approximations for the ‘original depot’ and ‘depot with ID 39’

Full size image
Fig. 2
figure 2

Comparison of the approximations for the ‘original depot’ and ‘depot with ID 12’

Full size image
Fig. 3
figure 3

Magnified results for the ‘original depot’ and ‘depot with ID 12’

Full size image

Obviously, the depot decision has long-term influences on the objectives. Exemplarily the comparison of the approximations between the ‘original depot’ and ‘depot with identification number (ID) 39’ are presented in Fig. 1. Note that the number 39 corresponds to identification number of the customer in the data set which has the x-coordinate 59 and y-coordinate 15. The whole approximation of the Pareto front for the ‘original depot’ lies below the other approximation, i.e. the approximation is considerable better. This presentation gives an idea how much influence a long-term decision, such as a ‘bad’ choice of the depot location, has on the inventory management and the vehicle routing. The approximations are compared after 235,000 number of evaluations, and e.g. not 300,000 evaluations as illustrated in Fig. 2 respectively Fig. 3, since all alternatives in the archive for ‘depot with identification number 39’ are already investigated by the local search.

The results presented in Fig. 2 for the ‘original depot’ and ‘depot with identification number 12’ (x-coordinate 31 and y-coordinate 32) are not as clear as the aforementioned findings. The gap between these approximations is much smaller compared to the approximations in Fig. 1. The advantage of choosing ‘depot with ID 12’ over the ‘original depot’ depends on the preferred part of the Pareto front. In Fig. 3 magnified results are illustrated for the approximations at the extreme end of the Pareto front. Here, it is highlighted that the solution quality is mainly better when ‘depot with ID 12’ is selected. In order to identify the magnitude of the improvement, we compute the difference between the routing distances for any given inventory level. Over the entire approximation of the Pareto front, the best improvement for the ‘depot selection with ID 12’ is 3.31%. This reduction can be meaningful since such decisions are made for a long-term planning horizon.

4 Conclusion

We have conducted experiments to study the two proposed research questions. Our main contributions are twofold. The maximal influence on the inventory levels and the routing distances of a ‘bad’ depot decision is rather significant. We could show with straight-forward experiments for benchmark data sets with a given depot that savings in transportation costs (around 3%) can be achieved with a revised depot selection. Based on these findings, it seems promising to include depot decisions in the IRP for long-term planning decisions. However, counterexamples exist for GS-b-01, where the ‘original depot’ achieves better results. For future research this must be further analyzed for more test instances with different demand patterns.