Survey on Thirty Years of Vehicle Routing Problems: Mathematical Models, Solution Methods, and Real-Life Applications

Survey on Thirty Years of Vehicle Routing Problems: Mathematical Models, Solution Methods, and Real-Life Applications

D. G. N. D. Jayarathna

Department of Scientific Computing, Faculty of Computing, University of Sri Jayewardenepura, Sri Lanka.

DOI: https://doi.org/10.51244/IJRSI.2024.1107032

Received: 15 June 2024; Revised: 27 June 2024; Accepted: 01 July 2024; Published: 03 August 2024

ABSTRACT

In recent years, warehouse management concerns have become a major focus in logistics management research, and they have been widely used in studying transportation and logistics distribution networks. The purpose of this work is to undertake a Carrying out a comprehensive analytical literature survey of past twenty years on Vehicle Routing Problem (VRP). VRP is a well-studied combinatorial optimization problem in operations research and computer science. The VRP can be classified as Capacitated Vehicle Routing Problem (CVRP), Vehicle Routing Problem with Time Windows (VRPTW), Vehicle Routing Problem with Multi-Depot (MDVRP), and their variants. Further discussions have taken place in the fields of VRP classification, summarization of common VRP constraints, and the model method created in recent years. Finally, the future model implications of VRP are being investigated, and it is expected that the Intelligent Vehicle Routing Problem and Intelligent Heuristic Algorithm will be major areas of future research.

Key words: Capacitated Vehicle Routing Problem, Exact Methods, Heuristics, Meta–Heuristics, Vehicle Routing Problem, Vehicle Routing Problem with Time Windows, Vehicle Routing Problem with Multi-Depot Optimization.

INTRODUCTION TO VEHICLE ROUTING PROBLEMS

The VRP is used in Logistics and supply chain management in physical delivery of goods and services. The VRP can be simply defined as the problem of designing least cost delivery routes from a depot to a set of geographically separated customers, subject to the side constraints. This is central to distribution management and must be routinely solved by carriers. There are several variants to the VRP and are formulated based on the nature of the goods transporting, the service quality and the characteristics of customers and vehicles.

VRP offers a varied range of heuristics and meta – heuristics approaches, that are introduced in Laporte (2009), Jayarathna et al. (2020) and Cordeau et al. (2005). The VRP is therefore broadly studied due to its wide applicability and its importance in determining economical methods for reducing transportation cost in distribution networks. Consequently, current research concentrates on approximating algorithms that have the ability of finding high quality solutions in a very restricted time frame, in order to be applicable to real world downside situations that are characterized by a large vehicle fleet and affected considerably to logistics and distribution strategies.

The development of several types of VRPs were found beside strategies for deciding the shortest route. (Jayarathna & Jayawardene 2019; Jayarathna et al. 2019a, b; Jayarathna et al. 2020, 2021a, 2021b, 2021c) define VRP as a problem of determining the shortest route from a vehicle that starts from one depot and returns to the depot to meet customer needs; whereas the vehicle has a certain capacity, each vehicle starts from the depot and returns to the depot. Each customer will only visit once. The goal of VRP is to meet the needs of every customer at a low cost. The cost is exactly proportional to the total distance traveled by all vehicles, hence the VRP chooses the shortest route.

Currently, the VRP software package is used by a number of public, commercial, and multinational enterprises across a wide range of industries. Coca-Cola Enterprises and Anheuser-Busch Inbev are the most significant. (Drexel 2012; Ganepola et al., 2018). The VRP literature has been developing steadily at a rate of 6% each year. This feature makes it difficult to keep track of changes in the field and provide a clear description of which variants and solution strategies are relatively novel. The VRP generalizes the well-known Traveling Salesman disadvantage (TSP), but it is far more difficult to overcome in practice. Whereas precise techniques exist that can consistently find TSPs with a wide range of vertices (Applegate et al. 2007). This will not be the case when the VRP’s most effective exact algorithms can only solve instances with about 100 vertices. Because real-world VRP incidents usually exceed this scale and solutions must often be established fast, heuristics are the most widely employed methods. In recent years, numerous sophisticated meta-heuristics algorithms have been developed.

Importantly the subsequent are some of the limitations that has to be met within the VRP.

1. The vehicle route starts from the depot and ends at the depot.
2. Each client should be visited once with one vehicle.
3. Vehicles used are alike and having a certain capacity so that consumer demand. on every route traversed should not exceed the capacity of the vehicle.
4. If the vehicle capacity has reached the limit, then the next client will be. served by the next shift.

Capacitated Vehicle Routing Problem and its Variants

The Capacitated Vehicle Routing Problem (CVRP) is a fundamental limitation in combinatorial improvement, with a number of practical applications in transportation, distribution, and logistics, as well as an extension of VRP. The goal of CVRP is to find a set of minimal total cost routes for a fleet of vehicles with large capacity based at a single depot, to serve a group of clients with the following constraints:

1. each route begins and ends at the depot,
2. each customer is visited exactly once,
3. the total demand of each route does not take over the capacity of the vehicle Laporte (2007).

Currently, numerous CVRP criteria have been established. General surveys can be found in Toth and Vigo (2002) and Laporte (2007). The CVRP falls into the group of NP-hard problems, which can only be exactly solved for smaller sized instances of a problem. As a result, numerous researchers have focused on building heuristic algorithms to solve these challenges (Gendreau & Potvin (2010); Laporte & Ropke (2014).

In some versions of the CVRP one also has to obey a route duration constraint that limits the lengths of the feasible routes. The VRPTW extends the CVRP by associating time windows to the customers. A time window could be defined as an interval during which the customer must be visited. The OVRP is closely related to the CVRP, but contrary to the CVRP a route ends as soon as the last customer has been served as the vehicles do not need to return to the depot. The MDVRP extends the CVRP by allowing multiple depots.

Mathematical Formulation of the CVRP

Let G = (V,H) be a complete directed graph with V = {0,1,2,…,m} as the set of nodes and  H = {(p,q) : p,q ∈ V,p  q} as the set of edges, where node 0 represents the depot for a fleet of vehicles with the same capacity  and remaining m nodes represent geographically spread customers. Each customer p ∈ V − {0} has a certain positive demand d_p ≤  . The non negative travel cost  is associated with each edge (p,q) . The cost matrix is symmetric, i.e.  = c_qp for all p,q ∈ V, p  q and satisfies the triangular inequality, c_pq+c_qr  ≥ c_pr for all p,q,r ∈ V , Toth & Vigo (2002).

Two – Index Vehicle Flow Formulation

In the two index formulation, the binary decision variable is defined as xpq, which takes value 1 if and only if there is a direct route from customer p to q, where p,q are in V. Furthermore, yq is a continuous decision variable that represents the cumulative demand on the route from node q ∈ V to this visit. Given these characteristics and decision variables,

The two-index flow formalization of the CVRP Jayarathna et al. (2021) can be given as:

Constraint (2) ensures that each consumer is visited just once. Constraint (3) ensures that vehicles flow correctly through the edges by requiring that if a vehicle arrives at a node h_0∈ V, it must depart from that node. Constraint (4) limits the maximum number of routes to K_0, or the number of cars. Constraints (5) and (6) combined ensure that the vehicle’s capacity is not exceeded. The objective function, depicted by (1), requires that the overall trip cost of the routes be reduced.

Constraint (5) also prohibits subtours in the solution, such as bike routes that do not pass through the depot. The literature proposes several limits to impose vehicle capacities and/or avoid subtours. Irnich et al. (2014). The benefit of employing constraints (5) and (6) is that the model has a polynomial number of constraints in terms of client count. However, the lower bound supplied by the linear relaxation persists to capacity constraints, which results in improved lower bounds, even when the number of constraints becomes exponential in terms of the number of customers, requiring the usage of a branch-and-cut method; Semet et al. (2014).

Three – Index Vehicle Flow Formulation

The binary decision variable x_{kpq} indicates if the vehicle k, k \in \left\{1,2,3\ldots\ldots..n\right\} tranverses an edge (p,q) in the optimal solution. Janacek et al. (2013) describe the CVRP’s integer linear programming model as:

The objective function (1) lowers the overall transportation cost. The model constraint (2) is the degree constraint, which ensures that each client is visited by only one vehicle. The flow limitations (3) and (4) ensure that each vehicle can only leave the depot once, and that the range of cars arriving at each client and entering the depot is sufficient to accommodate the number of vehicles leaving. The capacity restrictions (5) are expressed, ensuring that the sum of the requests of consumers visited along a route is less than or equal to the capacity of the vehicle executing the service. The sub-tour elimination requirement (6) ensures that the resolution comprises no unconnected cycles from the depot. The remaining necessary constraint (7) specifies the variable definition domains. The number of inequalities in the sub-tour elimination constraints increases exponentially with the number of nodes.

Capacitated Vehicle Routing Problem with Time Windows (CVRPTW)

The Capacitated Vehicle Routing Problem with Time Windows is the CVRP with added time window limitations. The goal of VRPTW is to serve customers within set time frames at the lowest possible cost (in terms of distance traveled), while maintaining the capacity and total tour time limitations for each vehicle. In reality, certain consumers can only be served during a specific time period. We referred to this time period as the time window.

As a result, time window constraints should be considered. Customers in CVRPTW could start receiving service within a certain time frame [Ep, Lp]. If cars arrive at customer p before Ep, they could wait until pi, as there is no additional cost for waiting. If the cars arrive at customer p after Lp, since the client is not present, the vehicle is unable to pick up anything, and hence an additional penalty should be imposed.

Mathematical Formulation of the CVRPTW

The constraints of the Vehicle Routing Problem with Time Windows (VRPTW) are a set of identical cars, a central depot node, a set of customer nodes, and a network that connects the depot and consumers. There are N + 1 customers and K 0 automobiles. The depot node is referred to as customer 0. Each edge in the network architecture represents a link between two nodes while also specifying the direction of movement. Each route starts at the depot. The number of routes in the network is equal to the number of vehicles used. One vehicle is dedicated to one route. Each network edge is assigned a cost (cpq) and a time period (tpq). Each client in a node can only be visited once with a single vehicle. Every vehicle has the same capacity ir, however each consumer has a variable demand mp. ir must be more than or equal to the sum of all demands on the route traveled by the vehicle r, implying that no vehicle may be overloaded. The time window constraint is indicated by a predefined time interval between the earliest and latest arrival times. Vehicles should arrive to customers’ locations on time or earlier. If vehicles come sooner than the specified earliest arrival time, they must wait. In addition, each customer assigns a service time to the route that takes into account the time it takes to load and unload items.  In Solomon’s case, the service time is believed to be unique, independent of the load quantity to be handled. Vehicles are also expected to finish their various routes within the entire route time, as required by the depot’s time frame.

There are three types of key decision variables in VRPTW. Key decision variable x_ijk (i,j ∈{0, 1, 2, ···, n}; k ∈ {1, 2, ···, K}; i ≠ j) is 1 if vehicle k travels from customer i to customer j, and 0 otherwise. The decision variable T_i denotes the time that vehicle arrives at the customer, and w_i denotes the waiting time at node i. The objective is to design a network that satisfies all limitations, while minimizing the total transportation cost. The integral linear programming model of the the VRPTW Jayarathna & Jayawardene (2019) can given by:

Decision Variables

T_i = arrival time at node p

W_i = wait time at node p

X_ijk ∈ {0,1}, 0 if there is no edge from node i to node j, and 1 otherwise,

Parameters

K = total number of vehicles

n = total number of customers

c_ij =cost incurred on edge from node i to j

t_ij = travel time between node i and j

m_i =demand at node i

q_k =capacity of vehicle k

e_i =earliest arrival time at node i

l_i = latest arrival time at node i

f_i = service time at node i

r_k =maximum route time allowed for vehicle k

Subject to:

The aim function minimizes the travel costs of all cars as they complete their journeys. Constraint set [1] ensures that the number of tours is K, with at most K outgoing edges from the depot (i = 0. The constraint set [2] ensures that each vehicle has precisely one outgoing edge from the designated depot. Similarly, the constraint set [3] assures that each vehicle has precisely one edge that enters the node with regard to the depot (i=0). These two constraint sets [2] and [3] work together to ensure that each vehicle completes its journey. The constraint set [4] assures that each node i contributes just one edge to each vehicle. The constraint set [5] ensures that each node j receives just one edge from each vehicle. These two constraints, [4] and [5], ensure that each vehicle only visits each node once. The constraint set [6] requires that each vehicle’s overall demand be less than or equal to its capacity. The constraint set [7] confirms that the total travel cost of each vehicle’s route is less than or equal to the maximum routing time assigned to that vehicle.

The constraint set [8] indicates that each vehicle’s arrival time, waiting time, and service time at the depot must be zero. The constraint set [9] ensures that each vehicle arrives at node j in less than the stipulated time. The constraint set [10] assures that the sum of each vehicle’s arrival and waiting time at each node i is higher than or equal to the initial arrival time at that node and less than or equal to the latest arrival time at that node (i = 1, 2, 3, ···, n). Constraint settings [8, 9], and [10] show the time windows. These formulations fully specify solutions with practicality. A constraint is called hard if it must be satisfied, and soft if it can be violated. The breach of soft constraints is typically penalized and added to the objective function.

Vehicle Routing Problem with Multi-Depot (MDVRP)

The Multi-Depot Vehicle Routing Problem (MDVRP) is a generalized version of the traditional Vehicle Routing Problem (VRP). The goal of this type is to establish routes for vehicles to service all customers at the lowest possible cost, both in terms of number of routes and total distance traveled, while adhering to the vehicles’ capacity and travel time limits. MDVRP is an NP-hard issue that is far more useful than VRP, which determines the routes for various trucks from multiple depots to a set of clients before returning to the same depot. Another goal of the MDVRP is to reduce the overall delivery distance or time spent serving all consumers. The shorter the delivery time, the greater the client happiness. As a result, fewer vehicles can reduce total operating costs, hence the goal may also be to minimize the number of vehicles. MDVRP’s goal, albeit having multiple aims, is to improve delivery efficiency.

The Multi-Depot Vehicle Routing Problem (MDVRP) proposed by Jayarathna et al. (2020) is a generalization of the Single-Depot Vehicle Routing Problem (SDVRP) in which vehicle(s) depart from multiple depots and return to their individual depots of origin at the end of their designated tours. The goal of MDVRP is to keep the aggregate of all tour lengths at a minimum, and existing research addresses this issue with a variety of assumptions and limits.

MDVRP provides suggestions for a number of depots. with the conventional model, each vehicle was tied to the same number of nodes; however, with MDVRP, the same number of vehicles are assigned to each depot. The preceding scenario, i.e. VRP, produced bad outcomes, hence this technique is allowed because it produces better results than VRP. In practically all real VRPs, demands at consumer nodes vary due to a variety of factors, including location and temporal seasonal influences. A network routing architecture created by solving min-max MDVRP yields a series of “daisy-chain network” configurations that reduce the maximum latency between a server and a client.

This can be useful in situations when the client-client connection cost is less than the server-client connection cost. Vehicles should leave the depot and return after serving a significant number of consumers. Every customer has a hazy requirement.  One client is served with only one vehicle by which they have designated. The MDVRP is consisting with creating a set of vehicle routing in such a way that: (1) each route starts and ends in the same depot, (2) each client is visited once by a vehicle, (3) the total demand of each route does not exceed the capacity of vehicle, (4) the total duration of each route (including travel and service times) does not over take a preset limit so that (5) the total routing cost is minimized.

There have been various models developed for the MDVRP (both exact and approximate tecniques). Because of its NP-hard combinatoric character, the models advocated in the liteture rely heavily on heuristics. Baldacci & Mingozzi (2009) devised a strategy for solving the Herogeneous Vehicle Routing Problem (HVRP) that is capable to solve, the MDVRP. This approach is based on the set partitioning formulation, where a procedure can be applied to build routes and three boundary procedures are utilized here to mitigate the number of variables in the formulation. When analysing heuristic algorithms to identify solutions for MDVRP, numerous have been developed, including Jayarathna et al. (2021) and Crevier et al. (2007). As a result, few accurate models for multi-depot situations have been advocated, even though several heuristic approaches exist. Academics have also expressed interest in the combination of these two methodologies. As a result, this paper analyses this potential and provides a hybrid solution for solving the multi-product, multi-depot vehicle routing problem that combines explicit formulation and heuristic procedures.

Mathematical Formulation of the MDVRP

As a result, few accurate models for multi-depot situations have been proposed, although several heuristic approaches exist for the same problem. Academics have also paid attention to the combination of these two strategies. As a result, this paper analyzes this potential and provides a hybrid solution for solving the multi-product, multi-depot vehicle routing problem by combining explicit formulation with heuristic procedures.

The notations used and the mathematical model are as follows:

Sets:  I₀= Set of all depots, J₀ = Set of all Customers, K₀ = Set of all vehicles

Indices: i = depot index, j = customer index, k = route index

Parameters: N = Number of vehicles, C_ij = Distance Between point i and j,

where i, j ∈I₀ ∪J₀

V_i =Maximum throughput at depot i, d_j = Demand of customer j

Q _k = Capacity of vehicle (route) k

Decision Variables

x_ijk =   1, if    i immediately preceeds j on route k

0, otherwise

 z_ij = 1, if customer j is allotted to depoi i

0, otherwise

U_I0k = auxiliary variable for sub-tour elimination constraints in route k

Mathematical Model                

The objective function [1] minimizes the total number of delivery distances for all vehicles in completing their tours, whilst constraint set [2] assures that each client is assigned just one route, and constraint set [3] ensures the vehicle capacity restriction. Similarly, constraint set [4] imposes sub-tour avoidance, and [5] specifies flow conservation. Constraint sets [6] and [7] specify the route to be served and the depot limit, respectively.

[8] Constraints define that a customer can only be assigned to a depot if there is a route from that depot that passes via that customer, and constraints [9] and [10] ensure that the binary criteria on the decision variables are met. Constraint [10] requires that auxiliary variables have positive values. Thus, the MDVRP seeks to minimize overall delivery distance by satisfying the aforementioned requirements

Exact Methods

Exact techniques for solving VRP, notably capacitated VRP (CVRP), include ‘branch-and-bound’, ‘branch-and-cut’, and ‘branch-and-price’ algorithms. Ropke et al. (2007) offers a     branch-and-cut and branch-and-price exact algorithm for CVRP with two-dimensional loading constraints. Jayarathna et al. (2021) presented an exact algorithm for the multiple vehicle     routing issue with time windows (VRPTW). They devised an exact branch-and-price technique to solve the multiple VRPTW. Column generation, also known as Dantzig-Wolfe decomposition, provides a versatile framework capable of accommodating complex constraints and time   dependent costs.

Exact algorithms for solving VRP, notably capacitated VRP (CVRP), include ‘branch-and-bound’, ‘branch-and-cut’, and ‘branch-and-price’. Ropke et al. (2007) offers a branch-and-cut and branch-and-price precise algorithm for the CVRP with two-dimensional loading constraints. Jayarathna et al. (2021) developed an exact algorithm for the multiple vehicle     routing issue with time windows (VRPTW). They devised an exact branch-and-price algorithm to resolve multiple VRPTW. Column generation, also known as Dantzig-Wolfe decomposition, provides a flexible framework for accommodating complex restrictions and time   dependent costs.

Algorithms Based on the Set Partitioning Formulation

Let R₀ denote a set of routes in which r denotes a specific route. Let a_ir be a binary coefficient equal to 1 if and only if vertex i  V \ {0} belongs to route r, let c_r^* be the optimal cost of the route r, and let y_k be a binary variable equal to 1 if and only if route r is used in the optimal solution. The problem is then as given below.

According Laporte (2009), it is impractical for a direct application of this formulation, because of the large number of potential routes encountered in most non trivial instances and of the difficulty of computing the c_r^* coefficients since it requires solving an exponential number of instances of an NP-hard problem.

Alvarenga et al. (2007) propose a two-phase method to the VRPTW that combines genetics and set partitioning. The VRPTW has been defined as a set partitioning problem (SP). Darwin’s idea of natural reproduction, selection, and evolution serves as the foundation for the genetic algorithm. Since then, evolutionary algorithms have gained popularity because they may help find good solutions to complex mathematical problems, such as the VRP and other NP-hard problems, in a reasonable amount of time. The final algorithms comprise the problem reduction and dominance tests. They give computer results for several issues obtained from the literature.

The results of the preceding authors show that the constraints produced from q-routes are superior than those derived from k-DCT, and that VRPs of up to around 25 customers can be solved precisely. Bard et al. (2002) devised a branch-and-cut procedure for the VRPTW. It discusses the topic of determining the minimal number of cars needed to visit a collection of nodes given a time window and capacity limitations. The fleet of cars is uniform and stationed at a shared depot. Every node requires the same type of service. Branch and cut are used to introduce an accurate procedure. Their calculations yield ever-increasing lower constraints on the ideal solution.

This is accomplished by completing a series of relaxed problems that include newly discovered valid inequalities. They use the greedy randomized adaptive search process to find feasible solutions or upper bounds. They also use a wide range of cuts to tighten the linear programming (LP) relaxation of the original mixed-integer program. To determine whether cuts have been violated, a separation problem must be solved.

Heuristic Approaches 

Baker and Sheasby (1999) explain some seed selection strategies. Exact comparisons with other methods are difficult because the experiments’ distance rounding convention is not stated. It is also intriguing from a methodological standpoint because it may benefit from algorithmic advances for the Generalized Assignment Problem (GAP) or the TSP.  Gandreau et al. (2006) proposed neighborhood search algorithms to optimize vehicle planned routes in a situation where new requests for pickup and delivery locations emerge in real time. This is a dynamic vehicle routing issue (DVRP). This framework uses a community structure built on ejection chains to identify novel solutions. The numerical findings show that these approaches are beneficial in a real-time situation. The influence of a master-slave parallelization method with a growing number of processors is also investigated.

Chen et al. (2006) offer a real-time dependent vehicle routing problem using time frames. This problem is represented by a set of mixed integer programming models that account for real-time and time-dependent travel times, as well as real-time demands, in a single framework. Vehicle routes and departure times are used as decision-making factors, with delayed departures permitted at each node. Additionally, heuristics for route construction and improvement are proposed.

Yuichi and Olli (2009) suggested an efficient route minimization strategy for the vehicle routing problem using time windows. They suggested a heuristic based on the discharge pool, powerful insertion, and guided local search algorithms. (Jayarathna & Jayawardene 2019; Jayarathna et al. 2019a, b; Jayarathna et al. 2020, 2021a, 2021b, 2021c) introduced a route construction heuristic with an adaptive parallel scheme is and the results from extensive computational experiments show the proposed parallel route construction heuristic is efficient and effective for route construction, which is particularly useful for generation of the initial solutions for many meta-heuristic approaches with improved solution.  Patrıcia et al. (2009) introduced   heuristics and scatter search methods to tackle real-world heterogeneous fleet vehicle routing problems with time windows and split deliveries. They presented two constructive techniques for generating initial solutions in the Scatter search algorithm.

Meta Heuristics Approaches

Many of the most effective meta-heuristics for large VRPTW instances rely on some type of parallel processing. According to Jayarathna and Jayawardene (2019), local searches (Ganepola et al. (2018), Tangiah et al. (1995)) and other meta heuristics such as tabu search Ganepola et al. (2018) and ant colony system Berger et al. (2003) represent hybridization of a GA with different construction heuristics.

Hoong et al. (2003) tested a form of VRPTW with a limited vehicle fleet, which is a more realistic logistical situation. A limited number of cars is provided (m-VRPTW). A potential solution in this case is either unserved clients or flexible time windows. It provides an analytical upper bound for that formulation and demonstrates that their search strategy was rather near to the upper bound. From the standpoint of stability, this algorithm is more feasible. It also demonstrates that the same approach can be used to achieve reasonable results for the standard VRPTW problem.

Montemanni et al. (2005) presented an ant colony system (ACS) meta heuristic technique for resolving the DVRP. It is built on dividing the working day into various time intervals. A set of static vehicle routing challenges is then constructed. And solved the challenges using the Ant Colony System technique. The features of ACS have also been used to transmit information about good solutions from one time slice to the next. They provide a new public domain benchmark issue and evaluate their proposed methods on those benchmark situations. A computer analysis of a freshly specified set of benchmarks revealed that the proposed solution performed well on both artificial and absolute problems.

Cho and Wang (2005) provide a meta heuristic method to the Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW) that combines Threshold Accepting with modified Nearest Neighbor and Exchange techniques. The VRPBTW acknowledges that trucks depart from the depot, transport products to line haul customers, then pick up goods from back haul customers before returning to the depot. Alba and Dorronsoro (2005) introduced a Cellular Genetic Algorithm (CGA), which is a type of decentralized population-based heuristic used to solve CVRP and improves several of the best current solutions in the literature. The study performs admirably in terms of the quality of the solutions discovered and the quantity of function evaluations.

Jayarathna et al. (2021b) suggested a cooperative parallel meta heuristic for the VRPTW that is based on a solution warehousing method. Distinct search threads were identified: cooperating asynchronously and exchanging information on the best options. The exchanges are carried out using a system known as a solution warehouse, which stores and manages a pool of solutions. Jayarathna et al. (2021c) proposed a two-phase hybrid meta heuristic for the VRPTW. The ultimate goal of VRPTW addressed here is to combine the smallest number of vehicles (primary criterion) with the total journey distance (secondary criterion). The first phase uses a (l;k)-evolution approach to reduce the number of cars, while the second phase employs a tabu search technique to reduce the overall distance.

Zhang and Tang (2009) introduce a novel hybrid ant colony optimization strategy, the SSACO (Scatter search ant colony optimization) algorithm, to address the vehicle routing problem. The fundamental feature of the hybrid algorithm is that it combines the solution creation process of Ant Colony Optimization (ACO) with Scatter Search (SS). In the hybrid algorithm, the ACO algorithm is employed as a heuristic to produce initial solutions, which are then combined to form the reference set. Within the scatter search frame, after applying the two solution combination approach to the reference set, we use the ACO method to produce new solutions by updating the common arc pheromone mechanism.

Furthermore, while implementing the hybrid algorithm, cyclic transfers, a new type of neighbourhood search algorithm, known as neighbourhood search, can be included into the scatter search framework to improve results. Despite the huge size of the cyclic transfer neighbourhood, a forbidden subset is used to minimize computational requirements to manageable levels. David and Braysy (2005) provide a new and successful meta-heuristic approach based on directed evolutional strategies for the VRPTW. The method combines the strengths of guided local search and meta-heuristic evolution strategies in an iterative two-stage procedure. In the first step, guided local search regulates a compound local search, while in the second stage, it regulates the neighbourhood of the growth strategies algorithm. Russell and Chiang (2006) employed a scatter search meta heuristic to solve the VRPTW. The common arc approach and an optimization-based set coverage model are used to connect vehicle routing solutions.  Solution development makes use of a reactive tabu search meta heuristic, a tabu search with an improved recovery feature, and a set covering technique.

Jayarathna et al. (2019) suggested a multi-depot vehicle routing problem with inter-depot routes, which is an extension of the multi-depot vehicle routing problem that allows cars to be replenished at intermediate depots along their routes. It suggested a heuristic methodology based on the adaptive memory principle, a tabu search method for solving subproblems, and integer programming. Abel and Bullinaria (2011) suggested a multi-objective Evolutionary Algorithm (EA) for solving the VRPTW. For multi-objective issues, heuristics often have two objectives: (1) to reduce the distance of the generated solutions, known as the Pareto approximation, from the genuine Pareto front, and (2) to maximize diversity.

Evolutionary Algorithms (EAs) are advancing based on Darwin’s idea of evolution, which states that only the fittest individuals survive and generate offspring to populate the next generation. Aziz (2010) suggested a hybrid ACO algorithm that solves the vehicle routing problem (VRP) using heuristics and an exact approach. The basic VRP provides geographically dispersed consumers with predictable demand from a single depot via a fleet of identically capacitive trucks. The proposed technique is that nodes that are close to each other will probably belong to the same branch of the minimal spanning tree of the problem graph, and hence will probably belong to the same route in VRP. Given a clustering of customer nodes, the resolution is to establish a route through these clusters using ACO and a modified version of the ant’s transition rule. At the end of each repeat, ACO attempts to improve the quality of the solutions by employing a local search method and updating the related weights of graph arcs.

Bin and Zhen (2011) proposed an Improved Ant Colony Optimization (IACO) approach to address the Period Vehicle Routing Problem with Time Windows. In PVRPTW, the planning period is prolonged over multiple days, and each customer must be provided within a specific time frame. A multi-dimensional pheromone matrix is used to collect heuristic data on multiple days. Two cross-over operations are brought up to develop the performance of the algorithm.

Balseiro et al. (2011) proposed an Ant Colony algorithm combined with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows (TDVRPTW). In the TDVRPTW, a fleet must deliver items to a set of customers, the customers’ time window limits must be observed, and the fact that journey time between two sites is determined by the time of departure must be considered.

Hybrid Methods

To solve the VRP, hybrid approaches combine exact, heuristic procedures, and meta-heuristics. Backer and Furnon (1997) presented a hybrid method combining constraint programming and meta-heuristics. The depth-first branch and bind methodology is naturally used in Constraint Programming to solve optimization problems. Although this strategy can provide the best solution for large problems, the time required to locate it will be limited. This study proposes an approach for leveraging constant development techniques within a constraint programming framework and applies it to vehicle routing problems. They introduced the constraint programming model for vehicle routing, followed by an explanation of a systematic integrating constraint programming and iterative improvement methodologies.

The results demonstrated how this method may be considerably accelerated by treating core constraints using rapid local checks, while other more complex constraints are handled using the constraint propagation system. It has combined their iterative improvement technique with a meta-heuristic to prevent the search from becoming locked in local minima. It employs two meta-heuristics: a straightforward Tabu Search method and Guided Local Search. It has undertaken an empirical investigation on benchmark problems, demonstrating the relative merits of these two strategies.

The Importance of Transportation Mathematical Models for Policymakers

From the standpoint of a logistician, securing the continuous flow of product from the producer to the ultimate consumer has become a critical task since transportation is a complicated network that includes a range of modes such as road, rail, air, and pipeline networks. When vehicle routing issues (VRP), which are one of the most common challenges in supply chain management, are effectively addressed, transportation management may be made more sustainable, resulting in a more efficient distribution system. As a result, various mathematical models and algorithms are devised in the quest for solutions to not only cut transportation costs but also to find the lowest cost possible based on the efficient use of the distribution area’s resources. Most businesses seek to keep costs low and earnings high while retaining product quality. By focusing on the flows to minimize the total cost of the network, organizations can avoid congestion in the distribution process while also boosting decision-making power. As previously said, several techniques, such as exact optimization, which applies mathematical models in the search for a solution that ensures the exact solution for small to medium-sized issues, are required. Under various logistical processes, mathematical models are employed to look for actionable solutions to practical problems. When constructing the required mathematical models, several specific facts like as vehicle capacity, delivery times, amount, distance, and so on are taken into account. The mathematical models’ links between the primary parts of the distribution process keep the equilibrium that happens inside the chain’s main channels. Transportation networks are intertwined with telecommunications, electric power generation and distribution networks, supply chains, and other industries.

CONCLUSION

Distribution costs are one of the most important components of logistics costs, and they have a greater impact on an organization’s overall cost structure. One of the most important aspects of optimizing the process is arranging vehicles and routes. As a result, the Vehicle Routing Problem becomes a vital aspect of supply chain management, allowing firms to increase productivity by delivering goods and services to customers efficiently and effectively. The   purpose of this work is to survey the most recent developments in the Vehicle Routing Problem (VRP) and its variants. The literature review was conducted in numerous domains, including exact methods, heuristic approaches, meta-heuristics, and hybrid methods. Furthermore, the contributions made by many researchers to the field were explored in depth.

The paper consists of a discussion of core location theory models and complicated applications in a variety of industries, including distribution planning systems, communications network design, supply chain decisions, and more. While most of the literature has focused on inventory control within the warehouse, taking into account mini-applications of travel plans without an overall plan, young researchers will be encouraged to develop solutions to address the issue of transportation from the warehouse to mini-hubs and from there to retailers.

REFERENCES

1. Alvarenga, G.B., Mateus, G.R., & de Tomi, G., A Genetic and Set Partitioning Two-Phase Approach for the Vehicle Routing Problem with Time Windows. Computers and Operations Research, Vol. 34, No. 6, 2007, pp. 1561-1584. doi: 10.1016/j.cor.2005.07.025
2. Applegate, D. L., Bixby, R. E., Chvatal, V., & Cook, W. J. (2007). The Traveling Salesman Problem. A Computational Study. Princeton University Press, Princeton, NJ.
3. Aziz, E. (2010). An Algorithm for the Vehicle Problem. International Journal of Advanced Robotic Systems, Vol. 7, No.2, pp. 125-132.
4. Azi, N., Gendreau, M., & Potvin, J.Y., An Exact Algorithm for a Vehicle Routing Problem with Time Windows and Multiple Use of Vehicles, European Journal of Operational Research, Vol. 202, No. 3, 2010, pp. 756-763. doi: 10.1016/j.ejor.2009.06.034
5. Baker, B. M., & Sheasby, J. (1999). Extensions to the Generalised Assignment Heuristic for Vehicle Routing. European Jour- nal of Operational Research, Vol. 119, No. 1, pp. 147- 157. doi:10.1016/S0377-2217(98)00348-8
6. Baldacci, R., Christofide, N., & Mingozzi, A. (2008). An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming Ser. A 115, 351-385
7. Baldacci, R., & Mingozzi, A. (2009). A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, 120, 347-380.
8. Bard, F.J, Kontoravdis, G., & Yu, G., A Branch-and-Cut Procedure for the Vehicle Routing Problem with Time Windows, Transportation Science, Vol. 36, No. 2, 2002, pp. 250-269. doi:10.1287/trsc.36.2.250.565
9. Balseiro, S.R., Loiseau, I., & Ramone, J. An Ant Colony Algorithm Hybridized with Insertion Heuristics for the Time
10. Bin, Y.U., & Zhen, Y.Z. An Ant Colony Optimization Model: The Period Vehicle Routing Problem with Time Windows. Transportation Research Part E, Vol. 47, 2011, pp. 166-181. doi: 10.1016/j.tre. 2010.09.010
11. Benoit, C., Cordeau, J. F., & Laporte, G. (2007). The Multi- Depot Vehicle Routing Problem with Inter-Depot Routes,” Euro- pean Journal of Operational Research, Vol. 176, No. 2, pp. 756-773. doi: 10.1016/j.ejor.2005.015
12. Cho, Y.J., & Wang, S.D. A Threshold Accepting Meta- Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows. Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, 2005, pp. 3022-3037. http://www.easts.info/on-line/journal 06.htm
13. Chen, X., Wan, W.S., & Xu, X.H., The Real-Time Time-Dependent Vehicle Routing Problem. Transportation Research Part E: Logistics and Transportation Re- view, Vol. 42, No. 5, 2006, pp. 383-408. doi: 10.1016/j.tre.2005.01.003
14. Crevier, B., Cordeau, J. F. & Laporte, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, 176, 756-773.
15. David, M., & Bräysy, O. (2005). Active Guided Evolution Strategies for Large-Scale Vehicle Routing Problems with Time Windows. Computers & Operations Research, Vol. 32, No. 6, pp. 1593-1614. doi:10.1016/cor.2003.11.017
16. Dependent Vehicle Routing Problem with Time Windows. Computers & Operations Research, Vol. 38, 2011, pp. 954-966. doi: 10.1016/j.cor.2010.10.011
17. De Backer, B., & Furnon, V. (1997). Meta-heuristics in Constraint Programming Experiments with Tabu Search on the Vehicle Routing Problem. Proceedings of the 2nd International Conference on Meta-Heuristics (MIC’97), Sophia Antipolis, France.
18. Drexl, M. (2012). Rich vehicle routing in theory and practice. Logistics Research, 5(1-2), 47–63.
19. Fukasawa, R., & Longo, H. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming 106(3), 497-511.
20. Fukasawa, R., Longo, H., Lysgaard, J., Poggi, M., de Aragão, Reis, M., Uchoa, E., & Werneck, R.F. (2006). Robust branch-and-cut-andprice for the capacitated vehicle routing problem. Programming Ser. A 106 491–511.
21. Gandreau, M., Guertin, F., Potvin, J.Y., & Seguin, R. Nei- ghborhood Search Heuristics for a Dynamic Vehicle Dis- patching Problem with Pick-Ups and Deliveries. Transportation Research Part E: Logistics and Transportation Review, Vol. 14, No. 3, 2006, pp. 157-174.
22. Ganepola, D. D., Jayarathna, N.D., & Madhushani, G. (2018). An intelligent cost optimized central warehouse and redistribution root plan with truck allocation system in Colombo region for Lion Brewery Ceylon PLC. Journal of Sustainable Development of Transport and Logistics, 3(2), 66-73. https://doi.org/10.14254/jsdtl.2018.3-2.4
23. Gendreau, M., Laporte, G., & Potvin, J.Y., Metaheuristics for the VRP, In: P. Toth and D. Vigo, Eds., The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002, pp. 129-154.
24. Gendreau, M., & Potvin, J.Y. (2010). Handbook of Metaheuristics, Second Edition, Springer, New York.
25. Irnich, S., Toth, P., & Vigo, D. (2014). The family of vehicle routing problems. In P. Toth and D. Vigo, editors, Vehicle routing: Problems, methods, and applications, MOS/SIAM Ser Optim, pages 1–33.
26. Jayarathna, D.G.N.D., Lanel, G.H.J., & Juman, Z. (2019). A contemporary recapitulation of major findings on vehicle routing problems: models and methodologies. International Journal of Recent Technology and Engineering (IJRTE), 8(2S4), 581-585. https://doi.org/10.35940/ijrte.B1115.0782S419
27. Jayarathna, N., Lanel, J., Juman, S., & Kankanamge, C.A. (2019). Modelling of an Optimal Outbound Logistics System (A Contemporary Review Study on effects of Vehicle Routing, Facility Location and Locational Routing Problems) International Journal of Humanities and Social Science Invention (IJHSSI), 08(10), 08-30.
28. Jayarathna, N.D., & Jayawardene, C.J. (2019). Application of Clusters in a Transportation Network. Journal of Mathematics and Informatics (JOMI), 17. https://doi.org/10.22457/jmi.130aav17a3
29. Jayarathna, N., Lanel, J., & Juman, Z. A. M. S. (2020). Five years of multi-depot vehicle routing problems. Journal of Sustainable Development of Transport and Logistics, 5(2), 109-123. https://doi.org/10.14254/jsdtl.2020.5-2.10
30. Jayarathna, N., Lanel, J., & Juman, Z. A. M. S. (2021). Survey on ten years of multi-depot vehicle routing problems: mathematical models, solution methods and real-life applications. Sustainable Development Research, 3(1), 36. https://doi.org/10.30560/sdr.v3n1p36
31. Jayarathna, D.G.N.D., Lanel, G.H.J. & Juman, Z.A.M.S. (2021). Modeling a cost benefit transportation model to optimize the redistribution process: Evidence study from Sri Lanka, Journal of Sustainable Development of Transport and Logistics, 6(2), 43-59. https://doi.org/10.14254/jsdtl.2021.6-2.3.
32. Jayarathna, D.G.N.D., Lanel, G.H.J., & Juman, Z.A.M.S. (2021). An intelligent cost-optimized warehouse and redistribution root plan with truck allocation system: Evidence from Sri Lanka. Journal of Business and Social Science Review, 2(10).
33. Jayarathna, D.G.N.D., Lanel, G. H. J. & Juman, Z.A.M.S., 2022. Industrial vehicle routing problem: a case study. Journal of Shipping and Trade, 7(1), pp.1-27.
34. Jayarathna, N. (2024). Optimizing petroleum redistribution in Sri Lanka: A cost-benefit transportation model. Journal of Sustainable Development of Transport and Logistics, 9(1), 121-136. doi:10.14254/jsdtl.2024.9-1.9.
35. Laporte, G., Fifty Years of Vehicle Routing. Transportation Science, Vol. 43, No. 4, 2009, pp. 408-416.
36. Janacek, J., Janosikova, L., & Kohani, M. (2013). Modelovanie a optimalizacia. EDIS vydavatelstvo ZU, in Slovak.
37. Laporte, G. (2007). What you should know about the vehicle routing problem. Naval Research Logistics, 54, pp. 811–819.
38. Laporte, G., Ropke, S., & Vidal, T. (2014). Heuristics for the vehicle routing problem. Vehicle routing: Problems, Methods and Applications, Second Edition. Philadelphia: SIAM, 18–87
39. Maheepala, H. P., Jayawardena, A. A. M., & Jayarathna, D.G.N.D. (2024). Factors influencing customer selection of omni-channel supermarket retailing: An empirical study in Sri Lanka. Journal of Sustainable Development of Transport and Logistics, 9(1), 85-95. doi:10.14254/jsdtl.2024.9-1.7.
40. Montemanni, R., Gambardella, L.M., Rizzoli, A.E., & Donati, A.V., Ant Colony System for a Dynamic Vehicle Routing Problem. Journal of Combinatorial Optimization, Vol. 10, No. 4, 2005, pp. 327-343.  doi:10.1007/s10878-005-4922-6
41. Patrıcia, B., Hugo, T., & Yoshida, Y. (2009). Scatter Search for a Real-Life Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries in Brazil. Euro-pean Journal of Operational Research, Vol. 199, pp. 750-758. doi: 10.1016/j.ejor.2008.08.003
42. Ropke, S., Cordeau, J.F., Iori, M., & Vigo, D., Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem with Two-Dimensional Loading Constraints. Proceedings of ROUTE, Jekyll Island, 13 May 2007.
43. Russell, R.A., & Chiang, W.C., Scatter Search for the Vehicle Routing Problem with Time Windows. European Journal of Operational Research, Vol. 169, No. 2, 2006, pp. 606-622. doi: 10.1016/j.ejor. 2004.08.018
44. Semet, F., Toth, P., & Vigo, D., Classical exact algorithms for the capacitated vehicle routing problem. In P. Toth and D. Vigo, editors, Vehicle Routing: Problems, Methods, and Applications, MOS/SIAM Ser Optim, pages 37–58. 2014.
45. Toth P., & Vigo D., A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls, European Journal of Operational Research 113, (1999), pp. 528-543.
46. Toth, P., & Vigo, D. (2002). Branch-and-bound algorithms for the capacitated VRP. P. Toth, D. Vigo, eds. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia, 29–51
47. Thangiah, S.R., Osman, I.H., & Sun, T., Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problems with Time Windows. Technical Report UKC/OR94/4, Institute of Mathematics and Statistics, University of Kent, Canterbury, 1995.
48. Yuichi, N., & Olli, B., A Powerful Route Minimization Heuristic for the Vehicle Routing Problem with Time Windows, Operations Research Letters, Vol. 37, No. 5, 2009, pp. 333-338. doi: 10.1016/j.orl. 2009.04.006
49. Zhang, X., & Tang, L., A New Hybrid Ant Colony Optimization Algorithm for the Vehicle Routing Problem, Pattern Recognition Letters, Vol. 30, No. 9, 2009, pp. 848- 855.