GVNS for a real-world Rich Vehicle Routing Problem with Time Windows
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)
A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem
Comput. Oper. Res.
(2011)- et al.
A goal programming approach to vehicle routing problems with soft time windows
Eur. J. Oper. Res.
(2007) - et al.
Survey: the vehicle routing problema taxonomic review
Comput. Ind. Eng.
(2009) - et al.
Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm
Appl. Soft Comput.
(2010) Future paths for integer programming and links to artificial intelligence
Comput. Oper. Res.
(1986)- et al.
A general vehicle routing problem
Eur. J. Oper. Res.
(2008) - et al.
Variable neighborhood search
Eur. J. Oper. Res.
(2008) - et al.
A variable neighborhood search heuristic for periodic routing problems
Eur. J. Oper. Res.
(2009) An improved LNS algorithm for real-time vehicle routing problem with time windows
Comput. Oper. Res.
(2012)- et al.
A heuristic for bi-objective vehicle routing with time window constraints
Int. J. Prod. Econ.
(1999)
An iterated local search algorithm for the vehicle routing problem with convex time penalty functions
Discrete Appl. Math.
Multi-objective vehicle routing problems
Eur. J. Oper. Res.
The balanced cargo vehicle routing problem with time windows
Int. J. Prod. Econ.
An efficient variable neighborhood search heuristic for very large scale vehicle routing problems
Comput. Oper. Res.
Rich vehicle routing problemsfrom a taxonomy to a definition
Eur. J. Oper. Res.
A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem
Comput. Oper. Res.
A bi-objective vehicle routing problem with time windowsa real case in Tenerife
Appl. Soft Comput. J.
A powerful route minimization heuristic for the vehicle routing problem with time windows
Oper. Res. Lett.
Variable formulation search for the cutwidth minimization problem
Appl. Soft Comput. J.
Two memetic algorithms for heterogeneous fleet vehicle routing problems
Eng. Appl. Artif. Intell.
Rich routing problems arising in supply chain management
Eur. J. Oper. Res.
A hybrid algorithm for the heterogeneous fleet vehicle routing problem
Eur. J. Oper. Res.
Heuristics for multi-attribute vehicle routing problems: a survey and synthesis
Eur. J. Oper. Res.
A unified exact method for solving different classes of vehicle routing problems
Math. Program.
Recent advances in vehicle routing exact algorithms
4OR
An algorithm for the capacitated vehicle routing problem with route balancing
Centr. Eur. J. Oper. Res.
A reactive variable neighborhood search for the vehicle routing problem with time windows
INFORMS J. Comput.
Vehicle routing problem with time windows, Part iimetaheuristics
Transp. Sci.
Cited by (46)
An effective matheuristic approach for solving the electric traveling salesperson problem with time windows and battery degradation
2024, Engineering Applications of Artificial IntelligenceRouting and scheduling field service operation by P-graph
2021, Computers and Operations ResearchCitation 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 IntelligenceCitation 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.
The heterogeneous vehicle routing problem with time windows and a limited number of resources
2020, Engineering Applications of Artificial IntelligenceAdaptive variable neighborhood search solution methods for the fleet size and mix pollution location-inventory-routing problem
2020, Expert Systems with ApplicationsCitation 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 IntelligenceCitation 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.