Nothing Special   »   [go: up one dir, main page]
Next Article in Journal
Improved Bacterial Foraging Optimization Algorithm with Machine Learning-Driven Short-Term Electricity Load Forecasting: A Case Study in Peninsular Malaysia
Previous Article in Journal
Automated Evaluation Method for Risk Behaviors of Quay Crane Operators at Ports Using Virtual Reality
Previous Article in Special Issue
On the Estimation of Logistic Models with Banking Data Using Particle Swarm Optimization
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Algorithms
Volume 17
Issue 11
10.3390/a17110509
algorithms-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Local Search Heuristic for the Two-Echelon Capacitated Vehicle Routing Problem in Educational Decision Support Systems

by
José Pedro Gomes da Cruz
1,*,
Matthias Winkenbach
2 and
Hugo Tsugunobu Yoshida Yoshizaki
1
1
Postgraduate Program in Production Engineering, University of Sao Paulo, Escola Politécnica, Sao Paulo 05508-220, Brazil
2
Center for Transportation & Logistics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
*
Author to whom correspondence should be addressed.
Algorithms 2024, 17(11), 509; https://doi.org/10.3390/a17110509
Submission received: 1 September 2024 / Revised: 30 October 2024 / Accepted: 31 October 2024 / Published: 6 November 2024
(This article belongs to the Special Issue New Insights in Algorithms for Logistics Problems and Management)
Browse Figures
Figure 1
<p>Illustrative example of a route in the 2E-CVRP. Adapted from [<a href="#B12-algorithms-17-00509" class="html-bibr">12</a>].</p> "> Figure 2
<p>Delivery density in the regions evaluated in the case study.</p> ">
Review Reports Versions Notes

Abstract

:
This study focuses on developing a heuristic for Decision Support Systems (DSS) in e-commerce logistics education, specifically addressing the Two-Echelon Capacitated Vehicle Routing Problem (2E-CVRP). The 2E-CVRP involves using Urban Transshipment Points (UTPs) to optimize deliveries. To tackle the complexity of the 2E-CVRP, DSS can employ fast and effective techniques for visual problem-solving. Therefore, the objective of this work is to develop a local search heuristic to solve the 2E-CVRP quickly and efficiently for implementation in DSS. The efficiency of the heuristic is assessed through benchmarks from the literature and applied to real-world problems from a Brazilian e-commerce retailer, contributing to advancements in the 2E-CVRP approach and promoting operational efficiency in e-commerce logistics education. The heuristic yielded promising results, solving problems almost instantly, for instances in the literature on average in 1.06 s, with average gaps of 6.3% in relation to the best-known solutions and, for real problems with hundreds of customers, in 1.4 s, with gaps of 8.3%, demonstrating its effectiveness in achieving the study’s objectives.

1. Introduction

The volume of e-commerce deliveries has witnessed significant growth in recent years, reaching a staggering USD 5.2 trillion in digital platform product sales during 2021. It is projected to surge by 56% in the coming years, reaching approximately USD 8.1 trillion by 2026 [1]. This substantial upswing not only reshapes the dynamics of commerce by shifting the delivery profile from a scenario of few customers with large volumes to many customers demanding small packages, but also poses intricate challenges on logistics, particularly in the efficient delivery of goods, especially within major urban centers, where there is heavy traffic and various limitations that reduce delivery efficiency. This, along with the increase in express orders, deliveries outside regular business hours, and the demand for rapid services underscore the need for an innovative logistics approach [2,3].
A potential solution to these challenges involves the utilization of small Urban Transshipment Points (UTPs) or Urban Distribution Satellites for the two-echelon capacitated vehicles routing problem (2E-CVRP). This strategy is essential for effectively managing the final delivery stage, often referred to as the last mile, and requires swift and strategic responses to optimize routes, reduce costs, and address complex urban variables. The concept of the 2E-CVRP involves dividing the final product delivery process in large urban centers into two levels, utilizing intermediate facilities (satellites) and different types of vehicles in the process [4]. The core concept is to use larger freight vehicles to consolidate large quantities of packages and transport them efficiently from the distribution center to the satellite, which is then responsible for completing the final delivery to customers using smaller urban vehicles, further streamlining the process [5].
Despite its benefits, the 2E-CVRP is an NP-hard problem and presents significant computational complexity, making efficient problem-solving a challenge [6]. This challenge is amplified when it must be implemented in systems that require quick responses, such as interactive Decision Support Systems (DSS), which are very useful for enhancing operations and providing training for logistics professionals and students to sharpen their intuition and improve their critical senses [7]. This is because interactive DSS must offer quick, efficient, and reliable responses [8]. However, achieving this requires the use of rapid and acceptable approximation techniques, with defined limits for compute time and solution quality [9]. For truly interactive decision support, computation times of less than a minute for group settings and less than 30 s for individual user settings are a typical minimum requirement, while real-time response is preferred [10].
Consequently, this study focuses on developing a heuristic designed to address the two-echelon capacitated vehicle routing problem (2E-CVRP). The specific aim is to integrate it into decision support systems for teaching and training logistics professionals in e-commerce and students. The proposed heuristic relies on local search operators, emphasizing the fundamental principles of this approach. Criteria for evaluating the heuristic center on operational efficiency, measured by resolution speed, while maintaining high-quality solutions.
Performance analysis of the heuristic involves benchmarks, including instances recognized in the literature as references. The evaluation extends to the practical application of the heuristic in solving real-world problems, utilizing data from a significant e-commerce retailer in Brazil. Thus, this work not only advances the approach to 2E-CVRP through the development of an effective heuristic, but also contributes to e-commerce logistics education, promoting operational efficiency without compromising solution quality.

2. Literature Review

This section aims to provide a description of the two-echelon capacitated vehicle routing problem (2E-CVRP) and highlight the primary resolution strategies designed for effective convergence to a solution while maintaining favorable values relative to the optimum. The mathematical model defining the problem consists of a directed graph, denoted as G = ( V , A ) , with vertices encompassing the central depot, customers, and satellites. The arcs connect the depot to satellites and satellites to customers, as outlined in the formal description provided in Figure 1 [11].
In this formal representation, products initially located at the central depot are transported by a fleet of homogeneous freight vehicles to the satellites. The satellites, in turn, execute the final delivery of the products to customers with heterogeneous demand, utilizing a fleet of smaller homogeneous vehicles. The vehicles in the first echelon (FE) and second echelon (SE) possess transport capacities denoted as Q 1 and Q 2 , with a specific number of trips, represented as m s , that the set of vehicles at each satellite can undertake. Additionally, within the problem, customers exhibit heterogeneity, each having their individual demand, denoted as d i , which must be entirely serviced by the same vehicle.
Other categories of strategies, discussed below, include local search heuristics, constructive heuristics, and genetic algorithms. However, similarly to exact algorithms, it is noted that many of them tend to take a long time to reach their final results, sometimes extending to hours, making them unfeasible for use in interactive DSS.
For the 2E-CVRP and its variants, the predominantly employed solution strategies revolve around exact branch-and-cut algorithms [12,13] and decomposition methods [14]. These approaches successfully tackle problems involving up to 5 satellites and 50 customers for the first group, and 15 satellites with 300 customers for the second group, with an average computational time of one hour.
The use of Genetic Algorithms (GAs) in the context of 2E-CVRP involves research that models the chromosome in various ways. The main approach is to use chromosomes that represent a complete solution to the problem [15], with each gene representing a route from the first (FE) or second (SE) echelon. Another approach considers a complete solution as an individual composed of several chromosomes [16], where each chromosome symbolizes a route, and its genes correspond to the nodes of the problem. An extra chromosome is introduced to establish connections between the chromosomes of the FE and SE.
In addition, various constructive heuristics are used to build the initial population of a GA [17,18], and the process of selecting individuals for reproduction includes techniques such as Random Selection, Tournaments, Roulette, and Best Fitness.
After selection, the process of exchanging chromosome code is done based on the following operators: the order-based operator [19,20], the route copy operator [15,18], the cycle crossover operator also [19], the Partially Mapped Crossover (PMX) operator [21], and an operator specific to the 2E-CVRP problem developed by Zhou et al. [16]. The authors use a criterion for stopping based on a limit of iterations without improvements.
Many of the heuristics for the 2E-CVRP commonly share the strategy of generating an initial solution with constructive heuristics by dividing the problem into two separate subproblems, one for the SE and one for the FE, and first solving the VRP related to the SE. Furthermore, constructive heuristics are exclusively employed in generating the initial solution, followed by a second improvement phase due to their rapid computational time. Two approaches to the routing problem of the SE are described by Crainic [4]. In the first, customers are assigned to the nearest satellites, solving independent CVRP problems. In the second, a multi-depot CVRP is solved. In both cases, the cumulative demand at the satellites is considered to solve the first echelon as a classical VRP. The results obtained were compared with test instances, achieving gaps from 0 to 7% in relation to the optimum. In turn, Crainic et al. [22] proposes Multi-Start heuristics based on the separation of depot-to-satellite transfer and satellite-to-customer delivery, using clusters and local search to calculate routes.
However, there are other methods that rely on heuristics, such as the nearest neighbor [23], cheapest insertion [24], Clarke and Wright savings heuristic [25], and random insertion [20]. All of them start with an assignment of customers to satellites and then proceed with the routing of the second echelon. The cheapest insertion method stands out, given the customers assigned to a satellite, as it can fit the customers in the best possible position on a route, achieving good results in fractions of a second, even for large problems [24].
After solving the routing problem related to the second level, the calculation of each satellite’s demand is carried out. This is done based on the total demand of the customers who were served by all the SE routes that departed from that specific satellite. Then, the FE routes are constructed. Due to the relatively small number of depots and satellites, many methods use exact approaches to solve the FE routing problem [6,26,27,28]. However, the most common procedure for calculating the FE is that of Breunig [29] which, in situations where satellites have a demand that exceeds the capacity of a single FE vehicle, proposes a preprocessing process. The process involves serving any satellite with demand exceeding the capacity of the FE vehicle through direct round trips from the nearest depot until the remaining demand is less than the capacity of the FE vehicle. After this step, a cheapest insertion heuristic is applied with the aim of constructing FE routes to meet the remaining demand from the satellites. It is important to note that this strategy was developed specifically for this situation to ensure the efficiency of the routing process.
Other approaches include local search heuristics, used to explore the neighborhood of a promising solution. They start from a solution and evaluate neighboring solutions obtained with some perturbation operator, such as relocating a customer to a different position within the route or even to a different route.
The best neighbor solution can be obtained with a first-best solution policy, as in the works of Amarouche et al. [26], which leads to faster convergence to a final solution. However, it can also be guided by better improvement policies, where the entire neighborhood is computed, and the best-performing solution is selected as the next candidate solution, as in the works of Belgin [23] and Liu [24], even though it requires more computational time from the algorithm.
The main operators used to perturb solutions are relocation, exchange, 2-opt, 2-opt*, satellite change, and satellite swap. The relocation and exchange operators are employed to relocate a sequence of m customers within the route, and to exchange the positions of two customers [26], including both individual customers and groups of up to three customers [4,20,30,31].
The 2-opt and 2-opt* operators are intra-route and inter-route operators, respectively, involving two pairs of customers. In the case of 2-opt, it includes the reversal of the service sequence between two respective customers or the substitution of one customer for another between customers of two different routes. As for 2-opt*, these operators are applied only to the routes of the second echelon [27,28,32]. However, they are also applicable to the routes of the first echelon of the problem [24,33]. For example, in the case of 2-opt*, changes in the demand allocated to the satellites occur, requiring adjustments in the first echelon as well.
To avoid changes in demand at the satellites, Hemmelmayr et al. [25] used the strategy of only applying operators to routes of the second echelon that originate from the same satellite, avoiding the need for recalculation of the first echelon. Another strategy is to evaluate only changes between customers limited to the m closest, thus limiting the number of iterations in their heuristics [16,29,34].
The satellite swap and satellite change operators, as defined to assess whether changing the satellite serving a route for another or exchanging the serving satellites of two distinct routes could yield better solutions [23,32,35]. However, it is noticeable that such changes require recalculation of the first echelon, and the methods of constructive heuristics for generating the initial solution of the FE are applied for this purpose.
Other local search procedures applied to the 2E-VRP include the reassignment of customers to their second nearest satellite [22], a Lin–Kernighan local search procedure devised by [18], a split procedure [25], and movements related to delivery options [16].

3. Methodology

This work aims to develop a heuristic capable of finding good solutions for the 2E-CVRP within a computational time of less than thirty seconds. The intention is to integrate this heuristic into decision support systems for teaching and training logistics professionals and students.
The developed heuristic operates in two stages. The first stage involves a constructive heuristic for generating an initial solution. In the second stage, a local search heuristic is applied to the routes of each satellite.

3.1. Constructive Heuristic

The first stage is constructive, where customers are assigned to satellites considering the criterion of the lowest cost in terms of distance and travel time, along with the capacity of the satellites, if applicable. Then, the cheapest insertion method is used to create routes for each satellite, described in Algorithm A1 in Appendix A.1.
The routes for the first echelon are calculated following the procedure by Breunig [34], described in Algorithm A2 in Appendix A.2. In this procedure, after assigning the demands that will be finalized by each satellite, any that have a total demand greater than the capacity of the first-echelon vehicles (FE) will have direct routes with a fully loaded vehicle from the depot to the satellites. For excess demands and customers that must be served directly from the depot, the insertion method is used to finalize the routes.
Algorithm A1 in Appendix A.1 represents this stage. It has the following input parameters: the set of satellites (S), the set of clients (C), the route limit that can originate from satellite s ( m s ), the capacity of the second-echelon vehicles ( Q 2 ), the demand of each client ( d i ), and the costs from origin i to destination j ( C i j ). Here, C i j is the sum of the costs per distance and per travel time on the arc i − j . The outputs are the routes of the second echelon, which travel from the satellites to the clients ( R o u t e s s ), and the total accumulated demand on satellite s ( D e m a n d s ).
Algorithm A2 in Appendix A.2 has the following input parameters: the set of satellites (S), the capacity of the first-echelon vehicles ( Q 1 ), and the total accumulated demand on satellite s ( D e m a n d s ). The outputs are the routes of the first-echelon vehicles, which travel from the depot to the satellites ( R o u t e s c d ).

3.2. Local Search Heuristic

The second stage of the heuristic involves a local search using the 2-opt operator, with a single large route per satellite as input, in the format [ s a t e l l i t e , c u s t o m e r 1 , c u s t o m e r 2 , c u s t o m e r 3 , s a t e l l i t e , c u s t o m e r 4 , c u s t o m e r 5 , s a t e l l i t e , c u s t o m e r 6 , c u s t o m e r 7 , s a t e l l i t e ]. The local search follows a first-improvement policy, meaning that in each iteration, if an improvement is found, the iteration ends, and the next one begins.
Algorithm A3 in Appendix A.3 represents this stage, where the input parameters are: the route of the second echelon of a satellite s, the capacity of the satellite s ( c a p ), the customer demands ( d i ), and the costs of the arcs i − j ( C i j ).

3.3. Performance Evaluation

For the performance evaluation of the heuristic, a numerical experimentation was conducted using a set of 54 instances employed by [6], consisting of 21 to 50 customers and 2 to 4 satellites, alongside the best-known solutions from the literature (BKS) identified by them along with their respective computational execution times. The heuristic’s performance is measured based on the runtime and the percentage gap between the heuristic’s result and the best-known literature solution. Additionally, the heuristic is assessed with a case study involving a major e-commerce retailer in Latin America, which allowed the use of real delivery data, including customer locations in the city of São Paulo, and their package quantity demands. To maintain the company’s anonymity, the distribution center locations were randomly chosen in a region equidistant from the city center, and the satellite locations were selected randomly based on a uniform distribution in the city. The case study evaluation was conducted by comparing the heuristic’s result with the Incumbent of the mathematical model optimization [11], using the Gurobi solver with a time limit of 1 h.
All numerical experiments were conducted in Python v13.11 on a machine with the following hardware specifications: an 11th Gen Intel(R) Core(TM) i7-1165G7 processor @ 2.80 GHz with a clock frequency of 1.69 GHz, 16 GB of RAM, and a 1 TB SSD storage capacity.

4. Numerical Experiments

The numerical experiments presented in this work seek to compare the performance of the proposed heuristic with some of the best solutions from the literature provided by Jie [6]. Table 1 and Table 2 contain the results of the heuristic and total execution time in the ‘Avg.’ and ‘T (seconds)’ columns, respectively, along with the best-known solutions (‘BKS’) from the literature and their execution times. Additionally, the ‘Gap’ column presents the percentage variation between the heuristic solution and the ‘BKS’. Finally, the ‘nS’ and ‘nC’ columns represent the number of satellites and customers, respectively.
The analysis of the results reveals an average gap of 6.3% for the heuristic, with an average resolution time of 1.06 s. This effectiveness is consistent, showing variations in the average gap between sets of instances ranging from 4.3% to 9.5% and in the average time, fluctuating between 0.21 and 3.25 s. Despite some peak values reaching 19.6% with 12.22 s, these results are promising for implementation in the system, as they exhibit runtime close to instantaneous, significantly less than the maximum of 30 s.

5. Case Study

The company studied in this work is a highly relevant e-commerce retailer in the industry, covering the entire Latin American region. The sample used in this study consists of data from one day of deliveries in the city of São Paulo, Brazil. A total of 1.2 thousand shipments delivered throughout the city of São Paulo were analyzed, and specific regions were selected for the evaluation of the heuristic. In the problem, the objective is to minimize travel costs, which include costs per hour of travel and per kilometer traveled.
All distance and time information between points were calculated using the OpenStreetMap API, and data for the vehicles used, which consist of electric bicycles, used as parameters for the model, were estimated based on the work of Gonzalez-Calderon [36], technical specifications from the manufacturers of the vehicles, company data, and the freight table from the TRC Guide [37]. The data include the capacity of the bicycles, which is 15 packages given the delivery profile in the regions, a cost of 0.35 per kilometer (km) traveled, and a cost of 29.25 per working hour, in Brazilian real, to be used in the second echelon. For the first echelon, a truck with a capacity of 450 packages is used, with a cost of BRL 1.89 per kilometer (km) traveled and a cost of BRL 81.69 per working hour.
The evaluated regions were the neighborhoods of Mooca, Pinheiros, República, and Tucuruví, as they are some of the main extremes of the city, with Pinheiros being slightly closer to the distribution center than the others; Tucuruví, with slightly lower demand than normal; República, with one of the highest daily demands; and Mooca, a region with extremely high demand and irregular terrain, with few flat areas. Figure 2 contains images of the four regions, with customers marked with blue drops and satellites in red, green, and brown drops.
The model proposed by Jepsen [11] served as the basis for calculating an optimal solution for the evaluated instances, setting a time limit of 1 h. Additionally, to meet the company’s objective, the objective function of the problem was altered, disregarding inventory maintenance cost parameters and calculating the total cost between arcs i and j. This was given by the sum of the products between the respective travel times and distances with their associated costs.
Table 3 contains the results of the case study. It can be observed that the computational time is very low, close to real-time, and the gaps, with an average of 8.3%, are around the values evaluated with instances from the literature. Thus, there is evidence that the proposed heuristic is effective for use in decision support systems for teaching and training logistics professionals and students, as it is sufficiently fast and produces a gap sufficiently close to the optimum.

6. Conclusions

This study aimed to develop a heuristic for use in decision support systems focused on education and training. The heuristic is focused on solving the two-echelon vehicle routing problem (2E-CVRP), using urban distribution satellites, highlighting them as an efficient alternative to optimize Last Mile efficiency.
A heuristic developed in this work showed promising results in solving the 2E-CVRP, with an average gap of 6.3% and average execution times of 1.06 s in theoretical instances, and an average gap of 8.3% and 1.46 s in real-world problems. These results were obtained through an approach that combines a constructive heuristic, responsible for generating initial solutions, and a local search heuristic focused on improving these solutions with exchange operators. Performance analysis covered numerical experiments with instances from the literature, as well as a case study with real data from an e-commerce retailer in Latin America.
The results indicate that the proposed heuristic is effective for use in decision support systems, providing solutions with gaps close to the optimum in computational times that meet the time constraints required by training and teaching systems (30 s or less). Furthermore, the practical application of the heuristic in a real delivery scenario demonstrated its operational viability and ability to handle the specific demands of the Last Mile.
Although the results are promising, it is important to highlight the identification of opportunities for improvement, especially considering the identification of a gap close to 20% in certain instances. This acknowledgment suggests the ongoing need for optimization and refinement of the heuristic, aiming to achieve even smaller gaps and thereby enhance the quality of the obtained solutions.
In summary, this study contributes not only to the approach of the 2E-CVRP problem, but also provides the algorithmic core of a tool for the training of professionals and students in the e-commerce logistics field. The development of effective heuristics, capable of reconciling computational speed and solution quality, plays a crucial role in adapting logistics operations to the dynamic demands of e-commerce, especially in the challenging context of the Last Mile.

Author Contributions

Writing—review editing, J.P.G.d.C. and M.W.; Resources and Formal analysis, M.W.; Conceptualization and Supervisionm, H.T.Y.Y. All authors have read and agreed to the published version of the manuscript.

Funding

The authors thanks to Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), contract 311232/2022-1 and Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES).

Data Availability Statement

Supplementary data associated with this article can be found, in the online version, at link: http://bit.ly/42n9fyW (accessed on 21 January 2024).

Conflicts of Interest

The authors declare no conflicts of interest.

Abbreviations

The following abbreviations are used in this manuscript:
DSSDecision Support System
2E-CVRPTwo-Echelon Capacitated Vehicle Routing Problem
SESecond, Echelon
FEFirst, Echelon

Appendix A

Appendix A.1

Pseudocode with constructive heuristics.
Algorithm A1: Insertion Constructive Heuristic.
Algorithms 17 00509 i001

Appendix A.2

Pseudocode of Breunig’s procedure.
Algorithm A2: Breunig procedure.
Algorithms 17 00509 i002

Appendix A.3

Pseudocode with Local Search heuristic.
Algorithm A3: 2-opt Local Search.
Algorithms 17 00509 i003

References

  1. Statista. Retail Retail e-Commerce Sales Worldwide from 2014 to 2026. Available online: https://bit.ly/32SAtPQ (accessed on 21 January 2024).
  2. Snoeck, A.; Winkenbach, M. The value of physical distribution flexibility in serving dense and uncertain urban markets. Transp. Res. Part A Policy Pract. 2020, 136, 151–177. [Google Scholar] [CrossRef]
  3. Janjevic, M.; Winkenbach, M.; Merchàn, D. Integrating collection-and-delivery points in the strategic design of urban last-mile e-commerce distribution networks. Transp. Res. Part E Logist. Transp. Rev. 2019, 131, 37–67. [Google Scholar] [CrossRef]
  4. Crainic, T.G.; Mancini, S.; Perboli, G.; Tadei, R. Clustering-Based Heuristics for the Two-Echelon Vehicle Routing Problem; CIRRELT: Montréal, QC, Canada, 2008. [Google Scholar]
  5. Guastaroba, G.; Speranza, M.G.; Vigo, D. Intermediate facilities in freight transportation planning: A survey. Transp. Sci. 2016, 50, 763–789. [Google Scholar] [CrossRef]
  6. Jie, W.; Yang, J.; Zhang, M.; Huang, Y. The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology. Eur. J. Oper. Res. 2019, 272, 879–904. [Google Scholar] [CrossRef]
  7. Perboli, G.; Rosano, M. A decision support system for optimizing the last-mile by mixing traditional and green logistics. In Lecture Notes in Business Information Processing; Springer International Publishing: Cham, Switzerland, 2018; pp. 28–46. [Google Scholar]
  8. Kazak, J. Decision support systems for a sustainable management of the indoor and built environment. Indoor Built Environ. 2018, 27, 1303–1306. [Google Scholar] [CrossRef]
  9. Manis, G.; Bakalis, D.; Sassi, R. A Multithreaded Algorithm for the Computation of Sample Entropy. Algorithms 2023, 16, 299. [Google Scholar] [CrossRef]
  10. Munzner, T. Visualization Analysis and Design; A K Peters/CRC Press: Natick, MA, USA, 2014. [Google Scholar] [CrossRef]
  11. Jepsen, M.; Spoorendonk, S.; Ropke, S. A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem. Transp. Sci. 2013, 47, 23–37. Available online: http://www.jstor.org/stable/23362884 (accessed on 18 October 2023). [CrossRef]
  12. Perboli, G.; Tadei, R.; Masoero, F. Valid Inequalities for the Two-Echelon Capacitated Vehicle Routing Problem; CIRRELT: Montréal, QC, Canada, 2009. [Google Scholar]
  13. Liu, T.; Luo, Z.; Qin, H.; Lim, A. A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints. Eur. J. Oper. Res. 2018, 266, 487–497. [Google Scholar] [CrossRef]
  14. Marques, G.; Sadykov, R.; Deschamps, J.; Dupas, R. An improved branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem. Comput. Oper. Res. 2020, 114, 104833. [Google Scholar] [CrossRef]
  15. Wang, K.; Lan, S.; Zhao, Y. A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service. J. Oper. Res. Soc. 2018, 68, 1409–1421. [Google Scholar] [CrossRef]
  16. Zhou, L.; Baldacci, R.; Vigo, D.; Wang, X. A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution. Eur. J. Oper. Res. 2018, 265, 765–778. [Google Scholar] [CrossRef]
  17. Sahraeian, R.; Esmaeili, M. A multi-objective two-echelon capacitated vehicle routing problem for perishable products. J. Ind. Syst. Eng. 2018, 11, 62–84. [Google Scholar]
  18. Bevilaqua, A.; Bevilaqua, D.; Yamanaka, K. Parallel island based memetic algorithm with lin–kernighan local search for a real-life two-echelon heterogeneous vehicle routing problem based on brazilian wholesale companies. Appl. Soft Comput. 2019, 76, 697–711. [Google Scholar] [CrossRef]
  19. Agárdi, A.; Kovacs, L.; Bányai, T. Two-echelon vehicle routing problem with recharge stations. Transp. Telecommun. J. 2019, 20, 305–317. [Google Scholar] [CrossRef]
  20. He, P.; Li, J. The two-echelon multi-trip vehicle routing problem with dynamic satellites for crop harvesting and transportation. Appl. Soft Comput. 2019, 77, 387–398. [Google Scholar] [CrossRef]
  21. Wang, Y.; Zhang, S.; Assogba, K.; Fan, J.; Xu, M.; Wang, Y. Economic and environmental evaluations in the two-echelon collaborative multiple centers vehicle routing optimization. J. Clean. Prod. 2018, 197, 443–461. [Google Scholar] [CrossRef]
  22. Crainic, T.G.; Gendreau, M.; Gendron, B. Multi-start heuristics for the two-echelon vehicle routing problem. In Evolutionary Computation in Combinatorial Optimization; Springer: Berlin/Heidelberg, Germany, 2011; pp. 179–190. [Google Scholar] [CrossRef]
  23. Belgin, O.; Karaoglan, I.; Altiparmak, F. Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach. Comput. Ind. Eng. 2018, 115, 1–16. [Google Scholar] [CrossRef]
  24. Liu, R.; Tao, Y.; Hu, Q.; Xie, X. Simulation-based optimisation approach for the stochastic two-echelon logistics problem. Int. J. Prod. Res. 2016, 55, 187–201. [Google Scholar] [CrossRef]
  25. Hemmelmayr, V.C.; Cordeau, J.-F.; Crainic, T.G. An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Comput. Oper. Res. 2012, 39, 3215–3228. [Google Scholar] [CrossRef]
  26. Amarouche, Y.; Guibadj, R.N.; Moukrim, A. A neighborhood search and set cover hybrid heuristic for the two-echelon vehicle routing problem. In Proceedings of the 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018), Dagstuhl, Germany, 23–24 August 2018; Borndorfer, R., Storandt, S., Eds.; OpenAccess Series in Informatics (OASIcs, 65). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik: Wadern, Germany, 2018. ISBN 978-3-95977-096-5. Available online: http://drops.dagstuhl.de/opus/volltexte/2018/9716 (accessed on 10 January 2024).
  27. Gu, W.; Archetti, C.; Cattaruzza, D.; Ogier, M.; Semet, F.; Speranza, M.G. A sequential approach for a multi-commodity two-echelon distribution problem. Comput. Ind. Eng. 2022, 163, 107793. [Google Scholar] [CrossRef]
  28. Wang, K.; Shao, Y.; Zhou, W. Matheuristic for a two-echelon capacitated vehicle routing problem with environmental considerations in city logistics service. Transp. Res. Part D Transp. Environ. 2017, 57, 262–276. [Google Scholar] [CrossRef]
  29. Breunig, U.; Schmid, V.; Hartl, R.F.; Vidal, T. A large neighbourhood based heuristic for two-echelon routing problems. Comput. Oper. Res. 2016, 76, 208–225. [Google Scholar] [CrossRef]
  30. Anderluh, A.; Hemmelmayr, V.C.; Nolz, P.C. Synchronizing vans and cargo bikes in a city distribution network. Cent. Eur. J. Oper. Res. 2016, 25, 345–376. [Google Scholar] [CrossRef]
  31. Anderluh, A.; Nolz, P.C.; Hemmelmayr, V.C.; Crainic, T.G. Multi-objective optimization of a two-echelon vehicle routing problem with vehicle synchronization and ‘grey zone’ customers arising in urban logistics. Eur. J. Oper. Res. 2021, 289, 940–958. [Google Scholar] [CrossRef]
  32. Zeng, Z.; Xu, W.; Xu, Z.; Shao, W. A hybrid GRASPVND heuristic for the two-echelon vehicle routing problem arising in city logistics. Math. Probl. Eng. 2014, 2014, 517467. [Google Scholar] [CrossRef]
  33. Enthoven, D.L.J.U.; Jargalsaikhan, B.; Roodbergen, K.J.; Broek, M.; Schrotenboer, A.H. The two-echelon vehicle routing problem with covering options: City logistics with cargo bikes and parcel lockers. Comput. Oper. Res. 2020, 118, 104919. [Google Scholar] [CrossRef]
  34. Breunig, U.; Baldacci, R.; Hartl, R.F.; Vidal, T. The electric two-echelon vehicle routing problem. Comput. Oper. Res. 2019, 103, 198–210. Available online: https://www.sciencedirect.com/science/article/pii/S0305054818302909 (accessed on 20 October 2023). [CrossRef]
  35. Yu, S.; Puchinger, J.; Sun, S. Two-echelon urban deliveries using autonomous vehicles. Transp. Res. Part E Logist. Transp. Rev. 2020, 141, 102018. [Google Scholar] [CrossRef]
  36. Gonzalez-Calderon, C.A.; Posada-Henao, J.J.; Granada-Munoz, C.A.; Moreno-Palacio, D.P.; Arcila-Mena, G. Cargo bicycles as an alternative to make sustainable last-mile deliveries in Medellin, Colombia. Case Stud. Transp. Policy 2022, 10, 1172–1187. [Google Scholar] [CrossRef]
  37. TRC Guide. Freight Tables. Available online: http://www.guiadotrc.com.br/ (accessed on 11 June 2023).
Algorithms 17 00509 g001
Figure 1. Illustrative example of a route in the 2E-CVRP. Adapted from [12].
Figure 1. Illustrative example of a route in the 2E-CVRP. Adapted from [12].
Algorithms 17 00509 g001
Algorithms 17 00509 g002
Figure 2. Delivery density in the regions evaluated in the case study.
Figure 2. Delivery density in the regions evaluated in the case study.
Algorithms 17 00509 g002
Table 1. Results from the first set of instances from the literature.
Table 1. Results from the first set of instances from the literature.
nSnCBKST (s) heur. *T (s)%dev2
Set 2a        
 E-n22-k4-s6-17221417.0727.00 443.160.056.3%
E-n22-k4-s8-14221384.9627.00 392.920.162.1%
E-n22-k4-s9-19221470.6035.00 499.130.096.1%
E-n22-k4-s10-14221371.5025.00 371.500.160.0%
E-n22-k4-s11-12221427.2231.00 446.050.024.4%
E-n22-k4-s12-16221392.7836.00 441.890.3812.5%
E-n33-k4-s1-9232730.1660.00 749.590.132.7%
E-n33-k4-s2-13232714.6360.00 746.520.134.5%
E-n33-k4-s3-17232707.4858.00 831.240.1117.5%
E-n33-k4-s4-5232778.7460.00 828.960.136.4%
E-n33-k4-s7-25232756.8553.00 800.330.395.7%
E-n33-k4-s14-22232779.0560.00 827.040.756.2%
Avg.44.33 0.216%
Set 2b
E-n51-k5-s2-17250597.4960.00 595.080.43−0.4%
E-n51-k5-s4-46250530.7660.00 577.580.518.8%
E-n51-k5-s6-12250554.8160.00 567.681.042.3%
E-n51-k5-s11-19250581.6460.00 610.193.944.9%
E-n51-k5-s27-47250538.2260.00 583.270.438.4%
E-n51-k5-s32-37250552.2860.00 590.800.827.0%
E-n51-k5-s2-4-17-46450530.7660.00 555.1812.224.6%
E-n51-k5-s6-12-32-37450531.9260.00 554.583.534.3%
E-n51-k5-s11-19-27-47450527.6360.00 565.776.307.2%
Avg.60.00 3.255%
Set 2c
E-n51-k5-s11-19250617.4260.00 644.722.414.4%
E-n51-k5-s11-19-27-47450530.7660.00 617.931.2716.4%
E-n51-k5-s2-17250601.3960.00 621.140.423.3%
E-n51-k5-s2-4-17-46450601.3960.00 676.940.1812.6%
E-n51-k5-s27-47250530.7659.00 625.330.4017.8%
E-n51-k5-s32-37250752.5960.00 840.390.1411.7%
E-n51-k5-s4-46250702.3360.00 746.770.106.3%
E-n51-k5-s6-12250567.4260.00 598.830.545.5%
E-n51-k5-s6-12-32-37450567.4260.00 609.007.457.3%
Avg.59.89 1.439%
* heur.: Results of the heuristic.
Table 2. Results from the second set of instances from the literature.
Table 2. Results from the second set of instances from the literature.
nSnCBKST (s) heur. *T (s)%dev2
Set 3a
E-n22-k4-s13-14221526.1543.00 526.150.030.0%
E-n22-k4-s13-16221521.0944.00 561.840.057.8%
E-n22-k4-s13-17221496.3849.00 496.380.020.0%
E-n22-k4-s14-19221498.8043.00 517.800.023.8%
E-n22-k4-s17-19221512.8026.00 524.800.022.3%
E-n22-k4-s19-21221520.4234.00 545.720.014.9%
E-n33-k4-s16-22232672.1758.00 689.830.152.6%
E-n33-k4-s16-24232666.0260.00 747.900.2512.3%
E-n33-k4-s19-26232680.3660.00 689.210.061.3%
E-n33-k4-s22-26232680.3660.00 708.270.164.1%
E-n33-k4-s24-28232670.4360.00 677.690.221.1%
E-n33-k4-s25-28232650.5860.00 722.640.1811.1%
Avg.49.75 0.104%
Set3b
E-n51-k5-s12-18250690.5960.00 694.180.130.5%
E-n51-k5-s12-41250683.0560.00 704.660.243.2%
E-n51-k5-s12-43250710.4160.00 849.890.1219.6%
E-n51-k5-s39-41250728.5460.00 788.260.238.2%
E-n51-k5-s40-41250723.7560.00 730.110.180.9%
E-n51-k5-s40-43250752.1560.00 822.111.419.3%
Avg.60.00 0.387%
Set3c
E-n51-k5-s13-19250560.7360.00 570.120.471.7%
E-n51-k5-s13-42250564.4560.00 618.681.799.6%
E-n51-k5-s13-44250564.4560.00 644.856.5214.2%
E-n51-k5-s40-42250746.3160.00 764.600.242.5%
E-n51-k5-s41-42250771.5660.00 857.370.1711.1%
E-n51-k5-s41-44250802.9160.00 831.810.093.6%
Avg.60.00 1.557%
* heur.: Results of the heuristic.
Table 3. Results from the second set of instances from the literature.
Table 3. Results from the second set of instances from the literature.
nSnCIncumbentBest BoundT (s)heur. *T (s)Gap
Pinheiros185119.13117.693600.32130.720.689.7%
Tucuruvi271213.50211.733600.28239.610.3212.2%
republica3129192.07184.003600.02199.401.623.8%
Mocca2141242.24235.083600.00259.923.217.3%
Avg.1.468.3%
* heur.: Results of the heuristic.
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Share and Cite

MDPI and ACS Style

Cruz, J.P.G.d.; Winkenbach, M.; Yoshizaki, H.T.Y. Local Search Heuristic for the Two-Echelon Capacitated Vehicle Routing Problem in Educational Decision Support Systems. Algorithms 2024, 17, 509. https://doi.org/10.3390/a17110509

AMA Style

Cruz JPGd, Winkenbach M, Yoshizaki HTY. Local Search Heuristic for the Two-Echelon Capacitated Vehicle Routing Problem in Educational Decision Support Systems. Algorithms. 2024; 17(11):509. https://doi.org/10.3390/a17110509

Chicago/Turabian Style

Cruz, José Pedro Gomes da, Matthias Winkenbach, and Hugo Tsugunobu Yoshida Yoshizaki. 2024. "Local Search Heuristic for the Two-Echelon Capacitated Vehicle Routing Problem in Educational Decision Support Systems" Algorithms 17, no. 11: 509. https://doi.org/10.3390/a17110509

APA Style

Cruz, J. P. G. d., Winkenbach, M., & Yoshizaki, H. T. Y. (2024). Local Search Heuristic for the Two-Echelon Capacitated Vehicle Routing Problem in Educational Decision Support Systems. Algorithms, 17(11), 509. https://doi.org/10.3390/a17110509

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop