Keywords

1 Introduction

The delivery of goods plays an important role within the logistics and transportation sector. With the increase of demand, promoted by the growth of e-commerce or the development of new logistic strategies such as just-in-time, the number of batches to deliver also grows. Therefore, an accurate planning of the delivery routes is extremely important.

Road transport constitutes a major activity especially in urban areas, but also in many regions with limited access to other modes of transport. Globally, road transport is responsible for around a quarter of the EU’s energy consumption and about a fifth of its CO2 emissions. Moreover, freight delivery within cities is seen as a disturbing factor by its inhabitants. Freight related activities increase traffic congestion and impact on the overall quality of life. Although all these inconveniences, goods need to be delivered and it is a major source of employment.

In this paper we focus on the planning of routes for the delivery of goods in mountainous regions. This problem applied to a general setting is very well characterized within the Operations Research/Management Science community by the Vehicle Routing Problem (VRP). The simplest version of the vehicle routing problem minimizes the total cost (usually based on distance) of visiting once all the customers departing from a depot. If the customers require some demand and the vehicle performing the route has limited capacity, then the problem is extended to the Capacitated Vehicle Routing Problem (CVRP). Another assumption is made regarding the type of vehicles available. The plain CVRP assumes that all the vehicles have the same capacity. On the contrary, if vehicles have different capacities the heterogeneous fleet CVRP is solved.

Mountainous regions may have special characteristics related to the topography. Some of the customers may be accessible only by regional roads, or after crossing mountain passes which in winter times may require that vehicles are equipped adequately. City centers, which usually have particular characteristics such as narrow streets and limited parking areas, may have even harder driving conditions (such as streets with slopes). All these characteristics limit the type of vehicles that can access certain areas. In particular, large trucks may be unable to access downtown areas or may experience difficulties in driving up and down the mountains. In such situation smaller vehicles seem more appropriate to be used to serve such customers.

The CVRP with heterogeneous fleet is then extended in order to incorporate the condition that some customers cannot be served by a particular type of vehicle. The particular characteristic of this application is that most of the customers are accessible for any type of vehicle except a reduced subset. This defines the Site-Dependent Vehicle Routing Problem, SDVRP.

The vast majority of the literature dedicated to solve VRPs assumes a symmetric cost matrix, thus neglecting the cost differences associated to drive in one direction or the other. It is clear that in mountainous regions, there can be large differences in cost if the route is uphill or downhill. The variant considered in this paper looks for routing all the nodes using an heterogeneous fleet within an oriented network (asymmetric costs) and ensuring that customers and delivery vehicles are compatible (site-dependent), HSDA-VRP (Heterogeneous Site-Dependent with Asymmetric costs VRP).

The contributions and aims of this paper are: (1) to present a heuristic procedure to solve the presented problem, and (2) to analyze how solutions change when the type of customers conditions the type of vehicles that can be used.

Regarding the solution procedure, we are interested in taking advantage of the existing algorithms for solving simpler versions of the VRP. Most of the metaheuristics used for solving enhanced versions of routing problems rely on efficient methods designed for solving classical VRPs. We also base our solution procedure on enhanced metaheuristics based on the classical Clarke-and-Wright Savings heuristic. A multi-round approach is presented similar to that in [1]. At each round a CVRP is solved considering a particular vehicle and assuming an unlimited number of vehicles of this type. Solutions are built from partial solutions found by solving CVRPs ensuring that customers are served only with appropriated vehicles. The methodology used is efficient yet it is simple to implement and it has few parameters to adjust.

The rest of the paper is organized as follows. Section 2 reviews the vehicle routing problem and its extensions, and the solution approaches presented in the literature. It follows Sect. 3 with the description of the problem. In Sect. 4 we present our choice for solving this problem. Section 5 presents the benchmark instances used to test the model and compares different solution configurations. To conclude, the main findings are enumerated together with future extensions to this work.

2 Literature Review

In this section, we first provide a general picture of the VRP and its variants and later we discuss some of the solution approaches.

2.1 The Vehicle Routing Problem and Its Variants

The Vehicle Routing Problem is a classical Combinatorial Optimization Problem (COP) present in many applications. The most popular VRP variant is the Capacitated Vehicle Routing Problem. Given a fleet of identical vehicles located at a depot, the goal is to provide routes to supply a set of customers with known demand so the total delivery cost is minimized. Each customer can be visited only once and each vehicle covers only one route. The total demand served by a particular route cannot exceed the vehicle capacity.

The VRP has been extended in many directions in order to incorporate more realistic characteristics. Regarding the properties of the fleet, this can be homogeneous (all vehicles have the same characteristics) or heterogeneous (include a combination of vehicles with different capacities), vehicles can have a limited driving range [2] or drivers have scheduled breaks [3]. The network structure may be defined based on symmetric costs (usually Euclidean distances are used) or asymmetric when other factors such as fuel consumption or time used define the cost structure [4]. The routes may be open (when vehicles do not have to go back to the depot) or closed (all routes start and end at the depot, which is the most common assumption). In the multi-depot VRP, customers are served from one of the several depots. Regarding the quality of service, there can be conditions on the time when the customers can be visited, i.e. time-windows are defined for each customer (VRPTW), or the customers are not only receivers of demand but there is pick-up and delivery (VRPPD). In the site-dependent VRP (SDVRP), a subset of customers is incompatible with some vehicles of the fleet. For an extensive review of these and other VRP variants and applications, the reader is referred to [5–10].

2.2 Solution Approach

Several approaches have been proposed to solve vehicle routing problems, both exact methods and heuristics. Regarding exact methods, Kallehauge [11] reviews several formulations of the VRP and exact solution methods. Baldacci et al. [12] provide different formulations of two classes of VRP variants. The set partitioning formulation shows to be the most appropriated when exact methods are used which combined with column-generation methods solve to optimality instances of up to one hundred customers.

Since the SDVRP belongs to the NP-hard category of problems [13], heuristic algorithms are usually used in practice. Many metaheuristics have been proposed to solve the many variants of the VRP, such as Tabu Search, Variable Neighborhood Search, Scatter Search or Genetic Algorithms. The description of site-dependent VRPs was first proposed in [14] and presented several simple heuristics to solve them. Chao et al. [15] developed a Tabu Search heuristic enhanced with deterministic annealing to widen the search space. Cordeau et al. [13] derived the SDVRP as a special case of the periodic VRP and solved it with a Tabu Search heuristic for the periodic VRP. Pisinger et al. [16] presented a unified heuristic based on the Adaptive Large Neighborhood Search framework capable to solve five variants of the VRP, being the site-dependent VRP one of them. To the best of our knowledge, there are few contributions for solving the VRP combining asymmetric costs with heterogeneous fleet and site-dependent characteristics. Recently, Yusuf [17] has presented a three-phase heuristic for solving the routing of ships considering two objectives, accessibility and profitability, as a multi-depot heterogeneous site-dependent VRP with asymmetric costs. The method proposed falls into the ‘cluster first and route second’ category.

3 Description of the Problem

The HSDA-VRP is a natural extension of the classical capacitated VRP. Formally, the HSDA-VRP is defined over a complete graph \( G = (N, A) \) where \( N = \{ 0, 1, \ldots , n\} \) is the set of nodes where node 0 is assumed to be the depot and the rest represent the customers that need to be visited. Each customer has a (deterministic) demand d i . The set \( A = \left\{ {\left( {i,j} \right):i,j \in N, i \ne j} \right\} \) contains the arcs that represent the road network. The set A considers that any pair of nodes is connected, and if this differs from the reality a large cost will be associated to it. The cost of travelling on the arc (i, j) is represented by c ij . In the heterogeneous version, the cost of going from i to j is different from the cost of going from j to i. This cost can be related to distance, travelling time, fuel costs or other measures depending on the interest of the application.

Customer demands are carried by one of the vehicles available in the fleet. The set F includes all available vehicles. Each vehicle k will have particular characteristics. Most notable, the total cost of travelling from i to j will not only depend on the cost of the arc but also depends on the type of vehicle used. The cost of the arc is multiplied by a factor that depends on the vehicle type, v k, (larger vehicles have higher variable cost than smaller ones), being then the total cost of the arc a three-index parameter, \( c_{ij}^{k} = v^{k} \times c_{ij} \). Moreover, each route includes a fixed cost for using a vehicle, \( f^{k} \). Therefore, the cost of a route corresponds to the sum of the fixed and variable costs of the arcs belonging to the route. Parameter Q k denotes the maximum load that vehicle k can carry. Vehicles can serve only compatible customers, C k, where \( C^{k} \subseteq N\,\,{ \setminus }\,\{ 0\} \) is the set of nodes that vehicle k can reach.

The AHSD-VRP goal is to find the routes that will serve all customers demand and minimize the total cost of travel. This problem can easily accommodate the main characteristics present when planning routes for freight transportation by road in mountainous regions: some type of vehicles may not be able to serve a subset of particular clients (thus requiring a fleet with multiple types of vehicles) and travelling costs depend on the direction of the route and type of vehicle. For a complete mathematical formulation of this problem, the reader should refer to [1].

4 Successive Approximations Method Algorithm

The solution approach that we propose is based on the Successive Approximations Method (SAM). This scheme is based on the ideas presented in [1]. The SAM algorithm is a multi-round process in which a solution is constructed in several steps. The number of rounds is limited by the number of type of vehicles. At each round a vehicle type is selected and routes are built to serve the subset of compatible nodes. When more routes than available vehicles are scheduled, a subset of routes is randomly discarded so no more vehicles than the available ones are used. Such routes are saved as a partial solution, and the nodes belonging to the discarded routes are extracted so they can be routed in the next round. In successive rounds, another type of vehicle is selected and a new VRP is solved assuming an unlimited number of vehicles. Side conditions (such as banning vehicles from visiting incompatible customers or the vehicle capacity) are ensured within the SAM algorithm. Improvements on the routing costs due to the orientation of the routes are done locally after the assignment of the nodes that a vehicle with visit is done.

At each round a classical capacitated VRP (with unlimited and homogeneous fleet) is solved. The sub-problems are efficiently solved with a randomized version of the Clarke and Wright savings (CWS) heuristic. The CWS heuristic uses the concept of savings which is the driver for merging routes. The savings reflect the gains in terms of visiting two consecutive nodes instead of going back and forth the depot for each of them. For example, if we consider just two nodes, we have two alternatives. One is to serve each node individually which reports a total cost of 2c 0i  + 2c 0j (assuming symmetric costs). The other is a route that serves first node i, next goes to node j and returns back to the depot, which costs \( c_{0i} + c_{ij} + c_{j0} \). The difference between those two alternatives gives the following savings, \( S_{ij} = c_{0i} + c_{0j} {-} c_{ij} . \) These savings are used to select the next arc when building the routes. For a deeper explanation, the reader is referred to [18].

Figure 1 shows the scheme used to solve the heterogeneous, asymmetric and site-dependent VRP. It starts by defining the set of nodes that need to be routed. The saving cost for each link in the network is calculated. At this initial stage, the network is reduced to a non-oriented symmetric network. A weighted saving associated to the link that connects node i and j is computed as defined in [4]:

Fig. 1.
figure 1

Flowchart of the SAM for the asymmetric, heterogeneous and site-dependent vehicle routing problem

Full size image
$$ \hat{S}_{ij} = \beta \hbox{max} \left\{ {S_{ij} ,S_{ji} } \right\}\,\, + \, \left( {1 - \beta } \right)\hbox{min} \left\{ {S_{ij} ,S_{ji} } \right\}, \,\,\,\,\,\beta \,\, \in \,\,\left[ {0.5,1} \right] $$
(1)

In Eq. (1), S ij is the saving associated to the arc (i, j) and S ji is the saving associated to the arc (j, i).

Then an available vehicle is chosen and the set of nodes to be routed is modified by excluding those nodes which are incompatible with the current vehicle type. The classical Clarke and Wright Savings algorithm is run enhanced with a randomization process. Instead of using the best possible edge to build a route, all edges are assigned a probability to be selected. Better edges have higher probabilities than the others. A biased distribution such as the geometric distribution is used. Then, several runs of the same procedure come up with different proposals. The best solution is then chosen as a partial solution.

In this partial solution, it is likely that the number of vehicles used is higher than the available ones. In this case, a route for each available vehicle is selected. The other routes are removed from the partial solution. In the next round, those nodes that remain unrouted plus any other node left out because of vehicle incompatibility compound the subset of nodes to be routed.

When all nodes have been assigned to a proper vehicle, a local search procedure is applied to improve the visiting order within each route. At this point asymmetric costs are employed. A first approach is to check a given route in both directions and take that with lowest value. More advanced techniques can be used such as those presented in [4].

The scheme presented so far constitutes a basic local search heuristic that determines a set of routes ensuring that vehicles capacity is satisfied (CWS take care of the capacity constraint), customers are served with adequate vehicles (incompatible nodes are removed from the set of unrouted nodes) and routes are measured with asymmetric costs (using a specific local search). To generate new solutions, a base solution is partially destroyed (by removing a random number of routes) and the procedure is repeated.

5 Numerical Experiments

The aforementioned procedure was coded as a Java application. In order to test the potential of our method we carried out three different experiments: (i) homogeneous VRP with asymmetric instances, (ii) heterogeneous VRP with asymmetric distances and, (iii) heterogeneous VRP with asymmetric distances and site-dependency (i.e. some customers can not be served by the vehicles with the largest capacity). Each experiment was carried over all selected instances using 5 different random seeds and was executed using a 2.4 GHz core i5 personal computer with 8 Gb RAM. The execution time was established in 120 s per run.

5.1 Test Cases

In order to perform the tests described above, we have randomly selected 4 instances with Euclidean distances from classical Homogeneous VRP instances available at [19]. These instances have been modified using the following procedure:

  1. 1.

    For each pair of nodes (a, b), if the y-coordinate of b is greater than y-coordinate of a we multiply the distance of the arc by 1.1, otherwise the distance remains unmodified. This allows us to generate asymmetric instances that can be easily replicated in further research projects.

  2. 2.

    Next we generate two new vehicle capacities corresponding to the 75 % and 50 % of the original (T1) vehicle capacity. The number of available vehicles of the original capacity is chosen to be lower than the number of vehicles needed in the best known solution (BKS) for the homogeneous case with asymmetric distances.

  3. 3.

    In order to have site-dependency, for each instance we randomly select a sub-region of the whole x-y space and we restrict the nodes belonging to that area of being visited by T1-capacity vehicles.

  4. 4.

    The number of available vehicles for each of the new capacities is established to ensure the demand satisfaction constraints, considering a reduced fleet of T1-capacity trucks and the demand of the restricted nodes.

5.2 Results and Analysis

Table 1 summarizes, for each instance, the results obtained during the experiments. For each instance we report the best solution obtained in terms of total costs (vehicle fixed cost + vehicle variable cost) and its corresponding distance-based cost. Note that our objective function is the minimization of the total costs, but we used the distance-based cost only for comparison purposes with respect to the best known solutions for the symmetric case.

Table 1. Summary of results
Full size table

The left side of the table allows the comparison of the asymmetric and symmetric versions of the homogeneous VRP. In this case, since we have only one type of vehicles, the optimization of the total costs has the same solution than the optimization of routing distances. Our mean gap in terms of distance cost is 0.20 % which shows the competitiveness of our approach.

The right side of the table shows the results obtained for the heterogeneous VRP without and with site-dependency, which corresponds to experiments (ii) and (iii) respectively. In the case of non-site dependency, we can see that, in average, the heterogeneous version outperforms the homogeneous version in terms of total costs (average gap of –1.47 %) while the distance cost is 8.89 % higher, in average. Since there are less available vehicles with larger capacities, solutions are forced to use smaller vehicles (with lower fixed and variable costs) and to perform more trips. In the case of site-dependency, which restricts even more the usage of larger trucks, the total costs increases (average gap of 6.64 %) with respect to the homogeneous case, while the distance costs increase, on average 19.71 %.

6 Conclusions and Future Enhancements

We have introduced an efficient, fast and easy to implement multi-round algorithm for planning goods delivery in mountainous regions with heterogeneous fleet. This situation is represented in this article by the so-called Heterogeneous Site-Dependent with Asymmetric Costs Vehicle Routing Problem (HSDA-VRP). The proposed algorithm is based on a randomized version of the CWS heuristic which assigns a higher probability of being chosen to the most promising movements. Preliminary tests carried out show that our approach seems promising in order to solve more realistic versions of the VRP.

Further research efforts could be oriented to include real-life data or conditions (i.e. customer locations, real distance-based costs, other vehicle types and associated costs, uncertain demand, uncertain travel times, etc.)