A Heuristic Algorithm For The Constrained Location – Routing Problem Abstract

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.

1. 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;

1. Sequential methods the location problem is first solved minimizing the distances between facility and consumers (radial distance), then a routing problem is faced.
2. 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.

1. 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.

1. 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

= daily equivalent fixed cost of opening facility j, Ɐj ϵ j,

= vehicle operating cost per unit travel time,

= daily equivalent fixed cost of a vehicle (including the driver cost)

= demand of customer i, Ɐi ϵ I,

= capacity of facility j, Ɐj ϵ J,

= capacity of a vehicle,

= time limit for a vehicle and the driver and

= travel time between locations I and j, Ɐ (I,j) ϵ A.

Decision variables

= 1 if vehicle h travel on arc (i, k), Ɐh ϵ H, (i, k) ϵ A,

0 otherwise

= flow on arc (i, k) carried by vehicle h, Ɐ (i, k) ϵ A, h ϵ H,

= 1 if facility j is selected, Ɐj ϵ J,

0 0therwise

= 1 if vehicle h is used, Ɐh ϵ H, and

0 otherwise

+   +                                                                  (1)

= 1              Ɐi ϵ I,                                                                                                 (2)

–   = 0        Ɐi ϵ N, hϵ H,                                                                              (3)

–   0        Ɐj ϵ j,                                                                                         (4)

–   0                           Ɐ (i, k) ϵ Ɐ, h ϵ H                                                                        (5)

–  +   = 0           Ɐi ϵ I, h ϵ H,                                                       (6)

–   0                                  Ɐh ϵ H,                                                          (7)

= 0     Ɐj ϵ j, k ϵ N, h ϵ , t ϵ J\ {j},                                                                                      (8)

ϵ {0, 1}     Ɐ (I , k) ϵ A, h ϵ H,                                                                                                  (9)

0 Ɐ (I, k) ϵ A, h ϵ H,                                                                                                           (10)

ϵ {0, 1}         Ɐj ϵ J, and                                                                                                           (11)

ϵ {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  and the flow variable   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 pr.............