Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The physical distribution of goods is an important part of the supply chain in various industries. On an operative level, the Vehicle Routing Problem (VRP) deals with this task and therefore is one of the most studied optimization problems in Operations Research. Since it has been introduced as “Truck Dispatching Problem” by Dantzig and Ramser (1959), a lot of research has led to a vast amount of different problem variants, each considering another problem emerging from the business world. However, most of them concentrate on just one or a few specific topics, e.g. VRP with Time Windows (VRPTW) (Cordeau et al. 2002), VRP with Pickups and Deliveries (VRPPD) (Parragh et al. 2008) or their combined consideration PDPTW (Dumas et al. 1991). Thus, they are often not sufficient for an application on complex real-world problems (Hartl et al. 2006). Besides this application pull, a push from the scientific community has been noticed as less comprehensive variants of the VRP are viewed as near-complete explored (Hasle and Kloster 2007). Hence, in recent years a new class of problems called real-life VRP’s or Rich Vehicle Routing Problems (RVRP) was developed to fill this gap between theory and practice. Here, a combination of several features leads to a better applicability on issues from the business world. The occurring characteristics are very diverse and can be, for instance, vehicle-, driver-, location-, or request-related (Drexl 2012). However, a consistent definition of RVRP’s does not yet exist. In a recent approach, Lahyani et al. (2015) formulated one based on a new taxonomy. There, an issue must have a minimum amount of different characteristics to be classified as RVRP. This new approach shows that there is still an open field of research to adapt the academic methods to the practical needs.

An industry, where vehicle routing is an important part for distributing goods, is the food retailing sector (Akkerman et al. 2010). This topic has been studied before by different authors. Some focus on the perishability of the food (Hsu et al. 2007; Osvald and Zadnik Stirn 2008), whereas others consider the combined transport of products with different transport temperatures (Chajakis and Guignard 2003; Ambrosino and Sciomachen 2007). The real-world issue motivating this paper is part of the latter subject and it will be specified in the next section for a better understanding. Afterwards, the occurring problem variants are derived from the characteristics. In Sect. 3, the cost function used by the retail company will be explained in detail as it differs from the usual form and therefore gives insight into the business practice. In the last section, an outlook on future research concludes this paper.

2 Case Study and Relevant VRP Variants

We consider a large German food retailing company which has to distribute its products from a central warehouse to about 120 markets on a daily basis. The company cooperates with several carriers to fulfill this task. Each of them is assigned a proprietary carrier region. This means that the markets are located in just one region and the carriers exclusively are allowed to supply those branches corresponding to their area. Thereby, the scheduling of the routes for the next day is made by the staff of the central warehouse within a tight timeframe of two hours, whereas the carriers provide the capacities, e.g. vehicles or drivers, needed. Hence, capacity shortages regarding the number of vehicles or a violation of the drivers’ working hours cannot occur. Besides, there are further particularities. The supply of the markets is only feasible at specific periods, though, there can be more than one—usually one in the early morning and one in the afternoon. Additionally, different handling times exist for unloading the vehicle at the markets. Another important feature is the existence of a heterogeneous set of goods as the company is a full range trader. Especially the transport of food is strictly regulated by law and thus, the goods are categorized in four commodity classes (CC) based on different transport temperatures as shown in Table 1. To cope with this feature, the load bed of the vehicles can be divided into up to three compartments with flexible sizes. Since cooling units are solely installed at the front and the rear end of the trailer, the middle compartment is not refrigerable. In addition to the supply with products, there are empty transport containers like pallets or stillages which have to be transported back to the depot according to a predefined schedule. From this features, a number of variants of the VRP can be derived and the issue may be classified as RVRP. This will be described below.

Table 1 Commodity classes existing in the case study
Full size table

Since the transport quantities are large for each market, the capacity of one vehicle is not sufficient and therefore the orders of the markets need to be split among different routes. Hence, this problem is called Split Delivery VRP (SDVRP) (Archetti and Speranza 2012) and the allocation of transport quantities to vehicles becomes part of the optimization problem. Due to the shipment of exclusively whole pallets, those quantities are integer. As explained above, the distinction between commodity classes leads to incompatibilities regarding a spatial combined transport. As a consequence, there have to be either vehicles dedicated to just one commodity class or the load bed of a vehicle has to be separated into compartments. For the latter is economically favorable, the VRP with Compartments (VRPC) (Derigs et al. 2011) is present in the business case. Given the problem characteristics mentioned above, this results in specific constraints like a maximum of one commodity class per compartment or a maximum of three different compartments per vehicle. Another problem arises in the context of compartments as the vehicles are unloaded from the rear end via the last in—first out method. Therefore, goods in a compartment are not reachable until the prior compartments are empty. This issue is part of a wide problem family referred to as VRP with Loading Constraints (Iori and Martello 2010). As mentioned above, there are multiple time windows for the delivery present in the underlying case and thus, it can also be seen as a VRPTW. Resulting from the necessity to carry empties from the markets to the central warehouse and the guideline that the complete delivery has to be done before the pickup, the VRP with Backhauls (VRPB) (Goetschalckx and Jacobs-Blecha 1989) originates. Furthermore, following from the cooperation between the retail company and the carriers, the vehicles do not need to return to the depot. This characteristic is essential for Open VRP’s (OVRP) (Li et al. 2007).

Another particular property of the presented case study is the calculation of transportation costs. In most research papers, the cost function is linear and depends just on the distance traveled. However, this does not apply here as transportation costs are based on contracts between the enterprises. These transport tariffs can be complex and are sparsely studied in the academic literature, although they are often used in practice (Drexl 2012). To the best of our knowledge, a more intense examination of tariffs in the context of vehicle routing has not yet taken place. In order to contribute to fill this gap, the real-world cost function emerging from the business case will be considered in greater detail hereinafter.

3 Tariff-Based Cost Function in a Real-World Application

Following from a large number of different objectives in distribution management, there also exist various objectives for VRP’s. The most commonly used is the minimization of the total costs. Other objectives could be to minimize the total length of all routes or the number of vehicles employed, a balancing of routes as well as the maximization of profit. Furthermore, a combination of different goals is possible and therefore the implementation of a hierarchical objective system or the usage of multi-criteria optimization methods is necessary (Irnich et al. 2014). Nevertheless, cost minimization is still the most important objective and as it is the single aim of the underlying real-world issue, it will be further examined.

As common, the VRP is modeled as a graph theory problem on a complete graph \({G} = ({V},{A})\) with the set of vertices \(V = \left( {0, \ldots ,n} \right)\) and the set of arcs \(A\). Vertices \(i = 1, \ldots ,n\) correspond to the markets, while vertex 0 denotes the central warehouse. The arcs represent the infrastructure connecting the markets. Additionally, there are \(K\) vehicles which transport the goods. Since the VRP was introduced by Dantzig and Ramser, their objective function has become some kind of standard formulation for many theoretical problems. In a three-index vehicle flow model, which is, unlike the two-index model, capable of a distinction between routes and therefore necessary for the present case, it can be stated as follows (Toth and Vigo 2002)

$$\mathop \sum \limits_{i \in V} \mathop \sum \limits_{j \in V} c_{ij} \cdot \mathop \sum \limits_{k = 1}^{K} x_{ijk} .$$
(1)

Here, \(c_{ij}\) is the cost associated with the usage of arc \(\left( {i,j} \right) \in A\) and \(x_{ijk}\) is a binary variable with the possible values

$$x_{ijk} = \left\{ {\begin{array}{*{20}l} 1 \hfill & { , {\text{if vehicle}} \,k\,{\text{travels directly from vertex}}\, i\,{\text{to vertex}}\,j} \hfill \\ 0 \hfill & { , {\text{otherwise}} .} \hfill \\ \end{array} } \right.$$
(2)

Hence, this formulation requires that the elements of the cost matrix \(c\) are known in advance and are independent of anything other than the starting and ending points to calculate the total costs. Unfortunately, this is not given in many real-world applications. Here, costs often are based on transport tariffs and therefore depend on load specifics (e.g. weight, volume), distances, time, or the chosen itinerary. Likewise, the decision variables may be connected in a non-linear way. As a result, real-world objective functions are much more complex than the one shown in (1) (Irnich et al. 2014). This also applies to the cost function present in the business case described above, which will be further studied in the following.

First of all, the price structure among the retail company and the carriers shall be explained as it is highly problem-specific. The retail company only knows prices for the trips from the central warehouse to each supermarket—prices for trips from one branch to another do not exist per se. They are calculated based on a ratio called detour and the particular method will be explained in Sect. 3.2. The price structure is defined by two criteria. On the one hand a distinction is made between routes without (open route) and with (closed route) return of empties. And on the other hand every commodity class \(p = 1, \ldots ,P\) has its own price. This results in 2\(P\) different, nonnegative prices for open routes \(po_{ip}\) as well as closed routes \(pc_{ip}\) for each market i. The price structure for three markets is exemplarily shown in Table 2.

Table 2 Price structure for the supply of markets 1, 2 and 3
Full size table

Due to the fact that prices for trips between two stores do not exist, the costs for multi-customer routes are not easy to calculate. Therefore, the charging of single-customer routes, which contain solely one branch, is explained first and afterwards an extension to multi-customer routes is made.

3.1 Single-Customer Routes

In the business case, the costs \(P_{k}^\text{s}\) of a single-customer route k are determined by the most expensive commodity class transported on the route. As the assumption \(pc_{ip} > po_{ip}\) is always valid, the price disparity \((pc_{ip} - po_{ip} )\) between a closed and an open route may be seen as a surcharge for backhauls onto the open route price which has to be considered if empty pallets or stillages are carried from the store to the central warehouse. This approach leads to

$$P_{k}^\text{s} = \mathop {\hbox{max} }\limits_{p} \left( {y_{ikp} \cdot po_{ip} + x_{i0k} \cdot (pc_{ip} - po_{ip} )} \right),$$
(3)

whereby \(y_{ikp} \in \{ 0;1\}\) is a binary variable which attains one if the commodity class p is transported on route k to store i and zero otherwise. The procedure shall be illustrated by an example.

The stores from Table 2 are supplied with goods by different single-customer routes as represented in Table 3.

Table 3 Examples of single-customer routes
Full size table

Route 1 is a closed route \((x_{101} = 1)\), whereas routes 2 and 3 do not return to the depot \((x_{202} = 0, x_{303} = 0)\). Equally, the values of the binary variables \(y_{ikp}\) are easy to derive from the shown transport quantities. Having the given data, the price of route 1 can be computed by

$$P_{1}^\text{s} = \hbox{max} \left( {\begin{array}{*{20}c} {1 \cdot 270 + 1 \cdot \left( {350 - 270} \right), 1 \cdot 260 + 1 \cdot \left( {330 - 260} \right), } \\ {0 \cdot 240 + 1 \cdot \left( {300 - 240} \right), 1 \cdot 230 + 1 \cdot \left( {280 - 250} \right)} \\ \end{array} } \right) = 350$$
(4)

and equate to the maximal price. Likewise, the prices of routes 2 and 3 can be easily calculated as \(P_{2}^\text{s} = \hbox{max} \left( {0, 210, 200, 190} \right) = 210\) respectively

$$P_{3}^\text{s} = \hbox{max} \left( {350, 0, 0, 310} \right) = 350.$$

3.2 Multi-customer Routes

As an extension to single-customer routes, multi-customer routes contain more than one store and hence the distance between the branches covered by the carrier and the additional stops have to be taken into account. This is realized as follows.

Multi-customer route costs of a route \(k\) consist of four parts. The first one is called base price \((P_{k}^{\text{base}} )\) and is the maximum open route price of all stores visited and all commodity classes transported on a route:

$$P_{k}^{\text{base}} = \mathop {\hbox{max} }\limits_{i} \left( {\mathop {\hbox{max} }\limits_{p} (y_{ikp} \cdot po_{ip} )} \right).$$
(5)

Since the price calculation of the carrier is based on the distance between depot and market, the deviation of the direct distance to the furthermost branch and the length of the route from the warehouse to the last market is decisive for costing. This difference is called detour \(dt_{k}\) and involving the distances \(d_{ij}\) plus the binary variable

$$w_{ik} = \left\{ {\begin{array}{*{20}l} 1 \hfill & { , {\text{if branch}} \,i\, {\text{is approached by vehicle}}\,k} \hfill \\ 0 \hfill & { , {\text{otherwise}}} \hfill \\ \end{array} } \right.$$
(6)

it can be computed in the following way:

$$dt_{k} = \mathop \sum \limits_{i \in V} \mathop \sum \limits_{{j \in V\backslash \{ 0\} }} x_{ijk} \cdot d_{ij} - \mathop {\hbox{max} }\limits_{i} \left( {w_{ik} \cdot d_{0i} } \right).$$
(7)

However, a detour up to a permitted distance \(dt^{\text{perm}}\) is already included in the prices given by the carriers and therefore the detour price \(P_{k}^{\text{detour}}\) is omitted if \(dt_{k}\) does not exceed \(dt^{\text{perm}}\). Otherwise the base price is multiplied by a coefficient so that

$$\begin{aligned} P_{k}^{\text{detour}} & = P_{k}^{\text{base}} \cdot \frac{{dt_{k} - dt^{\text{perm}} }}{{\mathop {\hbox{max} }\limits_{i} \left( {w_{ik} \cdot d_{0i} } \right)}} \\ & = P_{k}^{\text{base}} \cdot \left( {\frac{{\mathop \sum \nolimits_{i \in V} \mathop \sum \nolimits_{{j \in V\backslash \left\{ 0 \right\}}} x_{ijk} \cdot d_{ij} - dt^{\text{perm}} }}{{\mathop {\hbox{max} }\limits_{i} \left( {w_{ik} \cdot d_{0i} } \right)}} - 1} \right). \\ \end{aligned}$$
(8)

Furthermore, a fixed wage of \(cS\) for every stop in addition to the first one has to be paid. This leads to a stop price equivalent to

$$P_{k}^{\text{stop}} = \left( {\mathop \sum \limits_{i \in V} w_{ik} - 1} \right) \cdot cS.$$
(9)

As well as on single-customer routes, it is possible to carry empties on multi-customer routes. Since this is allowed exclusively from the last store in the sequence to the depot, the backhaul price depends on the surcharge of the last market and may be expressed as

$$P_{k}^{\text{backhaul}} = \mathop {\hbox{max} }\limits_{p} \left( {x_{i0k} \cdot (pc_{ip} - po_{ip} ) } \right).$$
(10)

Finally, the total price of a route k can be determined by the summation over all components, whereby a distinction has to be made regarding the travelled detour:

$$P_{k} = \left\{ {\begin{array}{*{20}l} {\mathop {\hbox{max} }\limits_{i} \left( {\mathop {\hbox{max} }\limits_{p} \left( {y_{ikp} \cdot po_{ip} } \right)} \right)} \hfill & {} \hfill \\ { \cdot \left( {\frac{{\mathop \sum \nolimits_{i \in V} \mathop \sum \nolimits_{{j \in V\backslash \left\{ 0 \right\}}} x_{ijk} \cdot d_{ij} - dt^{\text{perm}} }}{{\mathop {\hbox{max} }\limits_{i} \left( {w_{ik} \cdot d_{0i} } \right)}}} \right)} \hfill & {} \hfill \\ { + \left( {\mathop \sum \limits_{i \in V} w_{ik} - 1} \right) \cdot cS} \hfill & {} \hfill \\ { + \mathop {\hbox{max} }\limits_{p} \left( {x_{i0k} \cdot \left( {pc_{ip} - po_{ip} } \right)} \right)} \hfill & { , {\text{if }} dt_{k} > dt^{\text{perm}} } \hfill \\ {\mathop {\hbox{max} }\limits_{i} \left( {\mathop {\hbox{max} }\limits_{p} \left( {y_{ikp} \cdot po_{ip} } \right)} \right)} \hfill & {} \hfill \\ { + \left( {\mathop \sum \limits_{i \in V} w_{ik} - 1} \right) \cdot cS} \hfill & {} \hfill \\ { + \mathop {\hbox{max} }\limits_{p} \left( {x_{i0k} \cdot \left( {pc_{ip} - po_{ip} } \right)} \right)} \hfill & { , {\text{if }} dt_{k} \le dt^{\text{perm}} .} \hfill \\ \end{array} } \right.$$
(11)

This indicates that (3) is a special case of (11) with detour equal to zero and no stop price. As for the single-customer routes, an example shall explain this approach in the following.

The three markets from Table 2 are now supplied by one vehicle. The distances needed to calculate the multi-route costs are given in Fig. 1a and the transport quantities as well as the backhaul characteristics are shown in Table 3.

Fig. 1
figure 1

Distances and routes used in the example. a Distances, b Route 1, c Route 2

Full size image
Table 4 Transport quantities and backhaul characteristics of a multi-customer route
Full size table

To show how the detour influences the price, the same quantities are delivered by the two different routes in Fig. 1b respectively 1c. The base price of this market-commodity class combinations is

$$P_{1}^{\text{base}} = \hbox{max} \left( {\hbox{max} \left( {270, 0, 0, 0} \right),\hbox{max} \left( {0, 0, 0, 190} \right),\hbox{max} \left( {0, 330, 0, 310} \right)} \right) = 330 = P_{2}^{\text{base}} .$$
(12)

Furthermore, there are \(3! = 6\) possibilities to visit all branches in one route. Each of them has a varying length and hence, another detour length. For Route 1 with the sequence \([0, 1, 2, 3]\) in Fig. 1b the detour is calculated by

$$dt_{1} = 160 + 125 + 77 - \hbox{max} \left( {160, 150, 200} \right) = 162,$$
(13)

whereas Route 2 (Fig. 1c) with the same configuration but another sequence \([0, 2, 3, 1]\) yields

$$dt_{2} = 150 + 77 + 95 - \hbox{max} \left( {160, 150, 200} \right) = 122.$$
(14)

With a given permitted detour of \(dt^{\text{perm}} = 50\), the detour prices result in

$$P_{1}^{\text{detour}} = 330 \cdot \frac{162 - 50}{{\hbox{max} \left( {160, 150, 200} \right)}} = 184.8$$
(15)

and

$$P_{2}^{\text{detour}} = 330 \cdot \frac{122 - 50}{{\hbox{max} \left( {160, 150, 200} \right)}} = 118.8.$$
(16)

It is obvious that they are—as long as the permitted detour is not exceeded—dependent on the route length and therefore on the chosen itinerary. If, for example, a longer detour of 170 is allowed, then both detour prices would be equal to zero and the itinerary would be irrelevant. In contrary, the stop price just corresponds with the number of stops. A stop wage of \(cS = 25\) leads to

$$P_{1}^{\text{stop}} = \left( {3 - 1} \right) \cdot 25 = 50 = P_{2}^{\text{stop}} .$$
(17)

The same holds true for the backhaul price. Since there is no return of empties needed in the example, \(P_{1}^{\text{backhaul}} = P_{2}^{\text{backhaul}} = 0\) is valid. If a backhaul is necessary, the number of possible itineraries would reduce to \(\left( {3 - 1} \right)! = 2\), since the last market in the sequence is fixed. For instance, in the case of a backhaul from market 3, route 2 would be infeasible. The total prices of the routes 1 and 2 are

$$P_{1} = 330 + 184.8 + 50 = 564.8$$
(18)

and \(P_{2} = 498.8\).

4 Conclusion

This paper presented a business case occurring in the vehicle routing of a food retailing company, which can be considered as RVRP. Besides the deduction of several VRP variants, like the VRPC and VRPTW, from given peculiarities, it was especially focused on the exposition of the real-world cost function. This is based on negotiated transport tariffs, which take heterogeneous products as well as the chosen itinerary into account. Therefore, it is more complex and practically relevant than the widely used standard version originating from the first mathematical consideration of Dantzig and Ramser (1959). Yet, it is highly problem-specific and as a consequence, not transferable to other problems. Though, it could get even more complex if the transport across different carrier regions is no longer prohibited. However, an involvement of additional properties is accompanied by the introduction of new variables and constraints—if a consistent mathematical formulation is achievable at all. In this context, it would be possible to model the costs of a route \(P_{k}\) as decision variable and to implement the cost function as a constraint. Thus, nonlinear components like the maximum operators could be eliminated. Again, this is highly problem-specific and can only be discussed further with respect to the complete model.

Furthermore, modeling the cost function is just one part of handling a VRP on which we concentrated here due to the complex calculation of transportation costs. Besides the obviously necessary constraints that insure the feasibility of the solutions in accordance with the given case study, the problem-solving itself, i.e., the finding of feasible and good solutions, constitutes another major task. Since the problem instance in the case study contains ca. 120 markets, which is quite large, and the constraints are diverse, a solution with proven optimality is unlikely to determine. Additionally, the short planning timeframe restricts possible solution methods. Therefore, heuristics, especially metaheuristics, are probably most suitable and thus the subject of future research.