GVNS for a real-world Rich Vehicle Routing Problem with Time Windows

https://doi.org/10.1016/j.engappai.2015.03.009Get rights and content

Abstract

Rich Vehicle Routing Problems are vehicle routing problems (VRPs) that deal with additional constraints, which aim to better take into account the particularities of real-world applications. They combine multiple attributes, which constitute a complement to the traditional models. This work proposes an adaptive solution method based on metaheuristics for solving a Rich Vehicle Routing Problem with Time Windows. This software has been embedded into the fleet management system of a company in the Canary Islands. The attributes considered by the company are a fixed heterogeneous fleet of vehicles, soft and multiple time windows, customer priorities and vehicle–customer constraints. Furthermore, the company requires the consideration of several objective functions that include travelled distance and time/distance balance. Exact algorithms are not applicable when solving real-life large VRP instances. This work presents a General Variable Neighbourhood Search metaheuristic, which obtains high quality solutions. The computational experiments are presented in four sections, which comprise the parameter setting, the analysis of the effect of the considered attributes, the comparative with the literature for the standard VRP with Time Windows, and the study of the solutions provided by the algorithm when compared with the solutions implemented by the company.

Introduction

Many practical applications related to logistics in intelligent freight transportation systems lead to vehicle routing problems with varying degrees of difficulty regarding the problem constraints. The basic vehicle routing problem (VRP) is composed of a set of customers requiring a specified volume of goods to be delivered. A fleet of homogeneous vehicles dispatched from a single depot is used to deliver the goods, returning to the same depot once the routes have been completed. The constraints associated to the problem are that vehicles can carry a maximum capacity and each customer has to be visited once by a single vehicle. The VRP has been the subject of intensive research since the 1960s. A wide range of exact methods, heuristics and metaheuristics has been proposed in the specialized literature. We refer the interested reader to the following surveys by Schmid et al. (2013), Vidal et al. (2013), Eksioglu et al. (2009), Potvin (2009), Laporte (2009), Gendreau et al. (2008), Baldacci et al. (2007), and books by Toth and Vigo (2002) and Goldenet al. (2008).

The aim of this work is to solve a real-world VRP that has been posed to the authors by a company in the Canary Islands, Spain. The resulting software has been embedded into a fleet management system. The requirements provided by the company lead to the consideration of several constraints, which have to be integrated into the standard VRP. In the literature, there is a tremendous number of research papers related to VRP with additional constraints, which range from the need of time windows to regulations related to long-distance transportation. With the purpose of collecting all these possible constraints, Vidal et al. (2013) have given the notion of attributes of VRPs. Attributes refer to additional constraints that aim to better take into account the specificities of real-world applications. These attributes complement the traditional VRP formulations and lead to a variety of Multi-Attribute Vehicle Routing Problems (MAVRPs). These MAVRPs are supported by a well developed literature that includes a wide range of heuristics and metaheuristics (Glover, 1986). Furthermore, some MAVRPs combine multiple attributes together, obtaining the so-called Rich VRPs (RVRPs) (Schmid et al., 2013, Tarantilis et al., 2009). The problem tackled in this work corresponds to this last class of RVRPs. We refer the interested reader to the taxonomy and definition of Rich VRP proposed by Lahyani et al. (2015).

Due to the difficulty for solving VRPs to optimality, heuristics and metaheuristics constitute an increasingly active research area in the literature. In our work, a General Variable Neighbourhood Search (VNS) algorithm (Hansen et al., 2010b) is proposed for solving a Rich Vehicle Routing Problem with Time Windows (RVRPTW).

The main contributions of this paper relies upon the fact that a Rich VRPTW including several real-world constraints required by some companies has been tackled. First of all, a fixed heterogeneous fleet of vehicles is considered. Moreover, since the fleet is fixed, there might be customers which cannot be served during the planning horizon and the so-obtained infeasibility has to be managed. Two alternative solutions are given in this work; allowing the drivers work after their working shift or maximizing the number of customers served postponing the remainder. The problem combines constraints which have not been managed all together in the literature as far as we know. Computational experiments on instances based on the real data and standard benchmark instances have been carried out in this paper.

It is worth mentioning that the solution method proposed in this work, implemented as a metaheuristic, has already been integrated into the optimization tool of the fleet management system used by some companies. The fleet of a company which wants to use this optimization tool must have the necessary devices to communicate with the management system, and then the system will be able to use the optimization tool and provide an optimized route plan. The optimization tool has been implemented using C# and the current solution method has been implemented using C++. Therefore, in order to integrate the metaheuristic method in the optimization tool, a DLL has been developed. The data-interchange format used to communicate the optimization tool with the DLL has been JSON, that is a text-based open standard designed for human-readable data interchange. Furthermore, it is worth noting that through the system interface, the company can activate or deactivate the consideration of the different attributes.

Since the main goal of our work has been to embed the developed software into a commercial fleet management tool, it is desirable to develop an algorithm that not only performs well over the standard VRPTW instances, but also over constrained real-world problems. Therefore, this paper is not aimed at overcoming the best standard VRPTW results, but rather at proposing an algorithm that works effectively for solving real-world instances.

The rest of the paper is organized as follows. Section 2 is devoted to describe the Rich Vehicle Routing Problem with Time Windows (RVRPTW) tackled in this work. Section 3 thoroughly describes the General Variable Neighbourhood Search (GVNS) algorithm developed to solve the problem at hand. Section 4 summarizes the computational results carried out over both instances from the literature and real-world data. Finally, the conclusions and future work are reported in Section 5.

Section snippets

Rich Vehicle Routing Problem with Time Windows

Vidal et al. (2013) distinguish three main classes of attributes that appear frequently in the literature. These classes are the assignment of customers and routes to resources, the sequence choices, and the evaluation of fixed sequences. The attributes that are taken into consideration in this work are summarized in the following items.

  • Heterogeneous fleet: In the particular application of VRP tackled in this paper, it is considered a heterogeneous fleet of vehicles. When the number of

General Variable Neighbourhood Search for the RVRPTW

Exact algorithmic methodologies are not applicable when solving real-life large vehicle routing problem instances. Therefore, our interest is focused on metaheuristic methodologies that are capable of producing applicable high quality solutions within reasonable computing times. With the purpose of obtaining high quality solutions for the real-world problem at hand, this work proposes an algorithm based on General Variable Neighbourhood Search (GVNS) (Hansen et al., 2010b). Variable

Computational experiments

This section is devoted to thoroughly describe the computational experiments carried out in this work to assess the quality of the solutions provided by the algorithm developed to solve the RVRPTW. Our algorithm has been coded in C++ and runs on a machine with Intel(R) Core(TM) i5-2320 CPU, 3 GHz, 6 GB of RAM. The platform used has been Ubuntu 12.04.

First of all, the parameters of the algorithm are adjusted. Secondly, five different experiments are executed to analyse the effect of adding to the

Conclusions

This work tackles a real-world Rich Vehicle Routing Problem (RVRPTW) proposed by a company in Spain that combines multiple attributes together, which aim to better consider the specificities of real applications. Particularly, it has developed an efficient solution method to solve the RVRPTW. The attributes considered by the company consist of a fixed heterogeneous fleet of vehicles, soft and multiple time windows for customers, soft and multiple time intervals in the working shifts for

Acknowledgements

This work has been partially funded by the Spanish Ministry of Economy and Competitiveness (Project TIN2012-32608) and the Spanish Ministry of Industry, Tourism and Trade (Project TSI-020100-2011-298).

References (58)

  • T. Ibaraki et al.

    An iterated local search algorithm for the vehicle routing problem with convex time penalty functions

    Discrete Appl. Math.

    (2008)
  • N. Jozefowiez et al.

    Multi-objective vehicle routing problems

    Eur. J. Oper. Res.

    (2008)
  • M. Kritikos et al.

    The balanced cargo vehicle routing problem with time windows

    Int. J. Prod. Econ.

    (2010)
  • J. Kytöjoki et al.

    An efficient variable neighborhood search heuristic for very large scale vehicle routing problems

    Comput. Oper. Res.

    (2007)
  • R. Lahyani et al.

    Rich vehicle routing problemsfrom a taxonomy to a definition

    Eur. J. Oper. Res.

    (2015)
  • F. Li et al.

    A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem

    Comput. Oper. Res.

    (2007)
  • B. Melián-Batista et al.

    A bi-objective vehicle routing problem with time windowsa real case in Tenerife

    Appl. Soft Comput. J.

    (2014)
  • Y. Nagata et al.

    A powerful route minimization heuristic for the vehicle routing problem with time windows

    Oper. Res. Lett.

    (2009)
  • E. Pardo et al.

    Variable formulation search for the cutwidth minimization problem

    Appl. Soft Comput. J.

    (2013)
  • C. Prins

    Two memetic algorithms for heterogeneous fleet vehicle routing problems

    Eng. Appl. Artif. Intell.

    (2009)
  • V. Schmid et al.

    Rich routing problems arising in supply chain management

    Eur. J. Oper. Res.

    (2013)
  • A. Subramanian et al.

    A hybrid algorithm for the heterogeneous fleet vehicle routing problem

    Eur. J. Oper. Res.

    (2012)
  • T. Vidal et al.

    Heuristics for multi-attribute vehicle routing problems: a survey and synthesis

    Eur. J. Oper. Res.

    (2013)
  • Baldacci, R., Battarra, M., Vigo, D., 2008. Routing a heterogeneous fleet of vehicles. In: The Vehicle Routing Problem:...
  • R. Baldacci et al.

    A unified exact method for solving different classes of vehicle routing problems

    Math. Program.

    (2009)
  • R. Baldacci et al.

    Recent advances in vehicle routing exact algorithms

    4OR

    (2007)
  • I. Borgulya

    An algorithm for the capacitated vehicle routing problem with route balancing

    Centr. Eur. J. Oper. Res.

    (2008)
  • O. Bräysy

    A reactive variable neighborhood search for the vehicle routing problem with time windows

    INFORMS J. Comput.

    (2003)
  • O. Bräysy et al.

    Vehicle routing problem with time windows, Part iimetaheuristics

    Transp. Sci.

    (2005)
  • Cited by (46)

    • Routing and scheduling field service operation by P-graph

      2021, Computers and Operations Research
      Citation Excerpt :

      Rieck and Zimmermann (2010) presented a two-index vehicle-flow model that combines routing under complex conditions and assigning vehicles to loading points. To solve the real-life VRP with time windows, de Armas et al. (2015) introduced a metaheuristic called general variable neighborhood search, which provided high-quality solutions. In RVRP, the integration of a Geographic Information System (GIS) is a common requirement, which allows for more accurate determination of distances and travel times.

    • A lexicographic-based two-stage algorithm for vehicle routing problem with simultaneous pickup–delivery and time window

      2020, Engineering Applications of Artificial Intelligence
      Citation Excerpt :

      First, the main scheme of the VNS-BSTS is presented, then VNS and BSTS are introduced, respectively. Variable neighborhood search (VNS) (de Armas et al., 2015), initially proposed by Mladenović and Hansen (1997), is very easy to implement and can be combined with any local search algorithm as a subroutine easily. TS is a meta-heuristic search method employing local search methods with the particular memory mechanism for mathematical optimization.

    • Adaptive variable neighborhood search solution methods for the fleet size and mix pollution location-inventory-routing problem

      2020, Expert Systems with Applications
      Citation Excerpt :

      General variable neighborhood search (GVNS) is a widely used VNS variant, which uses a VND method as its main improvement phase (Hansen et al., 2017). Recently many GVNS schemes have been efficiently applied on solving hard combinatorial optimization problems (De Armas, Melián-Batista, Moreno-Pérez, and Brito, 2015, Bezerra, de Souza, and Souza, 2018, Karakostas, Sifaleras, and Georgiadis, 2019a, Mikić, Todosijević, & Urošević, 2019). To build an initial feasible solution, a three-phase construction method is proposed.

    • Demand coverage diversity based ant colony optimization for dynamic vehicle routing problems

      2020, Engineering Applications of Artificial Intelligence
      Citation Excerpt :

      To be specific, it involved a set of customers at different locations and a fleet of vehicles in a central depot, aiming to find optimal traveling routes for the vehicles to serve all the customers. Since the introduction of basic VRP, different variants of VRPs have been developed to model different types of real-world scenarios, i.e.,VRP with time windows (de Armas et al., 2015; Gong et al., 2012), VRP with pickup and delivery (Ai and Kachitvichyanukul, 2009; Mingyong and Erbao, 2010), VRP with stochastic demands (Bent and Hentenryck, 2004; Marinakis et al., 2013), multitrip VRP (Dorling et al., 2017; Rivera et al., 2016) and multidepot VRP (Ho et al., 2008; Wang et al., 2018), etc. The above VRP variants regard that all the routing information is known in advance and does not change during the route execution, i.e., vehicles, customers and traffic condition.

    View all citing articles on Scopus
    View full text