A Heuristic Algorithm For The Constrained Location – Routing Problem
Abstract
This paper is based on analysis of firm’s logistic system, the firm deals with purchasing of materials (acquisition logistics), controlling work in each production phase (production logistic system), controlling distribution of product to customer (distributive logistics), define the reverse of unusable product (reverse logistics). This will requires logistics network structures applied to guarantee an effective service with minimized costs. For this to be possible transport system performance, location of the distribution centers and issue to do with product distribution are fundamental. The allocation and distribution problem has not been well explored and with “real systems” representation complexity the area remain of extreme interest.
The TSPVRP heuristic approach is employed in this paper as framework to solve and as integrated routing model to solve facility location problem (FTP) and vehicle routing problem (VRP) simultaneously.
Introduction
We analyze a firm’s logistic systems using TSPVRP heuristic approach. This approach aim to solve location routing and scheduling problem, it optimizes the routing phase in a Location-Routing Problem (LRP). Results are compared with those obtainable from other commonly applied procedures.
Transport system performance is an essential part of logistic system, it must guarantee the mobility of products among the various nodes of the system with high efficiency and punctuality, minimizing the transport cost which, in particular cases, can weigh for 50 percent on the overall logistics costs, [1] hence small improvements can lead to huge improvements in absolute terms. Determining where to locate facilities and how to distribute goods to customers is another important decision that arises in design of the logistics systems.
In practice, products are distributed from facilities to customers in two main ways:
• Each vehicle serves only one customer on a straight-and back basis on a given route. This is when a full truckload is requested;
• Multiple-stop routes. This is when each customer requires less than a truckload. Here delivery cost depends on the route of the delivery vehicles. Location and routing decision are interdependent and must be optimized jointly.
Routing and location decisions are important in distribution. [1] The set of routes should minimize the number of vehicle used and the total distance traveled by each vehicle.
Integrated location routing models is an approach applied in solving the facility location problem and also the vehicle routing problem [2] which are basic in our case.
II. LITERATURE REVIEW
In literature there are accurate mathematical models and effective solution methods applied in location, allocation and distribution problems [3, 16], that mainly utilize concept of integrated logistics systems and based on combined location-routing model (LRP) [15, 17]. The location routing problem seeks to minimize total cost by simultaneously selecting set of facilities and constructing a set of delivery routes that satisfy certain constraints. By using this approach, the optimal facility location and the simultaneous construction of the routes leads to a considerable minimization of the overall costs. Logistics also can be thought of as transportation after taking into account all the related activities that are considered in making decisions about moving materials.
A LRP can be assimilated to a vehicle routing problem (VRP) in which the optimal number and location of the facilities are simultaneously determined with the vehicles scheduling and the circuits (route) release so to minimize a particular function (in general, the overall costs) [5]. LRP is an NP-hard since it is constituted by two NP-hard problems and it’s for this reason that simultaneous solution methods for locating and routing are limited to heuristics ([6], [17], [15]).
Solution methodologies utilized in LRP can be classified according to the way they create a relationship between the location and routing problems [19, 23]. Some of these methodologies are;
Sequential methods the location problem is first solved minimizing the distances between facility and consumers (radial distance), then a routing problem is faced.
Clustering solution methods first divide and group the customers, then:
For each cluster a facility is located and a VRP (or TSP) is executed [28];
A travelling salesman problem (TSP) for each cluster is executed and then the facilities are located.
Iterative heuristics breaks down the problem in two sub problems which are solved iteratively.
Hierarchical heuristics consider, instead, the location as the main problem and the routing as a subordinate problem
In the context of LRP, Iterative and hierarchical heuristic are mainly used in solving vehicle routing problems. [13]. Hierarchical network configurations with hub facilities which been proven to be flexible and cost-effective is widely applied in the transportation and telecommunication industries. Hub networks they can reduce total costs by more efficient vehicle infrastructure utilization by better matching capacity to demand.
There are several articles that venture on this field of location and routing problem. Barreto et al [5], used a cluster analysis procedure in LRP heuristic approach. The approach cluster consumer together and allocate them to certain serving facility while applying TSP for each cluster. In [4] is proposed a method for solving the multi-depot location-routing problem (MDLRP). Tuzun and Burke [3] employed the two phase tabu search algorithm in both location and routing phases, where they utilized TS on location variable to solve facility location problem.
There are also other procedures used in LRP which have difference in approach but with the same aim of minimizing the overall cost of LRP while satisfying the demand.
III. PROPOSED APPROACH
The proposed case deals with solving a class of problem that incorporates decision of vehicle routing, facility location, route assignment and tries to minimize the total cost incurred in the logistic system.
A. Problem definition
[2].A set of potential facility and consumers are given. Facilities are allocated to every consumer with demand D>0(where D represent value of demand). The vehicles which are limited in number deliver the consignment to the consumer on a networked route. The cost of facility set-up and cost of distribution per unit have been fixed and there is vehicle and potential center capacity. The objective is to determine facility location and vehicle routes while minimizing overall cost.
The following are constraints condition facing vehicle and distribution centers.
• Each customer’s demand must be satisfied;
• Each customer must be served by a single vehicle [2];
• The overall demand cannot exceed the capacity of vehicle serving that route.
• Each route begins and ends to the same facility [2].
Unlike LRP the vehicle here are not limited to one route.
The process of solving TSP-VRP is affected by constrained location and routing problem (CLRP).
CLRP can be solved by dividing the problem into two phases
Location-allocation (LAP);
Routing (VRP).
In Location phase –allocation problem the solution is a set of selected facilities and a project to allocate the customer to the facilities in computing the distance each customer is directly connected to the nearest facilities l this is achieved through Allocation of customer to nearest facility, Coming up with List of customer distribution and Determining facilities number. The objective of this procedure is to come up with minimum number of facilities that satisfies the total demand and provide configuration of the potential facilities.
VRP phase-output of the LAP is used as input to this phase. The procedure involves two main steps, allocating customer to the facilities according to their cluster and the proximity to facilities centers and s applying TSP in several routes to come up with least cost route, at first with no constraints to vehicle capacity and then with vehicle capacity forming a TSP-VRP.
The optimal solution in the whole problem is comprised of optimal number of routes and with each route [2].having best sequence (in terms of time/costs) of the served demand nodes.
Determining where to locate facilities and how to distribute goods to customers are important decisions that arise in the design of logistics systems. When customers demand less than truckload are interdependent and must be optimized jointly. Location and routing problems (LRPs) seek to minimize total cost by simultaneously selecting a set of facilities and constructing a set of delivery routes that satisfy the specified system constraints. Location and routing problems however, implicitly assume that each vehicle covers exactly one route. This may potentially overestimate the number of vehicles required and the associated distribution cost. Most often, it is possible to serve multiple routes with a single vehicle, in which case the decision of assigning routes to vehicle becomes interdependent with the location and routing decision. In this paper, we consider a class of problems that integrate the decision of facility location, vehicle routing and route assignment and seek to minimize the total cost. We can refer to this problems as location and scheduling problems. The location and scheduling problems generalizes and subsumes several well studied problem classes, such as the multi depot vehicle routing problem (MDVRP), vehicle routing problem (VRP) and the location and routing problems (LRPs). Given a set of candidate facility locations and a set of customer location, the objective of the location and scheduling problems is to select a subset of facilities, construct a set of delivery routes and assign routes to vehicles in such as to minimize total cost subject to satisfaction of the system constraints. Location and scheduling problems can be approached in a way that divide the problem into three phases that is facility location, vehicle routing and vehicle assignment.
Location and routing problems description and formulations
We consider a location and routing problem with capacity constraints on the facilities and on the vehicle, as well as time constraints on the vehicle. In particular, given set of candidates facility locations and a set of customer location, we seek solution in which (i) each customer is visited exactly once, (ii) each route starts and end at the same facility, (iii) the total demand of the customer assigned to a route is at most the vehicle capacity, (iv) the total working time of a vehicle is no more than the time limits, and (v) the total demand of the customer assigned to a facility does not exceed the capacity of the facility. Consider an instance of the location and routing problem in which there is at most one vehicle at each facility, there are no facility fixed cost, and the vehicle time limit is unrestricted.
We come up with a model for the delivery form of the location and the routing problem and make the assumption that there is no service time at the customer. The model nevertheless, can be adapted easily for pickup problems and for nonzero service times. At the heart of the location and routing problems is a network flow structure, deriving from the routing of customer demands, that is constrained through the vehicle and facilities capacities. Hence, we consider both the arc based and the path based formulations for the location and routing problems, as each has been widely applied for related problems. As explained below.
Graph based formulations of location and routing problem
For the related problems of location and routing problem and the vehicle routing problem, the literature contains two main types of graph based model, commodity flow and vehicle flow. In some formulations, integer variables make up the number of times a vehicle traverses a given edge or arc in an underlying graph. In commodity flow simulations, an extra variable representing the number of units of a given good transported along the arc is award. Generally, vehicle flow models comprise an exponential number of subtour elimination constraints, where commodity flow model, with the help of the extra flow variables, use a polynomial number of constraints to eliminate subtours [18]. In the case of location and routing problems and also the case of vehicle routing problem (VRP) two index vehicle flow formulations are favored in solution algorithms based on cut and branch since these formulations include smaller number of variable and their LP relaxations yield better bounds. Nevertheless, it is not possible to formulate the location and scheduling problems using variables with only two indices because of the time constraints for the vehicle. In this context, we require a three index commodity flow model.
To formulate the model, we introduce the following notation. Let I be the set of customers locations and J be the set of candidates facility locations. We define a graph G = (N, A) where N = I U J is a set of nodes and A = (J×I) U (I×I) is the set of arcs. Let H j be the set of vehicles, and let {H j} j ϵ J be a partition of H into homogeneous sets of vehicle assigned to each facility.
Parameters
CjF = daily equivalent fixed cost of opening facility j, Ɐj ϵ j,
C0 = vehicle operating cost per unit travel time,
CV = daily equivalent fixed cost of a vehicle (including the driver cost)
Di = demand of customer i, Ɐi ϵ I,
LjF = capacity of facility j, Ɐj ϵ J,
LV = capacity of a vehicle,
LT = time limit for a vehicle and the driver and
Tij = travel time between locations I and j, Ɐ (I,j) ϵ A.
Decision variables
xikh = 1 if vehicle h travel on arc (i, k), Ɐh ϵ H, (i, k) ϵ A,
0 otherwise
yikh = flow on arc (i, k) carried by vehicle h, Ɐ (i, k) ϵ A, h ϵ H,
tj = 1 if facility j is selected, Ɐj ϵ J,
0 0therwise
vh = 1 if vehicle h is used, Ɐh ϵ H, and
0 otherwise
jϵJCjFtj + CV hϵHvh + C0 hϵh(i, k)ϵATikxikh (1)
hϵHkϵNxikh = 1 Ɐi ϵ I, (2)
kϵNxikh – kϵNxikh = 0 Ɐi ϵ N, hϵ H, (3)
hϵHjkϵNyikh – LjFtj ≤ 0 Ɐj ϵ j, (4)
yikh – LjFtj ≤ 0 Ɐ (i, k) ϵ Ɐ, h ϵ H (5)
kϵIyikh – kϵIyikh + Di k ϵNxikh = 0 Ɐi ϵ I, h ϵ H, (6)
i, kϵ ATik xikh – LT vh ≤ 0 Ɐh ϵ H, (7)
xjkh = 0 Ɐj ϵ j, k ϵ N, h ϵ Ht, t ϵ J {j}, (8)
xikh ϵ {0, 1} Ɐ (I , k) ϵ A, h ϵ H, (9)
yikh ≥ 0 Ɐ (I, k) ϵ A, h ϵ H, (10)
tj ϵ {0, 1} Ɐj ϵ J, and (11)
vh ϵ {0, 1} Ɐh ϵ H (12)
The objective function (1) states that the cost, which includes the fixed cost of the selected facilities, the fixed cost of the vehicle which includes the driver cost, and the operating cost of the vehicle, should be minimized. Constraints (2) specify that exactly one vehicle must travel from customer node I to some other node. Constraints (3) require that a vehicle should enter and leave a node equal number of times. For customer nodes, constraints (2) and (3) ensure that if a vehicle enters a node, it will leave this node and therefore that each customer node is served exactly once. In case of facility nodes, the number of visit by any vehicle may exceed one, since a vehicle can cover several routes. Constraints (4) ensure that the total out bound flows to the customer nodes from each facility do not exceed its capacity. Constraints (5) are vehicle capacity constraints and define the relationship between the binary variable xikh and the flow variable yikh. each constraints ensures that the flow between any pair of nodes cannot exceed the capacity of a vehicle. Constraints (6) require conservation of flow at each customer node; these constraints must be modified for pick up problems. Constraints (5) and constraints (6) together ensure that no route violates the vehicle capacity. The combined sets of constraints (2), (3) and (6) ensure that only valid traveling salesman tour that include a facility are formed. Constraint (7) limits the total time of a vehicle schedule to the time limit. Constraint (8) restricts travel on the arcs originating from a facility to vehicles located to that facility. Constraints (9), (10), (11), and (12) are the integrality and no- negativity requirement on the variable.
In situations when locational problems do not have a routing aspect, the location-routing approach is clearly not an appropriate one. Some researchers may object to location-routing on the basis of a perceived inconsistency.
A distribution system can be designed properly by determining the location of facilities. There are some pother cases where the deliveries made over multiple routes, in these cases, the routing problem and location problems must be considered simultaneously. Determining the locations of facilities within a distribution network can be an important step that impacts not only the profitability of an organization but also its reliability. An assumption made in location modeling is that deliveries are made on out and back routes relating to a single customer. Under this assumption, the cost of delivery does not depend on the other deliveries made. However, in contexts, any deliveries are made along multiple stop routes leading to two or more customers under this the cost of delivery depends on the various customers on the route and the way in which they are visited. Solving both the routing problem and the location problem can lead to accurately capturing the cost of multiple stop routes within a location model.
But normally the location-routing problem
Location and routing problems seeks to economize on the total cost by simultaneously selecting a set theory of candidate facilities and coming up with a set of delivery routes that satisfy the following:
(i) Customer demands are satisfied without exceeding vehicle or facility capacities;
(ii) Each route begins and ends at the same facility.
(iii) The number of vehicles, route lengths, and route durations do not exceed the specified limits; and in order to prevent spoilage that often results to route duration or route length constraints, temperature restrictions need to be there. Also, time-critical delivery problems, such as express package delivery, have time-deadline restrictions that limit the duration or length of routes. Often time-critical delivery problems involve penalties if in case goods fail to reach the destination in time.
Exact methods have been generated for a small number of location and routing problem models. As the algorithm progresses, it realizes, outlines and adds violated constraints and then branches when it identifies no other violated constraints. The authors test the method of solving problem on randomly generated instances as large as eight candidate facilities and twenty customers. To get rid of the potentially exponential number of constraints, the authors develop a constraint-relaxation way of reaching for the solution in which they relax the sub tour elimination, integrality, and chain barring constraints to begin. An assumption made in location modeling is that deliveries are made on out and back routes relating to a single customer [19]. Under this assumption, the cost of delivery does not depend on the other deliveries made. A distribution system can be designed properly by determining the location of facilities. There are some pother cases where the deliveries made over multiple routes, in these cases, the routing problem and location problems must be considered simultaneously. As the algorithm progresses, it realizes, outlines and adds violated constraints and then branches when it identifies no other violated constraints. The authors test the method of solving problem on randomly generated instances as large as eight candidate facilities and twenty customers. It can be realize that the effectiveness of set-partitioning formulations and branch and price algorithms results in the context of developing exact algorithms for location and routing problems. There are two main contributions of this paper. First, it can be seen from the new formulation for the location and routing problems with reduces constraints and identify an alternative set of constraints that can improve the linear programming relaxation bound. Also, we can develop a branch and price algorithm for the location and routing problems with distance constraints. The pricing problem, which into a set of elementary shortest path problems with a single resource constrain can also be solved. We can also show that our algorithm can solve optimally instances with ten candidate or more customers with various distance constraints.
We can solve by following the steps below:
Problem Formulation
Integrality a new set-partitioning based formulation of the LRP with distance constraints can be seen in this section.
The objective of the location routing problem with distance constraints is to come up with a set of locations and construct a set of associated delivery routes in a way that can minimize facility costs plus routing costs. It can be realize that the effectiveness of set-partitioning formulations and branch and price algorithms results in the context of developing exact algorithms for location and routing problems. The set of routes must be that it does not exceed the maximum and each customer receives the visits with no complication. Branch and bound is a standard method or way of solving integer programs in which a series of relaxations of the original problem is solved to obtain an optimal solution. The generalized version of branch and bound in which the LP relaxation at each node of the tree is solved via column generation can be named as branch and price.
Column Generation
It has become a widely used technique for solving large-scale linear programs. Column generation entails is solving a linear program by generating only a subset of the variables while guaranteeing economical coming up of the solution over the entire set of variables. For the location and routing problem-DC model, column generation can be used to solve the LP relaxation [20]. We use the term restricted master problem to refer to a restricted version of the LP relaxation that contains only a subset of the feasible route variables. From LP theory, it can be seen that the reduced cost of every variable in an optimal solution is not minimal. Thus, if the pricing problem identifies feasible route columns with negative minimal cost, we add them to the restricted master problem and optimize. Column-generation is stopped when the pricing problem identifies no columns to add; i.e. every feasible route variable has a nonnegative minimal cost, which implies that the optimal solution to the restricted master problem is optimal for the original linear Programming relaxation.
Branching Rules
A final solution of the Linear Programming relaxation may contain variables with containing fractions. A standard branch and bound procedure can be applied but it does not guarantee optimality due to the column set which does not contain all of the variables. After variables are fixed during the branching process and the Linear Programming is optimized, the dual variables may have new values. Because of this, a column that did not price out favorably at a previous node of the tree may have negative minimized cost. Therefore, additional columns must be generated throughout the tree. In developing a branching technique for a branch and price algorithm, we need to consider the impact of the branching rule on the solution of the pricing problem [21]. For location and routing problem DC, our main aim is to ensure that we can continue to solve the modified pricing problem including the branching decisions as a shortest path problem. We come up different branching rules for the two variable classes. For our branch and price algorithm, we develop specific methods for coming up with an initial solution, solving the pricing problem, generating an upper bound at the root node, and choosing a branching variable. We provide some details of each function in this section
Initial Feasible Solution
To begin the algorithm, we need an initial set of columns that contains feasible solution. One possibility is to construct the set of routes that visit a single customer with a one way trip distance. Nevertheless the disadvantage of this simple approach is that the initial solution may probably be far from the real answer, and, as a result, more repetition of pricing may be required to solve the LP relaxation [22]. To improve the quality of the initial starting solution, constructing a set of feasible routes that involve multiple customers in addition to the singleton routes can assist in solving. We use a nearest insertion heuristic procedure to construct these routes. We start with a route that includes only customer node i =1 and repeatedly add the customer node of minimum insertion distance until the maximum allowable number of customers is reached. Then we repeat the procedure giving each customer node i for i = 2″ ‘ ‘ ‘ “! I! The opportunity to be the “seed” node of the route the routes are stored in order of increasing average cost, defined as the total cost of the route divided by the number of customers served. Finally, we calculate a threshold value and add any column with an average cost less than the threshold to the initial set of columns. Variables are fixed during the branching process and the Linear Programming is optimized, the dual variables may have new values. Because of this, a column that did not price out favorably at a previous node of the tree may have negative minimized cost. In the process of computing, the routes can be constructed up to four customers, and the threshold value computed as the midpoint between the minimum average cost and the maximum average cost of the routes constructed.
Pricing Problem
Keeping in mind that the pricing problem disintegrates into a set of independent pricing problems, one for each facility j, it means that during each pricing repetition, we must solve! J ! Elementary shortest path problems with one resource constraints . During an iteration of the column-generation Method of solving the problem, there may be a facility j for which no negative reduced cost columns are generated. Variable values are not changing much from iteration to iteration then it is likely that no negative reduced cost columns will be generated for facility j in the next iteration. Thus, in hopes of reducing the time spent generating columns; the pricing problem is not solved for facility j in the next iteration. To prove the optimum value, however, the pricing problem for all facilities must be solved during the final iteration.
Primal Feasible Solution
Before beginning the branching portion of the branch and price algorithm, good lower and upper bounds on the optimal integer objective function value must be there. The objective function value of the optimal LP relaxation solution is a valid lower bound. Integrality, we apply a standard branch and bound algorithm to solve the integer program defined over the set of columns generated during the solution of the LP relaxation. Typically, this upper bound is excellent, helping to keep the tree size manageable. To summarize on this, location and routing problems can be applied in contexts in which deliveries are made along many stop routes. A new set-partitioning-based formulation for a class of location and routing problems with distance constraints is represented. The objective function value of the optimal LP relaxation solution is a valid lower bound. Integrality, we apply a standard branch and bound algorithm to solve the integer program defined over the set of columns generated during the solution of the LP relaxation. Also a set of valid inequalities that strengthens the formulation and demonstrated the improvement empirically for a set of small cases are represented. It is also observed that a branch and price algorithm uses an extended label correcting algorithm for the ESPPRC to solve the pricing problem and present the results for the algorithm. Due in part to the strength of the LP relaxation bound, this way of solving problems could solve optimally instances with as many as 100 customer nodes and 10 candidate facilities with various distance constraints. To summarize on this, location and routing problems can be applied in contexts in which deliveries are made along many stop routes [24]. A new set-partitioning-based formulation for a class of location and routing problems with distance constraints is represented. The formulation and algorithm provide a framework for making location decisions that accurately shows the corresponding cost of transport. The structure of the set-partitioning-based formulation is such that additional or different constraints on the vehicle routes can be added easily. The pricing minimal problem for each facility becomes an elementary shortest path problem with two resource constraints that can still be solved by the extended label correcting algorithm
The difficulty of solving instances with additional or different resource constraints depends in part on if, and to what extend is the additional restrictions reduce the solution space and whether the LP relaxation bound remains strong [26]. Future work also will try to come up with adding cutting planes to the branch and price algorithm to allow even larger instances to be solved clearly and properly.
Classification of logical-routing problems
Hierarchical structure. These consist of facilities giving services to a number of customers, who are connected to their depot by means of vehicle tours. No routes connect facilities to each other. Some of these works represent quite complex extensions to the location and routing problem; some others may not even be considered to be part of the location and routing problem.
Type of input data. This may be deterministic or stochastic. There is a larger body of literature on the deterministic case. We note demand as the only stochastic variable.
Planning p
