VRP and Its Variants: History
View Latest Version
Please note this is an old version of this entry, which may differ significantly from the current revision.
Contributor:
Alice Nobre
,
Caio Cézar Rodrigues Oliveira
,
Denilson Ricardo De Lucena Nunes
,
André Cristiano Da Silva Melo
,
Gil Eduardo Guimarães
,
Rosley Anholon
,
Vitor Martins

The VRP solution revolves around finding a route plan, that is, a set of routes associated with a fleet of vehicles, which implies low costs associated with time, fuel, total distance traveled, and labor charges. 

  • vehicle routing problem
  • sustainability
  • TOPSIS

1. Introduction

The vehicle routing problem has been discussed in the literature and according to [1], in a simplified way, the problem consists of resources that are available and need to be transported to different locations where they are needed; and in the course of this movement, there is an associated cost. Additionally, according to these authors, the first formulation for the problem dates back to the 1940s; currently, the problem is well known as the vehicle routing problem (VRP).
The VRP solution revolves around finding a route plan, that is, a set of routes associated with a fleet of vehicles, which implies low costs associated with time, fuel, total distance traveled, and labor charges. These solutions are obtained through optimization problems that may not result in optimal solutions. In recent decades, different variations of the VRP can lead to different optimization goals. The authors of [2] developed a review study on solutions that simultaneously consider more than one optimization objective.
In addition to the cost context, other perspectives have been associated with a good route plan, such as the level of customer service [3][4][5][6] expressed by objectives such as waiting time, average delay and number of customers served per route, and have been considered in optimization problems. Objectives related to environmental issues [2][7] and risks have also been observed in the literature [8].
It is worth highlighting the perspective of the impact of the route plan on sustainability issues. According to [9], the growth of scripting considering sustainable aspects requires cooperation between regional economic development and environmental conservation, representing a global concern for both developed and developing countries, as in the case of Brazil. Brazil is a developing economy that has technological and logistical infrastructure limitations, with road transport as the main mode of transport, so the country has difficulties in promoting the achievement of goals aligned with sustainable objectives, which justifies the development of studies that enhance the debate in the area. There are several operational restrictions to be considered in a route plan, such as transport capacity, demand, time available to operate, and the type of modal to be used. The authors of [10] argue that transport activity, which is included in the development of the route plan, directly influences the three dimensions of sustainability (environmental, economic and social) and therefore becomes an essential operation in contributing to the achievement of sustainable objectives.
Given the growing diversity of elements to be considered in the elaboration of a route plan, together with interest in the VRP and its variants, the definition of a route plan can result in different aspects of performance depending on the objectives considered in its definition. Therefore, an important question emerges: “Considering the objectives found in the literature, which ones should be considered in the vehicle routing problem, what is their degree of importance in the perception of professionals in the area and how do they relate to the sustainability guidelines?”

2. VRP

The VRP can be interpreted as the definition of delivery routes assigned to a fleet of vehicles to obtain an optimal result in a given objective [1][11]. In the 1990s, the authors of [12][13] mathematically described the problem as a graph G = (V, A), where V = {v1, v2,..., vn} is a set of vertices or cities and A is a set of arcs such that A = {(vi, vj):i ≠ j, vi, vj∈V}. Additionally, according to the same authors, for each arc “path” used in the route plan, there is a parameter cij that generally represents the costs involved in transporting from vi to vj, and in specific contexts can represent distances traveled or travel time.
The different sets of routes that meet the constraints of the problem can be indefinitely gridded, but the set that matters is the one that will lead to the lowest or lowest total cost obtained by ∑cij. The VRP problem is usually formulated as an optimization problem, where the objective function expresses which aspect of the route plan should be optimized. The definition of route plans as a VRP solution has been widely discussed in the literature and several exact and sub-optimal methods have been obtained over time [2][14]. The authors of [15] argue that vehicle routing and scheduling are fundamental problems, both in the context of primary and secondary distribution. For primary distribution purposes, the services of third-party logistics companies are usually purchased. On the other hand, secondary distribution is generally carried out through its fleet of vehicles. Optimizing distribution at both levels is challenging and realistic routing plans can often require considering multiple conflicting objectives and identifying an appropriate trade-off.
In parallel with developing these more efficient solutions to the problem, new variants emerged to make the problem closer to practical situations. The inclusion of time windows is an example. Each customer that must be visited informs a time interval [16] in which it is convenient to receive the requested service. Another classic variant of the VRP includes a restriction on the transport capacity of each vehicle belonging to the fleet [5][17]. These are well-established variants in the literature, but in recent decades new perspectives have been considered in the elaboration of a route plan, for example, quality of service and sustainability issues, especially taking into account the triple bottom line vision (social, economic, and environmental) [7][18]. Furthermore, new technologies such as drones [4] and the evolution of communication technologies have taken the optimization goals of VRP and variants far beyond direct cost, distance traveled and travel time.
Many performance objectives can be considered in the formulations of the VRP. Given the diversity of performance objectives, the literature sought to identify which performance objectives compose the solution proposals for the VRP and its variants. The articles that served as the basis for this survey are from the last 5 years, and all are literature review articles in which their authors mapped the different objective functions according to the scope of their research. It was then possible to group the different performance objectives into four dimensions: cost, productivity, quality and time (Table 1).
Table 1. Performance objectives have been identified in the literature.
Dimensions Code Performance Objectives References
Cost Cos_01 Number of stops and transported volume [5][16]
Cos_02 Fuel [14][19][20]
Cos_03 Labor [19][20][21][22][23][24]
Cos_04 Vehicle and machinery maintenance [7][19]
Cos_05 Unit of goods delivered [23]
Cos_06 Subcontracting [7]
Cos_07 Overtime worked cost [16]
Productivity Pro_01 Total number of vehicles [2][6][8][16][18][21]
Pro_02 Number of customers served [3]
Pro_03 As fast as possible [4]
Pro_04 Risks associated with the route [2][7][8]
Pro_05 total distance traveled [3][4][6][8][18][21];
Pro_06 Profit [1][7][14][22]
Quality Qua_01 Total delay in deliveries [3][14][16][22]
Qua_02 Total emissions of pollutants [2][4][14][18][21]
Qua_03 Service Level (fraction of customer demand met by the route plan) [6][14][18]
Qua_04 Product damage depending on the route [22]
Time Tim_01 Customer wait [2][4][14][22]
Tim_02 Total congestion time [22]
Tim_03 Total service time [1][3][17]
Tim_04 Loading/unloading times [18]
Tim_05 Total empty truck time [17]
As shown in Table 1, it is observed that the performance objectives are grouped by dimensions. The cost dimension refers to performance objectives that are directly related to the operation costing issues. In the productivity dimension, the related objectives are linked to the idea of production rate, which leads to more operational issues. In the quality dimension, aspects related to the customer’s vision are observed. Finally, in the time dimension, performance objectives are related to the idea of time and can also be attributed to other dimensions directly or indirectly, as in the case of the customer’s expectation objective, which can also be interpreted as an element of quality. The 22 performance objectives identified in the literature were considered in the survey carried out with professionals.
Given the context, it is also relevant to emphasize the importance of the route plan to achieve sustainable goals and objectives both in the environmental dimension and in issues related to economic and social aspects [25]. The elaboration of the route plan aligned with sustainable issues has been gradually increasing [25]. According to [26], a joint development of the routing plan, inventory management, and operational adjustments ensure good cost management and reduce polluting gas emissions from activities belonging to a supply chain network.
Since production and consumption generally occur in different locations and with considerable distances, issues of negative environmental impacts are recurrent in this context, caused mostly by polluting gas emissions from physical transport activities [25]. Regarding social aspects, it is highlighted that the generation of traffic congestion, the increase in the incidence of noise pollution, the occurrence of public health problems and the increase in the risk of traffic accidents are still neglected in the face of economic goals. Organizations [25]. Analyzing this scenario, it is possible to notice that some companies adopt several measures aiming to minimize their environmental impacts resulting from the development of their transport activities, in which the route plan is inserted [23]. Such adjustments are due to current legislation and pressures and customer demands for increasingly sustainable services and products [25].
It is still important to highlight some similar studies that also used multi-criteria analysis methods. The authors of [27] highlight the importance of using multi-criteria methods for quality assurance in decision making and the final decision when selecting viable alternatives in a given context. Further, [28] is another example of a developed study that concluded that decision-making processes increasingly use models based on various methods to ensure the professional analysis and evaluation of the considered alternatives. The authors of [29] used the Neuro-Fuzzy System to support decision making in the selection of construction machines. The authors of [30] analyzed criteria for selecting the position of the air traffic control radar.
Therefore, researchers consider the importance of sustainability in the definition and elaboration of a route plan, in addition to the identification in the literature of the performance objectives and the analysis of the importance of each one by professionals in the logistics area working in Brazil, and also carries out an analysis of the relationship and impact of performance objectives considered the most important by professionals, making a parallel with the sustainability guidelines.
Considering the context presented, a multi-criteria analysis technique was employed, since it is understood that professionals in the area must analyze the objectives that include route plans considering different criteria and perceptions. Therefore, techniques such as Gray Relational Analysis, TOPSIS and Fuzzy TOPSIS are some possible examples of applications to achieve the objectives proposed. TOPSIS was used since it could be used to obtain a consistent ordering considering the amount of the sample obtained with the application of the survey. Details of using TOPSIS are presented in the next section.

This entry is adapted from the peer-reviewed paper 10.3390/logistics6020032

References

  1. Bera, R.K.; Mondal, S.K. Analyzing a Two-Staged Multi-Objective Transportation Problem under Quantity Dependent Credit Period Policy Using q-fuzzy Number; Springer: New Delhi, India, 2020; Volume 6.
  2. Ferreira, J.C.; Steiner, M.T.A.; Junior, O.C. Multi-objective optimization for the green vehicle routing problem: A systematic literature review and future directions. Cogent Eng. 2020, 7, 1807082.
  3. Eglese, R.; Zambirinis, S. Disruption management in vehicle routing and scheduling for road freight transport: A review. Top 2018, 26, 1–17.
  4. Macrina, G.; Pugliese, L.D.; Guerriero, F.; Laporte, G. Drone-aided routing: A literature review. Transp. Res. Part C Emerg. Technol. 2020, 120, 102762.
  5. Brandt, F.; Nickel, S. The air cargo load planning problem—A consolidated problem definition and literature review on related problems. Eur. J. Oper. Res. 2019, 275, 399–410.
  6. Moons, S.; Ramaekers, K.; Caris, A.; Arda, Y. Integrating production scheduling and vehicle routing decisions at the operational decision level: A review and discussion. Comput. Ind. Eng. 2017, 104, 224–245.
  7. Soysal, M.; Çimen, M.; Belbağ, S.; Toğrul, E. A review on sustainable inventory routing. Comput. Ind. Eng. 2019, 132, 395–411.
  8. Thibbotuwawa, A.; Bocewicz, G.; Nielsen, P.; Banaszak, Z. Unmanned Aerial Vehicle Routing Problems: A Literature Review. Appl. Sci. 2020, 10, 4504.
  9. Pratap, S.; Jauhar, S.K.; Paul, S.K.; Zhou, F. Stochastic optimization approach for green routing and planning in perishable food production. J. Clean. Prod. 2022, 333, 130063.
  10. Malladi, K.T.; Sowlati, T. Sustainability aspects in Inventory Routing Problem: A review of new trends in the literature. J. Clean. Prod. 2018, 197, 804–814.
  11. Zheng, J. A Vehicle Routing Problem Model with Multiple Fuzzy Windows Based on Time-Varying Traffic Flow. IEEE Access 2020, 8, 39439–39444.
  12. Gendreau, M.; Laporte, G.; Séguin, R. Stochastic vehicle routing. Eur. J. Oper. Res. 1996, 88, 3–12.
  13. Laporte, G. The traveling salesman problem: An overview of exact and approximate algorithms. Eur. J. Oper. Res. 1992, 59, 231–247.
  14. Shen, Z.J.M.; Feng, B.; Mao, C.; Ran, L. Optimization models for electric vehicle service operations: A literature review. Transp. Res. Part B Methodol. 2019, 128, 462–477.
  15. Khan, R.S. Multi-Objective Vehicle Routing Problem: Case Studies in Retail Distribution Table of Contents. Ph.D. Thesis, University of Manchester, Manchester, UK, 2016.
  16. Karoonsoontawong, A.; Punyim, P.; Nueangnitnaraporn, W.; Ratanavaraha, V. Multi-Trip Time-Dependent Vehicle Routing Problem with Soft Time Windows and Overtime Constraints. Netw. Spat. Econ. 2020, 20, 549–598.
  17. Malladi, K.T.; Sowlati, T. Optimization of operational level transportation planning in forestry: A review. Int. J. For. Eng. 2017, 28, 198–210.
  18. Vega-Mejía, C.A.; Montoya-Torres, J.R.; Islam, S.M.N. Consideration of triple bottom line objectives for sustainability in the optimization of vehicle routing and loading operations: A systematic literature review. Ann. Oper. Res. 2019, 273, 311–375.
  19. Erdelic, T.; Carić, T.; Lalla-Ruiz, E. A Survey on the Electric Vehicle Routing Problem: Variants and Solution Approaches. J. Adv. Transp. 2019, 2019, 5075671.
  20. Afshar-Bakeshloo, M.; Mehrabi, A.; Safari, H.; Maleki, M.; Jolai, F. A green vehicle routing problem with customer satisfaction criteria. J. Ind. Eng. Int. 2016, 12, 529–544.
  21. Kim, D.B.; Shin, S.; Shao, G.; Brodsky, A. A decision-guidance framework for sustainability performance analysis of manufacturing processes. Int. J. Adv. Manuf. Technol. 2015, 78, 1455–1471.
  22. Baykasoğlu, A.; Subulan, K.; Taşan, A.S.; Dudaklı, N. Transportmetrica A: Transport Science A review of fleet planning problems in single and multimodal transportation systems. Transp. A Transp. Sci. 2018, 15, 631–697.
  23. Coeljo, J.R.L.C.; Laporte, G. Roads Based Goods Transportation: A Urvey of Real-World Applications from 2000 to 2015; No. FSA-2015-007; Bibliothèque et Archives Canada: Québec, QC, Canada, 2015; Volume 54, pp. 79–97.
  24. Reyes-Rubiano, L.; Calvet, L.; Juan, A.A.; Faulin, J.; Bové, L. A biased-randomized variable neighborhood search for sustainable multi-depot vehicle routing problems. J. Heuristics 2020, 26, 401–422.
  25. Dündar, H.; Ömürgönülşen, M.; Soysal, M. A review on sustainable urban vehicle routing. J. Clean. Prod. 2021, 285, 125444.
  26. Rout, C.; Paul, A.; Kumar, R.S.; Chakraborty, D.; Goswami, A. Integrated optimization of inventory, replenishment and vehicle routing for a sustainable supply chain under carbon emission regulations. J. Clean. Prod. 2021, 316, 128256.
  27. Zolfani, S.H.; Yazdani, M.; Pamucar, D.; Zarate, P. A vikor and topsis focused reanalysis of the madm methods based on logarithmic normalization. Facta Univ. Ser. Mech. Eng. 2020, 18, 341–355.
  28. Kizielewicz, B.; Więckowski, J.; Shekhovtsov, A.; Wątróbski, J.; Depczyński, R.; Sałabun, W. Study towards the time-based mcda ranking analysis—A supplier selection case study. Facta Univ. Ser. Mech. Eng. 2021, 19, 381–399.
  29. Bozanic, D.; Tešić, D.; Marinković, D.; Milić, A. Modeling of neuro-fuzzy system as a support in decision-making processes. Rep. Mech. Eng. 2021, 2, 222–234.
  30. Petrovic, I.; Kankaras, M. A hybridized it2fs-dematel-ahp-topsis multi-criteria decision making approach: Case study of selection and evaluation of criteria for determination of air traffic control radar position. Decis. Mak. Appl. Manag. Eng. 2020, 3, 146–164.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
This entry is offline, you can click here to edit this entry!
Video Production Service
Feedback